import Jam import Data.List import Data.Maybe main = jam $ do w <- gets let dict = case nub w of [d] -> ['?', d] (d0:d1:ds) -> d1:d0:ds pure . show $ foldl (\n d -> n * length dict + fromJust (d `elemIndex` dict)) 0 w

## All Your Base

We already solved this recommended beginner problem, but we’ll write it again using our Jam monad:

## Center of Mass

A little algebra shows the distance of the center of mass from the origin,
is a quadratic equation in `t`

, with a positive leading coefficient.
Differentiating with respect to `t`

, or just by completing the square,
the minimum occurs when:

xs*vxs + ys*vys + zs*vzs == (vxs^2 + vys^2 + vzs^2) t

where `xs ys zs vxs vys vzs`

are the sum of each of the six numbers, that is
the three position coordinates and the three velocity coordinates, across all
fireflies.

We are only interested in `t >= 0`

so if the minimum is attained for a negative
`t`

value, we clip it to `t = 0`

. The leading cofficient is positive, hence the
parabola opens upward, which implies the distance is smallest when `t = 0`

for
this case. Thus:

import Jam import Control.Monad import Data.List import Text.Printf main = jam $ do [n] <- getints (ps, vs) <- splitAt 3 . foldl1' (zipWith (+)) <$> replicateM n getdbls let t0 = max 0 $ -(sum $ zipWith (*) ps vs) / (sum $ (^2) <$> vs) d0 = sqrt $ sum $ map ((^2) . (/ fromIntegral n)) $ zipWith (+) ps $ map (*t0) vs pure $ printf "%.7f %.7f" d0 t0

We have gratuitiously applied list functions like `sum`

and `zipWith`

to avoid
explicitly mentioning the three coordinates.

## Bribe the Prisoners

Suppose we release some prisoner first. Once done, the prisoners on one side can no longer communicate with those on the other.

Thus, the minimum total cost is the number of filled cells in a row on either side, plus the sum of the two solutions to smaller instances of the same problem, namely, the sum of the minimum costs to release the remaining prisoners on each side of the released prisoner considered independently.

We turn this observation into a dynamic programming solution. We use
sentinel values 0 and `p + 1`

to remove special cases with the edges of
the priosn. Then, we consder releasing each prisoner in turn, relying on
a memoized recursion to solve the subproblems, and return the cheapest
solution, or 0 if there is nothing to do.

import Jam import Data.Array import Data.Maybe import Data.MemoTrie import Safe main = jam $ do [p, _] <- getints qs <- getints let a = listArray (0, length qs + 1) $ (0:qs) ++ [p+1] f(i, j) = fromMaybe 0 $ foldl1May' min [a!j - a!i - 2 + g(i, k) + g(k, j) | k <- [i+1..j-1]] g = memo f pure $ show $ g $ bounds a

*blynn@cs.stanford.edu*💡