The basic combination generator is clear enough, it’s how to optimise it so as not to try every option forever. When I have some spare moments I’m going to restart from scratch with the knowledge I gained from writing versions 1-4 and see if that helps.
1 Like
Day18 part 2 visual spoilers
Here’s one of my droplet slices. Sadly, my results are not yet good for part 2. Too low. I think I must have overlooked some of the inside somehow connecting to the outside via L shapes or something.
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . # # . # # # # . . . . . . . .
. . . . . # # # # # # # # # # # . . . . . .
. . . . # # # # # # # # # # # # # . . . . .
. . . . . # # # # # o # # # # # # # # . . .
. . . . # # # # # o # o o o # # # # . . . .
. . . # # # # o o o o o o o o o # # . . . .
. . # o # # # o o o o o o o o # o # # . . .
. . # # o o o # o o o o o # o # # # # # . .
. . # # # # # o o o o o o o # o o o # # . .
. . # # # # o o o o o o o o o o o # # # . .
. . # # # # # o o o o o o o o o # # # . . .
. . . # # # o # o o o o o # o # # # # . . .
. . # # # o # # o o o o # # # o # # # . . .
. . . # # # # # # o # o o o # o # # # . . .
. . . . # # # # o # # o # # o o # # . . . .
. . . . . . # # # # # o # # # # # . . . . .
. . . . . # # # # o # # # # # # # . . . . .
. . . . . . . . . # # . # # # . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
My code looks neat for once which makes it worse that it isn’t working somehow.
1 Like
Slice? What if this were the topmost level?
1 Like
Day 18: My process is as follows:
- go throught the whole matrix and check each node that is a droplet piece. Check all six faces what is the neighbor in that direction: if the neighbor was filled with “outside” value or is beyond the matrix boundaries I count the face.
I had too many ArrayOutOfBounds…
In the meantime I’ve written the input parsers for Day 19 and 20. Because those were easy.
Some crucial Code for Day 18
to obtain neighboring blocks for droplet in each dimension and the function that calculates if such a block is counted
Block getNeighboringBlock( Block block, Dimension dimension, boolean negative ) {
int modifier = negative ? -1 : +1;
int x = block.x + ( dimension == Dimension.X ? modifier : 0 );
int y = block.y + ( dimension == Dimension.Y ? modifier : 0 );
int z = block.z + ( dimension == Dimension.Z ? modifier : 0 );
return new Block( x, y, z );
}
boolean isOutside(Block block){
return isOutsideOfMatrix( block ) || getValue( block )==OUTSIDE;
}
Here’s the whole thing. As can be seen, I was desperate enough to write javadoc on all my methods oO
My code solves the test input. But not mine. For part 2. Part 1 was easy.
I checked
- 13 faces facing the border. this is not the missing amount.
- all my blocks are present, I counted them and they equal the length of the input
- I am having some kind of dumb block that I cannot see beyond (just like the puzzle oO)
- visually the slices of all 3 dimensions look like my “outside” algorithm worked fine.
- I previously checked that there are no blocks marked as “undefined” (neither outside nor part of the droplet) that border on any “outside” blocks (confirming my visual check) so there are no hidden pockets that I have overlooked but this is what I would expect… ah well. Sleep. I need more of that.
day 18
Hmm, interesting - I started with a known empty space and flood-filled from there.
day 21
It takes a lot to make me use recursion, but sometimes it feels like the obvious way and this was one of those days. Then part 2 was an expanding binary search using “-” as the root op.
I didn’t actually implement
flood filling. Because I didn’t know the technique existed. Which is probably the problem. I instead did something else.
I look at the “cube” from each side and fill every “ray” until I see a piece of lava. Then stop. Then check if there are any more cubes that are not lava that can be reached from any of the cubes marked as outside in the first pass. But there were none.
I will later try and implement a proper flooding 
edit: it took me all of 10 minutes to implement the proper algorithm and I got it right on the first try. Meh. Teachable moment?
1 Like
Flood fill is just a special case of DFS.
and if I had to give one piece of advice about AoC it would be “be familiar with DFS and Dijkstra”. Or A*, which I’m not good enough at yet.
1 Like
I still don’t know why my other attempt doesn’t produce the same result. Ah well… if it works it works. Now for Day19
1 Like
So Day19… I have already found out that Matlab can simulate petri networks. Maybe I should play a round of Kanban EV…
And looking at it closer and with my experience with homebrew solutions on Day 18… I don’t want to go down that path again. And yet, I know I am going to try.
1 Like
Lack of time… For Day 19: I programmed
some preparatory code
as in: a production simulation.
But I lack a means of optimizing ore usage:
All the blueprints were the same and the thing that is needed everywhere is ore. The question becomes in each step where to use the current amount of ore? Maybe the solution is to try another depth first search approach tracking just ore usage. But I have no idea if there is a way to remove paths from consideration? 24 is not a huge amount of steps to simulate but with 4 possible choice along each step we still get 4 x 4 x 4 x 4 x blueprints paths to generate. I am reasonably sure just like in the example where there is a blueprint that never builds another ore bot that there is one where it is better to build a second obsidian bot before the first geode bot.
I am wanting to introduce heuristics to prioritize certain states but whenever I think I’ve got one I think, no surely there is a situation where we definitely need to do the other thing. (Probably because my first attempt at prioritizing the bots like this geode>obsidian>clay>ore and strictly build what can be build failed really badly with a lot of Clay robots and nothing else)
Day 19: I haven’t got it working yet, but
I think at each node the choices are for each robot X:
- build robot X now (I have the resources, advance one cycle)
- do nothing now, build robot X in N cycles’ time when I have the resources (advance that many, if production > 0 and there’s enough time left)
and then “build nothing until end of time”.
Day 22
Did part 1 all right, but then I read part 2 and an utter lack of enthusiasm washed over me. These geometric problems are usually the painful ones and I ended up solving it on virtual paper instead.
Finally finished off my day 19 code. At the very least it’s a lot cleaner than the first time I came up with it. PostScript has neither an else if construct (it does have else, and you can nest stuff, or there are other tricks*) nor a continue, though it does have break.
* 1 { ...code...} repeat is technically a loop, so you can exit it at the end of your conditional clause and not execute the remaining statements. Of course you can’t simultaneously jump out of the actual loop you were in; no deep exits here.
1 Like
Day 23.
It looks like Conway’s Life, but I’m glad to say it isn’t. In fact I end up with a fixed-size list of x, y coordinates, then build a second one of proposed moves, and have a hasher for those coordinate pairs so that I can easily see whether there’s something at a particular spot.
Also good to know for any random day: “On the other hand, when you clone two dimensional or multi-dimensional arrays, a shallow copy of elements is made i.e. only references are copied. This cloning of arrays is done by the ‘Clone ()’ method provided by the arrays.” (link)
Thanks Java.
Perl has dclone in Storable. I tend to regard using it as an admission of failure, but oh boy it can be handy.
In PostScript, it’s a bit weird, because if a is [ 1 3 2 ] then adding 1 to the first element is
a 0 a 0 get 1 add put
or possibly easier to understand
a 0 get 1 add a exch 0 exch put
BUT if a is [ [ 0 1 ] [ 2 3 ] ] etc. then I can use the references and don’t have to put all the way back up the tree:
a 0 get % top of stack is a[0] which is a reference
dup 0 get 1 add 0 exch put
I do hope this is never directly useful but I think it’s improving my Rust.
2 Likes
I think I need to postpone Day19 I just cannot wrap my head around how to do a DFS on this one. And if I could I might be able to find a different solution. All I can do right now is Breadth-First and that is … not working out really I cannot weed out enough states to make it feasible
Btw in order to get Java to round up integer division I have to do this: a/b + (a%b==0?0 : 1)
Hmm. I think I did (a-1) / b + 1.
My only real optimisation is:
On examining the state: if I magically build a geode robot per tick after this, how many geodes will I have? If that’s less than a total I already have, bail out now.
I tried in an earlier version, but not in the final version: if I already have enough X on hand that I can build an X+1 robot per turn for each remaining tick, I don’t need another X robot.
I suspect there are other possibilities, and my code took A While to run even allowing for PostScript’s slowness.
(Day 19–still not king) I have a couple of heuristics:
- geode is always a valid option as long as there exists any obsidian production
- building more obsidian bots is only valid if it means I can built at least 1 more geode bot before time runs out (that’s one big formula which I think is not quite correct)
- right now I am trying to figure out how many ore bots to build. If ore bot costs more than any other bot in ore than you never built ore. But how much ore production is really needed? Because ore is so early in the chain it eliminates most of the exponential growth from the problem if I can stop the search from trying for more ore production. (this must sound like gibberish if I tell my inlaws about it tomorrow night at dinner)
1 Like
In non-AoC news, I’ve just written a basic command-line ActivityPub/Mastodon posting client in Rust.
I’ve been doing mostly Perl for 20+ years. The great thing about Rust from that perspective is that while actual code-writing time may get a bit longer, and there are occasional major frustrations, the debug time – i.e. from getting a valid compile (or in Perl’s case syntax check) to being happy that the thing is working – is vastly lower, because most of the mistakes I make are caught by the compiler.
2 Likes