| Age | Commit message (Collapse) | Author |
|---|
|
Because it can never be negative, and some of the blueprint combinations
can cause it to wrap. This gives us one more factor of two breathing
room.
|
|
|
|
Either we don't need it, or we did but it's too late.
Speeds up part 2 from 570s (9m30s) to 5.2s
|
|
When the number of iterations was small, looking near the original
position of the num was a good idea. As the number of iterations
increases, the positions are fairly random, so speed of lookup is mostly
a factor of how quickly we can scan the whole buffer.
Speeds up part 2 of the problem from 2.2s to 0.12s.
|
|
We now manage the general case of dividing up the work between as many
plumbers as available, as equally as possible. Works for the test case
and the full input case.
(Actually, it seems to speed up the full input case, from around 68s to
55s!)
|
|
|
|
|
|
By realising that the first time we hit the need to skip, the items to
be skipped will be in sorted order; to change them to reverse-sorted
order just requires reversing the items, not re-sorting them backwards.
(On part 1 of the puzzle with a 40 minute limit, the timing goes from
6.6s to 4.3s, average of 5 runs.)
|
|
Even though we change from 3 small memcpy()s per 2 items, to 1 small
memcpy() per item plus 1 big memcpy(), it goes slower?
(On part 1 of the puzzle with a 40 minute limit, the timing goes from
6.6s to 6.8s, average of 5 runs.)
Leave commented out for now.
|
|
|
|
This solves the actual the puzzle, in the case where two plumbers (you
and the elephant) can't reach all the valves in time. But it doesn't
work for the test case, where you can, and it has to look for the most
efficient split of resources.
So, I got the gold star, but I wanted to create a full solution before
committing it. Obviously that didn't happen at the time. Might as well
commit what I have now, and look at improving it with a later fix.
|
|
Like the later puzzles
|
|
Like the later puzzles
|
|
Like the later puzzles
|
|
Like the later puzzles
|
|
Like the later puzzles
|
|
Here we teach the elf how to use the face information to walk around the
cube.
Finally
Just don't ask me to explain this again in 6 months time.
|
|
At the moment, I can't figure out how to break up the long stem of a
T-shaped net properly (and other similar nets with 2 or more faces in a
straight line), for an arbitrary cuboid. This should be possible, and
was something I was hoping to be able to do for this puzzle.
That's not happening, so add in a hackish solution that takes advantage
of some of the conditions of the Advent of Code rules/input, instead of
being a properly general solution.
If possible, come back and take this out later.
|
|
This makes it so that, given cube face 0 is in map->faces[0] and
pointing north, cube face 1 will be in map->faces[1], cube face 2 will
be in map->faces[2], etc..., with their orientations set appropriately.
This will allow us to be able to tell where on the cube an elf is, and
where they're going if they walk off an edge.
|
|
|
|
I need this for working out the shape of the net
|
|
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.
|
|
|
|
|
|
|
|
|
|
|
