https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 9> :thread:
# advent-of-code
a
K 8
advent of code intensifies 4
m
Part 1 (initial)
Part 2 (initial)
Some premade utils came useful: 
Point
class, 
Direction
class, 
Point.move(Direction)
method, and 
Point.getAdjacent()
.
m
can't get my head around the inverted 0,0 coordinate starting from bottom left ..
b
Actually when you know head and tail aren't adjacent, you don't have to check whether 
x == x
or 
y == y
, just do
Copy code
(tailPos.x + (headPos.x - tailPos.x).sign) to (tailPos.y + (headPos.y - tailPos.y).sign)
m
@Monster Brain I didn't even notice that. It doesn't really matter, no matter how you see the coordinate grid, you will end up with the same number of visited positions.
@Bin Wang Good point!
Part 1 improved
Part 2 improved
a
I hope someone else has also written: 
head.move(step.first).let { tail.follow(it) }
😂
j
Love it!
s
Here's what I've come up with. Kudos to Kotlin for the 
windowed
function and for the `Int.sign`:
j
Nice use of windowed!
j
I was also thinking about 
.indices.windowed
and then decided that 
i, i+1
is not something that would justify having to create a list of pairs in memory so i ended up with the following. I also spent quite some time searching for 
Int.sign
since 
kotlin.math.sign
works just with 
Double
and there are no 
Int
overloads :(
c
Sets are super useful for all advent of code.
k
Soooo, I cleaned up my code. Made it more functional less imperative
message has been deleted
does this count as a one liner?
c
Managed to reduced my when switch hell to a one liner:
Copy code
class Day09 : AdventDay(2022, 9) {
    data class Knot(var x: Int, var y: Int) {
        var moveCallback : ((Pair<Int, Int>) -> Unit)? = null
        fun moveBy(diffX : Int, diffY: Int) {
            x += diffX
            y += diffY
            moveCallback?.invoke(x to y)
        }
    }
    private val allTail1Positions : MutableSet<Pair<Int, Int>> = mutableSetOf((0 to 0))
    private val allTail9Positions : MutableSet<Pair<Int, Int>> = mutableSetOf((0 to 0))
    private val knots : List<Knot> = List(10) {
        Knot(0, 0)
    }.apply {
        get(1).moveCallback = { allTail1Positions.add(it) }
        get(9).moveCallback = { allTail9Positions.add(it) }
    }
    private fun moveTail(head : Knot, tail : Knot) {
        val lenX = (head.x - tail.x)
        val lenY = (head.y - tail.y)
        if (max(lenX.absoluteValue, lenY.absoluteValue) > 1) {
            tail.moveBy(lenX.coerceIn(-1..1), lenY.coerceIn(-1..1))
        }
    }
    init {
        val lines = input.lines()
        val ropeCallOrder = knots.windowed(2, 1)
        fun List<List<Knot>>.timeEvolution(diffX: Int, diffY: Int, number: Int) {
            repeat(number) {
                knots[0].moveBy(diffX, diffY)
                forEach { (head, tail) -> moveTail(head, tail) }
            }
        }
        lines.forEach {
            val number = it.grabInts().first()
            when (it.take()) {
                "U" -> ropeCallOrder.timeEvolution(0, 1, number)
                "D" -> ropeCallOrder.timeEvolution(0, -1, number)
                "L" -> ropeCallOrder.timeEvolution(-1, 0, number)
                "R" -> ropeCallOrder.timeEvolution(1, 0, number)
            }
        }
    }
    override fun part1(): String {
        return allTail1Positions.size.toString()
    }
    override fun part2(): String {
        return allTail9Positions.size.toString()
    }
}
n
I decided to use a mutable data class for the knot positions, and then used
Copy code
private fun onetwo(input: List<String>, length: Int): Int {
    val rope = List(length) { Pos(0, 0) }
    val visited = mutableSetOf(rope.last().copy())

    for (line in input) {
        val cmd = line.split(" ")
        repeat(cmd[1].toInt()) {
            rope.first().move(cmd[0])
            rope.windowed(2).forEach { (h, t) -> t.follow(h) }
            visited.add(rope.last().copy())
        }
    }
    return visited.size
}
(with implementations for 
move
and 
follow
being very similar to code posted here, but updating the Pos objects.
d
That was better than yesterday 🙂
e
https://github.com/ephemient/aoc2022/blob/main/kt/src/commonMain/kotlin/com/github/ephemient/aoc2022/Day9.kt I was slowed down by a failure to read the problem statement properly, but in the end this was doable in a pretty nice way
k
(about my solution, scan is runningFold, my function predates the stdlib's one)
m
I remember when it was called scan in a preview built too iirc
or was that something else?
in any case, here's my 'functional' approach to the whole problem:
Copy code
data class Point(val y: Int, val x: Int)
object Day9 : Challenge() {
    val parsed = input
        .lineSequence()
        .map { it.split(" ").let { (a, b) -> a to b.toInt() } }
        .flatMap { (move, amount) -> generateSequence { move }.take(amount) }
        .map(::moveToDif)
        .runningFold(List(10) { Point(0, 0) }, ::moveRope)

    private fun moveToDif(move: String) = when (move) {
        "U" -> Point(-1, 0)
        "R" -> Point(0, 1)
        "D" -> Point(1, 0)
        "L" -> Point(0, -1)
        else -> error("unknown move")
    }

    private fun moveRope(rope: List<Point>, direction: Point): List<Point> = rope
        .drop(1)
        .runningFold(Point(rope.first().y + direction.y, rope.first().x + direction.x), ::fixTail)

    private fun fixTail(head: Point, tail: Point): Point {
        val yDif = head.y - tail.y
        val xDif = head.x - tail.x
        return when (max(yDif.absoluteValue, xDif.absoluteValue)) {
            2 -> Point(tail.y + yDif.sign, tail.x + xDif.sign)
            else -> tail
        }
    }

    override fun part1() = parsed.distinctBy { it[1] }.count()

    override fun part2() = parsed.distinctBy { it[9] }.count()
}
not sure about the fixtail part, could probably be better?
you could get away with running the whole problem for a rope of size 10 anyways and then requestion the positions later for both parts 😛 edit: which is exactly what I did
r
Anyone up for a highly OOP approach? Please forgive my snake_case... I'm a py-head
Day09.kt.cpp
c
Today and yesterday where much cleaner + obvious to solve with imperative code instead of functional. You can do them functionally, but it's far less transparent and more error prone.
j
k
@Michael de Kaste huh, apparently 
scan
is also in the stdlib, it just delegates to runningFold
d
state machine
message has been deleted
r
luckily my solution for part 2 still worked for part 1 as well 😅
m
@Dan Fingal-Surma fun Rope... can be substituted by a stdlib fun:
Copy code
MutableList(10){ Point(0, 0) }
is probably what you want 😄
k
oooh, with a capital M
m
yeah, its not mutableListOf() but actually constructing a list 🙂
r
List(10) { Point(0, 0) }
works too 🙂
m
yeah but he uses mutability
r
yeah true, but I had a similar thing in my code, where I was using the immutable variant, so thanks 😁
b
Learned 2 new things today 
MutableList(10) { Point(0, 0) }
and 
Int.sign
definitely adding those to my backlog 🙂 
Int.sign
is so much better then 
max(-1, min(n, 1))
...
Also created a utility function for my 
Point
class:
Copy code
fun walkTo(other: Point): Sequence<Point> {
        return sequence {
            var curr = this@Point
            while (curr != other) {
                curr += Point((other.x - x).sign, (other.y - y).sign)
                yield(curr)
            }
        }
    }
t
abs
and 
coerceIn
to the rescue. I thought about using something with 
Int.sign
as well but this feels way nicer 🙂
m
There aren’t so many ways to do this, so all the solutions will be pretty similar in how they work. Here’s mine 🙂
Copy code
package aoc2022

import kotlin.math.abs

fun main() {
    data class Pos(val x: Int, val y: Int) {
        fun diagonals() = sequenceOf(Pos(x - 1, y - 1), Pos(x + 1, y + 1), Pos(x - 1, y + 1), Pos(x + 1, y - 1))
        fun straights() = sequenceOf(Pos(x - 1, y), Pos(x + 1, y), Pos(x, y + 1), Pos(x, y - 1))
        fun dist(p: Pos) = abs(x - p.x) + abs(y - p.y)
        fun follow(head: Pos) = when {
            dist(head) >= 3 -> diagonals().minBy { it.dist(head) }
            dist(head) == 2 && head !in diagonals() -> straights().minBy { it.dist(head) }
            else -> this
        }
    }

    fun List<Pair<String, Int>>.move(knots: Int): Int {
        val rope = MutableList(knots) { Pos(0, 0) }
        val tailHistory = mutableSetOf(rope.last())

        for ((dir, n) in this) repeat(n) {
            with(rope.first()) {
                rope[0] = when (dir) {
                    "R" -> copy(x = x + 1)
                    "L" -> copy(x = x - 1)
                    "U" -> copy(y = y - 1)
                    else -> copy(y = y + 1)
                }
            }

            for (i in rope.indices.drop(1)) rope[i] = rope[i].follow(rope[i - 1])

            tailHistory += rope.last()
        }
        return tailHistory.size
    }

    with(generateSequence { readlnOrNull() }.toList().map { it.split(" ").let { (a, b) -> a to b.toInt() } }) {
        listOf(2, 10).forEach { println(move(it)) }
    }
}
x
NEED A BIGGER TABLE
a
went with a more functional approach, without overkill and without golfing it. using 
buildSet, fold, generateSequence, when's, heave.move, tail.follow(head)
here's my part 1: https://github.com/aneroid/advent-of-code-2022-kotlin/blob/943f72305886b1b12b879faeb7a99af033739425/src/Day09.kt think I can shimmy part 2 into that "let tail follow head" part, with windowed or something.
p
A little ropey, but here we are:
c
after a few refactors I'm ok with this solution snowball hehe
Day09.kt
n
ITT I learned about 
runningFold
. What a great addition to the standard library! I had previously used 
fold
with a 
MutableList
as the accumulator, then returning 
acc.apply { add... }
. But that was really kludgy so then I started just using 
buildList { myCollection.forEach { add... } }
. But 
runningFold
is what I wanted all along!
message has been deleted
m
that looks almost identical to my code 👀 great minds huh
n
Definitely. 🙂
d
I went with a quite literal approach, just implementing the business requirements with logical steps, not concerned with any optimization and it turned out okay, I think, if I can summarize it with something from my code, it would be this:
Copy code
if (head == tail || (abs(head.x - tail.x) <= 1 && abs(head.y - tail.y) <= 1)) return Point.ZERO
            return Point(head.x.compareTo(tail.x), head.y.compareTo(tail.y))
In previous years, I made a data class called Point which can also serve as a (2D) Vector, you can add Points together to get new Points
And the compareTo is a sneaky way to get -1, 0 or 1 which is the step needed for the tail
p
nice use of compareTo but I don't think there's anything to say it must return ±1 or 0. Pretty much guaranteed for Int though
d
I know the method implementation does not need to adhere to it, it can return any number, but I just cheated a bit here knowing it returns [-1, 0 1] 😉
n
I originally did 
x.coerceIn(-1..1)
, but others pointed out that 
x.sign
does the same thing.
d
Ah didn't know about that, I guess I can steal that one 🙂
This was knot the hardest puzzle I've encountered, but it took some time (I'll see myself out) 😄
m
Cool - looking at the other solutions, I see that I do indeed have a unique approach to how the tail follows the “path”. I must say that I do find it more intuitive than most of the other solutions. It is less clever, but more along the lines of the actual instructions. What say you? 🙂
Copy code
data class Pos(val x: Int, val y: Int) {
    fun diagonals() = sequenceOf(Pos(x - 1, y - 1), Pos(x + 1, y + 1), Pos(x - 1, y + 1), Pos(x + 1, y - 1))
    fun straights() = sequenceOf(Pos(x - 1, y), Pos(x + 1, y), Pos(x, y + 1), Pos(x, y - 1))
    fun dist(p: Pos) = abs(x - p.x) + abs(y - p.y)
    fun follow(head: Pos) = when {
        dist(head) >= 3 -> diagonals().minBy { it.dist(head) }
        dist(head) == 2 && head !in diagonals() -> straights().minBy { it.dist(head) }
        else -> this
    }

    fun move(dir: String) = when (dir) {
        "R", "L" -> copy(x = x + if (dir == "R") 1 else -1)
        else -> copy(y = y + if (dir == "U") 1 else -1)
    }    
}
d
So you just iterate over the possible moves to find the one which minimizes the distance?
j
I made good use of my 
Position
, 
Vector
and 
Heading
classes from earlier years.
Copy code
val p09 = suspend {
    val input = readInput("09.txt")
    solve(input, 2).print { "Part 1: $it" }
    solve(input, 10).print { "Part 2: $it" }
}

private fun solve(input: String, numKnots: Int): Int {
    val knots = Array(numKnots) { Position(0, 0) }
    val visited = hashSetOf(knots[0])
    input.lines().forEach { step ->
        val heading = when (step.substring(0, 1)) {
            "U" -> Heading.N
            "L" -> Heading.W
            "R" -> Heading.E
            "D" -> Heading.S
            else -> error("")
        }

        val numSteps = step.substring(2).toInt()
        repeat(numSteps) {
            knots[numKnots - 1] = knots[numKnots - 1].move(heading)
            (numKnots - 2 downTo 0).forEach {
                if (knots[it + 1].notAdjacentTo(knots[it])) {
                    knots[it] = knots[it] + (knots[it + 1] - knots[it]).sign
                }
            }
            visited.add(knots[0])
        }
    }
    return visited.size

}
a
think I can shimmy part 2 into that "let tail follow head" part, with windowed or something. (edited)
haha - thanks to lunch and more coffee, added a runningFold and now my part2 is nearly identical to my part1 💪 (and now the possible refactoring for part 1 & 2 is obvious; probably for everyone's solutions) https://github.com/aneroid/advent-of-code-2022-kotlin/blob/main/src/Day09.kt
g
Today was very nice puzzle. First, I thought what the hell is this? But then I could easily understand the requirements. I'm happy when solution for task 1 can be extendable to task 2. I see that several other people had quite similar solution to mine 🤘
SolutionDay9.cpp
d
I like puzzles where the parsing is at least easy as in this case. When we have to parse an entire grid up front, ugh.
@Grzegorz Aniol you might as well put that 
Point
class in a separate util file or library, I did once and needed it at least oncee every year since then 😄
j
Yet again it’s all about folding the input lines. Other than that, I love it when part 2 is a some kind of generalization of part1. That was the case today. 17 mins for part 1 and then one and half an hour to understand how to properly generalize it for part 2 :)
Untitled.kt
m
@Davio I do not like solutions which aren’t “self-contained”. I keep a template which I clone for a new puzzle, it comes with a few pre-defined private methods. And I have prepared a live template for the Dijkstra algorithm … soon to be used, I guess.
d
Last year we had Dijkstra or A* so maybe we'll see it again this year, I put generic things, like a 2D Point in my util file, because it comes back so so often
m
Sure. I think I’m faster though writing things like tuple classes than using something from a library. The problem is that what is in the library rarely fits in the use case of the puzzle perfectly. This year I’m starting to build live templates with placeholders. It works quite well for Dijkstra.
p
I’m with @Michael Böiers’s approach - I tend to try and keep each day (or solution for each day) self-contained so I can see everything needed up front. Searching and copy/paste is good enough for me if something needs reuse. Obviously this isn’t how I approach real work though 😉
m
There are three functions I have prepared as utils: md5-hashing, JSON-parsing and regex group matching. Those are nice to have because the syntax is weird and unintuitive (e.g. Java legacy). If those come up I’ll use and eventually inline them in the solution.
Here’s the dijkstra live template btw, if anyone is interested. Assume an MIT license 😉
Copy code
class State($STATE_CONSTRUCTOR$) {
    fun neighbors(): Iterable<State> {
        return $NEIGHBORS$
    }
}

var s = State()
val v = mutableSetOf<State>()
val u = mutableSetOf<State>()
val d = mutableMapOf(s to 0)

while (true) {
    s.neighbors().filter { it !in v }.forEach { n ->
        u += n
        val distance = d.getValue(s) + 1
        d.compute(n) { _, old -> min(distance, old ?: Int.MAX_VALUE) }
    }
    v += s
    u -= s
    s = u.randomOrNull() ?: break
}
s
j
Also - what puzzled me most 🙂 here’s the execution times (10th run on same VM, so it’s a bit warmed up):
Copy code
Day 1 part 1: 70698 in 0.000335s
Day 1 part 2: 206643 in 0.000387s
Day 2 part 1: 15337 in 0.000344s
Day 2 part 2: 11696 in 0.000336s
Day 3 part 1: 8109 in 0.000377s
Day 3 part 2: 2738 in 0.000314s
Day 4 part 1: 459 in 0.000417s
Day 4 part 2: 779 in 0.000388s
Day 5 part 1: ZRLJGSCTR in 0.000432s
Day 5 part 2: PRTTGRFPB in 0.000380s
Day 6 part 1: 1080 in 0.000191s
Day 6 part 2: 3645 in 0.001114s
Day 7 part 1: 1648397 in 0.001207s
Day 7 part 2: 1815525 in 0.001300s
Day 8 part 1: 1843 in 0.000738s
Day 8 part 2: 180000 in 0.002459s
Day 9 part 1: 6266 in 0.514819s
Day 9 part 2: 2369 in 0.166540s
Notice that the part 1 of day 9 executes OVER HALF A SECOND… (when the rope is just 2 knots long) and 1/3 of that time in part 2 (when it’s a 10 knots long). Is it the same in your case? The culprit is of course the Set<Points> that collects the trail left by the last knot.
f
@Jakub Gwóźdź I got the exact same thing reg part 1 and part2. I have a warn up routine where I run everything, and then AFTER that:
I initially implemented part 1 with a Pair and converted to a List when doing part1. The Pair-variant also used around 500ms
the set keeping track of visited in part1 is 3 times as big as part2
d
Depends on which I run first:
Copy code
2427
Took 148 ms
5513
Took 12 ms
This is with part 2 run first, then part 1 is a breeze
With part 2, the tail end doesn't wag as much I think 🙂
j
Yeah, the “bonuses” of functional programming. When I switched from 
moves.fold(State) {...}
that created new state (with set inside) on every move to just a 
moves.forEach() {...}
that modifies a mutableSet in only one instance, suddenly it’s back to under reasonable 7ms
f
@Davio no difference in which is running first (both are run in init prior to the times above)
the “bonuses” of functional programming
- yupp
d
With my very crude benchmark, it seems to settle around:
Copy code
5513
Took 3 ms
2427
Took 16 ms
Which is part 1 first, then part 2
f
initially I thought the time was spent calculating the distance, so I switched to a simpler 
diff.y.absoluteValue <= 1 && diff.x.absoluteValue <= 1 -> tail
- but this had no affect
d
Some very minor optimzation I added was to only (try) to add the new tail's position to the set if it actually moved
f
with mutable set @Jakub Gwóźdź
🤯
j
yeah. similar. kind of sad, because I really love working on immutable data 🙂
f
nod
m
Immutability begets copying … who knew 😉
d
Immutability is a fantasy, because your computer is one giant state machine 😉
e
my solution is immutable except for a few primitives, and runs in 1ms (part 1) - 2ms (part 2)
m
Same roughly
Immutability is fine imho, yeah if you are really trying to optimize you do mutable stuff, but then again, you should also move away from 'idiomatic' kotlin since you will be doing plain for loops and vars
p
I have two solutions to today - one using immutable 
Rope
structure and 
foldRunning
and another using an 
IntArray
for state.
Copy code
year 2022 day 9 warmup (3000 iterations) took 22.824483343s
year 2022 day 9 part 1 (Arrays) took 1.186119ms: 6037
year 2022 day 9 part 1 (ImmutableRope) took 2.227789ms: 6037
year 2022 day 9 part 2 (Arrays) took 1.114141ms: 2485
year 2022 day 9 part 2 (ImmutableRope) took 2.874673ms: 2485
basic benchmarking - not accurate by any stretch.
j
@ephemient that really is great solution (although it took me a while to understand what’s going on there 🙂 )
f
@ephemient one cool thing is that your solution does not (try) to move all subsequent knots if the prior knot isn't moved. like that. also your initial 
moves
is so nice - which I had thought of just converting to a path right away instead of iterating "commands". very nice!
d
Oh yeah, I'm totally stealing the "only move knots if the previous one moved" part 🙂 Since I look at the threads after I (naively) solved the puzzle myself, I think that's OK 😛
e
honestly that's one of the things I stole from myself as I was implementing the solution multiple times 😄
h
My solution for day9. Second part took twice bigger time, then first. Initially i implemented solution where tail moves to previous head position, tried same approach for second part, but it didn't work. So needed to rewrite all for second part.
Copy code
import lib.Point

fun getMoves(input: List<String>): List<Pair<Char, Int>> {
    return input.map {
        val (dir, moveSize) = it.split(" ")
        Pair(dir.first(), moveSize.toInt())
    }
}

fun part1(input: List<String>): Int {
    return followHead(2, getMoves(input))
}

fun part2(input: List<String>): Int {
    return followHead(10, getMoves(input))
}

fun Point.updateHead(dir: Char): Point {
    return when (dir) {
        'R' -> toRight()
        'L' -> toLeft()
        'U' -> higher()
        'D' -> lower()
        else -> error("Invalid direction")
    }
}

fun Point.followIfBeyond(f: Point, distance: Double = 1.5): Point? {
    return if (this.distanceTo(f) < distance) {
        null
    } else Point(
        x + sign(f.x - x.toDouble()).toInt() * min(abs(f.x - x), 1),
        y + sign(f.y - y.toDouble()).toInt() * min(abs(f.y - y), 1)
    )
}

fun followHead(ropeSize: Int, moves: List<Pair<Char, Int>>): Int {

    val rope = MutableList(ropeSize) { Point(0, 0) }
    val tailPoints = HashSet<Point>().apply {
        add(rope.last())
    }

    for ((dir, steps) in moves) {
        repeat(steps) {
            rope[0] = rope[0].updateHead(dir)

            for (i in 1 until ropeSize) {

                rope[i].followIfBeyond(rope[i - 1])?.let {
                    rope[i] = it
                    if (i == ropeSize - 1) {
                        tailPoints.add(rope.last())
                    }
                } ?: break

            }
        }
    }
    return tailPoints.count()
}
e
while optimizing my Python solution I had that idea, and it sped up my Kotlin and Rust solutions too
(didn't speed up my Haskell solution, but I found a different optimization there)
d
For my solution, I could luckily easily change it, only needed to replace a forEach over all the knots with a takeWhile 🙂
e
or 
break
out of a regular 
for
loop, but yes it shouldn't be hard 🙂
d
It would have been pretty sneaky if they added moves such as 
R 0
😄
e
I think my approach handles that fine
d
Oh yeah, mine too, but it would so some unnecessary processing
e
my Rust solution actually handles 
R -1
as well, but that's definitely unnecessary 😄
d
Hmm, I think mine does too, more so by accident than by design 😄
m
My code would break due to the whole
Copy code
generateSequence{ move }.take(count)
part in my code 😂
p
A quick play with something akin to @ephemient’s sequence approach to see how my 
Rope
compared -
Copy code
year 2022 day 9 warmup (1000 iterations) took 12.776440358s
year 2022 day 9 part 1
	 Arrays took 1.160782ms: 6037
	 Sequences took 1.669952ms: 6037
	 ImmutableRope took 2.652892ms: 6037
year 2022 day 9 part 2
	 Arrays took 1.220136ms: 2485
	 Sequences took 2.152197ms: 2485
	 ImmutableRope took 3.810463ms: 2485
p
c
After the diagonal didn’t work for Part 2 I decided I’d had enough of the maths and went with a different approach where I compared surrounding coordinates to work out where to move to. Seems to work. Only after reading here did I see 
coerceIn
and 
sign
which would have helped a lot. Ah well.
Copy code
import kotlin.math.abs

private val input = readFileAsLines("9.txt")
    .map {
        val (direction, amount) = it.split(" ")
        direction to amount.toInt()
    }


fun main() {
    println("Part 1: ${part1()}")
    println("Part 2: ${part2()}")
}

private fun part1() = simulateRope(2)

private fun part2() = simulateRope(10)

fun simulateRope(size: Int): Int {
    val tailCoordinates = mutableSetOf<Coordinate>()
    val coordinates = MutableList(size) { Coordinate(0, 0) }

    for ((direction, amount) in input) {
        repeat(amount) {
            when (direction) {
                "U" -> coordinates[0] = coordinates[0].above()
                "D" -> coordinates[0] = coordinates[0].below()
                "L" -> coordinates[0] = coordinates[0].toLeft()
                "R" -> coordinates[0] = coordinates[0].toRight()
            }
            for (i in 1 until coordinates.size) {
                coordinates[i] = coordinates[i].moveTowards(coordinates[i - 1])
            }

            tailCoordinates.add(coordinates.last())
        }
    }

    return tailCoordinates.size
}

fun Coordinate.toRight() = Coordinate(x + 1, y)
fun Coordinate.toLeft() = Coordinate(x - 1, y)
fun Coordinate.above() = Coordinate(x, y + 1)
fun Coordinate.below() = Coordinate(x, y - 1)

fun Coordinate.moveTowards(other: Coordinate): Coordinate {
    if (abs(x - other.x) > 1 || abs(y - other.y) > 1) {
        val around = getSurroundingCoordinatesIncDiagonals().toSet()
        val aroundOther = other.getSurroundingCoordinatesIncDiagonals().toSet()
        val intersected = (around intersect aroundOther).toList()

        return intersected.firstOrNull { it.x == x && it.x == other.x }
            ?: intersected.firstOrNull { it.y == y && it.y == other.y }
            ?: intersected.first { it.x != x && it.y != y }
    }
    return this
}
a
I hope someone has done a Snake animation for this one 🤩 and sent it to Sebastian to show on the livestream I'll settle for a println done per knot per step
simplified my 
follow
to just:
Copy code
private fun Point.follow(head: Point): Point =
    if ((head.x - x).absoluteValue > 1 || (head.y - y).absoluteValue > 1)
        Point(x + (head.x - x).sign, y + (head.y - y).sign)
    else
        this
the other equality checks for x & y are not needed since 
(head.x - x).sign
is 
0
when they're the same https://github.com/aneroid/advent-of-code-2022-kotlin/commit/6a35d287
and just for fun, doing it with 100 knots, unique tail positions:
Copy code
100 knots test  : 1
100 knots testP2: 1
100 knots actual: 354
k
Anyone else used 
scanIndexed
? Full code here
w
i wrote my own Location class for part 1, and it worked perfectly for part 2 as well
Copy code
data class Location(val x: Int, val y: Int) {
    fun moveUp(): Location {
        return this.copy(y = y + 1)
    }

    fun moveDown(): Location {
        return this.copy(y = this.y - 1)
    }

    fun moveLeft(): Location {
        return this.copy(x = x - 1)
    }

    fun moveRight(): Location {
        return this.copy(x = x + 1)
    }

    fun chase(otherLocation: Location): Location {
        val xDelta = otherLocation.x - x
        val yDelta = otherLocation.y - y
        if (abs(xDelta) > 1) {
            return Location(
                x = x + xDelta.sign,
                y = y + yDelta.sign
            )
        }
        if (abs(yDelta) > 1) {
            return Location(
                x = x + xDelta.sign,
                y = y + yDelta.sign
            )
        }
        return this
    }
}
p
@Kevin Del Castillo quite a few people have used 
runningFold
(which is the an alias for 
scan
) but not sure I’ve seen any 
runningFoldIndexed
or 
scanIndexed
l
i spent wayyy too long with the ‘move diagonally’, woof. also totally missed 
Int.sign
from kotlin.math. time to finish day 8 part 2 😅
n
I stole @ephemient's idea of using a 
Sequence
for 
follow
. Now my code is a world's tour of 
Sequences
, using 
asSequence {}
, 
sequence {}
, and 
generateSequence()
in different parts. It also features a 
Sequence
within a 
Sequence
!
k
@phldavies is it a bad thing? Mainly asking out of curiosity as I saw a use case for 
scanIndexed
, but you mentioned two other methods, could they replace 
scanIndexed
in my solution?
p
Not a bad thing at all - 
scan{Indexed}
was renamed to 
runningFold{Indexed}
to be more consistent with 
fold{Indexed}
From the stdlib:
Copy code
@SinceKotlin("1.4")
@WasExperimental(ExperimentalStdlibApi::class)
public fun <T, R> Sequence<T>.scan(initial: R, operation: (acc: R, T) -> R): Sequence<R> {
    return runningFold(initial, operation)
}
k
d
Ah yes, 
MutableList(10){ Point(0, 0) }
… I kept reaching for 
mutableListOf(10) { Point(0, 0) }
which did not work
n
Sequences are like lengths on a figurative rope bridge. They just sit there all linked up doing nothing until something snaps and suddenly they're all whipping about.
p
Switched out my 
mutableSetOf<Int>
for a 
BitSet
and cantor-pairing the zigzag-encoded coordinates. Part2 is now less than 0.5ms
Copy code
year 2022 day 9 warmup (2000 iterations) took 16.602969683s
year 2022 day 9 part 1
	 Arrays took 191.41us: 6037
	 Sequences took 1.445318ms: 6037
	 ImmutableRope took 2.111331ms: 6037
year 2022 day 9 part 2
	 Arrays took 427.744us: 2485
	 Sequences took 1.945550ms: 2485
	 ImmutableRope took 2.256112ms: 2485
t
I'm late with the write-up today because of work and I've been fighting off a headache all day. Despite all that, I think this is one of my favorite ones of the year so far! • Blog • Code
k
parseInput() 😉 👍
x
Who else had to rewrite for part 2 because they cheesed part 1? 🙋 😅 https://github.com/xxfast/advent-of-code-22/commit/2e9b59f4346de41a8e025e1e9e29f6043146e875
n
I rewrote because I have an obsessive compulsion. My part 1 code worked just fine for part 2...except for a stupid movement bug that took me 45 minutes to figure out, even being mindful of the warning in the directions that part 2 introduced new kinds of movements.
l
@Neil Banman same, i had to print out each step to figure out what mine was doing compared to the example. prior to that i was just moving the knot to where the previous knot had been, which is valid for pt1 but not for pt2.
n
@Luke Armitage Mine tried to follow the movement rules, rather than just copy, but I overlooked the case where the Manhattan distance was 4, which was not possible with just two knots.
@Luke Armitage I also had to print out each step. I already had an 
Iterable<Char>.printToConsole()
utility function, but my code calculated each tail successively. It was difficult to make make all the knots appear on the same step. I eventually figured it out, but it was frustrating.
j
part1 and part2 use the same code except that part1 uses a rope of size 2 and part 2 uses a rope of size 10 https://github.com/jbotuck/aoc2022/blob/main/src/Day09.kt
24 Views
Open in Slack
PreviousNext
Powered by