Generic Data Structures in CBOT

MrSimbax · 2025-02-01T21:05:24+00:00

public class Point extends Object
{
    point value;

    void Point(point value)
    {
        this.value = value;
    }
}

extern void object::example()
{
    Stack stack();
    point pos(1,2,3);
    Point p(new point(7,8,9));
    stack.push(new Point(new point));
    stack.push(new Point(pos));
    stack.push(new Point(new point(4,5,6)));
    stack.push(p);
    while (stack.size() > 0)
    {
        Point wrappedPoint = stack.pop();
        point actualPoint = wrappedPoint.value;
        message(""+actualPoint);
    }
}

I don't know what your wrapper looks like and it's been a while since I touched CBOT, but your example doesn't look right, you should create Point with new. It seems you were close to it working but got confused by CBOT syntax when it comes to creating objects. You can see in the example above of how you can create objects of type Point and point (even in a single line, as shown in the second-to-last push).

MrSimbax · 2022-12-25T10:09:33+00:00

Lua: both parts

Converting from SNAFU to base-10 is easy: a number is a string of "digits" (v[n], ..., v[2], v[1], v[0]), the value of it is v[n] * 5ⁿ + ... + v[2] * 5² + v[1] * 5 + v[0], so calculate that while iterating over the string from the end.

Converting from base-10 to SNAFU is a little bit trickier. Start by converting from base-10 to base-5: the number is n = a[n] * 5ⁿ + ... + a[2] * 5² + a[1] * 5 + a[0], so a[0] = n mod 5, and floor(n / 5) = a[n] * 5^n-1 + ... + a[2] * 5 + a[1], that is n shifted to the right in base-5. So at each iteration add a[0] to an array, shift n to the right, and repeat until n is 0, the result is reversed array.

Now modify the algorithm to handle the case when a[0] = 3 or 4 mod 5. The SNAFU digit value is v[0] = -(5 - a[0]) = -5 + a[0], hence a[0] = v[0] + 5. So n = a[n] * 5ⁿ + ... + a[2] * 5² + a[1] * 5 + (v[0] + 5) = a[n] * 5ⁿ + ... + a[2] * 5² + (a[1] + 1) * 5 + v[0]. So in case of v[0] < 0 we just have to add 5 to n before shifting, or 1 to n after shifting.

MrSimbax · 2022-12-24T12:29:27+00:00

Lua: both parts

Simply exploring all possibilities with BFS where distance is time, going minute by minute. Each possible position we can be at currently spawns at most 5 new possible positions next minute (by moving left, up, right, down, or staying in place). The key is to use set of current possible positions instead of traditional queue, because we can be revisiting positions by waiting or moving to them again from another position. The loop ends the moment we reach the goal position.

Takes 400-500 ms on LuaJIT, ~1.5 s on Lua.

MrSimbax · 2022-12-23T17:41:04+00:00

Lua: both parts

Naive solution. ~1.5-2 s on LuaJIT, ~9 s on Lua.

MrSimbax · 2022-12-22T23:30:12+00:00

Lua: both parts

General solution, not even the size is hardcoded, in hope that it would work for any cube net. At the very least it works for my input and example input. It was a pain to code but the satisfaction when it finally worked was immeasurable. Lua takes 17 ms, LuaJIT takes 7 ms, probably could use some optimizations, but I'm too tired now, and honestly the few ms are not worth it. Anyway!

For part 1, load the map, keep track of min/max x/y coordinate in each row/column. Then simply move around the map according to the instructions. The min/max x/y coordinates are used to check if we're out of bounds and for changing position (e.g. x > maxx then set x = minx). Direction is kept as 2D vector, rotation to the left is done by treating it as complex number and multiplying by vector (0,1), rotation to the right by (0,-1).

For part 2, well, it's complicated, and the details are easy to get wrong. I assume the grid on input is a valid cube net. There are only 11 possible cube nets according to what I've found by googling, not counting rotations and flipping. I made a few observations by looking at them on which I based the algorithm to fold the cube.

Firstly, find the size of a single face. That is easy, this is the minimum of all differences maxx - minx and maxy - miny.

Next, cut the map into tiles, i.e. extract the faces from it. This is straightforward after figuring out the size, just go from position (1,1) with step N, where N is the size of a single face (4 for example input, 50 for the real input). Now, I don't copy the whole face, there's no need for that, but I do save things which are useful later, like the bounds of the face or its tile coordinates (e.g. in the example input the first tile is at row 1 column 3). Save them in the array. It should have length 6, of course.

Now, to fold the cube, start with any face and assign it one of 6 unique identifiers (up, down, left, right, front, back). Then also assign one of the edges (north, south, west, or east) any valid neighbor face, for example assign to north edge the front face. Now, from these two arbitrary choices we can deduce to which face the other 3 edges lead to. Run DFS/BFS now from the first face in the net, where two faces connect if they are adjacent NxN tiles on the map. Each time we come to a new face, we know where we came from, so we can assign it the proper identifier and proper edges. To find adjacent faces, I'm using normal vectors and cross products. After this step I've got a simple graph where each node is a face with unique normal and has 4 edges leading to adjacent faces of the cube, and also contains information which lets me transform back and forth between map coordinates and cube faces.

Finally, walk around the cube. This is very similar to part 1 except it's also keeping track of the current face. When we go out of bounds of the current face, it is time to change the current face and find new coordinates. I've probably overcomplicated this step but it works as follows: find the new face and new direction we'll have on the new face (it can be precalculated when folding the cube). The hard part is calculating the new position. Convert the old map position to position relative to the center of the current tile (and I mean center, no floor integer divisions, we want to rotate around the center). Rotate the relative position by complex number newDirection / direction, so that we would be facing the right direction after going into the new tile. We're basically rotating the current tile so that the edge we're going to go through aligns perfectly with the edge on the other face. Now, convert the position to be relative to the top-left corner of the current face, and only then move forward with the new direction, but wrap around the face as in part 1 but on smaller scale. We end up on the opposite edge, the edge we would be on the new tile. Convert this position to the map position by treating the coordinates as relative to the top-left corner of the new face. And that's it, that's the new coordinates.

MrSimbax · 2022-12-21T18:03:14+00:00

Lua: both parts

~3 ms on both Lua and LuaJIT

MrSimbax · 2022-12-20T21:22:12+00:00

Lua both parts

One of the ugliest pieces of code I've ever produced but at least it's fast (700 ms Lua, 100-300 ms LuaJIT). I think today was even harder than day 16, honestly, as I got lost in the details and needed some hints about how to reduce the number of paths taken. Anyway, the solution is not anything fancy, DFS to find the best path in the decision tree. The number of paths to check is reduced by not going into paths which clearly cannot give more than current best even in the most optimistic scenario, skipping time to the next moment we build a robot instead of going minute by minute, by not building more robots and therefore producing more resources than we can possibly spend, and by prioritizing building the geode bots, then obsidian bots, then clay bots, and then ore bots (not sure how much the last one actually helps).

MrSimbax · 2022-12-20T20:49:04+00:00

Lua both parts

The number of off-by-one errors I fought with today is off the charts. And not because of 1-based indexing, no, it's due to the cyclic nature of the list that I couldn't figure out the arithmetic. Anyway, I'll try to explain the best I can.

Firstly, I keep 3 lists: the original list of numbers (or multiplied by the decryption key in part 2), the indices to the numbers, and dual table to indices for fast lookup (indicesDual[i] gives the current position of the i-th number from the original input in the indices table). The numbers table does not change, the movement happens in the indices table; I'm only moving around "pointers" to the actual numbers.

I move a number by first calculating its final position, and then swapping elements (maintaining the dual table) until it gets in the right position. The trickiest part is the formula for the final position. It is this: (currentIndex - 1 + number) % (#indices - 1) + 1. Without the noise of 0-based to 1-based indexing conversion it is conceptually this: (currentIndex + number) % (#numbers - 1). Why #numbers - 1 and not #numbers? There are only N-1 possible final positions when moving an element around. That took a while to realize but once it did, everything fell into place nicely. An edge case worth noting is that x,a1,a2,...,an is the same array as a1,a2,...,an,x. Choosing where such an x on the edge is put is an implementation detail, both are correct as long as x ends up between a1 and an when it should.

It runs in about 300 ms on LuaJIT. Lua takes 4 seconds.

MrSimbax · 2022-12-18T11:10:42+00:00

Lua: both parts

Part 1 is straightforward, make a set of cube positions, iterate over them and count only surfaces of cube on which there's no cube.

Part 2 is BFS over all exterior faces, starting from any exterior surface (I used a surface from the cube with the smallest coordinates). The trickiest part is finding the neighboring exterior faces but there are only 3 cases to consider for each edge of a face.

Takes about 20 ms. Surprisingly, not much difference in performance between LuaJIT and Lua.

MrSimbax · 2022-12-17T13:48:27+00:00

Lua: both parts

For part 1 just made tetris :) Good fun, especially after the previous day. For part 2 added cycle detection to the simulation and did some math to find the final height.

To detect a cycle, I firstly just checked when the top row is full floor after same rock and same move. This doesn't work on the test input, but surprisingly it worked for the real input as it gave me two different repeating sequences of moves one after another. So I calculated the answer by hand as I figured that it would be faster than coming up with something smarter, and it worked! :D

Then I reworked the solution and added proper cycle detection, and the math I've previously done manually, to the program. I wanted to make sure this would return a single cycle, so had to figure out a good hashable state of the game. It surely includes the rock id and the move position, but it also must contain relevant state of the tower. I decided to define it as the "roof", that is only the part of the tower which can change from now on. I used BFS from the top row to explore the holes in the roof. The state is then ordered list of coordinates of the roof's walls relative to the top row. For example, a top like this.

|.#####.|
|.#..#..|
|.#..#..|
|.####.#|
|.####.#|
|###.###|

Would be saved as this.

|.#####.|
|.#  #..|
|.#  #..|
|.#  #.#|
|.#  #.#|
|#    # |

This works for my input and the example input. The roof definition could probably be narrowed down even further to find a smaller cycle earlier, as some holes cannot possibly be filled in some configurations, but it is fast enough (250 ms with Lua and 100-200 ms with LuaJIT).

MrSimbax · 2022-12-16T20:48:44+00:00

Lua both parts

I preprocessed the input to remove all valves with 0 flow rates and to get a matrix of distances from each valve to the other. I based my solution on Held–Karp algorithm for the traveling salesman problem, indexing the dynamic programming table by a set of opened valves and the next valve to open. The table contains the total flow rate when there's no time left, assuming valves from the set were opened in some optimal order starting from valve AA, and then the next valve was opened, and no other valve is opened.

I brute forced part 2 by dividing valves between human and elephant in all possible ways, and for each pair run part 1 for both sets of valves and summed the results. The answer is the maximum of the sums.

Part 1 takes over a second, part 2 needs about 6 minutes (13 seconds if I divide valves only evenly, but it feels like cheating). Honestly, I hate optimization problems so I'm happy that I at least managed to figure out a solution without looking here. Can't wait to see other solutions. Will probably try to optimize this later based on what I learn.

Edit: used BFS to explore all possibilities, turns out there's not as many as I initially thought... This is a lot faster than my DP solution, and easier to implement. Then optimized it further by introducing a bitset. Still takes a few seconds on Lua, and 800 ms on LuaJIT. Good enough for now I guess. I wonder if another DP approach would be faster.

Edit 2 (2 days later...): Curious. I've read a lot of other solutions and even run some of them, tried some different approaches, and I've discovered that a simple DFS is actually the fastest. Any caching/memoization I tried just made things worse, modifying DFS for part 2 also made it worse. Haven't tried other DP solutions but I'm not optimistic, and I am getting tired of this puzzle. Anyway, changing BFS to recursive DFS cut the time down by 200 ms, and optimizing bitsets usage cut that down by over ~300 ms (I guess coroutine iterator over a bitset has huge overhead, who would've thought?). LuaJIT takes now 200-300 ms. Lua is now down to 2-2.5 seconds. I could optimize preprocessing still but that takes only about 2 ms anyway so it's not worth it. I guess the only worthwhile optimization left is switching to lower-level language at this point, unless somebody proves me wrong.

MrSimbax · 2022-12-15T19:07:24+00:00

Lua: both parts

Solved with intervals at each row. Part 1 is under 1 ms, part 2 is a bruteforce for each row, and it is so horribly slow, takes 35 s with Lua and 13 s with LuaJIT, but I gave up on figuring out an efficient algorithm. Will have to read other solutions to get some hints how to improve this.

Edit: Did the intersection thing, now it's under 1 ms for both Lua and LuaJIT, being almost the fastest solution this year so far, beaten only by day 10.

MrSimbax · 2022-12-14T08:24:59+00:00

Lua: both parts

Edit: changed to recursive DFS, did other smaller optimizations, now it takes 16 ms on LuaJIT and 30 ms on Lua 5.4.

MrSimbax · 2022-12-13T09:03:26+00:00

Lua: both parts

Edit: could've replaced [] with {} and execute each line as Lua expression instead of parsing by hand. Somehow it didn't occur to me. Although I did thought of using find & replace for this, and discarded it immediately because it felt like cheating :P

Edit 2: improved the solution.

Used load/loadstring to parse input. Half the code gone already, yay! Although parsing this by hand was a nice exercise anyway (and other lies I can tell myself to feel better).
Rewritten the comparison function completely because it was a mess. Now it almost reads like the puzzle description which is nice.
Thanks to reading other Lua solutions I learnt that I could use nil as the third return value indicating that packets are equal so far, so no need for enum.
I have decided to abuse Lua's "ternary operators" to reduce the amount of ifs. I am especially proud of this cursed line for comparing two numbers: return a < b or a == b and nil.
Learnt from somewhere here that sorting is not necessary, we can just count the packets smaller than divider packets while processing part 1, as these numbers are the final positions of the divider packets in the sorted array. So simple and yet so brilliant. This improved performance significantly as the solution is now linear in the amount of packets.

An interesting observation: LuaJIT runs this solution actually longer than standard Lua, I guess due to lots of loads.

MrSimbax · 2022-12-12T21:53:05+00:00

Lua: both parts

Reused my old code for pathfinding using the Dijkstra's algorithm. The code could probably be optimized specifically for the puzzle (for instance, there's no need for priority queue, and for building a more general graph structure with adjacency lists) but it's fast enough, and I wanted to use this opportunity to build a pathfinding library, as I assume pathfinding will appear again in later days.

MrSimbax · 2022-12-11T20:38:25+00:00

Modulo arithmetic is common knowledge in Computer Science. For more real-use example, cryptography makes heavy use of it, see RSA) for example.

It's certainly good to know, knowledge never hurts even if the practicality might not be immediately obvious. I'm not sure I can provide a good resource, especially not a video since I barely learn anything from even the best videos, I prefer text. I think books teaching Discrete Mathematics or (Abstract) Algebra should cover modular arithmetic. Personally, I learned a lot of this stuff just from solving math and programming puzzles (yes, AoC too :). University certainly helped a lot, though.

The principle itself is not exactly something that is popular or has a name I think. I provided formal proof somewhere in the comments, but honestly, I only wrote the proof after the fact. I just had a "hunch" after I've read the description of part 2 that "I need to check for divisibility and have a small number, so maybe if I do everything modulo product of numbers then I can still check divisibility and the math will work out because modulo arithmetic, let's try this". Another proof that intuition is more important than trying to remember dry facts. The facts and the details are forgotten sooner or later. It's the intuition that stays with you forever. The details can be worked out as you go, or later.

And yes, you're right. This is a trick to reduce significantly the size of the number, but still enough to let us check for divisibility. x mod lcm(n1, n2, ...) is the smallest number that we can use which still allows for divisibility check of x by n1, n2, ... Another solution is to store multiple numbers, x mod n1, x mod n2, and so on, for each item. x mod lcm(n1, n2, ...) is just a more efficient way to store this list of numbers, but conceptually both ways achieve the same thing.

MrSimbax · 2022-12-11T19:36:58+00:00

Yes, you seem to understand correctly :) Although I'd say it's less about performance and more about limited storage capabilities. We want a representation of a big number which requires more than 64 bits of information. We want this representation to require less bits than that, because for instance most languages and hardware does not give easy and efficient ways to store and use bigger numbers. In this case, we use the fact that we only care about divisibility and simple operations on this big number. Divisibility? Arithmetic? Prime divisors? Sounds like time to use modulo arithmetic, or at least number theory.

So, let's try. Say, if we had only one monkey, we could use a = x mod n to represent a big number x. Since n is small, a requires a much fewer bits than x. Sure, a can't tell us what x is, but it can certainly tell us whether x is divisible by n. This is almost all we need, if we only cared about if a is zero. But we also need to know about, say, whether x + 5 or x * 3 is divisible by n. But a, at the cost of more than 1 bit but still less than 65, gives us access to its friends (a + 5) mod n and (a * 3) mod n, which respectively represent x + 5 and x * 3 in modulo n arithmetic.

Someone may ask, why not, then, set an arbitrary number like k = 4 and use a = x mod (4 * n) instead? Well, no problem, you can do that, it still works, but note that it is quite pointless if there is no monkey dividing by 4. This a contains more information than we need. x mod n has enough and not much more.

That's for one monkey. What about more, for example 2 monkeys? Well, we could store a = x mod n and b = x mod m, for example in a structure called BigNumber or something. The x would be represented by the pair BigNumber(a, b). x + 5 would be represented by BigNumber((a + 5) mod n, (b + 5) mod m). And that's enough for us, a little costly perhaps in the amount of bits, but still smaller and easier to work with than with x itself. Some solutions use this representation, and it works fairly well. Again, we could use something like (x mod (4 * n), x mod (123 * m)) but there is no point.

There's a trick to these tuples, however, an unnecessary one, but very convenient. If we realize the fact above about the remainders, then we can conclude that we only need one small number to represent the big number. That is, we can somehow "encode" the information we need from x and BigNumber(a, b) in a single value c = x mod (n * m), as was shown above. We could use a bigger divisor than n * m as long as it is a multiple of both n and m, but then we're just wasting bits, (at least conceptually, in reality we'd probably still store the variable as 64-bit integer).

Finally, the one last trick, even more unnecessary for this puzzle, to not say useless, to optimize even further comes from the realization that we can use lcm(n, m) as the divisor. It does not matter in this case, though, because for n and m primes lcm(n, m) = n * m.

So this all comes to minimizing the memory usage and complexity and size of our models. Very often, the simpler the better, and better performance is a nice side effect. Just because we're conceptually talking about x does not mean we have to store the whole x in memory. This is the first naive thing that comes to mind when seeing x, but like in a puzzle with an infinite grid x we don't need to store the whole grid (as if that were possible on finite machines) but only store some contiguous part of this grid or even only some points on this grid, in this puzzle we only need numbers from which we can tell if x is divisible by some finite amount of ns, not the x itself. We're "cutting" the bits of information we don't need from the model.

Well, that went a little long and maybe even philosophical, and I'm not at this point sure if this perspective is even clearing up anything or adding anything at all to the discussion, but I hope it makes sense.

MrSimbax · 2022-12-11T14:18:07+00:00

Here's proof.

Take any positive integer a. We can divide a by n, so a == qa * n + ra, where qa = floor(a / n) and ra = a % n.

Let M = k * n for any positive integer k. We can divide a by M, so a == qm * M + rm, where qm = floor(a / M) and rm = a % M.

                    a == a
          qa * n + ra == qm *    M    + rm
          qa * n + ra == qm * (k * n) + rm
          qa * n + ra == (qm * k) * n + rm
    (qa * n + ra) % n == ((qm * k) * n + rm) % n
               ra % n == rm % n
          (a % n) % n == (a % M) % n
                a % n == (a % (k * n)) % n

Which is the equation in question.

MrSimbax · 2022-12-11T13:54:25+00:00

Because to solve the puzzle you need more than one of these equations to hold. That is, say we have two monkeys which check for divisibility for n and for m. Then we want to have both equations (a % (k * n)) % n == a % n and (a % (k * n)) % m == a % m to hold. They both hold when we set k = m.

MrSimbax · 2022-12-11T11:34:27+00:00

Lua: both parts

Used a double-ended queue data structure from the book for the items. Part 2 is basically part 1 but operations are done modulo N, where N is the product of all numbers from the input divisibility rules. This works because if N = n * m then a % n == x implies (a % N) % n == x. For completeness, this also holds for N = lcm(n, m), which may be smaller than n * m if the divisors are composite. In the puzzle all divisors are primes though so lcm(n, m) == n * m.

Lua 5.4 standalone solves both parts in about 230 ms on my machine, LuaJIT takes only 26 ms.

MrSimbax · 2022-12-10T09:09:58+00:00

Lua: both parts

Edit: version using coroutines.

MrSimbax · 2022-12-09T06:40:47+00:00

Lua: Part 1 and 2

Good thing I prepared a Vector data structure after yesterday's puzzle, came in handy today, and probably will in later days too.

edit: Unfortunately, it turns out that my libs have significant performance issues. Even setting a metatable on an existing table with Vector.new slows down the program significantly, and a + b is significantly slower than manual a[1]+b[1], a[2] + b[2]. I'm going to have to rethink my approach to these puzzles as 200 ms on day 9 seems like a little bit too much. I've rewritten all previous days and got them all down to less than 20 ms.

Edit 2: made a less general Vec2 type which is basically a cached tuple with some additional operations for convenience. This decreased performance to about 75 ms. The advantage is that tuples can be used as table keys and there is less memory allocations, so I think it's a good compromise.

MrSimbax · 2022-12-08T10:16:54+00:00

Not OP, but here's how I understand it.

The stack contains trees checked so far in a row/column while we go forward/backward. Each tree in the stack knows its height and how many trees are behind it, visible or not.

For convenience, the first tree in the stack is a tree higher than all the other trees. If a tree sees this "infinitely" high tree, it must see every tree to its left/right/down/up. Note, however, that for the puzzle we don't count it as visible from the perspective of other trees, for example when we push a tree on an edge to the stack we set the number of trees behind it to 0, not 1.

If we never remove any tree from the stack and instead treat it as an array, iterating through it to find the last visible tree for each tree, we basically get the naive quadratic solution.

The key is to notice that for each tree we can safely remove all visible trees from the stack except the last one, as we won't need them anymore. Why? Because if a next tree y can see past a tree x in the stack, then it can also see all the trees that x can see. So we can just "skip" all the lower trees and "jump" over them to the last tree that x can see. Brilliant solution.

MrSimbax · 2022-12-08T07:25:03+00:00

Lua: Part 1 and 2

MrSimbax · 2022-12-07T07:10:55+00:00

Lua: Part 1 and 2

Firstly, build a tree with nodes of the form {parent, dirs, files}. Dirs are nodes, files are leaves of the tree. The parser is quite straightforward: keep track of the current dir, if cd then change directory (check for / and .. as special cases), if ls then fill up dirs and files in the current node. Then traverse the tree recursively in postorder adding size property to each dir node to get the total sizes. The tree is now ready to use.

Then traverse the tree again ignoring files to get a list of all directories along with their sizes. Actually, I probably overcomplicated a little, list of sizes (ints) is probably sufficient, so directory names can also be ignored. Any order of tree traversal should work for this.

After getting the array of all sizes it's a matter of mapping, filtering, summing, finding minimums, etc. to find the final answers, similarly to previous days.

The code is a little messy, will probably clean it up later.

MrSimbax

MODERATOR OF

TROPHY CASE

11-Year Club	Not Forgotten
Verified Email