Playing with the REPL
In my previous write-up I claimed that with a set of moves an end position could be reached from any start position. In fact, any position can be reached from any other position. How can I be so sure?
This time I'm not going to write a program. Well, in a sense I do, but I'm just going to type in expressions at the lisp REPL, and see where I end up. This time I'm not really bothered by effiency or elegance of the code, I'm more concerned about giving a feel for this kind of back-of-the-envelope coding you can do withing the REPL. You will also see that I kind of repeat the same code again and again with small modifications until I get it right. Because of this I feel it's important to use lisp with good history editing functions or a interface like the excellent slime mode for emacs.
And BTW: From the history numbers, you can tell that I actually messed around a lot more than what I'm showing you. This is normal and not an indication of my cluelessness level. I think.
With that out of the way, let's get started. First, let's recreate the apply-move function, this time we want to combine any kind of moves, not just the predefined moves in the *moves* list:
FLIPPER 50 > (defun xor (a b)
(loop for ap in a
for bp in b
collect (mod (+ ap bp) 2)))
XOR
FLIPPER 51 > (xor '(1 0 1) '(1 1 0))
(0 1 1)
FLIPPER 52 > (xor '(1 0 1) '(0 1 1))
(1 1 0)
If you played around with the game, you already knew this, but if you look at what we just did you can see that by applying a move on the result of a move, we get back to the starting position. What this means for us, is that we can replace a move in our list with the result of applying another move on it and we will still be able to generate the same results.
Let's look at our moves again (and add a move identifier to each move):
FLIPPER 55 > (defparameter *c-moves* (loop for m in *moves*
for i upfrom 1
collect (cons m (list i))))
*C-MOVES*
FLIPPER 56 > (format t "~{~a~%~}" *c-moves*)
((1 1 0 1 1 0 0 0 0) 1)
((1 1 1 0 0 0 0 0 0) 2)
((0 1 1 0 1 1 0 0 0) 3)
((1 0 0 1 0 0 1 0 0) 4)
((1 0 1 0 1 0 1 0 1) 5)
((0 0 1 0 0 1 0 0 1) 6)
((0 0 0 1 1 0 1 1 0) 7)
((0 0 0 0 0 0 1 1 1) 8)
((0 0 0 0 1 1 0 1 1) 9)
NIL
Not quite what I had in mind, we want the move identifier to be a list so we can push other identifiers onto it when we combine moves.
FLIPPER 57 > (defparameter *c-moves* (loop for m in *moves*
for i upfrom 1
collect (list m (list i))))
*C-MOVES*
FLIPPER 58 > (format t "~{~a~%~}" *c-moves*)
((1 1 0 1 1 0 0 0 0) (1))
((1 1 1 0 0 0 0 0 0) (2))
((0 1 1 0 1 1 0 0 0) (3))
((1 0 0 1 0 0 1 0 0) (4))
((1 0 1 0 1 0 1 0 1) (5))
((0 0 1 0 0 1 0 0 1) (6))
((0 0 0 1 1 0 1 1 0) (7))
((0 0 0 0 0 0 1 1 1) (8))
((0 0 0 0 1 1 0 1 1) (9))
NIL
Better. But our xor function won't work with "moves" from this list, we need to add code to handle the move identifiers. We will append the identifiers to keep track of which moves are combined to generate the new move.
FLIPPER 59 > (defun my-xor (a b)
(list (xor (first a) (first b))
(append (second a) (second b))))
MY-XOR
FLIPPER 60 > (my-xor (first *c-moves*) (second *c-moves*))
((0 0 1 1 1 0 0 0 0) (1 2))
Now, lets see if we can find a move with a specific "bit" set. (It's not really a bit but an integer, but that's what I'll call it.) Let's try to find the first move with the last bit set. (Should be move 5 by looking at the table above.)
We'll use the find-if function, find-if requires two arguments, a test function and a list. The test function should accept one argument and return true or false. We want to test if the nth element of the first list of is equal to 1 and will use a lambda function for this. The whole thing looks like this if we look for the 8th bit set:
FLIPPER 61 > (find-if #'(lambda (x) (= 1 (nth 8 (first x))))
*c-moves*)
((1 0 1 0 1 0 1 0 1) (5))
Ok, we're almost set, now we'll go through the list of moves, first looking for a move with the first bit set, we will xor this move with all other moves with the first bit set. Then we'll do the same for the second bit, and so on. First, let's try it out by just testing for the first bit and print it out:
FLIPPER 81 > (let* ((bar (find-if #'(lambda (x) (= 1 (nth 0 (first x)))) *c-moves*))
(gaz (remove bar *c-moves*)))
(format t "~{~a~%~}"
(loop for move in gaz
collect (if (= 0 (nth 0 (first move)))
move
(my-xor bar move)))))
((0 0 1 1 1 0 0 0 0) (1 2))
((0 1 1 0 1 1 0 0 0) (3))
((0 1 0 0 1 0 1 0 0) (1 4))
((0 1 1 1 0 0 1 0 1) (1 5))
((0 0 1 0 0 1 0 0 1) (6))
((0 0 0 1 1 0 1 1 0) (7))
((0 0 0 0 0 0 1 1 1) (8))
((0 0 0 0 1 1 0 1 1) (9))
NIL
That almost worked, we forgot to put the first element back on. Let's add it back in and at the same time wrap the whole thing in a loop that goes through the index for the "bits". We also have to make some changes inside the let* to update the bit index and the list of moves (foo). Finally we'll print the result.
FLIPPER 88 > (loop with foo = (copy-list *c-moves*)
for i from 0 to 8
do (let* ((bar (find-if #'(lambda (x) (= 1 (nth i (first x)))) foo))
(gaz (remove bar foo)))
(setf foo
(cons bar
(loop for move in gaz
collect (if (= 0 (nth i (first move)))
move
(my-xor bar move))))))
finally (format t "~{~a~%~}" foo))
((0 0 0 0 0 0 0 0 1) (1 2 1 2 1 1 4 1 2 1 2 1 2 1 1 5))
((1 0 1 1 0 0 0 1 0) (1 2 1 2 1 1 4 1 2 7))
((1 0 0 1 0 0 1 0 0) (1 2 1 2 1 1 4))
((1 0 1 1 0 1 0 0 0) (1 2 1 2 1 3))
((0 0 1 1 1 0 0 0 0) (1 2))
((1 1 1 0 0 0 0 0 0) (1 2 1))
((1 0 0 1 0 0 0 0 0) (1 2 1 2 1 1 4 1 2 1 2 1 2 1 1 5 1 2 1 2 1 3 1 2 1 2 6))
((0 0 1 0 0 0 0 0 0) (1 2 1 2 1 1 4 1 2 1 2 1 2 1 1 5 1 2 1 2 1 1 4 1 2 7 1 2 1 2 1 1 4 8))
((0 0 1 1 0 0 0 0 0) (1 2 1 2 1 1 4 1 2 1 2 1 2 1 1 5 1 2 1 2 1 1 4 1 2 7 1 2 1 2 1 3 1 2 9))
NIL
Huh? That doesn't look very nice at all. Let's try to print out the array for each loop and see what is going on.
FLIPPER 89 > (loop with foo = (copy-list *c-moves*)
for i from 0 to 8
do (let* ((bar (find-if #'(lambda (x) (= 1 (nth i (first x)))) foo))
(gaz (remove bar foo)))
(setf foo
(cons bar
(loop for move in gaz
collect (if (= 0 (nth i (first move)))
move
(my-xor bar move)))))
(format t "~{~a~%~}~%" foo)))
((1 1 0 1 1 0 0 0 0) (1))
((0 0 1 1 1 0 0 0 0) (1 2))
((0 1 1 0 1 1 0 0 0) (3))
((0 1 0 0 1 0 1 0 0) (1 4))
((0 1 1 1 0 0 1 0 1) (1 5))
((0 0 1 0 0 1 0 0 1) (6))
((0 0 0 1 1 0 1 1 0) (7))
((0 0 0 0 0 0 1 1 1) (8))
((0 0 0 0 1 1 0 1 1) (9))
((1 1 0 1 1 0 0 0 0) (1))
((0 0 1 1 1 0 0 0 0) (1 2))
((1 0 1 1 0 1 0 0 0) (1 3))
((1 0 0 1 0 0 1 0 0) (1 1 4))
((1 0 1 0 1 0 1 0 1) (1 1 5))
((0 0 1 0 0 1 0 0 1) (6))
((0 0 0 1 1 0 1 1 0) (7))
((0 0 0 0 0 0 1 1 1) (8))
((0 0 0 0 1 1 0 1 1) (9))
[rest of output snipped.]
Duh, since the first move has the second bit as well as the first bit set, it's chosen for the second round in the loop as well as the first, and from then on everything is a mess. We want to choose new moves a much as possible. Since find-if search from the front, we can do that by putting "bar" at the end of the list after applying the xor instead of the other way around.
We can't just reorder the bar and the loop in the cons call since that will break up "bar" the same way it broke the move identifier the first time we tried to create the *c-moves* parameter. Read up on conses and proper lists to figure out why.
FLIPPER 94 > (loop with foo = (copy-list *c-moves*)
for i from 0 to 8
do (let* ((bar (find-if #'(lambda (x) (= 1 (nth i (first x)))) foo))
(gaz (remove bar foo)))
(setf foo
(append (loop for move in gaz
collect (if (= 0 (nth i (first move)))
move
(my-xor bar move)))
(list bar)))
(format t "~{~a~%~}~%" foo))
)
((0 0 1 1 1 0 0 0 0) (1 2))
((0 1 1 0 1 1 0 0 0) (3))
((0 1 0 0 1 0 1 0 0) (1 4))
((0 1 1 1 0 0 1 0 1) (1 5))
((0 0 1 0 0 1 0 0 1) (6))
((0 0 0 1 1 0 1 1 0) (7))
((0 0 0 0 0 0 1 1 1) (8))
((0 0 0 0 1 1 0 1 1) (9))
((1 1 0 1 1 0 0 0 0) (1))
((0 0 1 1 1 0 0 0 0) (1 2))
((0 0 1 0 0 1 1 0 0) (3 1 4))
((0 0 0 1 1 1 1 0 1) (3 1 5))
((0 0 1 0 0 1 0 0 1) (6))
((0 0 0 1 1 0 1 1 0) (7))
((0 0 0 0 0 0 1 1 1) (8))
((0 0 0 0 1 1 0 1 1) (9))
((1 0 1 1 0 1 0 0 0) (3 1))
((0 1 1 0 1 1 0 0 0) (3))
[more output snipped]
((1 0 0 0 0 0 0 0 0) (1 2 3 1 4 3 1 5 1 2 3 1 4 1 2 6 8 9 1 2 3 1))
((0 1 0 0 0 0 0 0 0) (1 2 3 1 4 1 2 6 1 2 3 1 4 7 9 1 2 3 1 4 1 2 3))
((0 0 1 0 0 0 0 0 0) (1 2 3 1 4 3 1 5 1 2 3 1 4 1 2 6 8 1 2 3 1 4 1 2 6 1 2 3 1 4 7 1 2 3 1 4 1 2))
((0 0 0 1 0 0 0 0 0) (1 2 3 1 4 1 2 6 8 1 2 3 1 4 1 2 6 9 1 2 3 1 4))
((0 0 0 0 1 0 0 0 0) (1 2 3 1 4 3 1 5 1 2 3 1 4 7 9))
((0 0 0 0 0 1 0 0 0) (1 2 3 1 4 1 2 6 8 1 2 3 1 4 7))
((0 0 0 0 0 0 1 0 0) (1 2 3 1 4 3 1 5 1 2 3 1 4 1 2 6))
((0 0 0 0 0 0 0 1 0) (1 2 3 1 4 1 2 6 8))
((0 0 0 0 0 0 0 0 1) (1 2 3 1 4 3 1 5))
NIL
That's more like it! So to toggle the bottom right square, we just need to do the moves "1 2 3 1 4 3 1 5"? But the 3's and two of the 1'a cancel each other out so this is more complex than it needs to. As a final fix we can modify my-xor so that instead of appending the move identifiers, we collect the identifiers that are unique to each of the moves we combine. The function we want to use for this is set-exclusive-or:
FLIPPER 97 > (set-exclusive-or (list 1 2 3) (list 2 3 4))
(4 1)
FLIPPER 98 > (defun my-xor (a b)
(list (xor (first a) (first b))
(set-exclusive-or (second a) (second b))))
MY-XOR
FLIPPER 103 > (loop with foo = (copy-list *c-moves*)
for i from 0 to 8
do (let* ((bar (find-if #'(lambda (x) (= 1 (nth i (first x)))) foo))
(gaz (remove bar foo)))
(setf foo
(append (loop for move in gaz
collect (if (= 0 (nth i (first move)))
move
(my-xor bar move)))
(list bar)))
(format t "~{~a~%~}~%" foo)))
((0 0 1 1 1 0 0 0 0) (2 1))
((0 1 1 0 1 1 0 0 0) (3))
((0 1 0 0 1 0 1 0 0) (4 1))
((0 1 1 1 0 0 1 0 1) (5 1))
((0 0 1 0 0 1 0 0 1) (6))
((0 0 0 1 1 0 1 1 0) (7))
((0 0 0 0 0 0 1 1 1) (8))
((0 0 0 0 1 1 0 1 1) (9))
((1 1 0 1 1 0 0 0 0) (1))
((0 0 1 1 1 0 0 0 0) (2 1))
((0 0 1 0 0 1 1 0 0) (1 4 3))
((0 0 0 1 1 1 1 0 1) (1 5 3))
((0 0 1 0 0 1 0 0 1) (6))
((0 0 0 1 1 0 1 1 0) (7))
((0 0 0 0 0 0 1 1 1) (8))
((0 0 0 0 1 1 0 1 1) (9))
((1 0 1 1 0 1 0 0 0) (1 3))
((0 1 1 0 1 1 0 0 0) (3))
[snippety]
((1 0 0 0 0 0 0 0 0) (8 6 9 5))
((0 1 0 0 0 0 0 0 0) (7 2 9 4 6))
((0 0 1 0 0 0 0 0 0) (8 7 4 5))
((0 0 0 1 0 0 0 0 0) (2 9 4 3 8))
((0 0 0 0 1 0 0 0 0) (7 3 9 1 5))
((0 0 0 0 0 1 0 0 0) (2 7 1 6 8))
((0 0 0 0 0 0 1 0 0) (3 6 2 5))
((0 0 0 0 0 0 0 1 0) (8 3 4 6 1))
((0 0 0 0 0 0 0 0 1) (5 1 2 4))
NIL
Ok, we're done. We now know which moves we need to do to turn a single square on or off. So we can now just toggle the ones we want. Let's just test it by toggling the top left corner (moves 8 6 9 5):
FLIPPER 105 > (play-tty) 0 0 1 0 0 1 1 0 0 8 0 0 1 0 0 1 0 1 1 6 0 0 0 0 0 0 0 1 0 9 0 0 0 0 1 1 0 0 1 5 1 0 1 0 0 1 1 0 0Excellent.
If you want to experiment further, you can try to combine what we now know and make a function that takes a starting position and returns which moves a player needs to do to solve a puzzle. Good luck!
1 comment:
To create this article, 36 people, some nameless, worked to edit and improve it over time. Roulette can get very addicting; setting guidelines for your self might keep you from going overboard. It may be placed on the top of any "avenue" on the desk map. You can make a Triple by inserting a chip throughout the 카지노 사이트 grid line with the three numbers you wish to guess on.
Post a Comment