# Part 1

We are given three different commands:

• forward X increases the horizontal position by X units.

• down X increases the depth by X units.

• up X decreases the depth by X units.

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.

• down X increases your aim by X units.

• up X decreases your aim by X units.

• forward X does two things:

• It increases your horizontal position by X units.

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

Home