-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDay08.roc
154 lines (110 loc) · 3.59 KB
/
Day08.roc
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
143
144
145
146
147
148
149
150
151
152
153
154
interface Day08 exposes [ output ] imports [ TestUtil ]
output : List I64 -> List (List I64)
output = \puzzleInput ->
testCode = parseInput testInput
puzzleCode = parseInput puzzleInput
[ TestUtil.verify 8 1 1 (accBeforeLoop testCode ) 5
, TestUtil.show 8 1 (accBeforeLoop puzzleCode)
, TestUtil.verify 8 2 1 (accAtEnd testCode ) 8
, TestUtil.show 8 2 (accAtEnd puzzleCode)
]
# code instructions
Inst : [ Nop I64, Acc I64, Jmp I64 ]
# find loop in code
accBeforeLoop : List Inst -> I64
accBeforeLoop = \code ->
initial = initialRunState code
final = runUntilLoopOrEnd initial
final.acc
RunState : { length : I64, code: List Inst, ip: I64, acc: I64, visited: List I64 }
initialRunState : List Inst -> RunState
initialRunState = \code ->
length = List.len code
visited = List.repeat length 0
{ length, code, ip: 0, acc:0, visited }
runUntilLoopOrEnd : RunState -> RunState
runUntilLoopOrEnd = \state ->
if state.ip < state.length then
when List.get state.visited state.ip is
Ok 0 ->
newVisited = List.set state.visited state.ip 1
newState = step { state & visited: newVisited }
runUntilLoopOrEnd newState
_ ->
state
else
state
step : RunState -> RunState
step = \state ->
when List.get state.code state.ip is
Ok inst ->
when inst is
Nop _ ->
{ state & ip: state.ip + 1 }
Acc op ->
{ state & ip: state.ip + 1, acc: state.acc + op }
Jmp op ->
{ state & ip: state.ip + op }
_ ->
state
# correct code and run until end
accAtEnd : List Inst -> I64
accAtEnd = \code ->
accAtEndHelper code code 0
accAtEndHelper : List Inst, List Inst, I64 -> I64
accAtEndHelper = \originalCode, codeToExecute, chg ->
initial = initialRunState codeToExecute
final = runUntilLoopOrEnd initial
if final.ip < final.length then
when List.get originalCode chg is
Ok oldInst ->
newInst =
when oldInst is
Nop op -> Jmp op
Jmp op -> Nop op
inst -> inst
newCode = List.set originalCode chg newInst
newChg = chg + 1
accAtEndHelper originalCode newCode newChg
_ ->
-1
else
final.acc
# parse input to code instructions
parseInput : List I64 -> List Inst
parseInput = \input ->
(List.walk input parseWalker initialParseAcc).output
ParseAcc : { inst : I64, sign : I64, op : I64, output : List Inst }
initialParseAcc : ParseAcc
initialParseAcc =
{ inst: 0, sign: 0, op: 0, output: [] }
parseWalker : I64, ParseAcc -> ParseAcc
parseWalker = \val, acc ->
if val == 10 then
instOp = acc.sign * acc.op
parsed =
when acc.inst is
97 -> Acc instOp
106 -> Jmp instOp
_ -> Nop instOp
newOutput = List.append acc.output parsed
{ inst: 0, sign: 0, op: 0, output: newOutput}
else if acc.inst == 0 then
{ acc & inst: val }
else if acc.sign == 0 then
{ acc & sign: if val == 45 then -1 else 1 }
else
{ acc & op: 10 * acc.op + val - 48 }
# test data
testInput : List I64
testInput =
[ 110, 43, 48, 10
, 97, 43, 49, 10
, 106, 43, 52, 10
, 97, 43, 51, 10
, 106, 45, 51, 10
, 97, 45, 57, 57, 10
, 97, 43, 49, 10
, 106, 45, 52, 10
, 97, 43, 54, 10
]