# Navigating a bounded 2D list (Advent of Code, Day 2: “Bathroom Security”)

Posted on

Problem

I’m trying to solve the following Advent of Code problem in F# for practice.

Description of problem (can be found here):

Basically, there’s a ‘key pad’ that I need to figure the combination to. To do that, I have to follow instructions in the form ‘U’/’D’/’L’/’R’ to move a key up, down, left, or right in a gird of keys (see `puzzleInput` below). A newline means to take down the number I’m currently on and record it. I am bounded to the grid (eg. if I’m on the upper edge I can’t move any more if the instruction was ‘U’). The challenge is in 2 parts, in the first part the keypad is a 3×3 numerical grid (1..9). In the second part the keypad is a diamond shaped 5×5 alphanumeric grid (1..9, A, B, C, D) – movement is constrained to the diamond shape.

My attempt:

``````open System
open System.IO

// possible instructions, halt means to 'take down current number'
type Instruction =
| Up
| Down
| Right
| Left
| Halt

// helper method used later
let getLastElementOf seq =

// method to get code, see sample input below
let GetCode rawInput keyPadButtons startPos =

let parse (rawInput:string) :List<Instruction> =
rawInput.ToCharArray()
|> Seq.map (function
| 'U' -> Up
| 'D' -> Down
| 'R' -> Right
| 'L' -> Left
| 'n' -> Halt
| _ -> failwith "Unexpected token.")
|> (fun x ->  Seq.toList x @ [Halt])

// used to enforce grid bounds, method used by followOne
let validate pos fallbackPos (tdarr:List<List<char>>)  =
try
if tdarr.[fst pos].[snd pos] <> ' '  //I'm using ' ' as a padding
then pos
else fallbackPos
with
| e -> fallbackPos

// follows one instruction, method used by followAll
let followOne (grid:List<List<char>>) (pos:int * int) (instruction:Instruction) :int * int =
validate (match instruction with
| Up -> fst pos - 1 , snd pos
| Down -> fst pos + 1, snd pos
| Right -> fst pos, snd pos + 1
| Left -> fst pos, snd pos - 1
| _ -> failwith "Unknown instructon.") pos grid

// follow all instructions & produce result
let followAll (keyPadButtons:List<List<char>>) (instructions:List<Instruction>) :string =
instructions
|> Seq.mapFold (fun state instruction ->
"", (
if instruction = Halt
then fst state,
.[fst (getLastElementOf (fst state))]
.[snd (getLastElementOf (fst state))].ToString()
else fst state
@[followOne keyPadButtons (getLastElementOf (fst state)) instruction],
snd state
)
) ([startPos], "")
|> snd |> snd

rawInput
|> parse

[<EntryPoint>]
let main argv =

let puzzleInput = "DLUUULUDLRDDLLLUDULLULLRUURURLUULDUUUDLDDRUDLUULLRLDDURURDDRDRDLDURRURDLDUURULDDULDRDDLDLDLRDRUURLDLUDDDURULRLLLLRLULLUDRDLDUURDURULULULRLULLLULURLRDRDDDDDDDLRLULUULLULURLLDLRLUDULLDLLURUDDLDULDLULDDRLRLRDDLRURLLLURRLDURRDLLUUUUDRURUULRLDRRULLRUDLDRLUDRDRDRRDDURURRDRDRUDURDLUDRUDLRRULDLRDDRURDDUUDLDRDULDDRRURLLULRDRURLRLDLLLUULUUDLUDLDRRRRDUURULDUDUDRLDLLULLLRDDDDDLRDDLLUULLRRRDURLRURDURURLUDRRLRURDRDRRRRULUDLDRDULULRUDULLLUDRRLRLURDDURULDUUDULLURUULRDRDULRUUUDURURDDRRUDURRLRDRULRUUU
LDRURRUUUULDRDDDLLULDRUDDRLLDLDRDLRUDDDLDDULULULLRULDUDRRDLRUURURDRURURDLLRUURDUUDRLDURDRDLRRURURDUUUURUURRLLLDRDUURRRRURULUUUDLUDDRUURRLDULRDULRRRRUDURRLURULRURRDRDLLDRRDUDRDURLDDRURULDRURUDDURDLLLUURRLDRULLURDRDRLDRRURRLRRRDDDDLUDLUDLLDURDURRDUDDLUDLRULRRRDRDDLUDRDURDRDDUURDULRRULDLDLLUDRDDUDUULUDURDRLDURLRRDLDDLURUDRLDUURLLRLUDLLRLDDUDLLLRRRLDLUULLUDRUUDRLDUUUDUURLRDDDDRRDRLDDRDLUDRULDDDRDUULLUUUUULDULRLLLRLLDULRDUDDRDDLRRLRDDULLDURRRURDDUDUDDRLURRLUUUULLDRDULUUDRDULDLLUDLURDLLURRDLUULURRULRLURRRRRUURDDURLRLLDDLRRDUUURDRDUDRDDDLLDDRDRRRLURRDUULULULULRRURDDLDDLLLRUDDDDDDLLLRDULURULLRLRDRR
DDRLLLDLRRURRDLDDRUURRURRLRRRRUURUURDLURRRDDLRUDRURLUURLLRRLRLURLURURDULLLLDLRURULUUDURRLULRDRDRRDDLLULRLUDLUUUDRLLRRURRLDULDDLRRLUUUUDDLRLDRLRRDRDLDDURDDRDDLDLURLRRRDDUDLLRLRLURRRRULLULLLLDRLDULDLLDULRLDRDLDDRRDDDDRUDRLLURULRLDDLLRRURURDDRLLLULLULDDRDLDDDLRLLDRLDRUURRULURDDRLULLDUURRULURUUDULLRUDDRRLLDLLRDRUDDDDLLLDDDLLUUUULLDUUURULRUUDUUUDDLDURLDRDRRLLUDULDLUDRLLLDRRRULUUDDURUDRLUDDRRLLDUDUURDDRURLUURDURURURRUUDUDDLLLDRRRURURRURDLRULLDUDRLRLLRUDRUDLR
RRRDRLRURLRRLUURDRLDUURURLRDRRUDLLUUDURULLUURDLLDRRLURRUDUUDRRURLRRDULLDDLRRRUDUUDUUDLDDDLUUDLDULDDULLDUUUUDDUUDUDULLDDURRDLRRUDUDLRDUULDULRURRRLDLLURUDLDDDRRLRDURDLRRLLLRUDLUDRLLLRLLRRURUDLUDURLDRLRUDLRUULDRULLRLDRDRRLDDDURRRUDDDUDRRDRLDDRDRLLRLLRDLRDUDURURRLLULRDRLRDDRUULRDDRLULDLULURDLRUDRRDDDLDULULRDDRUDRLRDDRLDRDDRRRDUURDRLLDDUULRLLLULLDRDUDRRLUUURLDULUUURULLRLUDLDDLRRDLLRDDLRDRUUDURDDLLLDUUULUUDLULDUDULDRLRUDDURLDDRRRDLURRLLRRRUDDLDDRURDUULRUURDRRURURRRUUDUDULUDLUDLLLUUUULRLLRRRRDUDRRDRUDURLUDDLDRDLDDRULLRRULDURUL
DLLLRDDURDULRRLULURRDULDLUDLURDDURRLLRRLLULRDLDRDULRLLRDRUUULURRRLLRLDDDRDRRULDRRLLLLDLUULRRRURDDRULLULDDDLULRLRRRUDRURULUDDRULDUDRLDRRLURULRUULLLRUURDURLLULUURUULUUDLUDLRRULLLRRLRURDRRURDRULRURRUDUDDDRDDULDLURUDRDURLDLDLUDURLLRUULLURLDDDURDULRLUUUDLLRRLLUURRDUUDUUDUURURDRRRRRRRRRUDULDLULURUDUURDDULDUDDRDDRDRLRUUUUDLDLRDUURRLRUUDDDDURLRRULURDUUDLUUDUUURUUDRURDRDDDDULRLLRURLRLRDDLRUULLULULRRURURDDUULRDRRDRDLRDRRLDUDDULLDRUDDRRRD"

let part1Code = GetCode puzzleInput [ [' '; ' '; ' '; ' '; ' '];
[' '; '1'; '2'; '3'; ' '];
[' '; '4'; '5'; '6'; ' '];
[' '; '7'; '8'; '9'; ' '];
[' '; ' '; ' '; ' '; ' '] ] (2, 2)

let part2Code = GetCode puzzleInput [ [' '; ' '; ' '; ' '; ' '; ' '; ' '];
[' '; ' '; ' '; '1'; ' '; ' '; ' '];
[' '; ' '; '2'; '3'; '4'; ' '; ' '];
[' '; '5'; '6'; '7'; '8'; '9'; ' '];
[' '; ' '; 'A'; 'B'; 'C'; ' '; ' '];
[' '; ' '; ' '; 'D'; ' '; ' '; ' '];
[' '; ' '; ' '; ' '; ' '; ' '; ' ']] (3, 1)

printfn "Part 1: %A, Part 2: %A" part1Code part2Code
``````

This code yields the correct answers required by the challenge. The problem is I think it is too verbose (I’m doing this to learn clean code) and honestly I think there must be a better way to do most things that I haven’t considered. Feedback on how to shorten (DRY) this code and to make it more readable is appreciated.

Solution

As a late review I have the following comments:

`````` let getLastElementOf seq = seq |> List.rev |> List.head
``````

What’s wrong with `seq |> List.last`?

You use a lot of `fst` and `snd` to reach tuple values, instead you could do:

`````` let validate (x, y) fallbackPos (tdarr:List<List<char>>)  =
try
if tdarr.[x].[y] <> ' '  //I'm using ' ' as a padding
then (x, y)
else fallbackPos
with
| e -> fallbackPos
``````

To me it is much cleaner.

IMO the type definition of Instructions do more damage than good resulting in an unnecessary double match in `parse` and `followOne`.

I think it’s a good idea to extent the keypad and use it for validation of a step.

My solution would be something like below. The concept is to think of the keypad as a coordinate system and then convert the result point of each instruction sequence to a key in the pad:

``````module Program
open System

let squarePad = [[' '; ' '; ' '; ' '; ' '];
[' '; '1'; '2'; '3'; ' '];
[' '; '4'; '5'; '6'; ' '];
[' '; '7'; '8'; '9'; ' '];
[' '; ' '; ' '; ' '; ' '] ]

let diamondPad = [[' '; ' '; ' '; ' '; ' '; ' '; ' '];
[' '; ' '; ' '; '1'; ' '; ' '; ' '];
[' '; ' '; '2'; '3'; '4'; ' '; ' '];
[' '; '5'; '6'; '7'; '8'; '9'; ' '];
[' '; ' '; 'A'; 'B'; 'C'; ' '; ' '];
[' '; ' '; ' '; 'D'; ' '; ' '; ' '];
[' '; ' '; ' '; ' '; ' '; ' '; ' ']]

let isValid (pad: char list list) = fun x y -> pad.[y].[x] <> ' '   // Checks if a field in the keypad has a value
let toKey (pad: char list list) = fun (x, y) -> pad.[y].[x]         // Converts a coordinate set to the key in the pad

// The main function for the pad walk
let doTheWalk (input: string) (pos: int * int) isValid toKey  =
// Move or hold according to the validation of the new position
let move (x, y) instr =
let x1, y1 = match instr with
| 'L' -> x - 1, y
| 'R' -> x + 1, y
| 'U' -> x, y - 1
| 'D' -> x, y + 1
| _ -> x, y // Ignoring what ever invalid input
match isValid x1 y1 with
| true -> x1, y1
| false -> x, y

// Accumulating the resulting position through an instruction sequence
let parse pos instr =
let result = instr |> Seq.fold move pos
result, result // The result of the move is both the current accumulated state and the current mapping result

// The input is considered to be a string with line breaks defining each instruction sequence
input.Split('n')
|> Seq.mapFold (fun curPos instr -> instr |> parse curPos) pos // Maps each char in an instruction line to a new position with the "folded" position from the previous instruction as base
|> fst // Use the sequence of points calculated in the mapFold above to...
|> Seq.mapFold(fun str pos -> str, sprintf "%s%c" str (toKey pos)) "" // ... convert to a key in the pad and finally concat them to a string
|> snd // Returns the folded string with end key for each instruction line

// Starter function
let doMySolution input =

let squareResult =
doTheWalk
input (2, 2)

let diamondResult =
doTheWalk
input (3, 1)

printfn "Square: %AtDiamond: %A" squareResult diamondResult

[<EntryPoint>]
let main argv =

let input = "ULLnRRDDDnLURDLnUUUUD"
let puzzleInput = "DLUUULUDLRDDLLLUDULLULLRUURURLUULDUUUDLDDRUDLUULLRLDDURURDDRDRDLDURRURDLDUURULDDULDRDDLDLDLRDRUURLDLUDDDURULRLLLLRLULLUDRDLDUURDURULULULRLULLLULURLRDRDDDDDDDLRLULUULLULURLLDLRLUDULLDLLURUDDLDULDLULDDRLRLRDDLRURLLLURRLDURRDLLUUUUDRURUULRLDRRULLRUDLDRLUDRDRDRRDDURURRDRDRUDURDLUDRUDLRRULDLRDDRURDDUUDLDRDULDDRRURLLULRDRURLRLDLLLUULUUDLUDLDRRRRDUURULDUDUDRLDLLULLLRDDDDDLRDDLLUULLRRRDURLRURDURURLUDRRLRURDRDRRRRULUDLDRDULULRUDULLLUDRRLRLURDDURULDUUDULLURUULRDRDULRUUUDURURDDRRUDURRLRDRULRUUUn"
+ "LDRURRUUUULDRDDDLLULDRUDDRLLDLDRDLRUDDDLDDULULULLRULDUDRRDLRUURURDRURURDLLRUURDUUDRLDURDRDLRRURURDUUUURUURRLLLDRDUURRRRURULUUUDLUDDRUURRLDULRDULRRRRUDURRLURULRURRDRDLLDRRDUDRDURLDDRURULDRURUDDURDLLLUURRLDRULLURDRDRLDRRURRLRRRDDDDLUDLUDLLDURDURRDUDDLUDLRULRRRDRDDLUDRDURDRDDUURDULRRULDLDLLUDRDDUDUULUDURDRLDURLRRDLDDLURUDRLDUURLLRLUDLLRLDDUDLLLRRRLDLUULLUDRUUDRLDUUUDUURLRDDDDRRDRLDDRDLUDRULDDDRDUULLUUUUULDULRLLLRLLDULRDUDDRDDLRRLRDDULLDURRRURDDUDUDDRLURRLUUUULLDRDULUUDRDULDLLUDLURDLLURRDLUULURRULRLURRRRRUURDDURLRLLDDLRRDUUURDRDUDRDDDLLDDRDRRRLURRDUULULULULRRURDDLDDLLLRUDDDDDDLLLRDULURULLRLRDRRn"
+ "DDRLLLDLRRURRDLDDRUURRURRLRRRRUURUURDLURRRDDLRUDRURLUURLLRRLRLURLURURDULLLLDLRURULUUDURRLULRDRDRRDDLLULRLUDLUUUDRLLRRURRLDULDDLRRLUUUUDDLRLDRLRRDRDLDDURDDRDDLDLURLRRRDDUDLLRLRLURRRRULLULLLLDRLDULDLLDULRLDRDLDDRRDDDDRUDRLLURULRLDDLLRRURURDDRLLLULLULDDRDLDDDLRLLDRLDRUURRULURDDRLULLDUURRULURUUDULLRUDDRRLLDLLRDRUDDDDLLLDDDLLUUUULLDUUURULRUUDUUUDDLDURLDRDRRLLUDULDLUDRLLLDRRRULUUDDURUDRLUDDRRLLDUDUURDDRURLUURDURURURRUUDUDDLLLDRRRURURRURDLRULLDUDRLRLLRUDRUDLRn"
+ "RRRDRLRURLRRLUURDRLDUURURLRDRRUDLLUUDURULLUURDLLDRRLURRUDUUDRRURLRRDULLDDLRRRUDUUDUUDLDDDLUUDLDULDDULLDUUUUDDUUDUDULLDDURRDLRRUDUDLRDUULDULRURRRLDLLURUDLDDDRRLRDURDLRRLLLRUDLUDRLLLRLLRRURUDLUDURLDRLRUDLRUULDRULLRLDRDRRLDDDURRRUDDDUDRRDRLDDRDRLLRLLRDLRDUDURURRLLULRDRLRDDRUULRDDRLULDLULURDLRUDRRDDDLDULULRDDRUDRLRDDRLDRDDRRRDUURDRLLDDUULRLLLULLDRDUDRRLUUURLDULUUURULLRLUDLDDLRRDLLRDDLRDRUUDURDDLLLDUUULUUDLULDUDULDRLRUDDURLDDRRRDLURRLLRRRUDDLDDRURDUULRUURDRRURURRRUUDUDULUDLUDLLLUUUULRLLRRRRDUDRRDRUDURLUDDLDRDLDDRULLRRULDURULn"
+ "DLLLRDDURDULRRLULURRDULDLUDLURDDURRLLRRLLULRDLDRDULRLLRDRUUULURRRLLRLDDDRDRRULDRRLLLLDLUULRRRURDDRULLULDDDLULRLRRRUDRURULUDDRULDUDRLDRRLURULRUULLLRUURDURLLULUURUULUUDLUDLRRULLLRRLRURDRRURDRULRURRUDUDDDRDDULDLURUDRDURLDLDLUDURLLRUULLURLDDDURDULRLUUUDLLRRLLUURRDUUDUUDUURURDRRRRRRRRRUDULDLULURUDUURDDULDUDDRDDRDRLRUUUUDLDLRDUURRLRUUDDDDURLRRULURDUUDLUUDUUURUUDRURDRDDDDULRLLRURLRLRDDLRUULLULULRRURURDDUULRDRRDRDLRDRRLDUDDULLDRUDDRRRD"

doMySolution input

printfn "END"
0
``````

That was a fun exercise. Sorry if this isn’t much help, but I’ll post my approach here, since it at least has the advantage of being contrasting. It’s late afternoon, and I didn’t feel like thinking, so I thought I’d let the type system do the work.

In order to do that, I first defined these types:

``````type Instruction = Up | Down | Left | Right

type Key = One | Two | Three | Four | Five | Six | Seven | Eight | Nine
``````

The reason for that is that I could now define a function with the type `Key -> Instruction -> Key` using pattern matching without having to think hard about the problem. Not only that, but I get compile-time checking that I’ve handled all possible combinations:

``````// Key -> Instruction -> Key
let nextKey current instruction =
match current, instruction with
| One, Up      -> One
| One, Down    -> Four
| One, Left    -> One
| One, Right   -> Two
| Two, Up      -> Two
| Two, Down    -> Five
| Two, Left    -> One
| Two, Right   -> Three
| Three, Up    -> Three
| Three, Down  -> Six
| Three, Left  -> Two
| Three, Right -> Three
| Four, Up     -> One
| Four, Down   -> Seven
| Four, Left   -> Four
| Four, Right  -> Five
| Five, Up     -> Two
| Five, Down   -> Eight
| Five, Left   -> Four
| Five, Right  -> Six
| Six, Up      -> Three
| Six, Down    -> Nine
| Six, Left    -> Five
| Six, Right   -> Six
| Seven, Up    -> Four
| Seven, Down  -> Seven
| Seven, Left  -> Seven
| Seven, Right -> Eight
| Eight, Up    -> Five
| Eight, Down  -> Eight
| Eight, Left  -> Seven
| Eight, Right -> Nine
| Nine, Up     -> Six
| Nine, Down   -> Nine
| Nine, Left   -> Eight
| Nine, Right  -> Nine
``````

Okay, so it’s a little verbose, but it was trivial to write. It also included the benefit that I got to write `Seven, Up` as part of a regular piece of code ðŸ˜‰

Assuming that I’m going to read in my instructions text file and split it on newlines, I’ll first write a function that finds the ultimate key by following the instructions from a previous key:

``````// Key -> seq<Instruction> -> Key
let follow startValue = Seq.fold nextKey startValue
``````

This is simply a left fold over a sequence of `Instruction` values, using `nextKey` as the aggregator.

Likewise, you can `scan` an array of lines using the `follow` function:

``````// #seq<Instruction> [] -> Key []
let followAll instructions = instructions |> Array.scan follow Five |> Array.tail
``````

This functions takes an array of `Instruction` sequences (one for each line), and `scan`s it using the `follow` function for each line, using `Five` as the initial seed.

Since `Array.scan` also returns the initial state (`Five`), the function only returns the tail.

Finally, you’ll need to parse the input string:

``````// char -> Instruction
let parseChar = function
| 'U' -> Up
| 'D' -> Down
| 'L' -> Left
| 'R' -> Right
| c   -> invalidArg "arg1" (sprintf "Unexpected character: %c." c)

// string -> seq<Instruction> []
let parse (s : string) =
let lines = s.Split [|'n'|]
Array.map (Seq.map parseChar) lines
``````

The `parseChar` function throws an exception if the character isn’t one of `'U'`, `'D'`, `'L'`, or `'R'`. It’d be more functional to return either a Maybe (`option`) or an Either value, but for a single-use script I thought this was okay.

You can now take your input string and compose it with `parse` and `followAll`, like this:

``````input |> parse |> followAll
``````

This expression returns an array of `Key` values. I’ll leave it as an exercise to translate back to a string of numbers, if that’s required.