Solving ToaZZle with CPS

ToaZZle is a game akin to peg solitaire. This blog post talks about how to solve it by using Hy and Stilpo.

A word of warning, while solving a game with help of a computer can be interesting endeavour, it might spoil the game for you. Keep this in mind while working with such programs.

——

The idea with ToaZZle is to remove frogs one by one by jumping over them with other frog and leaving the red one as the last frog on the board.

Like always with CPS, we need four common things: how to represent current situation, what are operations available for the any given state, how do we recognize that solution has been found and how to tell that two states are identical.

My initial reaction was that I needed two distinct entities: the board and the frogs on the board. There would be a pointer from lilypad to frog currently on it and likewise from frog to a lilypad that it was currently sitting on. Each frog would have a colour stored in it, which would make it easy to check that the red one didn’t accidentally got eaten. While the solution worked, I figured out (after implementing it) that I don’t really need to track identity of the frogs. It’s enough that I know if a lilypad has a green or the red frog (or no frog at all). Turns out, I can just store that information as simple string attribute on a lilypad: “green”, “red” or None.

But I needed to track identity of lilypads. Otherwise it would be hard to tell on which lilypads frogs start and to where they should be jumping at. Thus, I ended up with following function for lilypad creation:

(defn create-lilypad [id]
  "create new lilypad"
  {:id id
   :frog None
   :connections []})

Because lilypads are connected to each others (how else could frogs jump from one to other?), I was thinking of simply listing lilypad’s neighbours in connections attribute. This doesn’t work though, as frogs need to jump over another frog on a lilypad and land on another lilypad behind it. So connections are represented as tuples of lilypads. First element is destination lilypad and second one is the lilypad that the frog jumps over (I’m wondering though, if I should have chosen different order). Building a board can then be done with following functions:

(defn connect-lilypads [origin connections]
  "connect lilypad to its neighbours"
  (for [connection connections]
    (.append (:connections origin) connection)
    (.append (:connections (first connection)) (, origin (second connection)))))

(defn create-board []
  "create board for puzzle number 13"
  (let [lilypads (dict-comp id (create-lilypad id) [id lilypad-ids])]
    (defn connect [origin-id &rest connection-pairs]
      "helper to connect pad to neighbours"
      (connect-lilypads (get lilypads origin-id)
                        (list (map (fn [x] (, (get lilypads (first x))
                                              (get lilypads (second x))))
                                   connection-pairs))))
    (connect "A1" (, "A2" "B1") (, "A3" "B2") (, "A5" "C1"))
    (connect "A2" (, "A4" "B3") (, "A5" "D2"))
    (connect "A3" (, "A4" "B4") (, "A5" "D1"))
    (connect "A4" (, "A5" "C2"))
    (connect "B1" (, "B2" "C1") (, "B3" "D2") (, "B4" "A5"))
    (connect "B2" (, "B3" "A5") (, "B4" "D1"))
    (connect "B3" (, "B4" "C2"))
    (connect "C1" (, "C2" "A5"))
    (connect "D1" (, "D2" "A5"))

    lilypads))

Now our state is a dictionary with lilypads as values and their ids as keys. And each lilypad has information of how it’s connected to other lilypads and if there are any frogs sitting on it.

Our goal is to remove all green frogs and leave only the red one sitting. This is expressed with function:

(defn goal? [state]
  "have we reached the end?"
  (not (list (filter (fn [lilypad]
                       (= (:frog lilypad) "green"))
                     (.values state)))))

Astute reader spots that I’m not actually checking if there’s a red frog left. I’m doing it this way in order to save some time and keep code simpler. I just have to make sure that red frog never gets eaten accidentally and we’re good to go.

Finding out possible frog moves is done in two steps (I have found this method works generally quite well). First step is to define what moving a frog from a lilypad to another actually means and second is to use this new function to each and every valid move.

When a frog jumps from a starting lilypad (source), using a connection several things have to happen:

  • remove frog from source lilypad
  • remove frog from the lilypad in between
  • place frog on destination lilypad (make sure frog is correct colour)

We also need a description of what is going on. This is just a string telling which frog jumped where and is used to report solution at the end:

(defn move-frog 
  (let [start-lilypad-id (:id source)
        destination-lilypad-id (:id (first connection))
        in-between-lilypad-id (:id (second connection))
        frog (:frog source)]
    {:action (fn [state]
               (let [new-state (deepcopy state)
                     start-lilypad (get new-state start-lilypad-id)
                     in-between-lilypad (get new-state in-between-lilypad-id)
                     destination-lilypad (get new-state destination-lilypad-id)]
                 (assoc in-between-lilypad :frog None)
                 (assoc start-lilypad :frog None)
                 (assoc destination-lilypad :frog frog)

                 new-state))
     :desc (.format "{} {} -> {}"
                    frog
                    start-lilypad-id
                    destination-lilypad-id)}))

After defining move-frog finding out all possible moves is matter of looping through all connections on all lilypads and seeing if there are frog with neighbouring frog and an empty space behind it (and make sure that red one never gets eaten). We’ll start with making a list of moves from a single lilypad:

(defn frog-moves [lilypad]
  "get valid moves for a frog on a given lilypad"
  (if (:frog lilypad)
    (let [connections (:connections lilypad)
          valid-connections (filter (fn [pair]
                                      (and (is (:frog (first pair)) None)
                                           (is-not (:frog (second pair)) None)
                                           (not (= "red"
                                                   (:frog (second pair))))))
                                    connections)
          moves (list (map (fn [connection]
                             (move-frog lilypad connection))
                           valid-connections))]
      moves)
    []))

If there are no frog on a lilypad, result will be an empty list. Otherwise we’ll check if there’s correct configuration of frogs available on any connection and create moves.

Final step is to pull all this together in operators function that will generate list of all valid moves for given configuration of lilypads and frogs:

(defn operators [state]
  "all valid operators and their descriptions for given state"
  (list (->> (.values state)
             (map frog-moves)
             (filter (fn [moves]
                       (> (len moves) 0)))
             (.from-iterable chain))))

Final piece to solution is identifying identical states. This is done by looping through all lilypads and checking that the frog status is identical (red, green or None). By using combination of all and map, we stop checking as soon as difference is found.

(defn identical? [state1 state2]
  "are two given states identical?"
  (let [lilypad-pairs (zip (.values state1)
                           (.values state2))]
    (all (map (fn [pair]
                (= (:frog (first pair))
                   (:frog (second pair))))
              lilypad-pairs))))

Last step is to assemble solver:

(setv solver (depth-first-solver :is-goal goal?
                                 :operators operators
                                 :is-identical identical?))

In all tests depth first solver outperformed breadth first one (no real surprise here though). In case of 6 frogs for example, the solution is always 5 moves. Breadth first solver will enumerate all possible combinations with 4 moves before starting with 5 moves. By the time it has gotten that far, depth first solver has already found a solution.

Solving this problem shows quite nicely (I think) that the representation one picks for the problem space matters. When I did away with individual frogs and just recorded colour of frog on a lilypad, code was cut down 20% (and simplified too).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s