### 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/")

(let [res (resource (str base-res case-name))]
(doall (line-seq rdr)))))

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

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.

(required)

(required)