Jump to:
D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25
Part 1
Day 13 hits us with some number theory! Part 1 starts off with a simple warm-up.
import D13input
-- earliest :: Int
-- buses :: [Int]
waitTime :: Int -> Int -> Int
waitTime t b = (-t) `mod` b
bestPair :: Int -> [Int] -> (Int, Int)
bestPair t bs = minimum (zip (map (waitTime t) bs) bs)
solve :: Int
solve = let (time, id) = bestPair earliest buses
in (time * id)
main :: IO ()
main = print $ solve
I suppose the main challenge here is knowing the mod function and how to use it. To rephrase the problem in mathematical terms, we need to find the smallest multiple of some number greater than some threshold, and then find the difference between that threshold and that multiple. This is accomplished in one shot by the waitTime function.
Coming from a C++ background, I originally wrote this more faithfully as waitTime t b = b - (t `mod` b), because the modulo operation is implementation-defined when negative numbers are involved in C++, so it would be ill-advised to use negative operands. In Haskell, however, it seems this operation is well-defined to give the positive remainder, so we can combine the steps as we did above.
Part 2
Part 2 poses a problem that can be very elegantly solved with the well-known Chinese Remainder Theorem. We note by inspection that all of the bus times are prime numbers. It is beyond the scope of this blog post to discuss this theorem in great detail, but it essentially states the existence of exactly what the problem asks for, as well as a method to construct it efficiently. The solution presented here implements the "direct construction" approach outlined in the Wikipedia article.
import D13input
-- earliest :: Int
-- buses :: [Int]
-- input :: [Int]
eEuclid :: (Int, Int, Int) -> (Int, Int, Int) -> (Int, Int, Int)
eEuclid (r, s, t) (r', s', t')
| r' == 0 = (r, s, t)
| otherwise = let q = r `div` r'
in eEuclid (r', s', t') (r `mod` r', s - q * s', t - q * t')
bezout :: (Int, Int) -> (Int, Int)
bezout (a, b) = let (_, s, t) = eEuclid (a, 1, 0) (b, 0, 1)
in (s, t)
waitTime :: Int -> Int -> Int
waitTime t b = (-t) `mod` b
primesAndRemainders :: [Int] -> [(Int,Int)]
primesAndRemainders bs =
let pairs = filter (\(_, x) -> x /= 1) (zip [0..] bs)
in map (\p@(i,b) -> (b, uncurry waitTime p)) pairs
chineseRemainder :: ([Int], [Int]) -> Int
chineseRemainder (ps, rs) =
let n = foldr (*) 1 ps
ns = map (div n) ps
ms = map (fst . bezout) (zip ns ps)
x = sum $ zipWith3 (\a b c -> a * b * c) rs ms ns
in x `mod` n
solve :: Int
solve = chineseRemainder $ unzip $ primesAndRemainders input
main :: IO ()
main = print $ solve
The first step is to implement bezout, a function that finds the integers whose existence is guaranteed by Bézout's Identity. In this problem, we will only feed prime numbers into this function, so their greatest common divisor will always be 1. Our bezout function therefore, for some given (a, b), returns the (x, y) such that ax + by = 1.
The workhorse behind bezout is the Extended Euclidean algorithm, which sounds fancy to those unfamiliar with number theory, but is actually a fairly simple algorithm. It is implemented very nicely with a recursive function, and outputs both the greatest common divisor and the Bézout coefficients of a pair of integers.
Armed with bezout, we can now turn our attention to solving the problem with the Chinese Remainder Theorem. In a nutshell, the theorem gives us a way to determine the number x that, when divided by some list of primes, gives some list of remainders, which is exactly what Part 2 demands. First, we need to obtain this list of primes and this list of remainders. With the help of our waitTime function from part 1, we can obtain this from the input using the primesAndRemainders function.
chineseRemainder is then a straightforward implementation of the construction outlined in the Wikipedia article. We compute all of the products-of-all-primes-except-one, and compute the Bézout coefficients involving them. More products and a final sum give us our answer.
Jump to:
D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25