Part 1

We are given three different commands:

Given a long list of these, we are to compute the final depth and horizontal position of the submarine. This is straightforward. We define a type of movement commands:

data Command = Forward Int | Down Int | Up Int

We then have a function move : [Command] → ⟨Int, Int⟩. Clearly this is a catamorphism:

move = foldr f ⟨0, 0⟩

f : Command → (Int × Int) → (Int × Int);
f (Forward k) ⟨x, y⟩ = ⟨x + k, y⟩;
f (Down k)    ⟨x, y⟩ = ⟨x, y + k⟩;
f (Up k)      ⟨x, y⟩ = ⟨x, y - k⟩

We’d like to replace the right fold with a (strict) left fold. Define:

f′ = flip f

Then by some quick informal calculations, we have that f associates with f′:

f c ⟨0, 0⟩ = f′ ⟨0, 0⟩ c

f c (f′ ⟨x, y⟩ d) = f c ⟨x + k, y + l⟩
                  = ⟨x + k + m, y + l + n⟩
                  = f′ ⟨x + k, y + l⟩ c
                  = f′ (f d ⟨x + k, y + l⟩) c

So we can write

move = foldl f′ ⟨0, 0⟩

Part 2

The commands are the same, but their meaning is a bit different now.

So now the 2D state of the submarine is only altered by a forward command, and the sub has an additional state variable, the aim. aim also starts at 0.

The skeleton of the program is mostly the same. We need a new gene [const ⟨0, 0, 0⟩, g] for the move catamorphism. We’re only interested in the final horizontal position and depth, though, so we extract the initial two elements of the result with an aux. function.

move : [Command] → (Int × Int)
move = first_two ∘ foldl g ⟨0, 0, 0⟩

first_two ⟨x, y, _⟩ = ⟨x, y⟩

g : (Int × Int × Int) → Command → (Int × Int × Int)
g ⟨x, y, a⟩ (Forward k) = ⟨x + k, y + (a * k), a⟩
g ⟨x, y, a⟩ (Down k)    = ⟨x, y, a + k⟩
g ⟨x, y, a⟩ (Up k)      = ⟨x, y, a - k⟩

The new gene component g simply encodes the semantics for the movement commands.

AOC 2021 Index