Maze display app for Always Turn Left

Last time, I presented a solution for Always Turn Left, a Google Code Jam problem. Given that their large dataset was quite big (up to 10k moves), I thought: “It would be interesting to see what mazes those moves produce”. So I set to write (in Clojure, of course) a maze-display app (using Seesaw, of course). Here’s what came out of that.

(ns com.icyrock.clojure.codejam.maze-display
  (:use clojure.java.io
        flatland.ordered.map
        seesaw.border
        seesaw.chooser
        seesaw.color
        seesaw.core
        seesaw.graphics
        seesaw.mig)
  (:require [seesaw.bind :as ssb]))

First, declare a lot of things I’m to use later. Most Seesaw and one thing from here, which is a Clojure implementation of ordered sets / maps which I wanted to try out.

(def state
  {:frame (atom nil)
   :file (atom nil)
   :cases (atom nil)
   :curr-case (atom nil)
   :maze (atom nil)})

Main state – contains:

  • Main frame
  • Currently selected case-file
  • Loaded cases themselves
  • Currently selected case
  • Maze bound to the currently selected case
(def room-width 16)
(def room-height 16)

Default room size when drawn, in pixels.

(def default-style
  (style
   :foreground "#000000"
   :stroke (stroke :width 3 :cap :round)))

Default style to use when drawing walls. It’s a black, 3-pixel wide line, with rounded edges.

(defn draw-wall [g w h wall]
  (case wall
    :n (draw g (line 0 0 w 0) default-style)
    :s (draw g (line 0 h w h) default-style)
    :w (draw g (line 0 0 0 h) default-style)
    :e (draw g (line w 0 w h) default-style)))

This draws a wall. Given that translation is used below, the north-west corner of the room is always at (0, 0), so the above is easy to understand given the case keys (:n for north, :s for south, :w for west and :e for east).

(defn draw-room [g w h walls-desc]
  (let [walls (case walls-desc
                \1 #{   :s :w :e}
                \2 #{:n    :w :e}
                \3 #{      :w :e}
                \4 #{:n :s    :e}
                \5 #{   :s    :e}
                \6 #{:n       :e}
                \7 #{         :e}
                \8 #{:n :s :w   }
                \9 #{   :s :w   }
                \a #{:n    :w   }
                \b #{      :w   }
                \c #{:n :s      }
                \d #{   :s      }
                \e #{:n         }
                \f #{           }
                )]
    (doseq [wall walls]
      (push g
            (draw-wall g w h wall)))))

The room is a set of cases to decipher the letter as set of walls for that room, as given in the problem description and then draw each of these walls.

(defn paint-maze 
  (try
    (let [w room-width
          h room-height
          maze @(state :maze)]
      (when maze
        (anti-alias g)
        (translate g w h)
        (doseq [row maze]
          (push g
                (doseq [room row]
                  (draw-room g w h room)
                  (translate g w 0)))
          (translate g 0 h))))
    (catch Exception e
      (invoke-later (alert e))
      (println e))))

Main paint function:

  • Check if maze is valid (i.e. user has selected a case)
  • Turn on anit-aliasing
  • Go through the rows of the maze
  • Translate to the position of the current room
  • Draw it
(defn content-panel []
  (mig-panel
   :constraints ["fill" "[|grow]"]
   :items [[(button :id :load
                    :text "Load file...") ""]
           [(text :id :file-name) "growx, wrap"]
           [(scrollable (listbox :id :cases)
                        :border (line-border)) "grow"]
           [(let [s (scrollable (canvas :id :maze-pict
                                        :background "#ffffff"
                                        :paint paint-maze)
                                :border (line-border))]
              (-> s (.getHorizontalScrollBar) (.setUnitIncrement (* 3 room-width)))
              (-> s (.getVerticalScrollBar) (.setUnitIncrement (* 3 room-height)))
              s) "grow, push"]]))

Main window contents:

  • “Load” button
  • Current file name
  • List box for cases
  • Canvas for the maze

Uses MigLayout, of course.

(defn split-cases [acc line]
  (let [case (re-find #"^Case #\d+:$" line)]
    (if case
      ;; Found case start line
      (assoc acc
        :curr-case case
        :cases (assoc (acc :cases) case []))
      ;; Continuation of the current case (maze definition)
      (let [cases (acc :cases)
            curr-case (acc :curr-case)
            curr-maze (cases curr-case)
            new-maze (conj curr-maze line)
            new-cases (assoc cases curr-case new-maze)]
        (assoc acc
          :cases new-cases)))))

When loading, split the cases one by one, taking into account maze description has two kinds of lines:

  • Case start
  • Maze lines for the current case
(defn load-cases [file]
  (with-open [r (reader file)]
    (let [lines (reduce conj [] (line-seq r))
          {:keys [cases]} (reduce split-cases {:cases (ordered-map)} lines)]
      (reset! (state :cases) cases))))

Case loader function:

  • Use reader to read from the file
  • Get the lines
  • Reduce using previous split-cases function
(defn load [e]
  (let [frame (to-frame e)]
    (choose-file frame
                 :type :open
                 :success-fn (fn [fc file] (reset! (state :file) file)))))

Just shows the standard Java file chooser to pick the file.

(defn set-listeners [frame]
  (listen (select frame [:#load])
            :action load))

(defn set-bindings [frame]
  ;; File binding
  (ssb/bind
   (state :file)
   (ssb/tee
    (ssb/b-do* load-cases)
    (ssb/bind
     (ssb/transform #(.getPath %))
     (select frame [:#file-name]))))
  ;; Cases binding
  (ssb/bind
   (state :cases)
   (ssb/transform #(keys %))
   (ssb/tee
    (ssb/property (select frame [:#cases]) :model)
    (ssb/b-do* (fn [v] (selection! (select frame [:#cases]) (first v))))))
  ;; Case selection binding
  (ssb/bind
   (ssb/selection (select frame [:#cases]))
   (ssb/b-do* #(reset! (state :curr-case) %)))
  ;; Selected case binding
  (ssb/bind
   (state :curr-case)
   (ssb/transform #(@(state :cases) %))
   (ssb/b-do* #(reset! (state :maze) %)))
  ;; Maze binding
  (ssb/bind
   (state :maze)
   (ssb/b-do* (fn [maze] (let [canvas (select frame [:#maze-pict])
                               cw (* room-width (+ 2 (count (first maze))))
                               ch (* room-height (+ 2 (count maze)))]
                           (config! canvas :preferred-size [cw :by ch])
                           (.revalidate canvas)
                           (repaint! canvas))))))

These two set up the listeners (only one in this case – button click) and bindings which nicely describe the state machine for this simple app:

  • When file is selected, load the cases and display the file name
  • When cases were loaded, populate the list box with the case map description
  • When a case is selected, update the current case
  • When the current case changes, update the maze
  • When the maze is updated, draw it
(defn maze-display []
  (native!)
  (let [f (frame :title *ns*
                 :width 1200 :height 700
                 :on-close :dispose
                 :visible? true
                 :content (content-panel))]
    (.setLocation f (java.awt.Point. 100 100))
    (reset! (state :frame) f)
    (set-listeners f)
    (set-bindings f)))

Main function:

  • Make the frame
  • Set its location
  • Set the listeners and bindings

The final result looks like this:

maze-display-app


Google Code Jam – Always Turn Left in Clojure

Last time I did the first practice problem (Alien Numbers). Now it’s time to do the second one – Always Turn Left.

Utilities

Utilities pretty much stayed the same – the only change is to the write-output function that now has three parameters – the last was added to allow for multi-line case output. This one is needed for this problem, while it was a series of one-liners in Alien Numbers. Read about these more in the Alien Numbers post, but here they are again for completeness:

(ns com.icyrock.clojure.codejam.utils
  (:use clojure.java.io))

(def base-res "com/icyrock/clojure/codejam/")

(defn read-case-lines [case-name]
  (let [res (resource (str base-res case-name))]
    (with-open [rdr (reader res)]
      (doall (line-seq rdr)))))
  
(defn read-cases [case-name]
  (let [lines (read-case-lines (str case-name ".in"))
        case-count (Integer/parseInt (first lines))
        cases (doall (rest lines))]
    {:case-count case-count
     :cases cases}))
  
(defn write-output [output case-name multi-line]
  (let [in-res (resource (str base-res case-name ".in"))
        in-file-name (.getFile in-res)
        out-file-name (clojure.string/replace in-file-name #".in$" ".out")]
    (with-open [wr (writer out-file-name)] 
      (doseq [[case-no case-out] (map vector (range 1 (inc (count output))) output)]
        (.write wr (str "Case #" case-no ":"
                        (if multi-line "\n" " ")
                        case-out "\n"))))))

Tests

Some tests to start with:

(ns com.icyrock.clojure.codejam.cj2008pp_test
  (:use [clojure.test])
  (:use [com.icyrock.clojure.codejam.cj2008pp]))

;; Always turn left
(deftest make-maze-test
  (is (= (make-maze
          {[0 0] #{   :s    :e}
           [0 1] #{      :w :e}
           [0 2] #{:n    :w   }
           [1 0] #{:n :s      }
           [1 1] #{         :e}
           [1 2] #{   :s :w   }
           [2 0] #{:n       :e}
           [2 1] #{      :w :e}
           [2 2] #{:n :s :w   }
           [3 0] #{   :s :w :e}
           [3 1] #{      :w   }
           [3 2] #{:n :s      }
           [4 0] #{:n       :e}
           [4 1] #{      :w :e}
           [4 2] #{:n    :w   }}
          0 0 4 2)
         '("ac5" "386" "9c7" "e43" "9c5"))))

(deftest always-turn-left-case-test
  (is (= (always-turn-left-case "WRWWLWWLWWLWLWRRWRWWWRWWRWLW" "WWRRWLWLWWLWWLWWRWWRWWLW")
         '("ac5" "386" "9c7" "e43" "9c5")))
  (is (= (always-turn-left-case "WW" "WW")
         '("3")))
  (is (= (always-turn-left-case "WWLW" "WLWRRWWW")
         '("3" "b" "1")))
  (is (= (always-turn-left-case "WWWRRWLW" "WLWW")
         '("3" "7" "1")))
  (is (= (always-turn-left-case "WWRWWLW" "WWRWWLW")
         '("ac7" "bc5")))
  (is (= (always-turn-left-case "WWRWRWW" "WWLWLWW")
         '("33" "95"))))

The first test is for the make-maze function. This one is used to generate the maze given the maze map, see below. Keys of the map are [row column] points and values are sets of directions (:n, :s, :w, :e, representing north, south, west and east, respectively).

As for the actual problem tests (always-turn-left-case-test) – the first two tests are from the problem page, the second of which covers an exit on the south. The next four of these cover east, west, south and north exits, in that order. I repeated the south exit as the one given on the problem page was rather trivial. Also, this example is also a “palindrome” maze – i.e. you walk in the same way (given the entrance-to-exit and exit-to-entrance descriptions) from entrance to exit and on the way back.

Solution overview

From my perspective, this problem yields itself quite nicely to the reduce function. That is – we start from the empty maze, we walk as given by the entrance-to-exit path description and improve our knowledge about the maze on the way. I chose to record the following information:

  • Current row index
  • Current column index
  • Minimal row index
  • Minimal column index
  • Maximal row index
  • Maximal column index
  • Current direction
  • The map of the maze, using points ([row column] vectors) as keys

After that, do the same in the opposite direction, updating the same set of information as above.

The first part above gives the maze map and the bounding box of the maze (min / max row / column index). The last thing left is to reconstruct the maze, which is rather trivial given that information.

Clojure solution

Here’s the actual code, explained step by step:

;; Always turn left
(defn opposite-dir [dir]
  ({:n :s, :e :w, :s :n, :w :e} dir))

This is a helper function to get the opposite direction of the one we are currently pointing toward.

(defn maze-move [[cr cc minr minc maxr maxc dir maze-map] cmd]
  (case cmd
    \W (let [nr (+ cr ({:n -1, :e 0, :s 1, :w 0} dir))
             nc (+ cc ({:n 0, :e 1, :s 0, :w -1} dir))
             croom (or (maze-map [cr cc]) #{})
             nroom (or (maze-map [nr nc]) #{})
             new-croom (conj croom dir)
             new-nroom (conj nroom (opposite-dir dir))
             new-maze-map (assoc maze-map [cr cc] new-croom [nr nc] new-nroom)]
         [nr nc
          (min minr nr) (min minc nc)
          (max maxr nr) (max maxc nc)
          dir new-maze-map])
    \L [cr cc minr minc maxr maxc
        ({:n :w, :e :n, :s :e, :w :s} dir)
        maze-map]
    \R [cr cc minr minc maxr maxc
        ({:n :e, :e :s, :s :w, :w :n} dir)
        maze-map]))

This one actually makes the move given the current parameters and yields the next state. This is used below to reduce over the set of moves. There are three possible moves:

  • L / R – these just change the direction, without changing the position or anything else. This is done by doing the map-lookup in both cases
  • W – perform the walk. Walking has three consequences:
    • Position is changed (so nr / nc = new row and column indices are updated, also using map-lookup method)
    • Current and new rooms’ (new-croom / new-nroom) walls are updated (i.e. removed on the appropriate sides, given walking is possible) and
    • The map is updated with the new rooms
(defn make-maze [maze-map minr minc maxr maxc]
  (for [r (range minr (inc maxr))] 
    (apply str
           (for 
             (case (maze-map [r c])
               #{:n         } "1"
               #{   :s      } "2"
               #{:n :s      } "3"
               #{      :w   } "4"
               #{:n    :w   } "5"
               #{   :s :w   } "6"
               #{:n :s :w   } "7"
               #{         :e} "8"
               #{:n       :e} "9"
               #{   :s    :e} "a"
               #{:n :s    :e} "b"
               #{      :w :e} "c"
               #{:n    :w :e} "d"
               #{   :s :w :e} "e"
               #{:n :s :w :e} "f"
               "#")))))

This is the function that generates the maze layout in the format required by the problem given the parameters output by the reduce over the given moves.

(defn always-turn-left-case [ent-to-exit exit-to-ent]
  (let [[exr exc minr minc maxr maxc dir maze-map]
        (reduce maze-move [-1 0 0 0 0 0 :s {}] ent-to-exit)
        [_ _ _ minc maxr maxc _ maze-map]
        (reduce maze-move [exr exc minr minc maxr maxc (opposite-dir dir) maze-map] exit-to-ent)
        act-minc (if (= dir :w) (inc minc) minc)
        act-maxr (if (= dir :s) (dec maxr) maxr)
        act-maxc (if (= dir :e) (dec maxc) maxc)]
    (make-maze maze-map 0 act-minc act-maxr act-maxc)))

The core of the solver:

  • Reduce from entrance to exit
  • Reduce from exit to entrance
  • Calculate the bounding box (discarding the last step, as entrance and exit are always outside of the maze)
  • Make the maze map
(defn always-turn-left []
  (let [case-names ["sample" 
                    "B-small-practice" 
                    "B-large-practice"]
        case-names-full (for [case-name case-names] 
                          (str "08pp/always-turn-left/" case-name))] 
    (time
     (doseq [case-name case-names-full] 
       (let [{:keys [case-count cases]} (read-cases case-name)
             output (for [case cases]
                      (let [[ent-to-exit exit-to-ent] (split case #" ")]
                        (join "\n" (always-turn-left-case ent-to-exit exit-to-ent))))]
         (write-output output case-name true))))))

The wrapper around the solver to run the given problems – sample is the sample given in the description and B-small-practice and B-large-practice are the files that you can download when submitting the solution. Cases are read using the utility functions and written in the expected format.


Google Code Jam – Alien Numbers in Clojure

Google Code Jam is a competition where participants compete in solving algorithmic puzzle. It’s been done usually a couple of times a year for different regions. The one for year 2013. starts in less than a couple of weeks from now!

I wanted to exercise my Clojure newbie skills to try to solve one of the practice problems from the first practice session available – Alien Numbers. Probably good to go read the problem statement to understand what I’m going to do below.

Here’s how I went about it…

Utilities

First, some generic utilities. Not sure if this applies to all, but looks like Code Jam problems are made so you read the .in file and write the .out file. The samples are given, for example for Alien Numbers the sample is:

  • Input
4
9 0123456789 oF8
Foo oF8 0123456789
13 0123456789abcdef 01
CODE O!CDE? A?JM!.

where the first line gives the number of cases (4 in this case) and then that many lines follow with the actual cases.

  • Output
Case #1: Foo
Case #2: 9
Case #3: 10011
Case #4: JAM!

where you have 4 cases with prefix “Case #N: ” and the corresponding output from the solver program.

So, my first thought is – I need a couple of functions to read and write these. Here’s how I did these:

(ns com.icyrock.clojure.codejam.utils
  (:use clojure.java.io))

(def base-res "com/icyrock/clojure/codejam/")

(defn read-case-lines [case-name]
  (let [res (resource (str base-res case-name))]
    (with-open [rdr (reader res)]
      (doall (line-seq rdr)))))
  
(defn read-cases [case-name]
  (let [lines (read-case-lines (str case-name ".in"))
        case-count (Integer/parseInt (first lines))
        cases (doall (rest lines))]
    {:case-count case-count
     :cases cases}))
  
(defn write-output [output case-name]
  (let [in-res (resource (str base-res case-name ".in"))
        in-file-name (.getFile in-res)
        out-file-name (clojure.string/replace in-file-name #".in$" ".out")]
    (with-open [wr (writer out-file-name)] 
      (doseq [[case-no case-out] (map vector (range 1 (inc (count output))) output)]
        (.write wr (str "Case #" case-no ": " case-out "\n"))))))

There are four things above:

  • base-res is the resource folder where I read the .in files from and then construct the name to write the .out file to
  • read-case-lines read the lines of the .in file
  • read-cases uses the above to read the number of cases and the cases themselves
  • write-output will get the program output and write the output in the required format (i.e. prefixing with “Case #N: “)

Actual solution methods

Solution is easy given two methods:

  • First part – alien to “computer” numbers converter
  • Second part – “computer” to alien numbers converter

I’ll make two methods here:

  • from-num-repr that does alien-to-computer conversion
  • to-num-repr that does computer-to-alien conversion

Tests

Let’s write some tests to define how these are to work:

(ns com.icyrock.clojure.codejam.cj2008pp_test
  (:use [com.icyrock.clojure.codejam.cj2008pp])
  (:use [clojure.test]))

(deftest from-num-repr-test
  ;; bin / dec / hex 
  (is (= 9 (from-num-repr "1001" "01")))
  (is (= 72 (from-num-repr "72" "0123456789")))
  (is (= 0x53 (from-num-repr "53" "0123456789abcdef")))

  ;; same as above, just different symbols
  (is (= 9 (from-num-repr "tfft" "ft")))
  (is (= 72 (from-num-repr "hc" "abcdefghij")))
  (is (= 0x53 (from-num-repr "wz" "1qaz2wsx3edc4rfv"))))

(deftest to-num-repr-test
  ;; bin / dec / hex 
  (is (= "1001" (to-num-repr 9 "01")))
  (is (= "72" (to-num-repr 72 "0123456789")))
  (is (= "53" (to-num-repr 0x53 "0123456789abcdef")))

  ;; same as above, just different symbols
  (is (= "tfft" (to-num-repr 9 "ft")))
  (is (= "hc" (to-num-repr 72 "abcdefghij")))
  (is (= "wz" (to-num-repr 0x53 "1qaz2wsx3edc4rfv"))))

Here I used three simple numbers in three common bases – binary, decimal and hexadecimal. Also did two cases – with “normal” symbols and with “garbage” symbols.

First part – alien to “computer” numbers

(defn from-num-repr [num lan]
  (let [lan-dig (apply hash-map (interleave lan (range)))
        rnum (reverse num)
        val-rnum (map lan-dig rnum)
        dig-cnt (count num)
        lan-cnt (count lan) 
        exps (iterate #(* lan-cnt %) 1)
        vals (map * val-rnum exps)]
    (apply + vals)))

Here:

  • lan-dig is a map of alien language symbol to digit. E.g. if language symbols are “abcd”, then lan-dig would be: {\a: 0, \b: 1, \c: 2, \d: 3}
  • rnum is reverse number. We need it reverse as we apply exponents based on the positional value of the digit
  • val-rnum is the digit value for each of the symbols in rnum
  • exps is the exponents of the digit position in the target alien language. E.g. if alien language has 2 symbols (i.e. binary system), exps would be [1, 2, 4, 8, 16, …]
  • vals is the positional value of the rnum
  • Finally, we just sum the values in vals to get the number value

Second part – “computer” to alien numbers

(defn to-num-repr [num lan]
  (let [dig-lan (apply hash-map (interleave (range) lan))
        lan-cnt (count lan)]
    (loop [left num tl-num '()]
      (if (= left 0)
        (apply str tl-num)
        (let [num-mod (mod left lan-cnt)
              num-left (quot left lan-cnt)] 
          (recur num-left (cons (dig-lan num-mod) tl-num)))))))

This is reverse from the previous:

  • dig-lan is reverse of lan-dig, i.e. keys and values reversed. E.g. if language symbols are “abcd”, then lan-dig would be: {0: \a, 1: \b, 2: \c, 3: \d}
  • We then loop until we reach zero, i.e. nothing more to convert
  • In each iteration, we get the modulus and reminder of the number and add the appropriate digit by mapping via dig-lan to the accumulated result (tl-num)
  • Finally, we just apply str function to tl-num list to get the actual string representation using the target alien language symbols

Third part – glue the above to get alien to another alien numbers converter

This is just a simple glue:

  • Get the number and the language symbols in the source alien language
  • Convert to “computer” representation
  • Convert that “computer” representation to the number in the target alien language, given the target language symbols
(defn alien-numbers-case [case]
  (let [[sl-num src-lan tgt-lan] (split case #" ")
        num (from-num-repr sl-num src-lan)
        tl-num (to-num-repr num tgt-lan)]
    tl-num))

Fourth part – do this for all available cases

There are usually three cases given for each Code Jam:

  • Sample – this is usually short and contains of a few input cases and their corresponding outputs
  • Small – a bigger set than Sample set. Looks like in real competition you get a different file each time you ask for the input (so outputs need to be re-created each time a file is downloaded)
  • Large set – larger set than Small set and looks like you get only this file always

I downloaded these in the resource folder of the app and ran for them all:

(defn alien-numbers []
  (let [case-names ["sample" 
                   "A-small-practice" 
                   "A-large-practice"]
        case-names-full (for [case-name case-names] 
                          (str "08pp/alien-numbers/" case-name))] 
    (time
      (doseq [case-name case-names-full] 
        (let [{:keys [case-count cases]} (read-cases case-name)
              output (for [case cases] (alien-numbers-case case))]
          (write-output output case-name))))))

End

The best thing – the output actually passes when submitted… Nice!