Code Jam to I/O 2015 for Women

I/O Error

We fold over a string to read a number in binary. We use fromEnum to convert a Bool to an Int; an alternative is to import Data.Bool and write bool 0 1 (c == 'I').

import Jam
import Control.Applicative
import Data.Char
import Data.List.Split

main = jam $ gets >> gets >>= \s -> return $
  chr . foldl (\n c -> 2*n + fromEnum (c == 'I')) 0 <$> chunksOf 8 s

Dreary Design

A fun exercise in combinatorics. In a given triple, label the component values a, b, c such that a <= b <= c.

First, we count the cases when all components are equal. There are k + 1 of these: one for each possible component value.

Otherwise, c - a == n for some n <- [1..v]. There are k - n + 1 possible solutions for this equation, one for each a <- [0..k - n].

Now, if a == b, then there are 3 possible orderings for these components: (a, a, c), (a, c, a), (c, a, a). Similarly if b == c there are 3 possible orderings.

Otherwise we have n - 1 possible choices for b satisfying a < b < c, and there are 3! = 6 possible orderings for a, b, c.

Thus for a given n, the number of possible colours satisfying c - a = n is:

(k - n + 1) * (3 + 3 + 6 * (n - 1)) = (k - n + 1) * 6 * n

Summing this over all n <- [1..v] and adding the equal-components case gives a grand total of:

k + 1 + sum [(k - n + 1) * 6 * n | n <- [1..v]]

With a little algebra, we can simplify this formula. The summation can broken into two:

6*(k + 1) * sum[n | n <- [1..v]] - 6*sum[n^2 | n <- [1..v]]

We can apply well-known formulas for the sum of the first v numbers (triangular numbers) and the first v squares (square pyramidal numbers) to get:

6*(k + 1)*v*(v + 1)/2 - 6*v*(v + 1)*(2*v + 1)/6

Hence:

import Jam

main = jam $ getints >>= \[k, v] ->
  return . show $ k + 1 + v*(v + 1)*(3*k - 2*v + 2)

Power Levels

Haskell’s built-in support for arbitrary-precision arithmetic means the simple approach works: just compute all multifactorials of 9000 and count their digits with length . show.

import Jam
import Control.Applicative
import Data.List
import Data.Maybe

fs = length . show . (\e -> product [9000,9000-e..1]) <$> [1..8999]

main = jam $ getints >>= \[d] -> return $ if d <= 4 then "..."
  else "IT'S OVER 9000" ++ replicate (1 + fromJust (findIndex (< d) fs)) '!'

Googlander

Suppose the first turn happens on the topmost row. Afterwards, it’s as if we’re starting again on a grid with c - 1 rows and r - 1 columns.

Otherwise the topmost row is uninvolved, so we may as well pretend we started on a grid with r - 1 rows and c columns.

Thus if f r c is the number of different paths, we have the recursion

f r c = f (r - 1) c + f (c - 1) (r - 1)

The base cases are simple: if r == 1 or c == 1, then there is only one possible path. By induction, this means f r c == f c r, and in fact the above recursion is describing a sort of off-by-one Pascal’s triangle. We have:

f r c = (r + c - 2) `choose` (r - 1)

It’s easy to compute binomial coefficients ourselves, but we may as well let a library do the hard work:

$ cabal install exact-combinatorics
import Jam
import Math.Combinatorics.Exact.Binomial

main = jam $ getints >>= \[r, c] -> return . show . choose (r+c-2) $ r-1

Ben Lynn blynn@cs.stanford.edu 💡