-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDay09.roc
127 lines (98 loc) · 3.18 KB
/
Day09.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
interface Day09 exposes [ output ] imports [ ListExtra, ListZip, TestUtil ]
output : List I64 -> List (List I64)
output = \puzzleInput ->
testInts = TestUtil.ints testInput
puzzleInts = TestUtil.ints puzzleInput
testInvalid = firstInvalid 5 testInts
puzzleInvalid = firstInvalid 25 puzzleInts
[ TestUtil.verify 9 1 1 testInvalid 127
, TestUtil.show 9 1 puzzleInvalid
, TestUtil.verify 9 2 1 (weakness testInvalid testInts ) 62
, TestUtil.show 9 2 (weakness puzzleInvalid puzzleInts)
]
# first part
firstInvalid : I64, List I64 -> I64
firstInvalid = \len, list ->
start = ListZip.newAtFirst list 0
next = ListZip.moveTo start list len
firstInvalidHelper len list start next
firstInvalidHelper : I64, List I64, ListZip.Zip, ListZip.Zip -> I64
firstInvalidHelper = \len, list, start, next ->
sorted = sortedSubList list start len
subStart = ListZip.newAtFirst sorted 0
subEnd = ListZip.last subStart sorted
if pairExists sorted next.val subStart subEnd then
newStart = ListZip.forward start list
newNext = ListZip.forward next list
firstInvalidHelper len list newStart newNext
else
next.val
pairExists : List I64, I64, ListZip.Zip, ListZip.Zip -> Bool
pairExists = \list, val, start, end ->
sum = start.val + end.val
if sum == val then
True
else if end.idx - start.idx < 2 then
False
else if sum < val then
newStart = ListZip.forward start list
pairExists list val newStart end
else
newEnd = ListZip.backward end list
pairExists list val start newEnd
sortedSubList : List I64, ListZip.Zip, I64 -> List I64
sortedSubList = \list, start, len ->
list |> ListZip.collect start len |> ListExtra.quicksort
# second part
weakness : I64, List I64 -> I64
weakness = \inv, list ->
start = ListZip.newAtFirst list 0
weaknessHelper1 inv list start
weaknessHelper1 : I64, List I64, ListZip.Zip -> I64
weaknessHelper1 = \inv, list, start ->
end = ListZip.forward start list
sum = start.val + end.val
result = weaknessHelper2 inv list start end sum
if result > 0 then
result
else
newStart = ListZip.forward start list
weaknessHelper1 inv list newStart
weaknessHelper2 : I64, List I64, ListZip.Zip, ListZip.Zip, I64 -> I64
weaknessHelper2 = \inv, list, start, end, sum ->
if sum < inv then
newEnd = ListZip.forward end list
newSum = sum + newEnd.val
weaknessHelper2 inv list start newEnd newSum
else if sum > inv then
0
else
len = end.idx - start.idx + 1
sorted = sortedSubList list start len
first = ListZip.newAtFirst sorted 0
last = ListZip.last first sorted
first.val + last.val
# test data
testInput : List I64
testInput =
[ 51, 53, 10
, 50, 48, 10
, 49, 53, 10
, 50, 53, 10
, 52, 55, 10
, 52, 48, 10
, 54, 50, 10
, 53, 53, 10
, 54, 53, 10
, 57, 53, 10
, 49, 48, 50, 10
, 49, 49, 55, 10
, 49, 53, 48, 10
, 49, 56, 50, 10
, 49, 50, 55, 10
, 50, 49, 57, 10
, 50, 57, 57, 10
, 50, 55, 55, 10
, 51, 48, 57, 10
, 53, 55, 54, 10
]