Little LISP challenge

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!

About these ads