infinitesimal's recent activity
-
Comment on Day 10: Pipe Maze in ~comp.advent_of_code
-
Comment on Day 9: Mirage Maintenance in ~comp.advent_of_code
infinitesimal LinkSurprisingly easy, the most trouble I had was failing to parse negative numbers. While trying to diagnose why my answer was wrong, I added some debug statements... that corrupted my data structure...Surprisingly easy, the most trouble I had was failing to parse negative numbers. While trying to diagnose why my answer was wrong, I added some debug statements... that corrupted my data structure because it was mutable and I doubly modified them. After fixing that (by copying everything), I finally got to look at the stack and noticed I was missing all the negative numbers.
Kotlin
object Day09 { fun parse(input: String): List<List<Long>> { return input.lines().map { longsOf(it).toList() } } fun diff1(l: List<Long>) = l.windowed(2).map { it[1] - it[0] } fun diffN(l: List<Long>): List<List<Long>> { val result = mutableListOf(l) while (!result.last().all { it == 0L }) { result.add(diff1(result.last())) } return result } fun fillForward(triangle: List<List<Long>>): List<List<Long>> { val result = mutableListOf<List<Long>>(triangle.last() + listOf(0)) for (i in triangle.size - 2 downTo 0) { result.addFirst(triangle[i] + listOf(triangle[i].last() + result.first().last())) } return result } fun fillBackward(triangle: List<List<Long>>): List<List<Long>> { val result = mutableListOf<List<Long>>(listOf(0L) + triangle.last()) for (i in triangle.size - 2 downTo 0) { result.addFirst(listOf(triangle[i].first() - result.first().first()) + triangle[i]) } return result } fun part1(input: String): Long { val seqs = parse(input) return seqs.sumOf { fillForward(diffN(it)).first().last() } } fun part2(input: String): Long { val seqs = parse(input) return seqs.sumOf { fillBackward(diffN(it)).first().first() } } } -
Comment on Day 8: Haunted Wasteland in ~comp.advent_of_code
infinitesimal LinkI tried to do part 2 naively at first and when that worked on the example but not the input I tried to do the next simplest thing which then happened to work, but upon reading other comments I...I tried to do part 2 naively at first and when that worked on the example but not the input I tried to do the next simplest thing which then happened to work, but upon reading other comments I realized it wasn't "supposed" to work except the input was specially crafted for it to work.
Kotlin
object Day08 { fun parse(input: String): Pair<String, Map<String, Pair<String, String>>> { val (path0, graph0) = input.split("\n\n") val path = path0.trim() val graph = mutableMapOf<String, Pair<String, String>>() for (line in graph0.lines()) { val (node, left, right) = alnumsOf(line).toList() graph[node] = Pair(left, right) } return Pair(path, graph) } fun cycleOf(path: String) = iterator { var i = 0 while (true) { yield(path[i]) i = (i + 1) % path.length } } fun stepsOf(node: String, path: String, graph: Map<String, Pair<String, String>>): Int { val cycle = cycleOf(path) var numSteps = 0 var location = node while (!location.endsWith('Z')) { location = when (cycle.next()) { 'L' -> graph[location]!!.first 'R' -> graph[location]!!.second else -> error(Unit) } numSteps++ } return numSteps } fun part1(input: String): Int { val (path, graph) = parse(input) return stepsOf("AAA", path, graph) } fun part2(input: String): Long { val (path, graph) = parse(input) val starts = graph.keys.filter { it.endsWith('A') } val steps = starts.map { stepsOf(it, path, graph).toLong() } return steps.reduce { x, y -> lcm(x, y) } } } -
Comment on Day 7: Camel Cards in ~comp.advent_of_code
infinitesimal LinkToday felt straightforward enough. I initially thought I'd have to handwrite the branches in part 2, but I just tried adding up jokers and then copypasting part 1 logic and it worked so shrug....Today felt straightforward enough. I initially thought I'd have to handwrite the branches in part 2, but I just tried adding up jokers and then copypasting part 1 logic and it worked so shrug.
Kotlin
package aoc2023 object Day7 { enum class Card { Two, Three, Four, Five, Six, Seven, Eight, Nine, Ten, Jack, Queen, King, Ace } enum class Type { HighCard, OnePair, TwoPair, ThreeKind, FullHouse, FourKind, FiveKind } fun p1TypeOf(cards: List<Card>): Type { val sizes = cards.groupBy { it }.map { it.value.size }.sortedDescending() return when (sizes[0]) { 5 -> Type.FiveKind 4 -> Type.FourKind 3 -> if (sizes[1] == 2) Type.FullHouse else Type.ThreeKind 2 -> if (sizes[1] == 2) Type.TwoPair else Type.OnePair 1 -> Type.HighCard else -> error(Unit) } } fun p2TypeOf(cards: List<Card>): Type { val numJacks = cards.groupBy { it }[Card.Jack]?.size ?: 0 if (numJacks == 5) { return Type.FiveKind } val sizes = cards.groupBy { it }.filter { it.key != Card.Jack }.map { it.value.size }.toMutableList() sizes.sortDescending() sizes[0] += numJacks return when (sizes[0]) { 5 -> Type.FiveKind 4 -> Type.FourKind 3 -> if (sizes[1] == 2) Type.FullHouse else Type.ThreeKind 2 -> if (sizes[1] == 2) Type.TwoPair else Type.OnePair 1 -> Type.HighCard else -> error(Unit) } } fun parse(input: String): List<Pair<List<Card>, Int>> { return input.trim().lines().map { line -> val (hand0, bid0) = line.split(" ") val bid = bid0.trim().toInt() val hand = hand0.trim().map { card0 -> when (card0) { '2' -> Card.Two '3' -> Card.Three '4' -> Card.Four '5' -> Card.Five '6' -> Card.Six '7' -> Card.Seven '8' -> Card.Eight '9' -> Card.Nine 'T' -> Card.Ten 'J' -> Card.Jack 'Q' -> Card.Queen 'K' -> Card.King 'A' -> Card.Ace else -> error(Unit) } } Pair(hand, bid) } } fun part1(input: String): Int { val sorted = parse(input).sortedWith { x0, y0 -> val x = x0.first val y = y0.first x.indices.fold(p1TypeOf(x).compareTo(p1TypeOf(y))) { acc, i -> if (acc != 0) acc else x[i].compareTo(y[i]) } } return sorted.mapIndexed { i, (_, bid) -> (i + 1) * bid }.sum() } fun part2(input: String): Int { val sorted = parse(input).sortedWith { x0, y0 -> val x = x0.first val y = y0.first x.indices.fold(p2TypeOf(x).compareTo(p2TypeOf(y))) { acc, i -> if (acc != 0) acc else { val xiOrd = if (x[i] == Card.Jack) -1 else x[i].ordinal val yiOrd = if (y[i] == Card.Jack) -1 else y[i].ordinal xiOrd.compareTo(yiOrd) } } } return sorted.mapIndexed { i, (_, bid) -> (i + 1) * bid }.sum() } } -
Comment on Day 6: Wait For It in ~comp.advent_of_code
infinitesimal LinkNthing comments that this really would've been faster if you just manually typed the inputs and the loop in a REPL. Kotlin package aoc2023 object Day6 { fun parse(input: String): Pair<List<Int>,...Nthing comments that this really would've been faster if you just manually typed the inputs and the loop in a REPL.
Kotlin
package aoc2023 object Day6 { fun parse(input: String): Pair<List<Int>, List<Int>> { fun intsOf(s: String) = Regex("""\d+""").findAll(s).map { it.value.toInt() } val (times, dists) = input.trim().lines().map { intsOf(it).toList() }.toList() return Pair(times, dists) } fun part1(input: String): Int { val (times, dists) = parse(input) fun wins(time0: Int, dist0: Int) = (0..time0).fold(0) { acc, time -> if (time * (time0 - time) > dist0) acc + 1 else acc } return times.indices.map { wins(times[it], dists[it]) }.reduce { x, y -> x * y } } fun part2(input: String): Long { val (times, dists) = parse(input) val time0 = times.joinToString("") { it.toString() }.toLong() val dist0 = dists.joinToString("") { it.toString() }.toLong() fun wins(time0: Long, dist0: Long) = (0..time0).fold(0L) { acc, time -> if (time * (time0 - time) > dist0) acc + 1 else acc } return wins(time0, dist0) } } -
Comment on Day 5: If You Give A Seed A Fertilizer in ~comp.advent_of_code
infinitesimal LinkI initially used my part 1 solution to write a naive part 2 solution, which worked fine on the example but failed on the input for obvious reasons. After trying (and failing) to write a proper...I initially used my part 1 solution to write a naive part 2 solution, which worked fine on the example but failed on the input for obvious reasons. After trying (and failing) to write a proper solution using intervals and ending up with a bazillion intervals all looking wrong, I slept on it before getting a working solution: change the representation of intervals to (start, end, shift) and augment my intervals with sentinels (with a shift of 0) so that the entire 0 to Long.MAX_VALUE space is partitioned by intervals. The former simplified the arithmetic and the latter reduced 6 cases to 2, and then everything worked. 🎉
Kotlin
package aoc2023 object Day5 { data class Range(val start: Long, val end: Long, val shift: Long) fun parse(input: String): Pair<List<Long>, List<List<Range>>> { fun longsOf(s: String) = Regex("""\d+""").findAll(s).map { it.value.toLong() } fun rangeOf(s: String) = longsOf(s).toList().let { (dest, src, n) -> Range(src, src + n, dest - src) } fun augment(map: List<Range>): List<Range> { val sentinels = mutableListOf<Range>() if (map.first().start != 0L) { sentinels.add(Range(0, map.first().start, 0)) } for (i in map.indices.drop(1)) { if (map[i - 1].end != map[i].start) { sentinels.add(Range(map[i - 1].end, map[i].start, 0)) } } if (map.last().end != Long.MAX_VALUE) { sentinels.add(Range(map.last().end, Long.MAX_VALUE, 0)) } return (map + sentinels).sortedBy { it.start } } fun mapOf(s: String) = s.lines().drop(1).map { rangeOf(it) }.sortedBy { it.start }.let { augment(it) } val parts = input.trim().split("\n\n") val seeds = longsOf(parts.first()).toList() val maps = parts.drop(1).map { mapOf(it) } return Pair(seeds, maps) } fun part1(input: String): Long { val (seeds, maps) = parse(input) fun convert(seed: Long, maps: List<List<Range>>) = maps.fold(seed) { num, map -> val range = map.first { it.start <= num && num < it.end } num + range.shift } return seeds.minOf { convert(it, maps) } } fun part2(input: String): Long { val (seeds, maps) = parse(input) val chunks0 = seeds.chunked(2).map { (start, n) -> Range(start, start + n, 0) } fun convert1(chunk0: Range, map: List<Range>): List<Range> { val inChunks = ArrayDeque<Range>() inChunks.addLast(chunk0) val outChunks = ArrayDeque<Range>() while (inChunks.isNotEmpty()) { val chunk = inChunks.removeFirst() val range = map.first { it.start <= chunk.start && chunk.start < it.end } if (chunk.end <= range.end) { outChunks.addLast(Range(chunk.start + range.shift, chunk.end + range.shift, 0)) } else { outChunks.addLast(Range(chunk.start + range.shift, range.end + range.shift, 0)) inChunks.addLast(Range(range.end, chunk.end, 0)) } } return outChunks } return maps.fold(chunks0) { chunks, map -> chunks.flatMap { chunk -> convert1(chunk, map) } }.minOf { it.start } } } -
Comment on Day 4: Scratchcards in ~comp.advent_of_code
infinitesimal LinkI can't find Kotlin's integer exponent operator or function. Part 2 also took a whole 1.5 seconds to do naively before I read the first comment by @lily and only tracked the counts after which it...I can't find Kotlin's integer exponent operator or function. Part 2 also took a whole 1.5 seconds to do naively before I read the first comment by @lily and only tracked the counts after which it went back to instantaneous.
Kotlin
import kotlin.math.pow object Day4 { data class Card(val id: Int, val winners: Set<Int>, val havers: Set<Int>) private fun parse(line: String) = let { fun numsOf(s: String) = Regex("""\d+""").findAll(s).map { it.value.toInt() }.toSet() fun idOf(s: String) = Regex("""\d+""").find(s)!!.value.toInt() line.split(":").let { val (winners0, havers0) = it[1].split("|") Card(idOf(it[0]), numsOf(winners0), numsOf(havers0)) } } fun part1(lines: List<String>) = lines.sumOf { line -> val (_, winners, havers) = parse(line) val inter = winners.intersect(havers) if (inter.isNotEmpty()) 2.0.pow(inter.size - 1).toInt() else 0 } fun part2(lines: List<String>) = let { val cards = lines.map { parse(it) } val counts = Array<Int>(cards.size + 1) { if (it == 0) 0 else 1 } cards.forEach { (id, winners, havers) -> ((id + 1)..(id + winners.intersect(havers).size)).forEach { counts[it] += counts[id] } } counts.sum() } val input = javaClass.getResourceAsStream("${javaClass.name}.txt")!!.reader().readLines() } fun main() { with(Day4) { println(part1(input)) println(part2(input)) } } -
Comment on Day 3: Gear Ratios in ~comp.advent_of_code
infinitesimal LinkJust wondering, do people ever use fancy spatial data structures for these 2D (or eventually 3D) AoC grid problems instead of just nested loops? Kotlin object Day3 { data class Number(val i: Int,...Just wondering, do people ever use fancy spatial data structures for these 2D (or eventually 3D) AoC grid problems instead of just nested loops?
Kotlin
object Day3 { data class Number(val i: Int, val row: Int, val col: IntRange) data class Symbol(val c: Char, val row: Int, val col: Int) data class Schematic(val nums: List<Number>, val syms: List<Symbol>) private fun parse(lines: List<String>) = lines.mapIndexed { row, line -> val nums = Regex("""\d+""").findAll(line).map { Number(it.value.toInt(), row, it.range) } val syms = Regex("""[^\d.]""").findAll(line).map { Symbol(it.value.first(), row, it.range.first) } Schematic(nums.toList(), syms.toList()) }.reduce { prev, next -> Schematic(prev.nums + next.nums, prev.syms + next.syms) } private fun isAdjacent(num: Number, sym: Symbol) = let { val vert = (num.row - 1)..(num.row + 1) val horz = num.col + (num.col.first - 1) + (num.col.last + 1) val neighborhood = vert.flatMap { row -> horz.map { col -> Pair(row, col) } } Pair(sym.row, sym.col) in neighborhood } fun part1(lines: List<String>) = let { val (nums, syms) = parse(lines) nums.filter { num -> syms.any { sym -> isAdjacent(num, sym) } }.sumOf { num -> num.i } } fun part2(lines: List<String>) = let { val (nums, syms) = parse(lines) syms.filter { it.c == '*' }.sumOf { sym -> val neighbors = nums.filter { num -> isAdjacent(num, sym) }.toList() if (neighbors.size == 2) neighbors[0].i * neighbors[1].i else 0 } } } -
Comment on Day 2: Cube Conundrum in ~comp.advent_of_code
infinitesimal LinkYesterday I hadn't written a line of Kotlin before. Today I learned more of its conveniences. Kotlin class Day2 { // Parse each line into a game and filter games where all bags are less than the...Yesterday I hadn't written a line of Kotlin before. Today I learned more of its conveniences.
Kotlin
class Day2 { // Parse each line into a game and filter games where all bags are less than the limit. Then sum the game ids. fun part1(lines: List<String>) = let { val limit = mapOf("red" to 12, "green" to 13, "blue" to 14) fun isPossible(game: Game) = game.bags.all { bag -> bag.entries.all { (k, v) -> v <= limit[k]!! } } lines.map { parseGame(it) }.filter { isPossible(it) }.sumOf { it.id } } // Parse each line into a game and take the union of all bags in a game. Take the product of each bag's counts and // then sum the products. fun part2(lines: List<String>) = let { fun Map<String, Int>.union(that: Map<String, Int>) = (this.keys + that.keys).associateWith { (this[it] ?: 0).coerceAtLeast(that[it] ?: 0) } lines.sumOf { val game = parseGame(it) val bag = game.bags.reduce { prev, next -> prev.union(next) } val power = bag.values.reduce { prev, next -> prev * next } power } } data class Game(val id: Int, val bags: List<Map<String, Int>>) private fun parseGame(line: String) = let { fun parseBag(s: String) = Regex("""(\d+) (\w+)""").findAll(s).map { it.groupValues[2] to it.groupValues[1].toInt() }.toMap() fun parseBags(s: String) = s.split(";").map { parseBag(it) } Regex("""Game (\d+): (.*)""").find(line)!!.groupValues.let { Game(it[1].toInt(), parseBags(it[2])) } } val input = javaClass.getResourceAsStream("${javaClass.name}.txt")!!.reader().readLines() } fun main() { val example1 = """ Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green Game 2: 1 blue, 2 green; 3 green, 4 blue, 1 red; 1 green, 1 blue Game 3: 8 green, 6 blue, 20 red; 5 blue, 4 red, 13 green; 5 green, 1 red Game 4: 1 green, 3 red, 6 blue; 3 green, 6 red; 3 green, 15 blue, 14 red Game 5: 6 red, 1 blue, 3 green; 2 blue, 1 red, 2 green """.trimIndent().lines() val example1Expected1 = 8 val example2Expected2 = 2286 val inputExpected1 = 2331 val inputExpected2 = 71585 val day = Day2() check(day.part1(example1) == example1Expected1) check(day.part2(example1) == example2Expected2) day.part1(day.input).also { println(it) }.also { check(it == inputExpected1) } day.part2(day.input).also { println(it) }.also { check(it == inputExpected2) } } -
Comment on Day 1: Trebuchet?! in ~comp.advent_of_code
infinitesimal LinkDecided to use Kotlin and see how far I get this year. I got tripped up on part 2 and had to switch from simple replacement to regex: import java.util.regex.Pattern fun main() { /* For each line,...Decided to use Kotlin and see how far I get this year. I got tripped up on part 2 and had to switch from simple replacement to regex:
import java.util.regex.Pattern fun main() { /* For each line, filter the digits, concatenate the first and last digits, and then add it to the result. */ fun part1(input: List<String>): Int { var result = 0 for (line in input) { val digits = line.filter { it.isDigit() }.map { it.digitToInt() } result += digits[0] * 10 + digits[digits.size - 1] } return result } check(part1(readExample(1, 1)) == 142) val output1 = part1(readInput(1)) println(output1) check(output1 == 53334) /* For each line, generate digits using a map, concatenate the first and last digits, and then add it to the result. */ fun part2(input: List<String>): Int { var result = 0 val map = mapOf( "one" to 1, "two" to 2, "three" to 3, "four" to 4, "five" to 5, "six" to 6, "seven" to 7, "eight" to 8, "nine" to 9 ).plus((0 until 10).map { it.toString() to it }) val pattern = Pattern.compile(map.keys.joinToString("|")) for (line in input) { val digits = arrayListOf<Int>() val matcher = pattern.matcher(line) while (matcher.find()) { digits.addLast(map[matcher.group()]) } result += digits[0] * 10 + digits[digits.size - 1] } return result } check(part2(readExample(1, 2)) == 281) val output2 = part2(readInput(1)) println(output2) check(output2 == 52834) }
I thought part 1 was straightforward but tedious (BFS, but every pipe shape has a different neighbor), and then I tapped out on part 2 and probably the rest of AoC2023. I tried to walk around the loop and look to my right until I hit another loop tile, which worked for the simplest examples. A small issue was that the loop could be oriented the opposite way (I'd just toggle looking left instead of right), but a bigger issue is that I don't think my code worked for corner pipes in some/many situations, and I didn't know how to fix it.