type
AOCSolution[T,U] = tuple[part1: T, part2: U]
Vec3 = tuple[x,y,z: int]
Node = ref object
pos: Vec3
cid: int
proc dist(a,b: Vec3): float =
sqrt(float((a.x-b.x)^2 + (a.y-b.y)^2 + (a.z-b.z)^2))
proc solve(input: string, p1_limit: int): AOCSolution[int, int] =
let boxes = input.splitLines().mapIt:
let parts = it.split(',')
let pos = Vec3 (parseInt parts[0], parseInt parts[1], parseInt parts[2])
Node(pos: pos, cid: -1)
var dists: seq[(float, (Node, Node))]
for i in 0 .. boxes.high - 1:
for j in i+1 .. boxes.high:
dists.add (dist(boxes[i].pos, boxes[j].pos), (boxes[i], boxes[j]))
var curcuits: Table[int, HashSet[Node]]
var curcuitID = 0
dists.sort(cmp = proc(a,b: (float, (Node, Node))): int = cmp(a[0], b[0]))
for ind, (d, nodes) in dists:
var (a, b) = nodes
let (acid, bcid) = (a.cid, b.cid)
if acid == -1 and bcid == -1: # new curcuit
a.cid = curcuitID
b.cid = curcuitID
curcuits[curcuitId] = [a, b].toHashSet
inc curcuitID
elif bcid == -1: # add to a
b.cid = acid
curcuits[acid].incl b
elif acid == -1: # add to b
a.cid = bcid
curcuits[bcid].incl a
elif acid != bcid: # merge two curcuits
for node in curcuits[bcid]:
node.cid = acid
curcuits[acid].incl curcuits[bcid]
curcuits.del bcid
if ind+1 == p1_limit:
result.part1 = curcuits.values.toseq.map(len).sorted()[^3..^1].prod
if not(acid == bcid and acid != -1): result.part2 = a.pos.x * b.pos.x
:::
Runtime: 364 ms
Part 1:
I compute all pairs of Euclidean distances between 3D points, sort them, then connect points into circuits, using, what I think is called a Union‑Find algorithm (circuits grow or merge). After exactly 1000 connections (including redundant ones), I take the three largest circuits and multiply their sizes.
Part 2:
While iterating through the sorted connections, I also calculate the product of each pair x‑coordinates. The last product is a result for part 2.
Problems I encountered while doing this puzzle:
I've changed a dozen of data structures, before settled on curcuitIDs and ref objects stored in a HashTable (~ 40 min)
I did a silly mistake of mutating the fields of an object and then using new fields as keys for the HashTable (~ 20 min)
I am stil confused and don't understand why do elves count already connected junction boxes (~ 40 min, had to look it up, otherwise it would be a lot more)
Time to solve Part 1: 1 hour 56 minutes
Time to solve Part 2: 4 minutes
Part 1: count each time a beam crosses a splitter.
Part 2: keep count of how many particles are in each column in all universes
(e.g. with a simple 1d array), then sum.
Runtime: 116 μs95 µs 86 µs
::: spoiler old version
type
AOCSolution[T,U] = tuple[part1: T, part2: U]
proc solve(input: string): AOCSolution[int, int] =
var beams = newSeq[int](input.find '\n')
beams[input.find 'S'] = 1
for line in input.splitLines():
var newBeams = newSeq[int](beams.len)
for pos, cnt in beams:
if cnt == 0: continue
if line[pos] == '^':
newBeams[pos-1] += cnt
newBeams[pos+1] += cnt
inc result.part1
else:
newbeams[pos] += cnt
beams = newBeams
result.part2 = beams.sum()
:::
Update: found even smaller and faster version that only needs a single array.
Update #2: small optimization
type
AOCSolution[T,U] = tuple[part1: T, part2: U]
proc solve(input: string): AOCSolution[int, int] =
var beams = newSeq[int](input.find '\n')
beams[input.find 'S'] = 1
for line in input.splitLines():
for pos, c in line:
if c == '^' and beams[pos] > 0:
inc result.part1
beams[pos-1] += beams[pos]
beams[pos+1] += beams[pos]
beams[pos] = 0
result.part2 = beams.sum()
The hardest part was reading the part 2 description. I literally looked at it for minutes trying to understand where the problem numbers come from and how they're related to the example input. But then it clicked.
The next roadblock was that my template was stripping whitespace at the end of the last line, making parsing a lot harder. I've replaced strip() with strip(chars={'\n'}) to keep the trailing space intact.
Runtime: 1.4 ms 618 μs
::: spoiler view code
type
AOCSolution[T,U] = tuple[part1: T, part2: U]
proc solve(input: string): AOCSolution[int, int] =
let lines = input.splitLines()
let numbers = lines[0..^2]
let ops = lines[^1]
block p1:
let numbers = numbers.mapIt(it.splitWhiteSpace().mapIt(parseInt it))
let ops = ops.splitWhitespace()
for x in 0 .. numbers[0].high:
var res = numbers[0][x]
for y in 1 .. numbers.high:
case ops[x]
of "*": res *= numbers[y][x]
of "+": res += numbers[y][x]
result.part1 += res
block p2:
var problems: seq[(char, Slice[int])]
var ind = 0
while ind < ops.len:
let len = ops.skipWhile({' '}, ind+1)
problems.add (ops[ind], ind .. ind + len - (if ind+len < ops.high: 1 else: 0))
ind += len + 1
for (op, cols) in problems:
var res = 0
for x in cols:
var num = ""
for y in 0 .. numbers.high:
num &= numbers[y][x]
if res == 0:
res = parseInt num.strip
else:
case op
of '*': res *= parseInt num.strip
of '+': res += parseInt num.strip
else: discard
result.part2 += res
Huh, I didn't expect two easy days in a row.
Part 1 is a range check. Part 2 is a range merge.
Runtime: ~720 µs
type
AOCSolution[T,U] = tuple[part1: T, part2: U]
proc merge[T](ranges: var seq[Slice[T]]) =
ranges.sort(cmp = proc(r1, r2: Slice[T]): int = cmp(r1.a, r2.a))
var merged = @[ranges[0]]
for range in ranges.toOpenArray(1, ranges.high):
if range.a <= merged[^1].b:
if range.b > merged[^1].b:
merged[^1].b = range.b
else:
merged.add range
ranges = merged
proc solve(input: string): AOCSolution[int, int] =
let chunks = input.split("\n\n")
var freshRanges = chunks[0].splitLines().mapIt:
let t = it.split('-'); t[0].parseInt .. t[1].parseInt
freshRanges.merge()
block p1:
let availableFood = chunks[1].splitLines().mapIt(parseInt it)
for food in availableFood:
for range in freshRanges:
if food in range:
inc result.part1
break
block p2:
for range in freshRanges:
result.part2 += range.b-range.a+1
type
AOCSolution[T,U] = tuple[part1: T, part2: U]
Vec2 = tuple[x,y: int]
proc removePaper(rolls: var seq[string]): int =
var toRemove: seq[Vec2]
for y, line in rolls:
for x, c in line:
if c != '@': continue
var adjacent = 0
for (dx, dy) in [(-1,-1),(0,-1),(1,-1),
(-1, 0), (1, 0),
(-1, 1),(0, 1),(1, 1)]:
let pos: Vec2 = (x+dx, y+dy)
if pos.x < 0 or pos.x >= rolls[0].len or
pos.y < 0 or pos.y >= rolls.len: continue
if rolls[pos.y][pos.x] == '@': inc adjacent
if adjacent < 4:
inc result
toRemove.add (x, y)
for (x, y) in toRemove: rolls[y][x] = '.'
proc solve(input: string): AOCSolution[int, int] =
var rolls = input.splitLines()
result.part1 = rolls.removePaper()
result.part2 = result.part1
while (let cnt = rolls.removePaper(); result.part2 += cnt; cnt) > 0:
discard
Today was so easy, that I decided to solve it twice, just for fun. First is a 2D traversal (see above). And then I did a node graph solution in a few minutes (in repo below). Both run in ~27 ms.
It's a bit concerning, because a simple puzzle can only mean that tomorrow will be a nightmare.
Good Luck everyone, we will need it.
type
AOCSolution[T,U] = tuple[part1: T, part2: U]
proc maxJoltage(bank: string, n: int): int =
var index = 0
for leftover in countDown(n-1, 0):
var best = bank[index]
for batteryInd in index+1 .. bank.high-leftover:
let batt = bank[batteryInd]
if batt > best: (best = batt; index = batteryInd)
if best == '9': break # max for single battery
result += (best.ord - '0'.ord) * 10^leftover
inc index
proc solve(input: string): AOCSolution[int, int] =
for line in input.splitLines:
result.part1 += line.maxJoltage 2
result.part2 += line.maxJoltage 12
Runtime: ~240 μs
Day 3 was very straightforward, although I did wrestle a bit with the indexing.
Honestly, I expected part 2 to require dynamic programming, but it turned out I only needed to tweak a few numbers in my part 1 code.
Easy one today. Part 2 is pretty forgiving on performance, so regex bruteforce was only a couple seconds . But eventually I've cleaned it up and did a solution that runs in ~340 ms.
type
AOCSolution[T,U] = tuple[part1: T, part2: U]
proc isRepeating(str:string, sectorLength=1): bool =
if str.len mod sectorLength != 0: return false
for i in countUp(0, str.len - sectorLength, sectorLength):
if str.toOpenArray(i, i+sectorLength-1) != str.toOpenArray(0, sectorLength-1):
return false
true
proc solve(input: string): AOCSolution[int, int] =
let ranges = input.split(',').mapIt:
let parts = it.split('-')
(parseInt parts[0], parseInt parts[1])
for (a, b) in ranges:
for num in a .. b:
if num < 10: continue
let strnum = $num
let half = strnum.len div 2
for i in countDown(half, 1):
if strnum.isRepeating(i):
if i == half and strnum.len mod 2 == 0:
result.part1 += num
result.part2 += num
break
That was the rough first day for me. Part 1 was ok.
For part 2 I didn't want to go the easy route, so I was trying to find simple formulaic solution, but my answer was always off by some amount. And debugging was hard, because I I was getting the right answer for example input.
After 40 minutes I wiped everything clean and wrote a bruteforce.
Later that day I returned and solved this one properly. I had to draw many schemes and consider all the edge cases carefully to come up with code below.
type
AOCSolution[T,U] = tuple[part1: T, part2: U]
proc solve(input: string): AOCSolution[int, int] =
var dial = 50
for line in input.splitLines():
let value = parseInt(line[1..^1])
let sign = if line[0] == 'L': -1 else: 1
let offset = value mod 100
result.part2 += value div 100
if dial != 0:
if sign < 0 and offset >= dial or
sign > 0 and offset >= (100-dial): inc result.part2
dial = (dial + offset * sign).euclmod(100)
if dial == 0: inc result.part1
I didn't want to dismiss it. For what I see, it's probably a really fun and complex strategy.
It's just that retro board games are on a whole another level of "complex" and I doubt we will ever get close to with the modern stuff.
For TCS - you have literally control of around hundred of space ships that each can hold many sub-spaceships, crew, tanks, etc. and you control each and every weapon.
Sadly, Trillion Credit Squadron does nothing whatsoever to make it simpler for the math-impaired to build and battle starships. Indeed, the TCS includes among its recommended materials "calculators or adding machines" and even suggests the use of programming a home computer "to handle much of the tedium of the design process
Imagine, having a programming skills was almost a requirement to play and compete in this game.
I've looked it up and anyone calling this "the most complex ..." clearly have never played 80s board games e.g.
The Campaign for North Africa (takes more than 1000 hours to finish)
I've had some problems with parsing in part 2 - I didn't account for double digit numbers before dna sequences and that caused my code to work on example, but silently fail only on the real input. I've figured it out after ~30 minutes with some external help.
Part 3 runs in 700ms - not great, but not too bad either.
proc similarity(a, b: string): int =
for i, c in a:
if c == b[i]: inc result
proc solve_part1*(input: string): Solution =
var sim: seq[int]
var dnaList: seq[string]
for line in input.splitLines():
dnaList.add line[2..^1]
for i in 0 .. dnaList.high:
for j in i+1 .. dnaList.high:
let s = similarity(dnaList[i], dnaList[j])
sim.add s
sim.sort()
result := sim[^2] * sim[^1]
proc parentTest(ch, p1, p2: string): bool =
for i, c in ch:
if (c != p1[i]) and (c != p2[i]): return false
true
proc simTable(dnaList: seq[string]): seq[seq[int]] =
result = newSeqWith(dnaList.len, newseq[int](dnaList.len))
for i in 0 .. dnaList.high:
for j in i+1 .. dnaList.high:
let s = similarity(dnaList[i], dnaList[j])
result[i][j] = s
result[j][i] = s
proc solve_part2*(input: string): Solution =
var dnaList: seq[string]
for line in input.splitLines():
dnaList.add line.split(':')[1]
let sim = simTable(dnaList)
var indices = toseq(0..dnaList.high)
for i, childDna in dnaList:
var indices = indices
indices.del i
block doTest:
for k in 0 .. indices.high:
for j in k+1 .. indices.high:
let p1 = indices[k]
let p2 = indices[j]
if parentTest(childDna, dnaList[p1], dnaList[p2]):
result.intVal += sim[i][p1] * sim[i][p2]
break doTest
proc solve_part3*(input: string): Solution =
var dnaList: seq[string]
for line in input.splitLines():
dnaList.add line.split(':')[1]
var families: seq[set[int16]]
var indices = toseq(0..dnaList.high)
for ch, childDna in dnaList:
var indices = indices
indices.del ch
block doTest:
for k in 0 .. indices.high:
for j in k+1 .. indices.high:
let p1 = indices[k]
let p2 = indices[j]
if parentTest(childDna, dnaList[p1], dnaList[p2]):
families.add {ch.int16, p1.int16, p2.int16}
break doTest
var combined: seq[set[int16]]
while families.len > 0:
combined.add families.pop()
var i = 0
while i <= families.high:
if (combined[^1] * families[i]).len > 0:
combined[^1] = combined[^1] + families[i]
families.del i
i = 0
else: inc i
let maxInd = combined.mapIt(it.len).maxIndex
result := combined[maxInd].toseq.mapIt(it.int+1).sum()
No? Most of his stuff are terrible movies.
But, I am watching them for fucking around with cool ideas and crazy visual scenes. Couldn't care less about plot, characters, sometimes logic, etc.
This is just another layer. Order in
8/2(2+2)is still not clear if you understand the division symbol correctly.https://en.wikipedia.org/wiki/Order_of_operations#Mixed_division_and_multiplication
Both are right, depending on who you ask:
most people see:
math people see "juxtaposition" instead of multiplication, it has precedence over multiplication and division:
Math notation just sucks and is not standard in general, everyone just tries to avoid ambiguity like in this equation.
https://doc.rust-lang.org/nomicon/races.html
I know that it was unsafe block in this CVE, but the irony of the situation is funny.
> zweihander
Nim
::: spoiler view code
:::
Runtime: 364 ms
Part 1:
I compute all pairs of Euclidean distances between 3D points, sort them, then connect points into circuits, using, what I think is called a Union‑Find algorithm (circuits grow or merge). After exactly 1000 connections (including redundant ones), I take the three largest circuits and multiply their sizes.
Part 2:
While iterating through the sorted connections, I also calculate the product of each pair x‑coordinates. The last product is a result for part 2.
Problems I encountered while doing this puzzle:
ref objects stored in a HashTable (~ 40 min)Time to solve Part 1: 1 hour 56 minutes
Time to solve Part 2: 4 minutes
Full solution at Codeberg: solution.nim
Nim
Another simple one.
Part 1: count each time a beam crosses a splitter.
Part 2: keep count of how many particles are in each column in all universes
(e.g. with a simple 1d array), then sum.
Runtime:
116 μs95 µs86 µs::: spoiler old version
:::
Update: found even smaller and faster version that only needs a single array.
Update #2: small optimization
Full solution at Codeberg: solution.nim
Nim
The hardest part was reading the part 2 description. I literally looked at it for minutes trying to understand where the problem numbers come from and how they're related to the example input. But then it clicked.
The next roadblock was that my template was stripping whitespace at the end of the last line, making parsing a lot harder. I've replaced
strip()withstrip(chars={'\n'})to keep the trailing space intact.Runtime:
1.4 ms618 μs::: spoiler view code
:::
Full solution at Codeberg: solution.nim
+1 shitty superpower ideas
I should really start writing them down at this point.
Nim
Huh, I didn't expect two easy days in a row.
Part 1 is a range check. Part 2 is a range merge.
Runtime: ~720 µs
Full solution at Codeberg: solution.nim
Nim
Today was so easy, that I decided to solve it twice, just for fun. First is a 2D traversal (see above). And then I did a node graph solution in a few minutes (in repo below). Both run in ~27 ms.
It's a bit concerning, because a simple puzzle can only mean that tomorrow will be a nightmare. Good Luck everyone, we will need it.
Full solution is at Codeberg: solution.nim
Nim
Runtime: ~240 μs
Day 3 was very straightforward, although I did wrestle a bit with the indexing.
Honestly, I expected part 2 to require dynamic programming, but it turned out I only needed to tweak a few numbers in my part 1 code.
Full solution at Codeberg: solution.nim
Nim
Easy one today. Part 2 is pretty forgiving on performance, so regex bruteforce was only a couple seconds . But eventually I've cleaned it up and did a solution that runs in ~340 ms.
Full solution at Codeberg: solution.nim
Nim
That was the rough first day for me. Part 1 was ok. For part 2 I didn't want to go the easy route, so I was trying to find simple formulaic solution, but my answer was always off by some amount. And debugging was hard, because I I was getting the right answer for example input.
After 40 minutes I wiped everything clean and wrote a bruteforce.
Later that day I returned and solved this one properly. I had to draw many schemes and consider all the edge cases carefully to come up with code below.
Full solution at Codeberg: solution.nim
I didn't want to dismiss it. For what I see, it's probably a really fun and complex strategy. It's just that retro board games are on a whole another level of "complex" and I doubt we will ever get close to with the modern stuff.
Fair, but:
Star Fleet Battles
Traveller Adventure 5: Trillion Credit Squadron
For TCS - you have literally control of around hundred of space ships that each can hold many sub-spaceships, crew, tanks, etc. and you control each and every weapon.
Some random blogpost about TCS:
Imagine, having a programming skills was almost a requirement to play and compete in this game.
I've looked it up and anyone calling this "the most complex ..." clearly have never played 80s board games e.g. The Campaign for North Africa (takes more than 1000 hours to finish)
uhh, how do these wheels turn exactly?
Nim
Very messy bruteforce.
I've had some problems with parsing in part 2 - I didn't account for double digit numbers before dna sequences and that caused my code to work on example, but silently fail only on the real input. I've figured it out after ~30 minutes with some external help.
Part 3 runs in 700ms - not great, but not too bad either.
Full solution at Codeberg: solution.nim