1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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..]
|
