From 44bb3403d2f42fb8ea48cfdd05b20318d99b0556 Mon Sep 17 00:00:00 2001 From: tomsmeding Date: Sun, 3 Dec 2017 10:46:59 +0100 Subject: Day 3 --- 2017/.gitignore | 3 +++ 2017/3.hs | 64 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2017/3.in | 1 + 3 files changed, 68 insertions(+) create mode 100644 2017/.gitignore create mode 100644 2017/3.hs create mode 100644 2017/3.in (limited to '2017') diff --git a/2017/.gitignore b/2017/.gitignore new file mode 100644 index 0000000..2b9a6e0 --- /dev/null +++ b/2017/.gitignore @@ -0,0 +1,3 @@ +*.hi +*.o +? diff --git a/2017/3.hs b/2017/3.hs new file mode 100644 index 0000000..a762965 --- /dev/null +++ b/2017/3.hs @@ -0,0 +1,64 @@ +import Control.Monad +import Data.Function +import Data.List +import Data.Maybe + +type Ring = Int +type Index = Int +type Value = Int + +righttop :: Ring -> Index +righttop ring = 1 + (2 * ring - 1) * (2 * ring) + +-- rt(r) = 1 + 2r(2r-1) = 4r^2 - 2r + 1 = n +-- 4r^2 - 2r + 1 - n = 0 +-- r = (2 + sqrt(4 - 4*4*(1-n))) / 8 +-- = (2 + sqrt(16n - 12)) / 8 +-- = (2 + 2sqrt(4n - 3)) / 8 +-- = (1 + sqrt(4n - 3)) / 4 + +-- counted from right-top numbers (1 is also a right-top number) +ringof :: Index -> Ring +ringof n = floor $ (1 + sqrt (fromIntegral (4 * n - 3))) / 4 + +posof :: Index -> (Int, Int) +posof n = + let r = ringof n + rt = righttop r + d = 2 * r + in case n of + _ | n < rt + d -> (r - (n - rt), r) + | n < rt + 2*d -> (-r, r - (n - (rt + d))) + | n < rt + 2*d + d+1 -> (-r + n - (rt + 2*d), -r) + | n < rt + 2*d + 2*(d+1) -> (r + 1, -r + n - (rt + 2*d + d+1)) + | otherwise -> undefined + +posidx :: (Int, Int) -> Index +posidx (x, y) = + let ring = if x > abs y then x - 1 else (max `on` abs) x y + rt = righttop ring + ringlen = 8 * ring + 2 + Just ringidx = findIndex (== (x, y)) (map posof [rt .. rt+ringlen-1]) + in rt + ringidx + +manhattan1 :: Index -> Int +manhattan1 = uncurry ((+) `on` abs) . posof + +valueof :: Index -> Value +valueof n = cache !! (n - 1) + where cache = map valueof' [1..] + +valueof' :: Index -> Value +valueof' 1 = 1 +valueof' n = + let (x, y) = posof n + nei = [(x + dx, y + dy) | dx <- [-1..1], dy <- [-1..1], dx /= 0 || dy /= 0] + indices = filter (< n) (map posidx nei) + in sum (map valueof indices) + +main :: IO () +main = do + input <- liftM read (readFile "3.in") :: IO Int + print (manhattan1 input) + -- putStrLn $ intercalate "\n" [intercalate " " $ map show [valueof (posidx (x,-y)) | x <- [-3..3]] | y <- [-3..3]] + print $ fromJust $ find (> input) $ map valueof [1..] diff --git a/2017/3.in b/2017/3.in new file mode 100644 index 0000000..fa5db30 --- /dev/null +++ b/2017/3.in @@ -0,0 +1 @@ +289326 -- cgit v1.2.3-70-g09d2