| Age | Commit message (Collapse) | Author |
|---|
|
To figure out where you're going on a net (as far as I can figure) you
need to be able to tell which faces of a cube are connected to each
other, and which direction they are in relative to each other.
|
|
Process command-line options by re-using a different variable than the
one we were re-using before.
|
|
|
|
Having 'y' go down was easier with navigating through the memory buffer
we were using to store the map, but some of the work we'll have to do
with the cube net is easier for me to get my head around with a more
traditional coordinate system.
|
|
This will help with some future changes
|
|
A char won't do.
|
|
|
|
Rather than just a linear position in the map buffer
|
|
|
|
|
|
That way we will keep a proposed orientation change alongside the
position change.
|
|
It doesn't work yet...
|
|
|
|
This will help when just moving around can change the orientation, as
you move over an edge
|
|
|
|
We obviously have enough of that resource at this time, so there's no
need for another robot yet.
Drops time by 60% on full 24-round test data (4.6s -> 1.8s)
|
|
The only reason to do nothing would be to save resources to build a
robot we can't affort to build yet. But if we have enough resources to
build all of them, there's no point in not building any
Drops time by 35% on full 24-round test data (7.2s -> 4.6s)
|
|
|
|
Just generate the output needed by the puzzle.
|
|
Don't try building ore robots if there are fewer than 10 rounds
remaining, or clays robots if there are fewer than 5. It's probably too
late for those robots to make a difference? Maybe?
(Why 5 and 10 rounds? Just a guess. And it seems to still get the right
result)
Drops time by 90% on 22-round test data (4.8s -> 0.4s)
|
|
Because we can only build one robot at a time, if the most expensive
robot in terms of ore takes 4 ore to build, we'll never need more than 4
ore robots. Because they can always collect enough ore to build one
robot of any type per turn.
Drops time by 90% on 20-round test data (5.4s -> 0.5s)
|
|
Drops time by about 20% on 20-round test data (6.6s -> 5.4s)
|
|
After reading the rules more carefully, I see we can only build one
robot per round! (Not just one robot per material type, one robot!) Doh!
This reduces the combinatorial explosion a lot. The exhaustive search
has become a lot more feasible, with Blueprint 2 of the test input able
to cover 22 rounds in a minute and a half. I shouldn't only need to find
some small wins from here to get the 24-round runtime to something
sensible.
|
|
As expected, the explosion in permutations makes this prohibitive.
With this stragegy, on Blueprint 2 of the test input, for:
10 rounds it takes 0.018s/59,979 iterations
11 rounds it takes 0.070s/1,257,483 iterations
12 rounds it takes 1.292s/59,156,010 iterations
13 rounds it takes 3m2.770s/8,395,942,157 iterations
Getting to 24 rounds just isn't feasible with that growth.
And I can't figure out how to cull unwanted permutations easily.
Going to have to try something else.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Phew. Nice that the puzzles for the 24th have been pretty easy
|
|
|
|
|
|
|
|
|
|
|
|
Back from Christmas travels, let's see if I can finish the set before
new year!
|
|
|
|
(Forgot to commit earlier, doh!)
|
|
|
|
|
|
|
|
Phew. Nice easy one for today! Caught up now.
|
|
|
|
|
|
It produces *a* result for each blueprint, but not the best result.
I feel like that's a hard problem. The number of decisions about what to
build when over 24 iterations explodes so much that you can't
brute-force the optimal geode count.
Either there's a way of pruning possibilities that I've not thought of,
or there's a pretty good heuristic you can get from the blueprint about
the proportions of how many of each type of material you want to be
producing, that you can pick what to build and get a geode count that
doesn't deviate from optimal in only 24 iterations.
One other possibility is transforming this puzzle into a SAT format and
letting a SAT solver attack it, with its ability to prune decision trees
effectively. But I don't have any actual experience with those, and I'm
not sure I have time to figure that out for AoC.
https://en.wikipedia.org/wiki/SAT_solver
|
|
|
|
Wow, it's hard figuring out the interior of a space. Did it the brute
force way, which worked OK because the total volume was small enough.
After part 1, I was hoping to be able to catch up the day I'm behind.
That's not happening today. We'll see how tomorrow's challenge goes.
|
|
|
