https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 19> :thread:
# advent-of-code
a
d
Processor spin-up = naĆÆve solution?
Ah - a little memoization again to save the day!
s
Trying to do memoization of the current state, but it OOMs on around 5 000 000 states in the memo šŸ„²
My best idea so far is to prune the recursive tree somewhat by exiting early if you have 1 step left and no geode robots, 2 steps left and no obsidian robots, etc. But that doesn't seem to help much.
j
@Sergei Petunin you could improve the one minute one to be generic
oh for me the real input puts everything for one blueprint into one line, but the example was formatted nicely
e
@David Whittaker whatā€™s the state in your solution and how it is represented?
j
oh man I missed, that the factory only can build one robot per minute
e
@Jonathan Kolberg I feel for you. Same story.
m
Just completed part 1 (runs in a few seconds), but Iā€™m not sure how to speed it up enough for part 2.
Iā€™m doing BFS with pruning.
Ok, solved part 2 in 108 seconds, maybe I didnā€™t need to speed it up after all.
e
@Marcin Wisniowski what are the nodes of the graph on which you do BFF and what kind of pruning you do? Iā€™m trying to figure why I had to do a lot of non-asymptotic optimization to get a decent run-time.
m
My nodes are a Pair of
Copy code
data class State(
    val ore: Int = 0,
    val clay: Int = 0,
    val obsidian: Int = 0,
    val geodes: Int = 0,
    val oreRobots: Int = 1,
    val clayRobots: Int = 0,
    val obsidianRobots: Int = 0,
    val geodeRobots: Int = 0
)
and a list of moves to reach that state. For each one I add all possible moves to my 
unvisited
list (which gets pruned).
e
I see. That would be usually called ā€œforward DP (in time)ā€œ. How do you prune?
j
@Marcin Wisniowski hm that's my state also, but for part1 in the second blueprint of the example I get 10 instead of 12, which drives me crazy any idea why that happens?
e
@Jonathan Kolberg Make sure, that you try all 5 possible transitions from the state to the next one (build no robot, or build one of 4 types of robots, if possible)
j
@elizarov hm if you build a geode robot it's always better
e
@Jonathan Kolberg can you prove it or is it just a hunch? Maybe you could build one more obsidian robot, that would let you build more geode robots at the end?
m
I remove all several types of useless states: more ore robots built than max ore cost (and other resources), robot built when itā€™s production resource is already at amount that cannot be possibly used up, another state at same or smaller minute is strictly better (more resources/robots), did not build geode robot when could.
j
@elizarov yeah not sure, maybe that is not worth it.
hm at least with the always build geode robots my part1 for the 2 examples worked, now I'll try it on real input
e
@Marcin Wisniowski ā€œanother state at same or smaller minute is strictly betterā€. Iā€™ve tried to implement this one, but it made things slower in my code, since all states need to be scanned to see if there is a ā€œbetter oneā€ out there, making O(number_of_states^2), where number_of_states is already pretty large. How many states (in order of magnitude) you end up with for part 1 and 2 with this kind of pruning?
j
@elizarov could you not keep your states in a set (one per minute), then checking should be O(minute)
e
@Marcin Wisniowski Iā€™m also trying to wrap my head onto why you should always build a geode robot if you can. Iā€™ve tried to change my code to ā€œdonā€™t build a lower robot if you can build a higher-oneā€, but it started to produce wrong results.
j
@elizarov yeah only works for geode robots, no idea why
e
@Jonathan Kolberg A set of states per minute is exactly how I keep it. However, this way I can only prune identical states. I cannot quickly check if there is better state somewhere.
m
In part 2, my unvisited list reaches no more than 75k states. In part 1 no more than 15k.
e
@Marcin Wisniowski You pruned well! My solution tracks massive number of states (dozens of millions)
m
I see that removing the check for strictly better states slows it down a lot, the state amounts skyrocket. Itā€™s expensive to scan the entire list, but looks like itā€™s worth it.
e
Iā€™ll play with my solution in the evening to see which kind of pruning approaches, that I have not figured out, yield the most reduction in states.
m
Iā€™m also trying to wrap my head onto why you should always build a geode robot if you can
I canā€™t prove why that works but it certainly works, at least for my input.
e
@Marcin Wisniowski Thatā€™s a cumulative effect of prunnings. I bet it will not help without other prunnings reducing the number of states first.
I ended up with a single prunning that, given a state, estimates the maximal number of geodes you can possibly produce based on the number youā€™ve already produced, the number of geode robots you have and the time remaining (assuming you build a geode robot at every future time-step), and prunes all states that cannot possibly produce more geodes as the best state will definitely produce.
(This basically a kind of prunning idea from A* search)
However, since the heuristic is based only on geode robots, I end up with a massive number of states even before it can start helping.
m
I had this one initially but removed it when trying other things since it didnā€™t seem to help much.
j
At least my part1 is done, but I have the feeling for part2 I have to do without recursion: Solution Part1
b
Instead of branching based on what you can afford at every minute, Iā€™m branching on what robot to buy next and then advancing the minutes to affordability.
j
oh the trick seems to be to track what sort of robot you could have bought earlier and not branch to buy that but only other ones
made part2 complete in a few seconds at most for me
s
@Jonathan Kolberg I don't understand, do you mean that you don't buy the same type of robot more than once?
m
@Sergei Petunin If you couldā€™ve bought robot X earlier and instead did nothing, buying it now does not need to be considered, because if the correct move is to buy it, you couldā€™ve done that on the previous turn where you did nothing instead.
s
It's not obvious to me why this works. What if I want to buy some more ore-consuming robot B first, and that's why I decided to wait and not buy robot A?
m
Then you are doing something else and this rule does not apply.
j
@Sergei Petunin no you reset as soon as you buy one
m
The progression [Nothing (couldā€™ve bought Ore Robot), Buy Ore Robot] can be pruned from your decision tree.
j
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space: failed reallocation of scalar replaced objects
damn it, part 2! šŸ˜†
r
my rather naive recursive tree implementation runs in about 3 minutes for the input of part 2, but about 33 minutes for the example part 2, hahah! The answer is correct tho, so it ain't much but it's honest work šŸ˜›
s
I've tried to implement this optimization, how I understood it: I pass both previous and current state to the recursive function. If a particular robot could have been created on the previous step (found by inspecting the previous state), but no robots were created (found by comparing the previous and current states), I don't try to create this robot on the current step. This reduces the running time in part 1 from 60 to 20 seconds, but it's still way too slow for part 2. What am I missing?
p
Copy code
year 2022 day 19 part 1
	 Default took 399.498751ms: 988
year 2022 day 19 part 2
	 Default took 171.593810ms: 8580
Quite happy with my runtime. Example input has:
Copy code
year 2022 day 19 part 1
	 Default took 194.074800ms: 33
year 2022 day 19 part 2
	 Default took 308.349257ms: 3472
e
I've played with different proposed prunings. The greatest one, I think, is that you don't need more ore robots than the maximal ore consumption. It is not enough by itself for part2, but it is a great baseline with massive impact.
p
@elizarov not sure you meant to send that to the channel too - a little bit of a spoiler šŸ˜‰
e
Thanks! That was accidentally sent to the channel, removed.
p
The next best pruning for me is to ignore any states for which Iā€™ve seen the same robots earlier. (using a 
MutableMap<Robots, Int>
to track current min elapsed time Iā€™ve seen the robots)
It might be that this pruning only really applies if youā€™re skipping time (I branch on next robot to build rather than a state-per-minute approach)
j
I'm only buying geode robots if possible, buying max robot to max cost of the resource and otherwise branch on robot purchase, so if i do not buy the ore robot that branch will not try to buy an ore robot next. That was enought for both part1 and 2
p
The pruning Iā€™ve used is: ā€¢ Only build a robot if the extra resources generated can be used (i.e. as Roman suggests but for all 3 producing robots) ā€¢ Only take states that have a higher maximal potential (assuming sudden infinite resources and building a geode robot on every tick, whatā€™s could the final geode count be) ā€¢ Ignore any states for which weā€™ve seen our robot army earlier With this (and 200 warmup rounds for the JIT) I get a part2 solve of 14ms which is sufficient šŸ™‚ Oh - and processing the blueprints concurrentlyā€¦ https://github.com/tKe/aoc-22/blob/main/kt/src/main/kotlin/year2022/Day19.kt
e
sending work to Dispatchers.Main for parallelism
p
@ephemient I knew when I opened that Iā€™d see a DRF šŸ˜‰
e
doing a quick pass with an inaccurate algorithm to get an upper bound and cutting off the search early if it's not possible to beat the current max
for my input, part1 1:35 part2 0:17 on intel, part1 1:04 part2 0:13 on appleā€¦ on JVM. the example on kotlin/native times out my test even when extended to 5:00, so I'm not gonna even try it on my real input
I actually took out all the duplicate state detection since it didn't appear to make any difference with my pruning active. although it's possible I had another issue there
s
Many thanks to everyone for the hints. Eventually this did the trick: 1) prioritizing geode robots, 2) skipping branches where we buy robot that we could but didn't buy on the previous step, 3) capping the number of robots to the maximum material requirement. Now it takes 5 seconds to run both parts for sample and personal input. Funny that the running time decreased significantly once I've removed memoization. https://github.com/forketyfork/aoc-2022/blob/main/src/main/kotlin/year2022/Day19.kt
p
I got a speedup from removing my visited set after adding the earliest-robots check.
m
I don't have a visited set at all, why did you need it?
p
I originally inlined my generic BFS function and didn't have as much pruning in place. It helped enough to get an answer but became redundant as I improved performance
e
I'm kind of surprised by how good my fast heuristic is (for pruning). it's pretty terrible at the beginning (overestimating by 100x) but once we find at least 1 geode, it seems to be off by at most 1 in the test cases and my input
also damn. using the same algorithm, my ~2 minute full run in Kotlin/JVM becomes ~20 seconds in Rust
t
For me this boiled down to increasingly trickier ways to avoid doing work. My solution depends on scheduling each possible build in the future when materials are available, skipping some turns entirely rather than scheduling every turn. This ended up savinga lot of turns that basically do nothing. Also, once you have enough bots to harvest the max materials in a single turn to build any item, stop building those bots - since you can only build one thing per turn, you wonā€™t run out. And then for the last one, order work by descending order of number of already found geodes. If the work item you are looking at canā€™t possibly, under the best conditions (building a new geode robot every turn) beat the best youā€™ve seen, donā€™t schedule any of its future states. This ended up trimming millions of items from the work queue. ā€¢ Blog ā€¢ Code
j
For me, I just kept a list of the possible states at the current time and mapped it to the list of states for the next second. Pruning was done in two ways: ā€¢ In the generation of possible next states ā€¢ After the entire list of next states is generated
When determining possible next states, if I could buy a geode robot, I always did that. Otherwise, I only added the option to save resources if I had at least one of each bot required to buy something I couldn't already.
Once the possible next states were generated, I pruned out any states that had the same number of bots as another, but strictly fewer resources. That was enough to keep the list of next states from growing to high.
Also, as Todd mentioned, I capped all bot production at the max needed for any purchase (aside from geode bots), since you could only make one purchase at a time.
j
I'm still stuck on part 1. For the sample blueprints I'm getting the correct answer for blueprint 1 but I'm getting 8 instead of 12 for blueprint 2. Does anyone know the correct manufacturing schedule for getting a 12 on blueprint 2?
p
My build order for Part1 Blueprint2 was 
[ore, ore, clay, clay, clay, clay, clay, clay, obsidian, obsidian, obsidian, obsidian, clay, obsidian, geode, obsidian, geode, obsidian, geode, clay]
j
thanks
p
The last 
clay
is superfluous as my algorithm at the time only idled if there was nothing to buy (so was greedy on buying if there was still time). With a bias to idling for the remaining minutes I get the following order: 
ore, ore, clay, clay, clay, clay, clay, obsidian, obsidian, obsidian, obsidian, obsidian, geode, obsidian, geode, geode
r
A bit late - Part 1 takes around 5 minutes. 
Part 2 - Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
11 Views
Open in Slack
PreviousNext
Powered by