https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 1> :thread:
# advent-of-code
a
n
On the soccer field, waiting for the coach to stop monologuing. Big tournament coming up this weekend. Already got part 1 solved in my head, of course.
j
good first day warmup
p
m
Part 1
Part 2
very nice 1
❤️ 1
m
I am once again asking for a 'indexOfOrNull' function
Copy code
override fun part2(): Any? {
    return parsed.sumOf {
        val firstDigit = digits
            .minByOrNull { (text, _) ->
                it.indexOf(text).let { if(it == -1) MAX_VALUE else it }
            }!!.value
        val lastDigit = digits
            .maxByOrNull { (text, _) ->
                it.lastIndexOf(text).let { if(it == -1) MIN_VALUE else it }
            }!!.value
        firstDigit * 10 + lastDigit
    }
}
K 2
👌 2
(digits being a map of strings to ints)
j
Copy code
fun part1(input: Input) = input.sumOf(String::part1calibration)
fun part2(input: Input) = input.sumOf(String::part2calibration)

private fun String.part1calibration() = first(Char::isDigit).digitToInt() * 10 + last(Char::isDigit).digitToInt()

private fun String.part2calibration(): Int {
    val l1: Int = indices.firstNotNullOf { betterToDigitOrNull(it) }
    val l2: Int = indices.reversed().firstNotNullOf { betterToDigitOrNull(it) }
    return l1 * 10 + l2
}

private fun String.betterToDigitOrNull(startIndex: Int): Int? =
    if (this[startIndex].isDigit()) this[startIndex].digitToInt()
    else digitNames.firstNotNullOfOrNull { (d, name) -> if (startsWith(name, startIndex)) d else null }

val digitNames = listOf(
    1 to "one",
    2 to "two",
    3 to "three",
    4 to "four",
    5 to "five",
    6 to "six",
    7 to "seven",
    8 to "eight",
    9 to "nine",
)
a
m
I assumed "zero" could appear in the input, which also makes the indices naturally form the mapping to strings.
b
Copy code
val digits =  listOf(
        "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'
    )

    var remaining = input

    return sequence {
        while(remaining.isNotEmpty()) {
            if (remaining.get(0).isDigit()) {
                yield(remaining.get(0))
            } else {
                digits.filter {
                    remaining.startsWith(it.first)
                }.firstOrNull()?.let { yield(it.second) }

            }
            remaining = remaining.drop(1)
        }
    }.toList()
}

fun part2(input: List<String>): Any {

    fun parse(input: List<String>) = input.map { parseLine(it) }

    return parse(input).sumOf { "${it.first()}${it.last()}".toInt() }
}
j
BTW I was so happy that I instinctively avoided the “oneight” trap, when I started with a series of 
.replace(…)
after reading the part2. And just after submitting the result I read the description and found out that 
"zero"
is not a valid digit name. Fortunately there was no such substring in my input
m
Full solution, with indexOfOrNull extension function
Copy code
object Day1 : Challenge() {
    val parsed = input.lines()
    override fun part1() = parsed
        .map { it.filter(Char::isDigit) }
        .sumOf { it.first().digitToInt() * 10 + it.last().digitToInt() }

    override fun part2() = parsed.sumOf {
        val firstDigit = digits.minByOrNull { (text, _) -> it.indexOfOrNull(text) ?: MAX_VALUE }!!.value
        val lastDigit = digits.maxByOrNull { (text, _) -> it.lastIndexOfOrNull(text) ?: MIN_VALUE }!!.value
        firstDigit * 10 + lastDigit
    }

    private val digits = mapOf(
        "1" to 1,
        "2" to 2,
        "3" to 3,
        "4" to 4,
        "5" to 5,
        "6" to 6,
        "7" to 7,
        "8" to 8,
        "9" to 9,
        "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,
    )
}
a
the joy of passing the calibration test for part 2 but not the correct answer with actual input 😭 is it possible for a line to have only one number? if so, I assume that should be counted as a digit in the units place? answer: example from part one: >
Copy code
treb7uchet --> 77
a
@Anirudh consider this line: “twone”. You need to make sure it’s parsed as 2 and 1
🤔 1
thank you color 1
d
a
@Arkadiusz isn't that like the trap of "eightwothree" ? as in, should we treat it as a fresh string (original) when we want to find the last digit?
d
TIL about 
String.findAnyOf
and 
String.findLastAnyOf
same 8
👍 1
n
What would you think would be the correct answer for a line "oneight"? [1], or [1, 8], or [8]?
m
1,8
☝️ 1
or at least 1
a
I would incorrectly put it as [1, 1] because of: > "oneight" --> "1ight" > first: 1; last: 1
n
hmm, but really that line does not contain 2 "complete" digits
d
the input all has at least 1 digit per line so it isn’t a relevant case
but 18 based simply on forward and reverse search for the first matching string
n
Yeah, but my solution was to convert the line into a list of digits, and I first thus did not use the 2nd of overlapping words. That created the wrong answer (e.g. I first converted "3oneight" to [3, 1] instead of [3, 1, 8] and thus got a 31 instead of a 38.
d
my answer 1 and answer 2 differed by 1
➕ 1
n
Of course, reading the puzzle again it explicitly asked for "find first and find last", and thus does not seem to care about overlaps. Therefore, for "oneight" first is 1 and last is 8.
👍 1
Definitely was more complicated than I expected for Day 1 (but of course was lots of fun!)
➕ 3
x
Sneaky requirements for second part 😉 https://x.com/IsuruKusumal/status/1730481605750517798?s=20
n
embarrassed to have "eno|owt|eerht..." in my regxp
a
🎉 thanks all, for the pointers wrt searching from the back for replacements. since doing it only once from left to right breaks the find-last for cases like "twone" and "oneight"
j
Untitled.kt
Untitled.kt
👍 1
d
Okay, I started out by doing a string replacement, but fell into the trap of replacing oneight errouneously (I'm not ashamed 😄 )
Finally, I made a (rather long but intuitive) version where for each line I just greedily try to find the first and last digit or word resembling a digit. So for the first digit I look at indices 0..2 (inclusive) and if there's a digit in there, it must be the first since the shortest words ("one", "six"), have at least three letters. Then I (try to) find the lowest index of the first word that is a digit, keeping track of its digit representation. If this index is lower than 2 it must be the first digit, otherwise we would have found it with trick above. Then I (try to) find the lowest index of the first character that is actually a digit, keeping track of its digit representation. Having found these 2 indices, I take the smallest one and use that digit representation. It could be that either the character or the word is null (not present in the line), but they can't both be null, since each line must be valid so it must have at least 1 character or 1 word digit. Then I do the same for the last digit, but starting from the back, using 
lastIndexOf
instead of 
indexOf
and using 
maxBy
instead of 
minBy
m
you can still make the replacement strategy work if you replace a written out NUMBER with its VALUE surrounded on both sides by NUMBER again. e.g. one = one1one and eight = eight8eight so oneight becomes one1oneight becomes one1oneight8eight. it becomes clunky, but at least you can reuse the logic of part 1 after doing this step 🙂
Copy code
object Day1 : Challenge() {
    val parsed = input.lines()

    private fun List<String>.solve() = map { it.filter(Char::isDigit) }
        .sumOf { it.first().digitToInt() * 10 + it.last().digitToInt() }

    override fun part1() = parsed.solve()

    override fun part2() = parsed
        .map { replacements.fold(it) { line, (key, value) -> line.replace(key, "$key$value$key") } }
        .solve()

    private val replacements = listOf(
        "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,
    )
}
j
A colleague figured out very nice solution to the “oneight” problem and I think it’s beautiful:
Copy code
gsed -r -e "s/one/on1ne/g" -e "s/two/tw2wo/g" -e "s/three/th3ee/g" -e "s/four/fo4ur/g" ...
d
Well I guess you can just replace four with 4, because four has no overlap, etc.
m
the minimal replacement map is this:
Copy code
private val replacements = listOf(
    "one" to "o1e",
    "two" to "t2o",
    "three" to "t3e",
    "four" to "4",
    "five" to "5e",
    "six" to "6",
    "seven" to "7n",
    "eight" to "e8t",
    "nine" to "n9e",
)
plus1 1
n
Copy code
private fun three(input: List<String>, withLetters: Boolean): Int {
    val map = (1..9).associateBy { it.toString() }.toMutableMap()
    if (withLetters) 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
    )
    val pattern = map.keys.joinToString("|").toRegex()
    fun calibration(line: String): Int {
        fun IntProgression.digit() = firstNotNullOf { i -> pattern.find(line, i)?.let { map[it.value]!! } }
        val first = line.indices.digit()
        val last = line.indices.reversed().digit()
        return first * 10 + last
    }
    return input.sumOf { calibration(it) }
}
m
Refactored solution:
Copy code
package aoc2023

fun main() = day01(String(System.`in`.readAllBytes()).split("\n")).forEach(::println)

private fun day01(lines: List<String>): List<Any?> {

    val part1 = lines.sumOf { line ->
        line.mapNotNull(Char::digitToIntOrNull).let { it.first() * 10 + it.last() }
    }

    val digits = buildMap {
        listOf("one", "two", "three", "four", "five", "six", "seven", "eight", "nine").forEachIndexed { i, s ->
            val n = i + 1
            put(n.toString(), n)
            put(s, n)
        }
    }

    val part2 = lines.sumOf { line ->
        val first = digits.getValue(digits.keys.minBy { line.indexOfOrNull(it) ?: Int.MAX_VALUE })
        val last = digits.getValue(digits.keys.maxBy { line.lastIndexOf(it) })
        first * 10 + last
    }

    return listOf(part1, part2)
}

fun String.indexOfOrNull(s: String) = indexOf(s).takeIf { it >= 0 }
l
solution:
Copy code
fun main() {
    fun Pair<String, String>.replacement() = second + first.substring(1)

    fun findCalibrationCodePartOne(input: List<String>): Long {
        // Calculate the code
        var sum = 0L
        input.map { calibrationLine ->
            var firstDigit: Char? = null
            var lastDigit: Char? = null
            for (index in calibrationLine.indices) {
                calibrationLine[index].takeIf { it.isDigit() }?.let { digit ->
                    if (firstDigit == null) firstDigit = digit
                    lastDigit = digit
                }
            }
            sum += ("$firstDigit$lastDigit").toInt()
        }
        return sum
    }

    fun findCalibrationCodePartTwo(input: List<String>): Long {
        // Mapper
        val mapper = arrayOf(
            "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",
        )
        // Remap values
        val adjustedInput = input.map { oldCalibrationLine ->
            var newCalibrationLine = oldCalibrationLine
            for (index in oldCalibrationLine.indices) {
                mapper.forEach { mapperPair ->
                    val substring = oldCalibrationLine.substring(index)
                    if (substring.startsWith(mapperPair.first)) {
                        newCalibrationLine = newCalibrationLine.replace(
                            oldValue = substring,
                            newValue = substring.replaceFirst(mapperPair.first, mapperPair.replacement()),
                        )
                    }
                }
            }
            newCalibrationLine
        }
        return findCalibrationCodePartOne(adjustedInput)
    }

    val calibrationDocument = readInput("Day_01_calibration")
    println(findCalibrationCodePartOne(calibrationDocument))
    println(findCalibrationCodePartTwo(calibrationDocument))
}
t
Day01_kt.cpp
Day01_kt.cpp
@Michael de Kaste wouldn't the minimal replacement for two be 
t2o
in case of a 
twone
?
m
ah yes @Tolly Kulczycki, my input didn't have that so I guess the bug slipped by my problem haha
kodee happy 1
o
Look ahead regex
Copy code
```
fun main() {
    val filePath = Paths.get("input1.txt")
    val input = Files.readAllLines(filePath)
    val digitMap = (1..9).groupBy { it }.mapKeys { it.key.toString() }.mapValues { it.value.first() } +
            ("one,two,three,four,five,six,seven,eight,nine").split(",")
                .mapIndexed { index, value -> value to index + 1 }.toMap()

    val result = input.sumOf { line ->
        val matched = Regex("""(?=(\d|eight|one|two|three|four|five|six|seven|nine))""").findAll(line).toList()
        (digitMap[matched.first().groups[1]!!.value]!! * 10 + digitMap[matched.last().groups[1]!!.value]!!).toInt()
    }
    println(result)
}```
j
day01.kt
day01.kt
d
I wonder what the most 'optimal' solution would look like, maybe using a buffer and (for the first digit) starting at index 0 and scanning through the string: • If the character we are looking at is a digit, we're done and can use this digit • If it's a letter, it could be we've encountered a word resembling a digit, so ◦ we could use some kind of state machine where e.g. the character 'o' can transition to 'on' or "NO_DIGIT" (end state), while the character 't' can transition to 'tw', 'th' or "NO_DIGIT" if another character than 'w' or 'h' is encountered next
I'll see if I can devise a nice overengineered solution with this idea 😈
K 1
Got a working implementation, this is its heart:
Copy code
private val digitWords = listOf(
        "one", "two", "three", "four", "five",
        "six", "seven", "eight", "nine"
    )
    private val digitWordsReversed = digitWords.map { it.reversed() }

    private fun getFirstDigit(line: String): Int = getNthDigit(line, digitWords)
    private fun getLastDigit(line: String): Int = getNthDigit(line.reversed(), digitWordsReversed)

    private fun getNthDigit(line: String, words: List<String>): Int {
        var buffer = ""
        var expectedChars = words.map { it.first() }.toSet()

        line.forEach { c ->
            if (c.isDigit()) return c.digitToInt()

            if (!expectedChars.contains(c)) {
                buffer = ""
                return@forEach
            }

            buffer += c
            expectedChars = words.filter { it.startsWith(buffer) }.mapNotNull { it.drop(buffer.length).firstOrNull() }.toSet()
            if (expectedChars.isEmpty()) {
                return words.indexOf(buffer) + 1
            }
        }

        return -1
    }
So this builds up a buffer of characters which may end up forming a digit word, but as soon as a character is found that is not expected, it clears the buffer and continues:
Copy code
expectedChars = words.filter { it.startsWith(buffer) }.mapNotNull { it.drop(buffer.length).firstOrNull() }.toSet()
is a bit of cryptic way to get the set of next expected characters. If there are no more expected characters, it must mean we have completed a word and can convert it to its digit (just using the index of it in the list). The 
return -1
is actually never reached with this input. It could be streamlined a bit more, but for now it suffices
p
Part 1 was very straight-forward but the second part costs me too many code:
Copy code
private enum class Digits(val intValue: Int) {
    ONE(1),
    TWO(2),
    THREE(3),
    FOUR(4),
    FIVE(5),
    SIX(6),
    SEVEN(7),
    EIGHT(8),
    NINE(9)
}

private fun createWordIndexMapFor(line: String): Map<Digits, Sequence<Int>> = Digits.entries.associateWith { word ->
    Regex(word.name.lowercase()).findAll(line).map { it.range.first }
}.filter { matches -> matches.value.any { it > -1 } }

private fun Map<Digits, Sequence<Int>>.getMin(): Int {
    return this.minBy { it.value.min() }.key.intValue
}

private fun Map<Digits, Sequence<Int>>.getMinIndex(): Int {
    return this.minBy { it.value.min() }.value.min()
}

private fun Map<Digits, Sequence<Int>>.getMax(): Int {
    return this.maxBy { it.value.max() }.key.intValue
}

private fun Map<Digits, Sequence<Int>>.getMaxIndex(): Int {
    return this.maxBy { it.value.max() }.value.max()
}

private fun findFirstDigit(
    indexOfWords: Map<Digits, Sequence<Int>>,
    line: String,
    index: Int
): Int = when {
    indexOfWords.isEmpty() -> line[index].digitToInt()
    index == -1 -> indexOfWords.getMin()
    indexOfWords.getMinIndex() < index -> indexOfWords.getMin()
    else -> line[index].digitToInt()
}

private fun findLastDigit(
    indexOfWords: Map<Digits, Sequence<Int>>,
    line: String,
    index: Int
): Int = when {
    indexOfWords.isEmpty() -> line[index].digitToInt()
    index == -1 -> indexOfWords.getMax()
    indexOfWords.getMaxIndex() > index -> indexOfWords.getMax()
    else -> line[index].digitToInt()
}

 fun part2(input: List<String>): Int {
        return input.sumOf { line ->
            val indexOfWords = createWordIndexMapFor(line)
            val firstIndexInt = line.indexOfFirst { it.isDigit() }
            val lastIndexInt = line.indexOfLast { it.isDigit() }

            val first = findFirstDigit(indexOfWords, line, firstIndexInt)
            val last = findLastDigit(indexOfWords, line, lastIndexInt)

            "$first$last".toInt()
        }
    }
c
Felt slightly more involved than usual for a day 1 that did.
➕ 1
t
lowkey conspiracy theory but IMO the puzzle was kinda made to be hard for AI to figure out I tried it afterwards with both GPT-3.5 and 4 and both struggled hard with it if that is so then we can expect the next few days to be like this
n
Discovered two new functions today - findAnyOf findLastAnyOf. Great start :)
K 4
n
yeah, that is better than my regex approach. Here is my version using these 2 functions:
Copy code
private fun three(input: List<String>, withLetters: Boolean): Int {
    val map = (1..9).associateBy { it.toString() }.toMutableMap()
    if (withLetters) 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
    )
    fun calibration(line: String): Int {
        val first = map[line.findAnyOf(map.keys)!!.second]!!
        val last = map[line.findLastAnyOf(map.keys)!!.second]!!
        return first * 10 + last
    }
    return input.sumOf { calibration(it) }
}
🙂 1
👍 1
c
Day01pt2.kt
Day01pt2.kt
r
Copy code
fun part1(input: List<String>): Int {
    return input.sumOf {
        (it.find { it.isDigit() }.toString() + it.findLast { it.isDigit() }).toInt()
    }
}

fun part2(input: List<String>): Int {
    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,
        "1" to 1, "2" to 2, "3" to 3, "4" to 4, "5" to 5, "6" to 6,
        "7" to 7, "8" to 8, "9" to 9
    )
    return input.sumOf {
        val first = map[it.findAnyOf(map.keys)!!.second].toString()
        val second = map[it.findLastAnyOf(map.keys)!!.second].toString()
        (first + second).toInt()
    }
}
m
Copy code
fun part2() {
    val figures = listOf("one", "two", "three", "four", "five", "six", "seven", "eight", "nine")
    val nums = (1..9).map { it.toString() }
    val figMap = figures.associateWith { figures.indexOf(it) + 1 } + nums.associateWith { it.toInt() }

    val values = mutableListOf<Int>()
    inputList.forEach { line ->
        var firstIndex = Int.MAX_VALUE
        var lastIndex = Int.MIN_VALUE
        var firstValue = 0
        var lastValue = 0

        (figures+nums).forEach {
            if (line.contains(it)) {
                if (firstIndex != minOf(firstIndex, line.indexOf(it))) {
                    firstIndex = minOf(firstIndex, line.indexOf(it))
                    firstValue = figMap[it]!!.toInt()
                }
                if (lastIndex != maxOf(lastIndex, line.lastIndexOf(it))) {
                    lastIndex = maxOf(lastIndex, line.lastIndexOf(it))
                    lastValue = figMap[it]!!.toInt()
                }
            }
        }

        values.add("${firstValue}${lastValue}".toInt())
    }
    println(values.sum())
}
Unusually tricky Day 1.
p
Early(ish - I'm terrible at mornings) to solve, late to post. https://github.com/tKe/aoc/blob/main/kt/src/main/kotlin/year2023/Day01.kt I went with the reverse and indexOf approach for matching the last.
d
m
e
https://github.com/ephemient/aoc2023/blob/main/kt/aoc2023-lib/src/commonMain/kotlin/com/github/ephemient/aoc2023/Day1.kt 
indexOfLast
and 
lastIndexOf
are clearly different functions but it's a bit annoying when I write one expecting the other 😕
n
Played around with avoiding duplicates as much as possible -> abstracted away usages of 
findAnyOf
and 
findLastAnyOf
and passed them as params into separate fun. Though it may be harder to understand now.
p
Copy code
@AoKSolution
object Day01FindAnyOf : PuzDSL({
    part1 {
        lines.sumOf {
            val first = it.firstNotNullOf(Char::digitToIntOrNull)
            val last = it.lastOrNull(Char::isDigit)!!.digitToInt()
            10 * first + last
        }
    }
    part2 {
        val digits = listOf(
            "one", "two", "three", "four", "five",
            "six", "seven", "eight", "nine",
        ) + (1..9).map(Int::toString)

        fun Pair<Int, String>?.value() =
            if (this == null) 0
            else second.singleOrNull()?.digitToInt()
                ?: digits.indexOf(second).inc()

        lines.sumOf {
            val first = it.findAnyOf(digits).value()
            val last = it.findLastAnyOf(digits).value()
            10 * first + last
        }
    }
})
I opted to create an extension off the result of each so the flow of the code stays clear.
👍 1
t
Better late than never. I honestly didn’t find part 2 all that difficult. We will see how long I can keep up with the blog this year. New job. Lots of stuff going on in December. • Code • Blog
K 1
m
Sort of newish to advent of code… is there any extended test input that I could use to see why my part2 solution does not work? Because when I run it against the 7 test input strings I get the right answer.
r
t
add twone and eighthree to your test input and see if they resolve to 21 and 83 respectively
⭐ 1
m
hmm, indeed my code is not ready for that as I’m doing replacements so the second 
one
will not ever be replaced…. Thank you, will try it!
m
There’s no additional text input given beyond the one you already have. It can be a bit tricky but there’s no exact science to figuring out edge cases in your implementation. You can do a routine debug and walkthrough your solution, you can take note of the hint given when you submit - you’re told if it’s low, high, too high, too low, etc. In my case yesterday, my part 2 implementation could also solve my part 1, so I used that to figure out why my solution wasn’t working. In some cases I just get hints from AoC communities.
m
The adventofcode page does indeed suggest me to go to the subreddit, which is at this point filled with memes and geniuses solving it on esoteric hardware. Thanks kotlinlang community!
😂 1
K 2
j
Screenshot 2023-12-03 at 13.55.34.png
91 Views
Open in Slack
PreviousNext
Powered by