Page 1 of 1
help creating a simple word scramble program
Posted: Thu Dec 09, 2010 8:26 am
by aaron4osu
I'm new to lisp and am trying to create a simple word scramble program. Eventually it will read in a text file and scramble the words leaving the first and last letter of each word intact.
for the first part I'm trying to create a function that takes a word and only scrambles the middle letters.
Code: Select all
(defun scramble (word)
(if (< (length word) 4) ; word must be 4 letters long in order for this to work
; below is where i need help with rearranging the middle part between first and last letters.
word (append (list (first word) ....need help here.... (last word))
then I need to read in a text file of words that will take each word separated by a space or dash and run the scramble function of them. here is what i have thus far to just read in the file.
Code: Select all
(let ((in (open (stream filename)
(do ((char (read-char stream nil)))
(word nil))
any help would be greatly appreciated
Re: help creating a simple word scramble program
Posted: Thu Dec 09, 2010 9:49 am
by nuntius
For modifying the string, something like this might be good.
Code: Select all
(let ((s (copy-seq "asdf"))) ; make a copy so we don't modify a string literal
(rotatef (char s 1) (char s 2))
s)
If you don't already know about it, also read up on the Fisher–Yates shuffle.
For reading the file, see PCL or the CL Cookbook section on files (links in the FAQ).
Re: help creating a simple word scramble program
Posted: Thu Dec 09, 2010 2:33 pm
by Warren Wilkinson
A few considerations:
- are all words seperated by only 1 space? And if not, must our output match the input?
- Will punctuation be entirely absent? And if not, is it permutated or left as is?
- How scrambled should the words be? Is it okay if our some permutations are more likely?
- Do we allow the 'identity' permutation (i.e. we scramble the word so much it goes back to how it was).
- Should the selected permutation be random, (if it is deterministic, you could write a decoder).
From your initial post I'm thinking that our output must match the input. Punctuation will be there, and should be ignored. And the other three conditions are 'dont care'.
So here is what I think:
- First load the entire file into memory
- Set a HEAD marker at the start of the next word.
- Set an END marker at the next (#\space #\period #\semicolon #\comma #\tab #\newline) after HEAD.
- (incf head), (decf end) [so that we ignore the first and last letters].
- Run a scramble routine which picks 2 numbers at random between HEAD and END, and as long as one of them isn't punctuation, we swap them.
- Repeat
The choice and behavior of the scramble can be whatever you need. Depending on the algorithm you choose, you may have a more or less good cipher, and you may or may not be able to decode.
Re: help creating a simple word scramble program
Posted: Thu Dec 09, 2010 8:27 pm
by nuntius
Oh yeah, for splitting out words, split-sequence or cl-ppcre would be good.
Re: help creating a simple word scramble program
Posted: Fri Dec 10, 2010 6:45 am
by imba
What about this function? (Doesn't preserve first and last letter, though.)
Code: Select all
(defun random-shuffle (lis)
(let ((len (length lis)))
(loop for i from 0 to (1- len)
do (let ((temp (elt Liste i))
(Position (random len)))
(setf (elt lis i) (elt lis Position))
(setf (elt lis Position) temp)))))
Re: help creating a simple word scramble program
Posted: Fri Dec 10, 2010 7:11 am
by aaron4osu
Here is what I have now. It's almost there but still getting errors. any help cleaning it up would be greatly appreciated.
Code: Select all
(defun scramble (word)
(concatenate 'string
(subseq word 0 1)
(coerce (randomize-list (coerce (subseq word
1 (- (length word) 1) ) 'list ) ) 'string )
(subseq word (- (length word) 1) (length word)) ) )
(defun randomize-list (list)
(mapcar #'car
(sort (mapcar (lambda (c)
(cons c (random 1.0)) )
list)
#'> :key #'cdr ) ) )
; Reads a file of text and scrambles the words.
(defun read-and-scramble(filename)
; Read in words
(with-open-file (stream filename)
(do ((char (read-char stream nil) (read-char stream nil))
(word nil)
)
((null char))
(if (alpha-char-p char)
(setq word (append word (list char)))
(progn
(format t "~a" (coerce (scramble word) 'string))
(format t "~a" (coerce (list char) 'string))
(setq word nil)
)))))
Re: help creating a simple word scramble program
Posted: Sun Dec 12, 2010 12:58 pm
by Warren Wilkinson
Are they errors that trigger the debugger, if so what does it say? I think you might have errors in scramble with 1 letter words (it might print the letter twice). Heres my scramble routine.
Code: Select all
(defun scramble (word &aux (end (length word)))
(if (> end 3)
(concatenate 'string
(list (schar word 0))
(randomize-list (coerce (subseq word 1 (1- end)) 'list))
(list(schar word (1- end))))
word))
You're randomize-list method is clever. I wrote one -- now I'm going to compare them for speed (in SBCL).
Code: Select all
(defun randomize-list1 (list)
(mapcar #'car (sort (mapcar (lambda (c) (cons c (random 1.0))) list) #'> :key #'cdr ) ) )
(defun randomize-list2 (a)
(let ((a (copy-list a))
(b nil)
(n (length a)))
(loop repeat n
for place = (random (length a))
for item = (elt a place)
do (push item b)
do (setf a (delete item a :start place :count 1)))
b))
(defvar *test-input* (loop for i from 0 to 1024 collecting i))
(time
(dotimes (i 100)
(randomize-list1 *test-input*)))
;; 0.181 seconds
(time
(dotimes (i 100)
(randomize-list2 *test-input*)))
;; 0.668 seconds
Looks like yours is considerably faster, neat.
Re: help creating a simple word scramble program
Posted: Sun Dec 12, 2010 10:35 pm
by Vivitron
Interesting; that is a neat randomize-list. You can write one that performs Warren's benchmark significantly faster by coercing a copy of the list to a vector and shuffling that, but it's significantly slower on word length lists.
aaron wrote:Here is what I have now. It's almost there but still getting errors. any help cleaning it up would be greatly appreciated.
Scramble doesn't work right when you pass it short words. You can start scramble with an if statement that returns the word as a string if it's length is under 4.
Re: help creating a simple word scramble program
Posted: Mon Dec 13, 2010 5:06 am
by gugamilare
Warren Wilkinson wrote:You're randomize-list method is clever. I wrote one -- now I'm going to compare them for speed (in SBCL).
Code: Select all
(defun randomize-list1 (list)
(mapcar #'car (sort (mapcar (lambda (c) (cons c (random 1.0))) list) #'> :key #'cdr ) ) )
(defun randomize-list2 (a)
(let ((a (copy-list a))
(b nil)
(n (length a)))
(loop repeat n
for place = (random (length a))
for item = (elt a place)
do (push item b)
do (setf a (delete item a :start place :count 1)))
b))
(defvar *test-input* (loop for i from 0 to 1024 collecting i))
(time
(dotimes (i 100)
(randomize-list1 *test-input*)))
;; 0.181 seconds
(time
(dotimes (i 100)
(randomize-list2 *test-input*)))
;; 0.668 seconds
Looks like yours is considerably faster, neat.
I don't know if you noted, but randomize-list1 is O(n log(n)) (and yes, that is the complexity for sorting lists in SBCL) and randomize-list2 is O(n^2).