rot13 in pure newlisp no regex(p)

[newdep]

Here we go...





;;

;; usage: (rot13 string )

;; pure newlisp no regex relations, not the quickest implant btw!

;;

;; (rot13 "hottentottententententoonstellingstafellaken")

;;



(define (rot13 txt)

(for (y 0 (- (length txt) 1)) ( set-nth y txt (slurp (nth y txt)))) txt)



(define (slurp x)  

(if  

  (or (and (>= (char x)(char "a")) (<= (char x)(char "m")))

      (and (>= (char x)(char "A")) (<= (char x)(char "M"))))

      (char (+ (char x) 13))



  (or (and (>= (char x)(char "n")) (<= (char x)(char "z")))

      (and (>= (char x)(char "N")) (<= (char x)(char "Z"))))

      (char (- (char x) 13))    

      x))

[pjot]

Mine is longer..... but more userfriendly....



#!/usr/bin/newlisp

;;

;; ROT13 converter

;;

;;-------------------------------------------------



;; Setup ROT13 conversion strings

(set 'ROT13FROM "NOPQRSTUVWXYZABCDEFGHIJKLMnopqrstuvwxyzabcdefghijklm")

(set 'ROT13GOTO "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz")



;; Get input from user

(print "Enter a string to convert: ")

(set 'dat (read-line))



;; Initialize result variable to string

(set 'enc "")



;; Mainloop

(while (> (length dat) 0) (begin

   (if (!= (find (nth 0 dat) ROT13FROM) nil)

      (set 'enc(append enc(nth (find (nth 0 dat) ROT13FROM) ROT13GOTO)))

      (set 'enc(append enc(nth 0 dat))))

   (set 'dat (rest dat))))



;; Print result

(println enc)



;; Exit newLISP

(exit)

[newdep]

Mmm which one is more lisp ? :-)

heheh i think neighter ;-)

[pjot]

Yours is more ingenious I think.... I prefer the lazy way... ;-)

[newdep]

Its still too big and slow.....

[nigelbrown]

Here is a string to string function rot13 that explodes a string, maps a conversion fn over it and joins it up again. I've not timed it but I hope that using an array for the conversion maintains speed. It's based on pjot's conversion string idea.

code:



;; Setup ROT13 conversion strings

(setq ROT13FROM "NOPQRSTUVWXYZABCDEFGHIJKLMnopqrstuvwxyzabcdefghijklm")

(setq ROT13GOTO "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz")



;; create a mapping array int->int modified to give rot13

(setq rotarray  (array 256 (sequence 0 255)))

(map (fn (x y) (nth-set x rotarray y)) (map char (explode ROT13FROM)) (map char (explode ROT13GOTO)))



(define (rot13 s) (join (map (fn (x) (char (nth (char x) rotarray))) (explode s))))



test:



newLISP v7.5.2 Copyright (c) 2004 Lutz Mueller. All rights reserved.



> (rot13 "The butler did it!")

"Gur ohgyre qvq vg!"

> (rot13 (rot13 "The butler did it!"))

"The butler did it!"

>

[nigelbrown]

Less transparent than using the strings as above is 'hard coding' the array:



(setq rotarray (array 256 (apply append (map sequence '(0 78 65 91 110 97 123) '(64 90 77 96 122 109 255)))))

(define (rot13 s) (join (map (fn (x) (char (nth (char x) rotarray))) (explode s))))





Alternatively, to keep everything in one place if you don't mind the overhead of regenerating the array each rot13 call:



(define (rot13 s , rotarray) (begin

   (setq rotarray (array 256 (apply append (map sequence '(0 78 65 91 110 97 123) '(64 90 77 96 122 109 255)))))

   (join (map (fn (x) (char (nth (char x) rotarray))) (explode s)))))





using the (map sequence construct is just more compact than listing the conversion array in toto:



(define (rot13 s , rotarray) (begin

   (setq rotarray (array 256 '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 78 79 80 81

 82 83 84 85 86 87 88 89 90 65 66 67 68 69 70 71 72 73 74 75 76 77

 91 92 93 94 95 96 110 111 112 113 114 115 116 117 118 119 120 121

 122 97 98 99 100 101 102 103 104 105 106 107 108 109 123 124 125

 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157

 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173

 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189

 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205

 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221

 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237

 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253

 254 255)))

   (join (map (fn (x) (char (nth (char x) rotarray))) (explode s)))))

[nigelbrown]

Timings are interesting

Although the array approach is about twice as fast as the slurp approach

viz

slurp based:

> (time (dotimes (x 100000)  (rot13 "hottentottententententoonstellingstafellaken")))

35693



array based:

> (time (dotimes (x 100000)  (rot13 "hottentottententententoonstellingstafellaken")))

15493



converting rotarray to a list only slows rot13 down a little (20% longer) compared to an array:

> (setq rotarray (array-list rotarray))

...

> (list? rotarray)

true

> (array? rotarray)

nil

> (time (dotimes (x 100000)  (rot13 "hottentottententententoonstellingstafellaken")))

18557

>

and applies for longer strings much the same

>(silent (setq s (read-file "newlisp_manual.html")))

> (length s)

412339

>  (time (dotimes (x 10) (rot13 s)))

24717

> (setq rotarray (array-list rotarray))

...

> (time (dotimes (x 10) (rot13 s)))

29904

>



I realise this is just using (nth to retrieve from an array and not looking at the advantage of array access for setting values.

[newdep]

Hello Nigelbrown,



Thanks for the alternative ways (nice exmaples)

I was already checking if my rot13 can be speeded-up.



And i think the big delay in the (CHAR) convertion,

using << or >> bit-shifting will make it more quicker,

but still a little cryptic.



ill report back...



Norman...

[pjot]

Hi nigelbrown!



Well, you have beaten me with your smart algorithm... indeed it is faster and smaller, pretty cool! Thanx!!



Peter.

[newdep]

Actualy this character mapping amazes me on the speed, its damm fast..

Well for the rot13 i removed some overlay on char and the result below is

on my system 18600 using the timer 10000 from nigel..



Currious how quick the the version below is for you nigel??





(define (rot13 txt )

 (for ( y 0 (- (length txt) 1))

 (set-nth y txt  (char(slurp (char (nth y txt))))))

 txt)



(define (slurp x)

(if  

(or (and (>= x   97)(<= x 109)) (and (>= x  65)(<= x  77))) (+ x 13)  

(or (and (>= x 110)(<= x 122)) (and (>= x  78)(<= x  90))) (- x 13) x))



Norman.

[nigelbrown]

Hi Norman,

Timing for your latest version is:

newLISP v7.5.6 Copyright (c) 2004 Lutz Mueller. All rights reserved.



> rot13

(lambda (txt)

 (for (y 0 (- (length txt) 1))

  (set-nth y txt (char (slurp (char (nth y txt)))))) txt)

> slurp

(lambda (x)

 (if (or (and (>= x 97) (<= x 109)) (and (>= x 65) (<= x 77)))

  (+ x 13)

  (or (and (>= x 110) (<= x 122)) (and (>= x 78) (<= x 90)))

  (- x 13) x))

> (time (dotimes (x 100000) (rot13 "hottentottententententoonstellingstafellaken")))

26692

... load other version

> rot13

(lambda (s) (join (map (lambda (x) (char (nth (char x) rotarray)))

   (explode s))))

> (time (dotimes (x 100000) (rot13 "hottentottententententoonstellingstafellaken")))

15385

>



This is on a IBM T23 (~730MHz, 512MB) laptop running WinXP-Pro



Nigel

[nigelbrown]

As another look I took out the nth array access so it doesn't change anything just does a (char (char x)) and it shows the array access is only about 10% of the processing time.

The test was:

> (define (charonly s) (join (map (lambda (x) (char (char x)))(explode s))))

(lambda (s) (join (map (lambda (x) (char (char x))) (explode s))))

> (time (dotimes (x 100000) (charonly "hottentottententententoonstellingstafellaken")))

13695

>

vs the working version:



> rot13

(lambda (s) (join (map (lambda (x) (char (nth (char x) rotarray)))

   (explode s))))

> (time (dotimes (x 100000) (rot13 "hottentottententententoonstellingstafellaken")))

15385

[nigelbrown]

More interesting timings



I also tried a more iterative approach :

(define (rot13nth s) (dotimes (i (length s)) (nth-set i s (char (nth (char (nth i s)) rotarray)))))

rather than the lispy'er explode-map-join but it is marginally slower

if the string is short:

> (time (dotimes (x 100000) (rot13nth "hottentottententententoonstellingstafellaken")))

16605

>

vs

> rot13

(lambda (s) (join (map (lambda (x) (char (nth (char x) rotarray)))

   (explode s))))

> (time (dotimes (x 100000) (rot13 "hottentottententententoonstellingstafellaken")))

15385



However, if the string is long the rot13nth function goes very! slow

It takes 25 times !!!! longer for a 75k text viz:



> (silent (setq s (read-file "newlisp-tk.html")))

> (length s)

75323

> (time (rot13 s))

542

> (time (rot13nth s))

13593

>



From this one could, perhaps, conclude that to do things in lisp in a lispy way scales better than iterative accessing.

[nigelbrown]

My iterative version forgot to return the modified string s, it should be:



(define (rot13nth s) (begin (dotimes (i (length s)) (nth-set i s (char (nth (char (nth i s)) rotarray)))) s))



but this shouldn't significantly affect timings.