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

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 3x3 numerical grid (1..9). In the second part the keypad is a diamond shaped 5x5 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 =
seq |> List.rev |> List.head

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

let parse (rawInput:string) :List =
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>) =
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>) (pos:int int) (instruction:Instruction) :int int =
validate (match instruction with
| Up -> fst pos - 1 , snd pos
| Down -> fst pos + 1, snd pos
| R

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 -> 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 [] -> Key []
let followAll instructions = instructions |> Array.scan follow Five |> Array.tail

This functions takes an array of Instruction sequences (one for each line), and scans 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 []    
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.

StackExchange Code Review Q#149829, answer score: 2