-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day17.fs
142 lines (112 loc) · 3.9 KB
/
Day17.fs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
module aoc23.Day17
type Grid = int array2d
module Grid =
let ofLines (lines: string array) =
lines
|> Array.map (fun line -> line |> Seq.map (fun char -> System.String([| char |]) |> int))
|> array2D
let dimensions grid =
grid |> Array2D.length1, grid |> Array2D.length2
let inBounds (row, col) grid =
row >= 0
&& col >= 0
&& row < (grid |> Array2D.length1)
&& col < (grid |> Array2D.length2)
[<Struct>]
type PossibleDirection =
| Vertical
| Horizontal
[<Struct>]
type Cursor =
{ row: int
col: int
possibleDirection: PossibleDirection
heatLoss: int }
module Cursor =
let possibleMoves minTravel maxTravel grid cursor =
let next3 increase =
(Some cursor, seq { 1..maxTravel })
||> Seq.scan (fun state _ ->
state
|> Option.map increase
|> Option.filter (fun x -> grid |> Grid.inBounds (x.row, x.col))
|> Option.map (fun x ->
{ x with
heatLoss = x.heatLoss + grid[x.row, x.col]
possibleDirection =
match cursor.possibleDirection with
| Vertical -> Horizontal
| Horizontal -> Vertical }))
|> Seq.skip minTravel
seq {
match cursor.possibleDirection with
| Horizontal ->
yield! next3 (fun c -> { c with col = c.col + 1 })
yield! next3 (fun c -> { c with col = c.col - 1 })
| Vertical ->
yield! next3 (fun c -> { c with row = c.row + 1 })
yield! next3 (fun c -> { c with row = c.row - 1 })
}
|> Seq.choose id
let key cursor =
struct (cursor.row, cursor.col, cursor.possibleDirection)
let solve minTravel maxTravel lines =
let grid = Grid.ofLines lines
let startCursor1 =
{ row = 0
col = 0
possibleDirection = Vertical
heatLoss = 0 }
let startCursor2 =
{ startCursor1 with
possibleDirection = Horizontal }
let rec nextRank previous current =
let allNext = current |> Seq.collect (Cursor.possibleMoves minTravel maxTravel grid)
let chosenNext =
allNext
|> Seq.groupBy Cursor.key
|> Seq.map (fun (_g, cursors) -> cursors |> Seq.minBy _.heatLoss)
|> Seq.filter (fun cur ->
previous
|> Map.tryFind (cur |> Cursor.key)
|> Option.map (fun prevLeastHl -> prevLeastHl >= cur.heatLoss)
|> Option.defaultValue true)
|> Seq.toArray
let updatedPrevious =
(previous, chosenNext)
||> Seq.fold (fun map cur -> map |> Map.add (cur |> Cursor.key) cur.heatLoss)
if (chosenNext.Length > 0) then
nextRank updatedPrevious chosenNext
else
previous
let best = nextRank Map.empty [| startCursor1; startCursor2 |]
let rows, cols = grid |> Grid.dimensions
let result1 = best |> Map.find (rows - 1, cols - 1, Vertical)
let result2 = best |> Map.find (rows - 1, cols - 1, Horizontal)
min result1 result2
let part1 lines =
solve 1 3 lines
let part2 lines =
solve 4 10 lines
let run = runReadAllLines part1 part2
module Test =
open Xunit
open Swensen.Unquote
let example =
[| "2413432311323"
"3215453535623"
"3255245654254"
"3446585845452"
"4546657867536"
"1438598798454"
"4457876987766"
"3637877979653"
"4654967986887"
"4564679986453"
"1224686865563"
"2546548887735"
"4322674655533" |]
[<Fact>]
let ``part 1 example`` () = part1 example =! 102
[<Fact>]
let ``part 2 example`` () = part2 example =! 94