|
Ihmemies posted:I am a bad programmer with smooth brain, but I FINALLY managed to get it done. There are probably a million better ways. I did something very similar. I only expanded the map to 2x2. Tiles where both X and Y are both divisible by 2 are then part of the original map. I put zero effort into optimizing my flood fill and it took nearly 2 seconds to run.
|
#
?
Dec 10, 2023 18:29
|
|
|
|
| # ? May 2, 2024 20:11 |
|
|
i think doing a flood fill is perfectly sensible, especially considering how often it's come up around this time in past years my approach was to scan each row of the grid, doing an even-odd rule check for interiority: start off with inside = false, then every time we cross a vertical edge, toggle inside. the only complication is when we hit a horizontal edge. there we have to look at the corner pieces at both ends together. if they both turn up or both turn down, then ignore the whole edge (imagine pushing the edge a very tiny amount up or down and then just walking straight by it). if they turn opposite directions, then the edge is kind of just a crooked vertical edge, so count the whole thing as one vertical edge this row by row scanning is what's shown in the second part of my gif above
|
|
#
?
Dec 10, 2023 18:50
|
|
|
did anyone say advent of chode
|
|
#
?
Dec 10, 2023 18:51
|
|
|
work got a bit crazy so only got around to catching up now, but i dare say that for 10b doing it by tracking states on the scanlines as given was *not* easier than transforming the input, so those with up-projecting to 2x2 or 3x3 probably had it right :p
|
|
#
?
Dec 10, 2023 20:46
|
|
|
my 10b was a real PITA because I didn't implement reasonable methods for my representation of the grid until the very end. Ended up implementing "connects_{north,south,east,west}" because I kept loving up the logic to replace the starting square with its appropriate shape for the final part. Turns out that made everything else much easier to reason about!!!  on the plus side im feeling much more comfortable writing Rust at a primitive level, so I just need to actually dive into more idiomatic parts. at the very least i have a long list of traits to look into understanding now
|
|
#
?
Dec 10, 2023 21:16
|
|
|
i definitely spent 5-10 minutes considering how to even do part 2 but came up with keeping track of the tiles that are on the left and right of the path as it is traversed, then when traversal is done removing the loop squares from the left/right arrays. finally i look at the top-left most square that was in the path, and look to the left of it -- i know this is outside the loop by definition so i use the array that it isn't in, and floodfill based off of that
|
|
#
?
Dec 11, 2023 00:22
|
|
|
A common sort of puzzle today, with the usual trick of picking a sensible representation for your sparse array
|
|
#
?
Dec 11, 2023 09:33
|
|
|
Personally I extracted the Coord (x,y) to a list and iterated on the Coord list, transforming x,y values by cumulative amount of added rows/cols.. Like this: for galaxy in galaxies.iter_mut() { galaxy.y += empty_rows.iter().filter(|&&row| row < galaxy.y).count() * (step-1); galaxy.x += empty_cols.iter().filter(|&&col| col < galaxy.x).count() * (step-1); } Luckily that was the first thing I thought about and it worked well.
|
|
#
?
Dec 11, 2023 12:40
|
|
|
Yeah, Day 11 was light years easier to puzzle through. After misreading the prompt and accidentally finding the shortest path through every start once via a quick BFS it was about a half hour's work.pre: fun List<String>.toGalaxies(distance: Long = 2): List<Point2dL> {
val clearRows = this.indices.filter { this[it].none { c -> c == '#' } }
val clearCols = (0 until this.maxOf { it.length }).filter { this.none { line -> line[it] == '#' } }
return flatMapIndexed { y, line ->
val expandedY = (distance - 1) * clearRows.count { it < y } + y
line.mapIndexedNotNull { x, c ->
val expandedX = (distance - 1) * clearCols.count { it < x } + x
when (c) {
'#' -> Point2dL(expandedX.toLong(), expandedY.toLong())
else -> null
}
}
}
}Day 10 took me a while because I didn't realize you could do it in only two raycasts slightly offset from each other. I was checking all directions and firing the rays straight down the line.. but you kinda needed to offset it to the left and right and make sure both signaled "inside". Upscaling and flood filling seemed to take too long, so I just went back to my original raycasting on the original map idea and used a bunch of graph paper to more clearly see what I was doing. pre: private fun Point2d.inside(boundary: Map<Point2d, PipeTile>): Boolean {
val freq =
if (y == 0) {
emptyList()
} else {
Point2dRange(x..x, 0..<y)
}.mapNotNull { boundary[it] }.frequency()
val hCount = freq[PipeTile.Horizontal] ?: 0
val westWalls = abs((freq[PipeTile.BendSW] ?: 0) - (freq[PipeTile.BendNW] ?: 0))
val eastWalls = abs((freq[PipeTile.BendSE] ?: 0) - (freq[PipeTile.BendNE] ?: 0))
return (hCount + westWalls) % 2 == 1 && (hCount + eastWalls) % 2 == 1
}MrQueasy fucked around with this message at 20:15 on Dec 11, 2023 |
|
#
?
Dec 11, 2023 20:13
|
|
|
I like the days where seeing part 2 makes me just scrap what I did for part 1 entirely and reimplement it in a smarter way, feels like an important learned lesson. 
|
|
#
?
Dec 11, 2023 20:52
|
|
|
MrQueasy posted:Yeah, Day 11 was light years easier to puzzle through. After misreading the prompt and accidentally finding the shortest path through every start once via a quick BFS it was about a half hour's hrmmm shortest path to visit every point once? if so I suspect you did not write a quick algorithm for that lol
|
|
#
?
Dec 12, 2023 00:31
|
|
|
thank goodness that rat pipe one was 2d. I had a hell of a bad time with the 3d ones last year.
|
|
#
?
Dec 12, 2023 00:33
|
|
|
cool av posted:hrmmm shortest path to visit every point once? if so I suspect you did not write a quick algorithm for that lol I’m pretty sure it didn’t work, but it failed fast enough on the sample data to show me my numbers were way off
|
|
#
?
Dec 12, 2023 03:06
|
|
|
oof, day 12 part 2 is mystifying to me
|
|
#
?
Dec 12, 2023 08:07
|
|
|
MrQueasy posted:oof, day 12 part 2 is mystifying to me Yeah, I'm gonna need to do some refactoring here.
|
|
#
?
Dec 12, 2023 12:11
|
|
|
Oh, this part 2 is one of those where it forces you to do a real solution instead of brute forcing it. I know AoC does those and I still did a brute force solution for part 1.
|
|
#
?
Dec 12, 2023 13:12
|
|
|
Managed to make it work without too much loving around using the trick everyone should know for this sort of problem, memoization
|
|
#
?
Dec 12, 2023 13:16
|
|
|
Jabor posted:Managed to make it work without too much loving around using the trick everyone should know for this sort of problem, memoization Ugh, identifying that this was memoizable was a BEAST Solved it with a state machine that stepped through the diagram and tracking what springs we'd already seen, branching recursively on the ?s. I am ashamed by the amount of hints I needed for this one.
|
|
#
?
Dec 12, 2023 20:27
|
|
|
this one was pretty easy, but the only reason that is the case is because i teach a course which is like 50% problems that can be stated in this way.
|
|
#
?
Dec 12, 2023 20:29
|
|
|
i stumbled on the right approach fairly early but then hosed it up in 2-3 different ways and each time decided yeah no it actually won't work and tried something else for way too long i don't go for time and like let myself get disrupted but this year so far this day was probably the longest wall clock time from when i downloaded the input to when i finished part 2 at some point i went "ok this semi-brute-force solution in python is making really really slow progress but it's making some progress occasionally, so maybe rewriting it in rust and parallelizing it before leaving for dinner will be enough", and, it wasn't Ihmemies posted:I am a bad programmer with smooth brain, but I FINALLY managed to get it done. There are probably a million better ways. i'm so glad i wasn't the only one. i love the problems where i get to repeatedly printf a map with a thing moving across it for debugging.
|
|
#
?
Dec 12, 2023 21:58
|
|
|
Jabor posted:Managed to make it work without too much loving around using the trick everyone should know for this sort of problem, memoization dear god i was so close to this but didnt follow through. I had constructed a hashset to stop myself from repeatedly returning the same string in the end, but didn't cache the result, I just threw it away. should've just done the hashmap from the beginning Its a Rolex fucked around with this message at 02:12 on Dec 13, 2023 |
|
#
?
Dec 13, 2023 01:48
|
|
|
I don't actually understand how this one is memo-izable. I just finally managed to get it with a boatload of specific optimizations to prune the search tree, but... how are you breaking down the problem into subproblems where you get a lot of duplicates for lookups?
|
|
#
?
Dec 13, 2023 03:02
|
|
|
cool av posted:I don't actually understand how this one is memo-izable. I just finally managed to get it with a boatload of specific optimizations to prune the search tree, but... how are you breaking down the problem into subproblems where you get a lot of duplicates for lookups? It's possible I tackled it from a different direction than you did - my first approach was to enumerate all possible strings that match the given numbers and overall length, and then filter those to just the ones matching the given pattern. The generation was done by placing the first group at the first possible position, then recursing over the remaining groups, moving that first group one space along and recursing, etc. After some kinda straightforward transformations, the subproblem becomes given N groups already placed in the first X characters, how many ways are there to legally place the remaining groups?
|
|
#
?
Dec 13, 2023 03:41
|
|
|
Jabor posted:It's possible I tackled it from a different direction than you did - my first approach was to enumerate all possible strings that match the given numbers and overall length, and then filter those to just the ones matching the given pattern. The generation was done by placing the first group at the first possible position, then recursing over the remaining groups, moving that first group one space along and recursing, etc. ahh gotcha. that makes sense.
|
|
#
?
Dec 13, 2023 03:59
|
|
|
cool av posted:I don't actually understand how this one is memo-izable. I just finally managed to get it with a boatload of specific optimizations to prune the search tree, but... how are you breaking down the problem into subproblems where you get a lot of duplicates for lookups? My approach (that totally wasn't planned to be memoizable, just worked neatly) was that I have a set of possibly valid substitutions that starts out as just the input, then I loop over that until the set is empty. For each <spring chars, numbers> pair I remove from the set, I look at the leftmost "decision point" (ie "looking at the leftmost number, can i place that sequence of springs at the leftmost # or ?, or is the ? a . and we try later"), adding both possibilities back to the set if they're possibly valid, like <spring chars with a leftmost sequence of #/? of the respective length removed, tail(numbers)> and <spring chars with leftmost ? removed, numbers>. It's valid if we're out of numbers and out of # at the same time.. The "memoization" part is that I don't add duplicates, I just add a "weight" value. It seems to help a lot to always continue with the longest element in the set, rather than using a stack like I tried first. I should probably spend some time looking at other people's solutions because I don't think I understand their descriptions... Vanadium fucked around with this message at 04:09 on Dec 13, 2023 |
|
#
?
Dec 13, 2023 04:03
|
|
|
for 12: I treated the spring diagram and chunk sizes list as two tapes in a state machine. starting with - a pointer to the first char - a pointer to the first chunk size - the number of hashmarks I've seen (0) - if this is the last diagram character (add a dot to it at the end): - - if all the chunks are used up: - - - - return 1 - - else: - - - - return 0 - if current diagram char is a dot: - - if the number of hashmarks I've seen is != the current chunk size element - - - - return 0 - - if I'm out of chunks - - - - return 0 - - else: - - - - increment the diagram pointer - - - - increment the chunk-size pointer - - - - reset seen to 0 - - - - recurse <<memoized>> - if current diagram char is a hash: - - if I've seen a number of hashmarks equal to the current chunk size - - - - return 0 - - else: - - - - increment the diagram pointer - - - - increment seen - - - - recurse <<memoized>> - if current diagram is a ? - - recurse from current point as if it was a hash - - recurse from current point as if it was a dot And no, I didn't do this off the dome. I had a bunch of hints. MrQueasy fucked around with this message at 07:59 on Dec 13, 2023 |
|
#
?
Dec 13, 2023 07:56
|
|
|
Day 13 was suspiciously simple in comparison to even Day 12 Part 1.
|
|
#
?
Dec 13, 2023 07:58
|
|
|
MrQueasy posted:for 12: this is nice and clean mine is a miserable pile of half-written and unused aborted code stitched together in incomprehensible ways but hell I’ll take it
|
|
#
?
Dec 13, 2023 15:01
|
|
|
MrQueasy posted:Day 13 was suspiciously simple in comparison to even Day 12 Part 1. Yes, I spent only like 4 hours on it. Maybe it was not the best to store data as bits to i32’s, while this was the first time ever I voluntarily used bit operations, with any language. On the other hand 2,5ghz Xeon computes answer to both in 2-3ms.
|
|
#
?
Dec 13, 2023 15:16
|
|
|
day13 is gonna get me to actually write a Matrix struct which returns iterators over rows/columns. probably for the best
|
|
#
?
Dec 13, 2023 17:38
|
|
|
trying to tidy up my day 13 got me to learn how to do operator overloading in python so i could write a transposing list-of-list adapter for indexing at least, i'm sure i'll get to iterators eventuallycool av posted:mine is a miserable pile of half-written and unused aborted code stitched together in incomprehensible ways but hell I’ll take it i enjoy the difficulty/code quality curve where it's like easy -> short and sweet solution medium -> kinda janky write-once-read-never code, but not too bad hard -> unholy mess of abandoned approaches and repurposed control flow, just barely not inefficient enough to fail to terminate before i give up super hard -> clean and legible again with intuitive abstractions because i couldn't solve it without refactoring/rewriting after figuring out my mistakes
|
|
#
?
Dec 13, 2023 17:48
|
|
|
day13 pt 2 was a fun lil refactor that didn't make me feel like a dummy. today was a nice chill day
|
|
#
?
Dec 13, 2023 23:54
|
|
|
I made myself a visual debugging aid for day 14 part 1 
Vanadium fucked around with this message at 17:08 on Dec 14, 2023 |
|
#
?
Dec 14, 2023 16:50
|
|
|
nice. I let it run for 2000 iterations and then eyeballed the output pattern in excel to see where to start looking for the pattern. This particular solution is a yearly standby, and yet I feel like I still have to relearn how to do the arithmetic from first principles every year.
|
|
#
?
Dec 14, 2023 17:18
|
|
|
MrQueasy posted:nice. God yeah. I spent way too long going "oh I'll just have to skip to iteration 1000000000 minus x, easy part 2" and not figuring out the arithmetic for x.
|
|
#
?
Dec 14, 2023 17:30
|
|
|
advent of 
|
|
#
?
Dec 14, 2023 17:31
|
|
|
pretty sure a fast language would do b brute-force pretty easy. my crude python it would have been a couple of hours.
|
|
#
?
Dec 14, 2023 17:42
|
|
|
especially if you memoize it
|
|
#
?
Dec 14, 2023 17:46
|
|
|
Cybernetic Vermin posted:pretty sure a fast language would do b brute-force pretty easy. my crude python it would have been a couple of hours. I think a billion iterations adds up faster than you think. A billion nanoseconds is 11.57 days.
|
|
#
?
Dec 14, 2023 17:48
|
|
|
|
| # ? May 2, 2024 20:11 |
|
|
MrQueasy posted:I think a billion iterations adds up faster than you think. a billion is a good number for estimates in that you can ballpark get that many instructions done a second, so the question becomes how many instructions you need to do a round
|
|
#
?
Dec 14, 2023 17:50
|
|