janAkali
- 5 Posts
- 30 Comments
Nim
view code
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.xRuntime: 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 minutesFull solution at Codeberg: solution.nim
- I’ve changed a dozen of data structures, before settled on curcuitIDs and
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 µsold 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 optimizationtype 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()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 μsview 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 += resFull 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
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+1Full solution at Codeberg: solution.nim
Nim
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: discardToday 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
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 12Runtime: ~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.
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 breakFull 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.
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.part1Full solution at Codeberg: solution.nim
1·1 month agoI 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 SquadronFor 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:
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)
2·1 month agouhh, how do these wheels turn exactly?
2·1 month agoNim
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.
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()Full solution at Codeberg: solution.nim
Nim
Part 2 - I just really didn’t want to think that day. So when puzzle asked me to check if lines intersect - I wrote the intersection checking solution with 2D points.
Part 3 is geometry + bruteforce.
proc solve_part1*(input: string): Solution = let pins = input.split(',').mapIt(parseInt(it)) for i in 0 ..< pins.high: let d = abs(pins[i] - pins[i+1]) if d == 16: inc result.intVal proc ccw(A,B,C: Vec2): bool = (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x) proc isIntersection(A,B,C,D: Vec2): bool = ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D) proc solve_part2*(input: string): Solution = const two_pi = PI * 2 const pin_count = 256 var pins: array[pin_count, Vec2] for i in 0 ..< pin_count: let angle = two_pi * (i / pin_count) let point: Vec2 = (cos(angle), sin(angle)) pins[i] = point let inst = input.split(',').mapIt(parseInt(it)) var lines: seq[(Vec2, Vec2)] for i in 0 ..< inst.high: let A = pins[inst[i]-1] let B = pins[inst[i+1]-1] for (C, D) in lines: if isIntersection(A,B,C,D): inc result.intVal lines.add shortenSegment(A, B, 0.0001) proc solve_part3*(input: string): Solution = const two_pi = PI * 2 const pin_count = 256 var pins: array[pin_count, Vec2] for i in 0 ..< pin_count: let angle = two_pi * (i / pin_count) let point: Vec2 = (cos(angle), sin(angle)) pins[i] = point let inst = input.split(',').mapIt(parseInt(it)) var lines: seq[(Vec2, Vec2)] for i in 0 ..< inst.high: let A = pins[inst[i]-1] let B = pins[inst[i+1]-1] lines.add shortenSegment(A, B, 0.0001) var bestSum = 0 for i in 0 ..< pin_count: for j in i+1 ..< pin_count: let A = pins[i] let B = pins[j] var sum = 0 for (C, D) in lines: if isIntersection(A,B,C,D): inc sum if sum > bestSum: bestSum = sum result := bestSumFull solution at Codeberg: solution.nim
Nim
Part 3 is a recursive solution with caching (memoization).
proc isValid(name: string, rules: Table[char, set[char]]): bool = for i in 0 ..< name.high: if name[i+1] notin rules[name[i]]: return false true proc allNames(prefix: string, rules: Table[char, set[char]], range: Slice[int]): int = var memo {.global.}: Table[(int, char), int] if prefix.len >= range.b: return if (prefix.len, prefix[^1]) in memo: return memo[(prefix.len, prefix[^1])] for ch in rules.getOrDefault(prefix[^1]): if prefix.len + 1 >= range.a: inc result result += allNames(prefix & ch, rules, range) memo[(prefix.len, prefix[^1])] = result proc solve_part1*(input: string): Solution = let (names, rules) = parseInput(input) for name in names: if name.isValid(rules): return Solution(kind: skString, strVal: name) proc solve_part2*(input: string): Solution = let (names, rules) = parseInput(input) for ni, name in names: if name.isValid(rules): result.intVal += ni + 1 proc solve_part3*(input: string): Solution = let (names, rules) = parseInput(input) var seen: seq[string] for name in names: if not name.isValid(rules): continue if seen.anyIt(name.startsWith it): continue result.intVal += allNames(name, rules, 7..11) seen.add nameFull solution at Codeberg: solution.nim
Nim
parts 1 and 2 - easy
For part 3 - When I first looked at the example input - it seemed a bit daunting to solve. But then I had a hunch and decided to check the real input and turns out - I was right! The real input is easier to solve because it’s longer than 1000 chars.
This means that there is only 3 possible configurations we care about in repeated input: leftmost section, rightmost section and 998 identical sections in the middle. We solve each individually and sum them.
Another trick I used is looking up mentors with modulo to avoid copying the input.
proc solve_part1*(input: string): Solution = var mentors: CountTable[char] for c in input: if c notin {'a','A'}: continue if c.isUpperAscii: mentors.inc c else: result.intVal += mentors.getOrDefault(c.toUpperAscii) proc solve_part2*(input: string): Solution = var mentors: CountTable[char] for c in input: if c.isUpperAscii: mentors.inc c else: result.intVal += mentors.getOrDefault(c.toUpperAscii) proc solve_part3*(input: string): Solution = var mentors: Table[char, seq[int]] for index in -1000 ..< input.len + 1000: let mi = index.euclMod input.len if input[mi].isLowerAscii: continue let lower = input[mi].toLowerAscii if mentors.hasKeyOrPut(lower, @[index]): mentors[lower].add index var most, first, last = 0 for ci, ch in input: if ch.isUpperAscii: continue for mi in mentors[ch]: let dist = abs(mi - ci) if dist <= 1000: inc most if mi >= 0: inc first if mi <= input.high: inc last result := first + (most * 998) + lastFull solution at Codeberg: solution.nim
Nim
Nothing fancy. Simple iterative tree construction and sort, using the
std/algorithmand a custom<operator on types.type LeafNode = ref object value: int Node = ref object value: int left, right: LeafNode center: Node Sword = object id, quality: int levels: seq[int] fishbone: Node proc add(node: var Node, val: int) = var curNode = node while not curNode.isNil: if val < curNode.value and curNode.left.isNil: curNode.left = LeafNode(value: val) return elif val > curNode.value and curNode.right.isNil: curNode.right = LeafNode(value: val) return elif curNode.center.isNil: curNode.center = Node(value: val) return else: curNode = curNode.center node = Node(value: val) proc calcQuality(sword: Sword): int = var res = "" var curNode = sword.fishbone while not curNode.isNil: res &= $curNode.value curNode = curNode.center return parseInt(res) proc getLevels(s: Sword): seq[int] = var curNode = s.fishbone while not curNode.isNil: var strVal = "" strVal &= (if curNode.left.isNil: "" else: $curNode.left.value) strVal &= $curNode.value strVal &= (if curNode.right.isNil: "" else: $curNode.right.value) result.add parseInt(strVal) curNode = curNode.center proc `<`(s1, s2: seq[int]): bool = for i in 0..min(s1.high, s2.high): if s1[i] != s2[i]: return s1[i] < s2[i] s1.len < s2.len proc `<`(s1, s2: Sword): bool = if s1.quality != s2.quality: s1.quality < s2.quality elif s1.levels != s2.levels: s1.levels < s2.levels else: s1.id < s2.id proc parseSwords(input: string): seq[Sword] = for line in input.splitLines: let numbers = line.split({':',','}).mapIt(parseInt(it)) var node= Node(value: numbers[1]) for num in numbers.toOpenArray(2, numbers.high): node.add num result &= Sword(id: numbers[0], fishbone: node) proc solve_part1*(input: string): Solution = let swords = parseSwords(input) result := swords[0].calcQuality() proc solve_part2*(input: string): Solution = let qualities = parseSwords(input).mapIt(it.calcQuality()) result := qualities.max - qualities.min proc solve_part3*(input: string): Solution = var swords = parseSwords(input) for i in 0..swords.high: swords[i].levels = swords[i].getLevels() swords[i].quality = swords[i].calcQuality() swords.sort(Descending) for pos, id in swords.mapit(it.id): result.intVal += (pos+1) * idFull solution at Codeberg: solution.nim
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.