help creating a simple word scramble program

Discussion of Common Lisp
Post Reply
aaron4osu
Posts: 2
Joined: Thu Dec 09, 2010 8:04 am

help creating a simple word scramble program

Post by aaron4osu » Thu Dec 09, 2010 8:26 am

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

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: help creating a simple word scramble program

Post by nuntius » Thu Dec 09, 2010 9:49 am

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).

Warren Wilkinson
Posts: 117
Joined: Tue Aug 10, 2010 11:24 pm
Location: Calgary, Alberta
Contact:

Re: help creating a simple word scramble program

Post by Warren Wilkinson » Thu Dec 09, 2010 2:33 pm

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.
Need an online wiki database? My Lisp startup http://www.formlis.com combines a wiki with forms and reports.

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: help creating a simple word scramble program

Post by nuntius » Thu Dec 09, 2010 8:27 pm

Oh yeah, for splitting out words, split-sequence or cl-ppcre would be good.

imba
Posts: 35
Joined: Sun Nov 21, 2010 2:13 pm

Re: help creating a simple word scramble program

Post by imba » Fri Dec 10, 2010 6:45 am

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)))))

aaron4osu
Posts: 2
Joined: Thu Dec 09, 2010 8:04 am

Re: help creating a simple word scramble program

Post by aaron4osu » Fri Dec 10, 2010 7:11 am

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)
			)))))

Warren Wilkinson
Posts: 117
Joined: Tue Aug 10, 2010 11:24 pm
Location: Calgary, Alberta
Contact:

Re: help creating a simple word scramble program

Post by Warren Wilkinson » Sun Dec 12, 2010 12:58 pm

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.
Need an online wiki database? My Lisp startup http://www.formlis.com combines a wiki with forms and reports.

Vivitron
Posts: 4
Joined: Mon Nov 22, 2010 2:05 pm

Re: help creating a simple word scramble program

Post by Vivitron » Sun Dec 12, 2010 10:35 pm

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.

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: help creating a simple word scramble program

Post by gugamilare » Mon Dec 13, 2010 5:06 am

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).

Post Reply