aoc2020/Day19.roc at master · pithub/aoc2020 · GitHub

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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
interface Day19 exposes [ output ] imports [ TestUtil ]


output : List I64 -> List (List I64)
output = \puzzleInput ->
    testData1  = parseData testInput1
    testData2  = parseData testInput2
    puzzleData = parseData puzzleInput

    [ TestUtil.verify 19 1 1 (firstResult testData1 ) 2
    , TestUtil.verify 19 1 2 (firstResult testData2 ) 3
    , TestUtil.show   19 1   (firstResult puzzleData)
    , TestUtil.verify 19 2 1 (secondResult testData2 ) 12
    , TestUtil.show   19 2   (secondResult puzzleData)
    ]


#  first part


firstResult : List I64 -> I64
firstResult = \data ->
    countValidMsgs data (getSafe data 0) 0


countValidMsgs : List I64, I64, I64 -> I64
countValidMsgs = \data, msgIdx, cnt ->
    if msgIdx < List.len data then
        newMsgIdx = isValid data msgIdx
        if newMsgIdx > 0 then
            countValidMsgs data (newMsgIdx + 1) (cnt + 1)
        else
            countValidMsgs data (1 - newMsgIdx) cnt
    else
        cnt


isValid : List I64, I64 -> I64
isValid = \data, msgIdx ->
    eom = nextDelimiter data msgIdx
    afterMatch = match data 0 msgIdx
    if afterMatch == eom then
        eom
    else
        -eom


#  second part


#   8: 42     ->  42{n}         n >= 1
#  11: 42 31  ->  42{n} 31{n}   n >= 1
#  ---
#   0: 8 11  =  42 42 31  ->  42{n+m} 31{m}  n, m >= 1


secondResult : List I64 -> I64
secondResult = \data ->
    countValidMsgs2 data (getSafe data 0) 0


countValidMsgs2 : List I64, I64, I64 -> I64
countValidMsgs2 = \data, msgIdx, cnt ->
    if msgIdx < List.len data then
        newMsgIdx = isValid2 data msgIdx
        if newMsgIdx > 0 then
            countValidMsgs2 data (newMsgIdx + 1) (cnt + 1)
        else
            countValidMsgs2 data (1 - newMsgIdx) cnt
    else
        cnt


isValid2 : List I64, I64 -> I64
isValid2 = \data, msgIdx ->
    eom = nextDelimiter data msgIdx

    newMsgIdx = match data 42 msgIdx
    if newMsgIdx > 0 then
        match2 data eom newMsgIdx 0
    else
        -eom


match2 : List I64, I64, I64, I64 -> I64
match2 = \data, eom, msgIdx, sufLen ->
    newMsgIdx1 = match data 42 msgIdx
    if newMsgIdx1 > 0 then
        newMsgIdx2 = match data 31 newMsgIdx1
        if newMsgIdx2 > 0 then
            afterMatch = matchSuffix data eom newMsgIdx2 sufLen
            if afterMatch == eom then
                eom
            else
                match2 data eom newMsgIdx1 (sufLen + 1)
        else
            match2 data eom newMsgIdx1 (sufLen + 1)
    else
        -eom


matchSuffix : List I64, I64, I64, I64 -> I64
matchSuffix = \data, eom, msgIdx, cnt ->
    if msgIdx == eom then
        eom
    else if cnt > 0 then
        newMsgIdx = match data 31 msgIdx
        if newMsgIdx > 0 then
            matchSuffix data eom newMsgIdx (cnt - 1)
        else
            -eom
    else
        -eom


#  util


match : List I64, I64, I64 -> I64
match = \data, ruleNum, msgIdx ->
    ruleIdx = getSafe data (ruleNum + 1)
    when getSafe data ruleIdx is
        -34 -> matchChar data (ruleIdx + 1) msgIdx
        -58 -> matchSequence data (ruleIdx + 1) msgIdx
        -124 -> matchAlternative data (ruleIdx + 1) msgIdx
        _ -> -msgIdx


matchChar : List I64, I64, I64 -> I64
matchChar = \data, ruleIdx, msgIdx ->
    if getSafe data msgIdx == getSafe data ruleIdx then
        msgIdx + 1
    else
        -msgIdx


matchSequence : List I64, I64, I64 -> I64
matchSequence = \data, ruleIdx, msgIdx ->
    ruleNum = getSafe data ruleIdx
    if ruleNum < 0 then
        msgIdx
    else
        newMsgIdx = match data ruleNum msgIdx
        if newMsgIdx > 0 then
            matchSequence data (ruleIdx + 1) newMsgIdx
        else
            newMsgIdx


matchAlternative : List I64, I64, I64 -> I64
matchAlternative = \data, ruleIdx, msgIdx ->
    newMsgIdx = matchSequence data ruleIdx msgIdx
    if newMsgIdx > 0 then
        newMsgIdx
    else
        newRuleIdx = nextDelimiter data ruleIdx
        if getSafe data newRuleIdx == -124 then
            matchAlternative data (newRuleIdx + 1) msgIdx
        else
            -newRuleIdx


nextDelimiter : List I64, I64 -> I64
nextDelimiter = \data, idx ->
    if getSafe data idx < 0 then
        idx
    else
        nextDelimiter data (idx + 1)


getSafe : List I64, I64 -> I64
getSafe = \list, idx ->
    when List.get list idx is
        Ok val -> val
        _ -> -1


#  parser


parseData : List I64 -> List I64
parseData = \input ->
    parseDataHelper input 0 0 [] 0 []


parseDataHelper : List I64, I64, I64, List I64, I64, List I64 -> List I64
parseDataHelper = \input, idx, num, indexes, start, result ->
    when List.get input idx is
        Ok val ->
            #  new input index
            newIdx = idx + 1

            if 48 <= val && val <= 57 then
                #  add digit to num
                newNum = num * 10 + val - 48
                parseDataHelper input newIdx newNum indexes start result

            else
                #  determine rulesToMessages switch
                rulesToMessages =
                    if val == 10 && List.len result == start then
                        1
                    else
                        0

                #  new rule indexes
                newIndexes =
                    if val == 58 then
                        setSafe indexes num start
                    else
                        indexes

                #  prepend message and rule indexes
                newResult1 =
                    if rulesToMessages > 0 then
                        increase = List.len newIndexes + 1
                        prepend = List.map newIndexes (\i -> i + increase)
                        List.join [ [ increase + List.len result ], prepend, result ]
                    else
                        result

                #  append num if set
                newResult2 =
                    if num > 0 && val != 58 then
                        List.append newResult1 num
                    else
                        newResult1

                #  append val
                newResult3 =
                    if val == 32 || val == 34 || (val == 10 && rulesToMessages > 0) then
                        newResult2
                    else if val == 10 || val == 58 || val == 124 then
                        List.append newResult2 -val
                    else
                        List.append newResult2 val

                #  set rule type
                newResult4 =
                    if val == 34 || val == 124 then
                        List.set newResult3 start -val
                    else
                        newResult3

                #  new start
                newStart =
                    if val == 10 then
                        List.len newResult4
                    else
                        start

                #  recurse with num == 0
                parseDataHelper input newIdx 0 newIndexes newStart newResult4

        _ ->
            #  add final lf
            List.append result -10


setSafe : List I64, I64, I64 -> List I64
setSafe = \list, idx, val ->
    add = idx - List.len list
    if add < 0 then
        List.set list idx val
    else if add > 0 then
        List.join [ list, List.repeat add 0, [ val ] ]
    else
        List.append list val


#  test data


testInput1 : List I64
testInput1 =
    [ 48, 58, 32, 52, 32, 49, 32, 53, 10
    , 49, 58, 32, 50, 32, 51, 32, 124, 32, 51, 32, 50, 10
    , 50, 58, 32, 52, 32, 52, 32, 124, 32, 53, 32, 53, 10
    , 51, 58, 32, 52, 32, 53, 32, 124, 32, 53, 32, 52, 10
    , 52, 58, 32, 34, 97, 34, 10
    , 53, 58, 32, 34, 98, 34, 10
    , 10
    , 97, 98, 97, 98, 98, 98, 10
    , 98, 97, 98, 97, 98, 97, 10
    , 97, 98, 98, 98, 97, 98, 10
    , 97, 97, 97, 98, 98, 98, 10
    , 97, 97, 97, 97, 98, 98, 98
    ]


testInput2 : List I64
testInput2 =
    [ 52, 50, 58, 32, 57, 32, 49, 52, 32, 124, 32, 49, 48, 32, 49, 10
    , 57, 58, 32, 49, 52, 32, 50, 55, 32, 124, 32, 49, 32, 50, 54, 10
    , 49, 48, 58, 32, 50, 51, 32, 49, 52, 32, 124, 32, 50, 56, 32, 49, 10
    , 49, 58, 32, 34, 97, 34, 10
    , 49, 49, 58, 32, 52, 50, 32, 51, 49, 10
    , 53, 58, 32, 49, 32, 49, 52, 32, 124, 32, 49, 53, 32, 49, 10
    , 49, 57, 58, 32, 49, 52, 32, 49, 32, 124, 32, 49, 52, 32, 49, 52, 10
    , 49, 50, 58, 32, 50, 52, 32, 49, 52, 32, 124, 32, 49, 57, 32, 49, 10
    , 49, 54, 58, 32, 49, 53, 32, 49, 32, 124, 32, 49, 52, 32, 49, 52, 10
    , 51, 49, 58, 32, 49, 52, 32, 49, 55, 32, 124, 32, 49, 32, 49, 51, 10
    , 54, 58, 32, 49, 52, 32, 49, 52, 32, 124, 32, 49, 32, 49, 52, 10
    , 50, 58, 32, 49, 32, 50, 52, 32, 124, 32, 49, 52, 32, 52, 10
    , 48, 58, 32, 56, 32, 49, 49, 10
    , 49, 51, 58, 32, 49, 52, 32, 51, 32, 124, 32, 49, 32, 49, 50, 10
    , 49, 53, 58, 32, 49, 32, 124, 32, 49, 52, 10
    , 49, 55, 58, 32, 49, 52, 32, 50, 32, 124, 32, 49, 32, 55, 10
    , 50, 51, 58, 32, 50, 53, 32, 49, 32, 124, 32, 50, 50, 32, 49, 52, 10
    , 50, 56, 58, 32, 49, 54, 32, 49, 10
    , 52, 58, 32, 49, 32, 49, 10
    , 50, 48, 58, 32, 49, 52, 32, 49, 52, 32, 124, 32, 49, 32, 49, 53, 10
    , 51, 58, 32, 53, 32, 49, 52, 32, 124, 32, 49, 54, 32, 49, 10
    , 50, 55, 58, 32, 49, 32, 54, 32, 124, 32, 49, 52, 32, 49, 56, 10
    , 49, 52, 58, 32, 34, 98, 34, 10
    , 50, 49, 58, 32, 49, 52, 32, 49, 32, 124, 32, 49, 32, 49, 52, 10
    , 50, 53, 58, 32, 49, 32, 49, 32, 124, 32, 49, 32, 49, 52, 10
    , 50, 50, 58, 32, 49, 52, 32, 49, 52, 10
    , 56, 58, 32, 52, 50, 10
    , 50, 54, 58, 32, 49, 52, 32, 50, 50, 32, 124, 32, 49, 32, 50, 48, 10
    , 49, 56, 58, 32, 49, 53, 32, 49, 53, 10
    , 55, 58, 32, 49, 52, 32, 53, 32, 124, 32, 49, 32, 50, 49, 10
    , 50, 52, 58, 32, 49, 52, 32, 49, 10
    , 10
    , 97, 98, 98, 98, 98, 98, 97, 98, 98, 98, 97, 97, 97, 97, 98, 97, 98, 98, 97, 97, 98, 98, 98, 98, 97, 98, 97, 98, 97, 98, 98, 98, 97, 98, 98, 98, 98, 98, 98, 97, 98, 97, 97, 97, 97, 10
    , 98, 98, 97, 98, 98, 98, 98, 97, 97, 98, 97, 97, 98, 98, 97, 10
    , 98, 97, 98, 98, 98, 98, 97, 97, 98, 98, 98, 98, 98, 97, 98, 98, 98, 98, 98, 98, 97, 97, 98, 97, 97, 97, 98, 97, 97, 97, 10
    , 97, 97, 97, 98, 98, 98, 98, 98, 98, 97, 97, 97, 97, 98, 97, 97, 98, 97, 98, 97, 97, 98, 97, 98, 97, 98, 98, 97, 98, 97, 97, 97, 98, 98, 97, 98, 97, 98, 97, 98, 97, 98, 97, 97, 97, 10
    , 98, 98, 98, 98, 98, 98, 98, 97, 97, 97, 97, 98, 98, 98, 98, 97, 97, 97, 98, 98, 97, 98, 97, 97, 97, 10
    , 98, 98, 98, 97, 98, 97, 98, 98, 98, 98, 97, 97, 97, 97, 97, 97, 97, 97, 98, 98, 97, 98, 97, 98, 97, 97, 97, 98, 97, 98, 97, 97, 98, 97, 98, 10
    , 97, 98, 97, 98, 97, 97, 97, 97, 97, 97, 98, 97, 97, 97, 98, 10
    , 97, 98, 97, 98, 97, 97, 97, 97, 97, 98, 98, 98, 97, 98, 97, 10
    , 98, 97, 97, 98, 98, 97, 97, 97, 97, 98, 98, 97, 97, 97, 97, 98, 97, 98, 98, 97, 97, 98, 97, 98, 98, 10
    , 97, 98, 98, 98, 98, 97, 98, 98, 98, 98, 97, 97, 97, 97, 98, 97, 98, 98, 98, 98, 98, 98, 97, 97, 97, 97, 98, 97, 98, 98, 10
    , 97, 97, 97, 97, 97, 98, 98, 97, 97, 98, 97, 97, 97, 97, 97, 98, 97, 98, 97, 97, 10
    , 97, 97, 97, 97, 98, 98, 97, 97, 97, 97, 98, 98, 97, 97, 97, 10
    , 97, 97, 97, 97, 98, 98, 97, 97, 98, 98, 97, 97, 97, 97, 97, 97, 97, 98, 98, 98, 97, 98, 98, 98, 97, 97, 97, 98, 98, 97, 97, 98, 97, 97, 97, 10
    , 98, 97, 98, 97, 97, 97, 98, 98, 98, 97, 97, 97, 98, 97, 97, 98, 97, 98, 98, 97, 97, 98, 97, 98, 97, 98, 97, 97, 97, 98, 10
    , 97, 97, 98, 98, 98, 98, 98, 97, 97, 98, 98, 98, 97, 97, 97, 97, 97, 97, 98, 98, 98, 98, 98, 97, 98, 97, 98, 97, 97, 97, 97, 97, 98, 98, 97, 97, 97, 98, 98, 97
    ]