https://kotlinlang.org logo
Join Slack
Powered by
:boom:Day 17 solution thread:brain:
# advent-of-code
b
💥Day 17 solution thread🧠
n
I'm somewhat embarassed to post my solution here because I literally just copy and pasted for parts A and B...
I'd need to think a bit more about how to make all the generics work out so that you can use the same code for both parts, but still be "strongly typed", i.e., without simply using List<Int> to represent coordinates (this is a big loss in typed information since a List<Int> can be any length, vs a Point3 or a Point4)
This would be a really nice time to have a type system where values can be part of a type, e.g. like in C++ std::array<Int, N>
d
y'all I've got 4 nested 
for
statements in part 2 so anything's gotta be prettier than that
n
You can do prettier stuff if you switch from a Point3 or Point4 dataclass ot just using lists for the coordinates
or at least, it won't be as repetitive, not sure if it will be that much prettier 🙂 but less type safe
d
help a functional newb out - how do you do this in functional programming?
Copy code
count = 0
for (i in mx until sx) {
    for (j in my until sy) {
        for (k in mz until sz) {
            for (p in mw until sw) {
                if (mm[i][j][k][p] == '#') count++
            }
        }
    }
}
(ignore that bad variable names - cuz -- for me -- fast means less typing)
n
probably using groupingBy
well, maybe not actually, I'm not sure.
🤔 1
d
luckily - part 2 was super easy for me -- just add another 
for
loop!
n
lol yeah
not really a fan of today's problem
d
I was so ready for it to say in part 2: "Now do 3000000 cycles"
i
No need to have two different point types for parts 1 and 2. Point3 is just Point4 with 
w = 0
.
And then parts 1 and 2 differ only in what neighbors a point has.
n
That's a good compromise
But still not ideal :-)
But there's very few languages that can do this ideally so eh
In C++you can write the entire solution generic in the dimension, and have an optimal solution in all dimensions at once, pretty cool
i
Quite generic for any point type:
Copy code
fun <Point> oneCycle(field: Set<Point>, neighbors: Point.() -> List<Point>): Set<Point> = buildSet<Point> {
    addAll(field)
    field.forEach { addAll(it.neighbors()) }
    retainAll { e ->
        val n = e.neighbors().count { it in field }
        n == 3 || (n == 2 && (e in field))
    }
}
👍 2
j
And my solution without any x,y,z,w loops 🙂
(the difference between part1 and part2 being in the initial point creation op: either to 3-dimensional or 4-dimensional) part1 is 90ms, part2 is 120ms, I believe most of that time is spent on warm up 🙂
e
10% improvement on part 1 with Byte instead of Int, 4% improvement on part 2
@Nir even in Rust, criterion.rs measured a 10% improvement in my solution by changing isize/i64 to i32, and another 10% improvement by changing that to i8. i8 happens to work for this problem, but i32 is more widely applicable
j
just realized. plane for z=1 is same as for z=-1. -2 matches 2 etc. similar with dimension W. Potentially one could save 75% of time, but additional calculations for plane 0 makes it not really worth the effort...
g
how do you do this in functional programming?
@David Whittaker You could run a 
fold
across your entire world: https://github.com/cortinico/adventofcode-2020/blob/6b798992648ec61287efe94bc877cef4f14f54d4/src/main/java/Exercise17-part2.kt#L40-L46
Copy code
world.fold(0) { acc, next ->
        acc + next.fold(0) { acc2, next2 ->
            acc2 + next2.fold(0) { acc3, chars ->
                acc3 + chars.count { it == '#' }
            }
        }
    }.also(::println)
e
rather than 
acc +
, you can make it tail-recursive with 
.fold(0) { acc, next -> next.fold(acc) { ...
➕ 1
but in this case 
.sumOf { it.sumOf { it.sumOf { it.sum() } } } }
would work
g
☝️ I believe they modelled as a 
CharArray
so they need to filter for 
'#'
. So just 
.sum()
won’t work.
e
.count('#')
then
➕ 1
n
Sure, thats not surprising, I said that was expected during our convo
e
just to say: even in low-level languages that aren't pointer-heavy, on modern 64-bit processors, 64-bit integers are not the right default for performance. they make some sense for consistency with pointers and indexing, but we honestly should fix that the other way around.
n
I already said if you have a lot of something, then you always pick the samllest data type you can, there's no end to it
if you have one of something, then there is no performance cost
but hey, prove me wrong, email the designers of C++, Swift, Go, Rust and tell them they have the wrong defaults, I'm sure they'll be receptive
@ilya.gorbunov thanks for the tips there, I had a feeling that the approach was to pass around lots of functions, late last night couldn't quite put it together, so copy pasta 🙂
my new solution uses that approach and the amount of repetition isn't that bad. Mostly, needed to repeat in the Point3 and Point4 definitions and neighbor functions, like you said
t
I've been battling My Actual Job and a headache that will not go away today, so my solution for Part 2 is a copy and paste job of Part 1. I spent about 10 minutes trying to write an n-Dimensional class like @Jakub Gwóźdź seems to have done (nice!) but couldn't dedicate a lot of time to it today. Maybe I'll go back and rethink it. Certainly will if we see n-Dimensional grids again and I have the time! Blog: https://todd.ginsberg.com/post/advent-of-code/2020/day17/
b
yeah I just modified my Part1 code to add a dimension, I have to make a code that can do both again
n
yeah, same
I mean I did it that way at first
and then I refactored to minimize the repetition, reasonably
I didn't go all the way to doing it for general N; I don't really love that solution in Kotlin
since you can't be generic on N
b
Yeah I've been more gross and just handle 3 and 4
n
you can make the code generic other than the actual Point* data class, and Point.getNeighbors (and a Pair<Int, Int>.toPoint* function)
b
yes that's what I'm writing right now
with lists
n
Now I'm wondering if it is possible to hack something together in Kotlin which is fully generic yet type safe. Hmmm
b
yes you can
it is much slower but it works
n
Yeah it's tricky to do though
b
Copy code
var initialList: List<List<Int>> = (-1..1).map { listOf(it) }
        repeat(dimensions - 1) {
            initialList = initialList.flatMap { oldList -> (-1..1).map { oldList + listOf(it) } }
        }
this to generate all dimensions
n
if you just work with raw lists it's not very type safe
because there's nothing guaranteeing that the lists are the same size
If you compare to a solution that uses Point3, Point4 classes, these are different types so they prevent mixups at compile time and catch all kinds of potential issues
when you are working with 
List
as your point class, you don't have those guarantees
b
well you check the lists
that's what I do when I initialize my ConwayND class
n
that's at runtime
I'm not saying it's terrible or anything, I'm just saying its a downside
b
absolutely, but my data is loaded at runtime anyway
n
your data is loaded at runtime, but there are still errors in your program that can be caught statically
b
I don't see how you can have a type definition that would handle that
probably in any language
n
err well in C++ it's easy 🙂
std::array<int, N>
the N there can be any value, and you can be generic over it.
If you use Lists, then you'll have a 
fun getNeighbors(x: List<Int>): List<List<Int>>
the type system doesn't guarantee that the inner lists are the same size as the argument
in C++ you'd have something like 
template <std::size_t N> vector<array<int, N>> get_neighbors(const std::array<int, N>&);
b
yeah but how do you make sure it is the same N everywhere?
n
in the code above, N has to be the same value everywhere
it's the same argument
If you try to write code where the N's going in and out are different, it just wont' compile
Copy code
array<int, 3> some_point;
vector<array<int, 4>> list_of_points;
list_of_points = get_neighbors(some_points); // compilation error
b
yeah sure
but you can't have variable dimensions at runtime
so you can do
typealias List3 = List<Int>
that's not perfect
n
well, it's not just not perfect, it's literally no type safety
In Kotlin your Point3 and Point4 types are now the same
The best you can do to fake it in kotlin is something like:
Copy code
interface Dimension {
    val size: Int
}

class Three : Dimension {
    override val size = 3
}

class Four : Dimension {
    override val size = 4
}

data class Point<T: Dimension>(val data: List<Int>, val dim: T) {
    init {
        assert(data.size == dim.size)
    }
}
So now, we have a generic function:
Copy code
fun <D: Dimension> Point<D>.getNeighbors(): List<Point<D>>
and we now the points going in and the points going out are the same types
b
does c++ complain if you try to add 5 elements to a array<int, 4> ?
(at compilation time)
n
an array<int, 4> simply always has 4 elements
you can't push back or add
b
I see
n
when you construct it, depending how you construct it, but typically you'll just initialize with an int of 4 0's
*array of 4 0's
b
adding a cache makes it super fast
I think I have a decent solution now
n
a cache for getting the neighbors?
b
(not type safe but I don't really care)
yep
it reduces by 5 the runtime
n
I mean you can just get the sequence of steps up front
b
which was pretty fast but still
this is done as well
n
and then + them to the current square
i'd be surprised if caching adds much on top of that; looking up in a cache is probably roughly the same speed as +'ing two points
b
well my solution is probably not optimal in the first place
n
I just had globals like this:
Copy code
val neighborDirs3 = (-1..1).map { x ->
    (-1..1).map { y ->
        (-1..1).map { z ->
            Point3(x, y, z)
        }
    }
}.flatten().flatten().filter { it != Point3(0, 0, 0) }
And then you get all neighbors via 
neighborDirs3.map { p + it }
b
oh I forgot an obvious optimization again
n
Alright, thsi is the best combinatino of type safe and generic I was able to do in kotlin
This isn't that bad I think
b
Why do you do lines.withIndex().map instead of mapIndexed ?
n
Just ignorance probably :-)
e
my code is always 4-dimensional, it just leaves the 4th dimension in the range of 0..0 when doing part 1
b
That's how I did it initially but then I wanted to play with n-dimensional
3 Views
Open in Slack
PreviousNext
Powered by