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 1)
  (: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 1
             (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.

Be Sociable, Share!

One Response to “Google Code Jam – Always Turn Left in Clojure”

Maze display app for Always Turn Left « Blog Archive « icyrock.com on April 3rd, 2013 21:50:

[...] 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. [...]


Leave a Reply


five − = 1