```
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
```

# 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')`

.

## 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

This library uses a fast method due to Goetgheluck.

```
import Jam
import Math.Combinatorics.Exact.Binomial
main = jam $ getints >>= \[r, c] -> return . show . choose (r+c-2) $ r-1
```

*blynn@cs.stanford.edu*💡