Little LISP challenge

Tuesday, February 21st, 2006

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
	 (elt l i)
	 (elt l (random (length l)))))

(defun prompt (l)
  (format t "~{~a~^, ~}~%How many to swap? " l)

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)))
		   (reverse (subseq state 0 howmany))
		   (subseq state howmany)))))
	((equal state goal)
	 (format t "Done! that took ~d steps.~%"

and the recursive version:

(defun play (state step)
  (if (equal state (sort (copy-list state) #'<))
      (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!


5 Responses to “Little LISP challenge”

  1. Paul Says:

    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.

  2. ozone Says:

    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.

  3. Daniel Says:

    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)
    finally (format t “~{~a~^ ~}~%Done! That took you ~a steps.~%” numbers steps))

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

Comments are closed.

%d bloggers like this: