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