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 1))

(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!

Be Sociable, Share!

2 Responses to “Google Code Jam – Alien Numbers in Clojure”

Google Code Jam – Always Turn Left in Clojure « Blog Archive « icyrock.com on March 21st, 2013 19:29:

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


rebcabin on March 23rd, 2013 22:48:

There seems to be an unbound symbol, “resource”, in the definition of “read-case-lines.” I can’t get utils to run without it.


Leave a Reply


nine − = 2