From 44bb3403d2f42fb8ea48cfdd05b20318d99b0556 Mon Sep 17 00:00:00 2001
From: tomsmeding <tom.smeding@gmail.com>
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

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-54-g00ecf