Last night, I happened to land on Paul Bissex’s Letâ€™s play a game: BASIC vs. Ruby vs. Python vs. PHP. Obviously this competition has degenerated into a brawl involving a great variety of programming languages including Rebol, Haskell and JavaScript, for example. I decided to set myself a little challenge: come up with a LISP competitor (at the same time, I’ll prove to Jer that I’m not afraid of a pair of parenthesis or two). I quote Paul for the rules of the game:

The game of REVERSE requires you to arrange a list of numbers in numerical order from left to right. To move, you tell the computer how many numbers (counting from the left) to reverse. For example, if the current list is 2 3 4 5 1 6 7 8 9 and you reverse 4, the result will be 5 4 3 2 1 6 7 8 9. Now if you reverse 5, you win.

I came up with two versions. But first, let me introduce two self-explanatory utility functions used in both versions:

(defun shuffle-list (l)
(loop for i below (length l) do
(rotatef
(elt l i)
(elt l (random (length l)))))
l)
(defun prompt (l)
(format t "~{~a~^, ~}~%How many to swap? " l)
(read))

Here is the non-recursive version:

(defun playgame (n)
(let ((goal (loop for i from 1 to n collect i)))
(do ((count 0 (1+ count))
(state (shuffle-list (copy-list goal))
(let ((howmany (prompt state)))
(append
(reverse (subseq state 0 howmany))
(subseq state howmany)))))
((equal state goal)
(format t "Done! that took ~d steps.~%"
count)))))

and the recursive version:

(defun play (state step)
(if (equal state (sort (copy-list state) #'<))
step
(let ((howmany (prompt state)))
(play (append
(reverse (subseq state 0 howmany))
(subseq state howmany))
(+ step 1)))))
(defun playgame2 (n)
(format t \"Done! That took ~d steps.~%\"
(play (shuffle-list
(loop for i from 1 to n collect i)) 0)))

Can you improve on this? Do not hesitate to comment!

### Like this:

Like Loading...

*Related*

This entry was posted on Tuesday, February 21st, 2006 at 17:38 and is filed under challenge, Lisp, Programming Language.

Wednesday, February 22nd, 2006 at 1:50

[…] « Little LISP challenge […]

Friday, February 24th, 2006 at 22:01

I went and wrote a Scheme version (link added to the original post). I tried not to look at yours until I was finished. I like the recursive version of the “play” loop.

Saturday, February 25th, 2006 at 9:41

Paul, I just had a look at your Scheme implementation. It’s confusingly close to the LISP one. The relationship between these two languages is more than obvious.

Regarding the recursive LISP version, it is more “Old School” than the

`do`

loop one. It’s my favourite too.Saturday, July 15th, 2006 at 13:40

Here’s the version I came up with:

(loop for flipcount = 0 then (read)

for numbers = (sort (loop for i from 1 upto 9 collect i)

(lambda (a b) (zerop (random 2))))

then (nconc (reverse (subseq numbers 0 flipcount))

(subseq numbers flipcount))

as steps from 0

until (apply #'< numbers) do

(format t “~{~a~^ ~}~%Reverse how many? ” numbers)

(force-output)

finally (format t “~{~a~^ ~}~%Done! That took you ~a steps.~%” numbers steps))

Saturday, July 15th, 2006 at 21:25

Very elegant, I like the “sort by random”.