Advent of Code F# – Day 25

The source code for this post is avail­able here and you can click here to see my solu­tions for the oth­er Advent of Code chal­lenges.

Descrip­tion for today’s chal­lenge is here.

 

It’s the last day of the advent cal­en­dar, and today’s chal­lenge appears dif­fi­cult at first but most­ly because of the grid sys­tem it impos­es upon you.

But after some thought, the prob­lem can be dras­ti­cal­ly sim­pli­fied.

Giv­en this grid sys­tem:

day25_02

we can work out the one-based index for row N, col­umn 1 in this for­mu­la:

F N = F(N-1) + (N-1) where F 1 = 1, F 2 = 2

e.g.

F 2 = 2,

F 3 = F 2 + (3 — 1) = 2 + 2 = 4

F 4 = F 3 + (4 — 1) = 4 + 3 = 7

From here, col­umn M is (M — 1) dis­tance away from the first ele­ment on the same row and (M — 1) dis­tance away from the row N that marks the start of the diag­o­nal:

day25_03v2

So, the one-based index for row N, col­umn M can be expressed in terms of the F func­tion above:

G (M, N) = F (N + M — 1) + (M — 1)

e.g.

G (3, 2) = F (2 + 3 — 1) + (3 — 1) = F 4 + 2 = 7 + 2 = 9

G (6, 1) = F (1 + 6 — 1) + (6 — 1) = F 6 + 5 = 16 + 5 = 21

So for my puz­zle input of row 2981, col­umn 3075, it trans­lates = G (3075, 2981)th ele­ment where the first ele­ment is 20151125.

Tak­ing all these into account, and trans­lat­ing G (M, N) into an (x, y) based sys­tem, we can have the fol­low­ing to solve today’s chal­lenge:

day25_01

Pret­ty straight­for­ward, right? Well, the only caveat is how we imple­ment­ed F here, this is only because I want­ed the imple­men­ta­tion to be tail recur­sive, oth­er­wise it can be sim­ple as:

let F = func­tion | 1 -> 1 | 2 -> 2 | n -> F (n-1) + (n-1)

 

So that’s it folks! We’ve com­plet­ed all the Advent of Code chal­lenges for 2015, and our F# xmas tree is up and run­ning in all its glo­ry 

day25_complete