https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 4> :thread:
# advent-of-code
a
m
Part 1
Part 2
Feels like we are out of "weekend problems are harder" now.
j
I’m not sure if there is a challenge today if you know your libraries, basically kotlin stdlib (`split`+`intersect` +`shl`) solved it today for me… but now I found out I was lucky not to have repetitions in the sets, otherwise I’d be in trouble 🙂
day4.kt
day4.kt
n
Yeah, this was much easier than expected. For part 2, I added a count to my Card class (initialized to 1), and then simply did
Copy code
cards.forEachIndexed { index, card ->
  (1..card.wins).forEach { cards[index +  it].count += card.count }
}
return cards.sumOf { it.count }
j
@Norbert Kiesel uuuuuh, var in data class, living on the edge, aren’t we 🙂
n
actually, not a data class:
Copy code
class Card(val wins: Int, var count: Int = 1)
But yeah, sometimes use mutable data classes as well
👍 1
j
I must say, again the most time I spent on parsing (also the only one mistake I did was with
Copy code
fun String.ints() = split(" ").map { it.toInt() }
which failed on 
...65  6 55...
and required additional `.filterNot { it.isBlank() }`…
m
I have the same solution as @Jakub Gwóźdź, down to the detail haha
Copy code
object Day4 : Challenge() {
    private val parsed = input.lines().map { line ->
        line.split("\\D+".toRegex()).drop(1).map(String::toInt).let { numbers ->
            numbers.subList(1, 11).intersect(numbers.subList(11, 36).toSet()).indices
        }
    }

    override fun part1() = parsed.sumOf { 1.shl(it.last + 1) }

    override fun part2() = IntArray(parsed.size) { 1 }.apply {
        parsed.forEachIndexed { index, winningNumbers ->
            winningNumbers.forEach {
                this[index + it + 1] += this[index]
            }
        }
    }.sum()
}
n
Initially, my Card class also had 
winning
and 
mine
properties, but then saw that we just need the size of the intersection. And my "extract numbers" is
Copy code
fun nums(line: String) = Regex("""\d+""").findAll(line).map { it.value.toInt() }.toSet()
❤️ 1
m
I keep forgetting 'findAll' is a thing blob think smart
n
@Jakub Gwóźdź: you could have used 
split(Regex(" +"))
to avoid the filter
same 1
j
Part 2 I messed the counting up multiple times, the code is still not pretty https://github.com/bulldog98/advent-of-code/blob/main/advent2023/src/main/kotlin/year2023/Day04.kt
d
j
@Norbert Kiesel I know, I just felt like I don’t want to employ regex 🙂 (really, it was mostly about feelings, not facts)
d
Should have used 
shl
instead of using 
pow
m
d
MutableList(lines.size) { 1 }
, that’s what I was looking for
turns out you don’t need bounds checking for doubling cards > the total # of cards
true story 1
I put it in being like, surely they will trip people on that
j
@Dan Fingal-Surma wellll. yes. apparently the input data files were kind enough to omit that trap 🙂
(but the puzzle description didnt say anything about it so it could have been a case)
p
Love seeing all the functional programming approaches. I'm still trying to train my brain to be more functional. Here's my little imperative approach for fun. not sure why part 2 took me as long as it did but my brain stopped working at one point haha
e
https://github.com/ephemient/aoc2023/blob/main/kt/aoc2023-lib/src/commonMain/kotlin/com/github/ephemient/aoc2023/Day4.kt I originally had a 
runningFold
pushing the counts forward, but simplified it down to a single mutable array of counts
d
Cleaned it up a bit
🙌 1
n
@Jakub Gwóźdź: I interpreted the "Cards will never make you copy a card past the end of the table." rule to not needing a range check.
➕ 2
j
@Peter Duong since you have a 
var
, it’s not too functional yet, but there is an opportunity to introduce 
fold
instead. (Although it will be probably less optimal)
@Norbert Kiesel haha, I managed to omit this line when skimming the puzzle text 🙂
m
I went for a score lookup map because I saw from the data that we could never have more than 10 matching numbers. Especially in trepidation of some or other exploding thing that makes me do lots of pow calculations. Then in part two I had an IntArray with tallys and just ran through from top to bottom incrementing future tallys.
d
Okay, for part 1, I'm quite happy that 2 pow -1 (which is 1/2), converted to an Int is just 0 😉
My part 1 can be summarized by this line:
Copy code
fun getScore(): Int = 2.0.pow(myNumbers.intersect(winningNumbers).size - 1).toInt()
y
Today's task is easier than the first day
r
p
SPOILER_image-1.png
d
There is a periodicity, I find this one easier than yesterday, and 2 was easier than 1. I sacrificed performance a bit for readability today and ended up with this at its heart:
Copy code
override fun part2(): Int {
        val totalCopies = cards.associateWith { 1 }.toMutableMap()
        totalCopies.forEach { (card, total) ->
            val idsOfCopies = card.getIdsOfCopies()
            idsOfCopies.forEach { id ->
                val copy = Card(id)
                totalCopies[copy] = totalCopies.getValue(copy) + total
            }
        }
        return totalCopies.values.sum()
    }
This just keeps a running count of number of copies of each card, starting with 1. As the table is scanned from top to bottom, we only have to increase the running totals of the IDs that match. So in the example, #1 has 4 winning numbers, so we increase the totals of cards 2, 3, 4 and 5. Then we get to #2 and see it has 2 copies so we need to increase the winning cards ID totals with 2, etc
p
Nice quick one today - used an 
IntArray
to track copies as a map felt overkill. year 2023 day 4 part 1 Default took 488.366us (1.00x): 23673 year 2023 day 4 part 2 Default took 402.9us (1.00x): 12263631 > note: this was missing a 
.filter { it > 0 }
in part 1, however I ended up with an even number of non-winning cards which resulted in an even number of 
1 shl -1 == Int.MIN_VALUE
which summed to 0 and didn't impact my result
y
You could just go backward, the most right card will have no produced cards, while other cards will be guaranteed to have all produces cards calculated
x
d
These kinds of challenges are nice to discover some otherwise unused (extension) functions in the standard library, there are many ways to find the amount of elements from set A that are also in B, such as 
setA.count { setB.contains(it) (or it in setB) }
, but I quite like 
setA.intersect(setB).size
it might not be optimal as we don't really need a new set, only the number of matches, but it's a fun and straightforward way to get it
K 1
j
So I was curious if it is easy and clean to go purely functional without any 
var
, any side effect, just 
map
and 
fold
, and yes it is. following is the excerpt, sans boring parsing: The interesting thing in part2 is, I pass only the important data in fold’s accumulator, immediately forgetting about the copies of cards already calculated. I believe it’s pretty optimized now EDIT: Fixed mistake discussed below
purelyFunctionalV2_kt.kt
d
I also kept track of the IDs of the cards, never knowing what kind of shenanigans would appear in part 2, but I guess their ID is always just their index in the list + 1
@Jakub Gwóźdź I see you found a stylish way to calculate 2 to the N - 1th power 😉
But won't it yield the wrong result for part 1? If there are no matches, 
1 shl -1
returns 
Int.MIN_VALUE
?
j
no, 
1 shl -1
is basically 
1 / 2 => 0
nono 1
differences may occur on negative numbers
m
it makes Int.MIN_VALUE for me tho 😉
might be kotlin/java version decrepancy
j
HUH
no you’re right. So why is my code workign….
p
Likely integer rollover - I lost my 
.filter { it > 0 }
when refactoring and didn't notice as my answer came out the same.
I have an even number of zero-scoring cards - which results in adding 
Int.MIN_VALUE
an even number of times, which ends up overflowing to 
0
p
d
Now Jakub can claim that he already knew in advance there was an even number of cards without matches and this was just a stroke of genius 😄
j
no, apparently I had more luck than I deserved 🙂
p
Fixed part1 to include the missing filter :)
Day04.kt
j
I heard @Sebastian Aigner talk so much about his off-by-one errors, I'm happy to say I finally had one as well in this task. (Line 21 in https://github.com/JBeet/MyAdventOfCode2023/blob/main/src/Day04.kt )
1️⃣ 1
😅 1
r
I'm really not comprehending what part2 wants
j
sweet lords, I was soooo lucky with the 
1 shl -1
, I thought it will be equivalent of 
1 shr 1 => 0
, while the docs clearly say:
Note that only the five lowest-order bits of the bitCount are used as the shift distance. The shift distance actually used is therefore always in the range 0..31.
and 5 lowest-order bits of -1 (
0b11111111111111111111111111111111
) equal to 31. now 
1 shl 31
is effing far from 
1 shr 1
😆
👍 1
d
@Rafs part 2 wants you to keep copying cards, so if card 1 has 4 matching numbers, you create extra copies of the next cards, 2 to 5. Now you evaluate card 2, but you have an extra copy. So if the original card 2 had 2 matches, you now have 4 matches total, 2 from the original and 2 from the copy. This means you create copies of 3 and 4 twice. You already created copies of 3 and 4 because of card 1. So you now have 1 instances of card 1, 2 of card 2, 3 of card 3 and 3 of card 4, etc. When you get to all instances of card 3 you do the same thing
p
Ah but @Jakub Gwóźdź, 
(1 shl 31) + (1 shl 31) == 0
😄 so either Eric was feeling generous and always included multiples of 2 non-winning cards or 50/50 luck 😉
😀 1
r
@Davio so when you win a copy of the card, will you still be checking the extra card against the winning numbers of the original card?
p
p
Every time you win a card, you win the cards that card wins too - i.e. Card 1 wins you a copy of Card 2 (in addition to the Card 2 you already had), so you have two copies of Card 2, each of those copies wins you a copy of card 3 and card 4 - so you end up with 2 more card 3s, and 2 _more card 4s ... etc)
👍 1
d
I also initially thought that shl with a negative number would just be a shr, so this was pretty surprising
j
I love the fact that yet again I learned something new about kotlin - thank y’all ❤️
K 2
a
I added the 'current card counts' as the number I increment the other counts by. fairly straightforward, didn't do anything fancy. definitely easier to parse and solve than day 3. I suppose we could refactor till it fits part 1 & 2 perfectly in hindsight, like not really storing the index or not storing the original cards and storing only the intersects 
Card = List<Int>
(but that feels like we're lying about how we did it for part 1 😂 )
did everyone get the same card count in their puzzle input? I got 204
p
Nope
Copy code
@Test
  fun part1() {
    Day4.solvePart1() shouldBeExactly 25174
  }

  @Test
  fun part1TestInput() {
    Day4.solvePart1(testInput) shouldBeExactly 13
  }

  @Test
  fun part2() {
    Day4.solvePart2() shouldBeExactly 6420979
  }

  @Test
  fun part2TestInput() {
    Day4.solvePart2(testInput) shouldBeExactly 30
  }
p
I had 210 cards
👍 1
d
For my part 2 I ended up with ~ 13 million cards
📈 1
p
Aww, I only "won" 12,263,631 cards 😞
d
Now I'm curious about the biggest winner 😄
😂 1
Although my computer doesn't feel like a winner computing it all, luckily it still does so in less than half a second
p
I got a part2 solve time of 
402.9us
(after warming up the VM, 
~1.3ms
cold)
d
Ah I refactored a bit and now it only counts the time actually solving, not the time that also includes copy-pasting the answer to my clipboard which I do cause I'm lazy 😄
Copy code
val contents = StringSelection(result.toString())
Toolkit.getDefaultToolkit().systemClipboard.setContents(contents, null)
for those that are interested...
👍 2
j
1.6ms cold, 0.9ms warm (empty data), 0.3ms warm (real data)
t
SPOILER_day04.part1.kt.png,SPOILER_day04.part2.kt.png
s
IMG_20231204_154128_773.png
s
I ended up with this after many cleanings. First AoC for me, and after the experience of the previous days I was randomly keeping track of the card IDs in part 1 😅 Trying to figure out if this would be more efficient with 
intersect
Copy code
fun main() {
    val cards = readInput("Day04")

    val cardsInfo = buildList {
        cards.forEach { card ->
            val (winningNumbers, myNumbers) = card.split(":").last().split("|")
                .map { it.trim().split("\\s+".toRegex()).map(String::toInt) }

            val count = winningNumbers.count { it in myNumbers }
            add(Pair(count, 1))
        }
    }.toMutableList()

    cardsInfo.forEachIndexed { index, pair ->
        (index + 1 until index + pair.first + 1).forEach { i ->
            cardsInfo[i] = cardsInfo[i].copy(second = cardsInfo[i].second + pair.second)
        }
    }

    println("Part 1 answer: ${cardsInfo.sumOf { (count, _) -> if (count == 0) 0 else 1 shl (count - 1) }}")
    println("Part 2 answer: ${cardsInfo.sumOf { it.second }}")
}
o
Copy code
Kotlin
val input = File("input1.txt").readText()
val lines = input.split("\n").dropLast(1).map {
    it.split(": ")[1].trim()
}
fun main() {
    println(lines.mapIndexed { index, s ->
       val sum= processLinePart2(s, index)
        sum
    }.sum())
}
val cache = mutableMapOf<Int, Int>()
fun processLinePart2(line: String, lineNumber: Int): Int {
    cache[lineNumber]?.let { return it }
    cache[lineNumber] =
        getMatchingCardForLine(line).let { numberOfMatchingCards ->
             1 + (lineNumber + 1..lineNumber + numberOfMatchingCards).sumOf {
                processLinePart2(lines[it], it)
            }
        }
    return cache[lineNumber]!!
}
fun processLinePart1(line: String, lineNumber: Int): Int {
     getMatchingCardForLine(line).let {numberOfMatchingCards ->
         return  2.0.pow(numberOfMatchingCards.toDouble()-1).toInt()
    }
}
fun getMatchingCardForLine(line: String): Int {
    return line.split(" | ").let {
        it[0].trim().split(Regex("\\s+"))
            .map { it.trim().toInt() }.toSet()
            .intersect(it[1].trim().split(Regex("\\s+")).map { it.trim().toInt() }.toSet()).size
    }
}
a
did everyone get the same card count in their puzzle input?
I got 204
I meant number of cards in the input aka rows 🙂
Now I'm curious about the biggest winner 😄
not me then. puzzle answer was only 5,744,979
j
5747443 for me
📈 1
c
8549735 for me
g
n
@Anirudh I got 214
🙏 1
📈 1
t
Solved and written up over my lunch break (which I need to conclude, so I'll catch up on this thread this evening!). • Code • Blog
t
managed to cut out one of the for loops which was useless and eating my time up
d
Part 1
Copy code
fun main() {
    File("src/_2023/day4/input.txt")
        .readLines()
        .sumOf { line ->
            val tokens = line.split(Regex(" +")).drop(2)
            val winningNumbers = tokens.takeWhile { it != "|" }.map { it.toInt() }
            val numbers = tokens.takeLastWhile { it != "|" }.map { it.toInt() }
            val count = winningNumbers.count { it in numbers }
            2.0.pow(count - 1).toInt()
        }
        .printed()
}
K 1
Part 2
Copy code
fun main() {
    File("src/_2023/day4/input.txt")
        .readLines()
        .map { line ->
            val tokens = line.split(Regex(" +")).drop(2)
            val winningNumbers = tokens.takeWhile { it != "|" }.map { it.toInt() }
            val numbers = tokens.takeLastWhile { it != "|" }.map { it.toInt() }
            winningNumbers.count { it in numbers }
        }
        .reversed()
        .fold(emptyList<Int>()) { acc, winCount ->
            val count = 1 + (0..<winCount).sumOf { acc[it] }
            listOf(count) + acc
        }
        .sum()
        .printed()
}
K 4
j
☝️ This is my favorite solution 👏
n
I really like that part2. I originally tried to come up with a fold or recursive solution but wasn't smart enough to figure it out. The guys trying to avoid mutation will like this one!
a
the advantage of doing 
sumOf { ... 2.0.pow(count - 1).toInt() }
over 
sumOf { ... 2.0.pow(count - 1) }.toInt()
is that having an inner 
.toInt()
converts all the 0.5's to 0's for 
2.0.pow(-1)
so we then don't need a 
count == 0
check 👏
👍 1
e
or just bitshift again, 
1 shl count shr 1
doesn't need floating point and doesn't need an 
== 0
check
K 6
➕ 1
31 Views
Open in Slack
PreviousNext
Powered by