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!

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