Optimal triple town algorithm

Question

I've been trying to find an optimal algorithm for a problem inspired by the game 'triple town'. The game goes as such:

You place objects in a grid, and each time you make a set of three, they condense into one object of higher level at the position of the last object placed.

---

---

Furthermore, if you place three of these b objects together they again compress to form an even higher level object.

---

---

---

Note: in these diagrams the level of an object is expressed as a_i, b_i, and c_i and the subscript denotes the objects number in the set of three.

To simplify things, I am only considering when every object you have to place is of the lowest level.

Now my questions are:

1: Is there an algorithm to determine the least amount of grid area needed to make an object of level x, given x?

For example, for level a you need 1x1, for level b you need 1x3, for level c you need 1x5.

2: Given the dimensions of a grid, can we find the highest level and number of objects achievable?

For example, for a 2x2 you can get 2 level 'a's and 2 level 'b's

3: Is there an algorithm to find the optimal order and position of objects to get the highest possible level, given a fixed grid?

For example, for a 2x2 you can get (1,1),(1,2),(2,2)

4: Given a position of an intended level x object, what set of moves minimize the amount of space needed to make this object?

5:What are the optimal complexities of these algorithms?

Update:

One thing that I think is prominent in the finding of solutions is that the getting an item of level x can't be done in any arbitrary place.

For instance: [ _ _ _ _ c] is impossible to achieve in a fixed 1 by 5 grid because you need your last b in the 5th place, and therefore your last a in the 5th place. So to place the first b: [a _ _ _ _]->[a a _ _ _]->[_ _ b _ _] or [_ a _ _ _]->[_ a a _ _]->[_ _ _ b _]. In both cases there is not enough room to place 3 'a's to make the last b of the c.

Another thing, we can't assume that anything can be unrolled to a 1 dimensional grid. This becomes clear with my next point.

Something interesting that I have found:

There is a minimum closeness to the boundary that a level c object can be in a 1 dimensional grid. [_ _ a a a]->[_ _ _ b]->[_ a a a b]->[_ _ _ b b]->[a a a b b]->[_ _ c _ _]. So a level c object in a 1 by 5 (optimal) grid can only be made at the 3rd position.

It follows that this is the highest level that can be made in 1 by any number grid. Take a 1 by infinity grid:

..._ a a a _ ... -> ... _ a a a b _ ... -> ... _ a a a b b _ ... -> ... _ c _ ...

now we try to get another c directly next to it:

..._ c a a a _ ... = ... _ c b _ ... or ... _ c _ b _ ... or ... _ c _ _ b _ ...

The only option is ..._ c b _ ... because the others make it impossible to form another b between c and b. Our only option prevents our only way to create c directly next to our first c because it blocks the last c from going there. Therefore, in one dimension, c is the highest level we can make. In other words, the problem must be considered in 2 dimensions.

Answer 1

EDIT: The below is actually false, and here's why: do what it describes to get a "c", here's how that goes: _ _ a a a -> _ _ _ _ b -> (..) _ _ _ b b -> _ _ b b b -> _ _ c _ _

So the "c" is now in the middle of the line, and the prepending doesn't work this way. I leave it here so if someone read it, at least there's an explanation why it's false. Maybe that'll save you some time thinking about the same mistake.

---

[FALSE FROM HERE] 1: You can always do it in 3+2*(x-1) since you just "prepend" the required elements and for every "level" of letter. Proof by induction:

to get a "b", you need 3+2*(1-1) = 3 spaces.

If you can get level x in 3+2*(x-1) spaces, level x+1 takes you 3+2*(x-1) spaces for building a character of level x and 2 storage spaces, costing you 3+2*(x-1)+2 = 3+2*((x+1)-1) spaces.

---

Think about what this suggests: if you want to package your letter into a small area, find a small area that holds 3+2*(x-1) spaces and turn the prepending when needed. This means you can always go outwards from the position you want to end up in in spirals. Here's the twist though: you possibly need your last stone of each level to come from alternating directions so you won't move away from where you started. Complexity of actually going through all steps is O(3^x) since you need 3 letters of the previous level for the next one, and it's all multiplicative.