Simple Combo/Permute calculation

[DaveC426913]

TL;DR Summary

How many possible shapes can there be, given these parameters?

I'm playing a Steam game called Shapez wherein the goal is to produce and deliver given shapes to the Hub by conveyor belt.

In the screencap you can see resources of discs and squares and well as green and red, which are to be extracted, chopped up and recombined to form the "product" specified in the Hub.

Here's a sample of three different final "products" with multiple quadrants, layers, colours and shapes (all four shapes are at least partially represented here: a disc, star and windmill; a full square is only partially represented):

I was lying awake last night, trying to figure out how many possible products there can be, and I kept getting intuitively wrong numbers.I'll start with the easy one. I'll enumerate only products that are fully rotationally symmetrical. i.e. all four quadrants of the deliverable product are identical. Thus:

This is a blue windmill, on top of a white disc, on top of a blue disc.Parameters:

• There are four primary shape resources: square, disc, star and windmill.
• Each shape can have one of seven colours: R,G,B,C,M,Y and white.
• And there can be up to four layers. (There is always a bottom later; if there is a second layer, it is on top of that; if there is a third later, it is on top of that, etc. There are no "empty" layers.)
• (Size is not a parameter; rotational orientation is not a parameter.)

So, the number of (symmetrical) products should be 4x7x4 = 112. Is this right? Is this too low?Now we go to asymmetrical products:

Each quadrant of an asymmetrical product can have one quarter of any of the above, so:

112⁴, or about 157 million, right?I'm just not sure I've enumerated it correctly. I suspect I've done the layers wrong in the symmetrical step. It's not just x4, is it? Is it to the power of 4?

 

[erobz]

I’m assuming adjacent layers must be of a different color?

Also, can you put a square on top of a fan? It seems ordering matters too.

 

[DaveC426913]

I’m assuming adjacent layers must be of a different color?

No.

I mean, it might be true, but that can be treated as an exception. There are likely many exceptions - combinations that have specious rules.

 

[erobz]

No.

No to both?

 

[DaveC426913]

Also, can you put a square on top of a fan? It seems ordering matters too.

You can. There are products where the points of stars are all you can see behind a disc.

Higher layers are rendered smaller for this purpose, as seen in the examples, but that has no effect on combinations.

 

[erobz]

e.g. a blue circle , on a blue circle , on a blue circle, etc... is a valid configuration?

 

[DaveC426913]

e.g. a blue circle , on a blue circle , on a blue circle, etc... is a valid configuration?

Yes. It may not actually be called for, but that doesn't mean it isn't part of the set of all possible products. It is not categorically ruled out.

Note that - whether or not it's called for - I can still produce it if I choose. Pretty easily, in fact.

 

[erobz]

So 1, 2, 3, 4 layers are all good too? If so:

1 layer configurations $4\cdot 7$

2 layer configurations $\left( 4 \cdot 7\right)^2$

3 layer configurations $\left( 4 \cdot 7\right)^3$

4 layer configurations $\left( 4 \cdot 7\right)^4$

Total symmetrical configurations:

$28+28^2+28^3+28^4 = 637,420$

 

[erobz]

If you are going to try to find the number of configurations in general (each quadrant), its going to be a much worse combinatorics problem than that because of removing rotationally symmetric configurations...well over my head.

For single layer - single shape, is blue circle quad 1 distinct from blue circle quad 4?

 

[DaveC426913]

If you are going to try to find the number of configurations in general (each quadrant), its going to be a much worse combinatorics problem than that because of removing rotationally symmetric configurations...well over my head.

Good point.

For single layer - single shape, is blue circle quad 1 distinct from blue circle quad 4?

No. That's what I meant by 'orientation is not a parameter'.
But I see why it can't be ignored, because ignoring it would let duplicates slip in.

 

[pbuk]

Total symmetrical configurations: $28+28^2+28^3+28^4 = 637,420$

So with $n = (28^4 + 28^3 + 28^2 + 28)^4 = 637,420$ quadrant types there are $n ^ 4 = 165,083,148,768,756,940,960,000$ possible permutations: if we divide this by 4 to get 41,270,787,192,189,235,240,000 we will eliminate rotations but we will have eliminated too many (for instance the unique permutation {type1, type1, type1, type1} will have been incorrectly "eliminated" 3 times) so the answer is a little over that. I make it 41,270,830,356,497,512,121,750: can you get this result or have I made a mistake?

 

[erobz]

So with $n = (28^4 + 28^3 + 28^2 + 28)^4 = 637,420$ quadrant types there are $n ^ 4 = 165,083,148,768,756,940,960,000$ possible permutations: if we divide this by 4 to get 41,270,787,192,189,235,240,000 we will eliminate rotations but we will have eliminated too many (for instance the unique permutation {type1, type1, type1, type1} will have been incorrectly "eliminated" 3 times) so the answer is a little over that. I make it 41,270,830,356,497,512,121,750: can you get this result or have I made a mistake?

Removing rotational symmetry:

For a 1 layer 1 quadrant selection, there is only one configuration.

There are then $4\cdot7 = 28$ ways to select a shape and a color.

For a 1 layer 2 quadrant selection, there are two configurations. Sides touching, corners touching.

Thats $2 \cdot \left( 4\cdot7 \right)^2 = 1,568$

For a 1 layer 3 quadrant selection, there is one configuration.

Thats $\left( 4\cdot7 \right)^3 = 21,952$

For a 1 layer 4 quadrant selection, there is one configuration.

Thats $\left( 4\cdot7 \right)^4 = 614,656$

Total 1st layer configurations - removing rotational symmetry $638,204$, which is not $\frac{\left( 4 \cdot 7\right)^4}{4} = 153,664$. So for the general case, I don't think that's working.

Also, I feel like there is a layer dependency issue to consider as well.

I think the possible configurations of the second layer, hinge on what configuration has been selected on the first layer? i.e. putting the blue layer on top of the green layer below would not be allowed?

But this would be valid.

Maybe I'm misinterpreting that part.

 

[pbuk]

I feel like there is a layer dependency issue to consider as well.

I think the clarifications in #5 and #7 implied that the layers are entirely independent.

putting the blue layer on top of the green layer below would not be allowed?

View attachment 326240

Why not?

 

[erobz]

I think the clarifications in #5 and #7 implied that the layers are entirely independent.Why not?

I've probably misinterpreted this:

Parameters:

• And there can be up to four layers. (There is always a bottom later; if there is a second layer, it is on top of that; if there is a third later, it is on top of that, etc. There are no "empty" layers.

But I can't see any example in #5 that clarifies that?

I guess that first one on the left does clarify that as a misinterpretation(I think).

 

[erobz]

Assuming there no interlayer dependency:

Then I think the total is the sum of all possible layer shapes and configurations:

$638,204+ 638,204^2 +638,204^3+ 638,204^4$

?

Its still not clear in my mind whether or not we need to remove a bunch of rotational symmetries in that. These problem quickly get me spinning in circles. My gut says the answer to that is certainly.

 

[pbuk]

Assuming there no interlayer dependency:

Then I think the total is the sum of all possible layer shapes and configurations:

$638,204+ 638,204^2 +638,204^3+ 638,204^4$

No, you seem to be confused. The shapes are not composed of 1, 2, 3 or 4 layers each with 4 quadrants, they are composed of 4 quadrants each with 1, 2, 3 or 4 layers. You calculated the correct number of quadrant types in #8: see my extension of that calculation in #11.

 

[erobz]

No, you seem to be confused. The shapes are not composed of 1, 2, 3 or 4 layers each with 4 quadrants, they are composed of 4 quadrants each with 1, 2, 3 or 4 layers. You calculated the correct number of quadrant types in #8: see my extension of that calculation in #11.

In the green shape in post #5 there is no first layer shape in the right side quadrants. The first layer in that shape is

The next layer is:

The third and final layer is:

Which makes:

 

[pbuk]

In the green shape in post #5 there is no first layer shape in the right side quadrants. The first layer in that shape is

View attachment 326265

I see what you mean. That example shape seems to contradict the stated rules:

...There is always a bottom latyer ... There are no "empty" layers

@DaveC426913 where did you get the examples from? Edit: and where did you get the rules from?

 

[pbuk]

OK, I have now played the (demo version of the) game: the examples are right, my interpretation of @DaveC426913's rules was wrong.

A shape consists of 1, 2, 3 or 4 layers.
No layer can be completely empty: at least one quadrant must have a part.
Rotational orientation DOES matter so we don't have to worry about eliminations.
So each quadrant of a layer can have any one of 4 shapes in any one of 7 colours, or no shape at all, except that the configuration with no shapes in any quadrant is not allowed.
Edit: That gives $c = ((4)(7)+1)^4 - 1 = 707,280$ configurations for a layer.
And with 1, 2, 3 or 4 layers with no interdependencies there are c + c^2 + c^3 + c^4 = 250,245,412,237,998,716,617,680 \approx 2.5 \times 10^{23} shapes in all.
That gives $c = ((4)(8)+1)^4 - 1 = 1,185,920$ configurations for a layer.
And with 1, 2, 3 or 4 layers with no interdependencies there are $c + c^2 + c^3 + c^4 = 1,977,980,197,799,639,651,080,320 \approx 2.0 \times 10^{24}$ shapes in all.

 

[DaveC426913]

In the green shape in post #5 there is no first layer shape in the right side quadrants.

Sunuvagun. You're right.
All the more foolish of me since I had just finished building that one.

@DaveC426913 where did you get the examples from? Edit: and where did you get the rules from?

The examples are levels I've finished. The rules I am deducing. So yeah, I made a mistake there.

 

[DaveC426913]

Rotational orientation DOES matter so we don't have to worry about eliminations.

Not sure why you say this. As far as I am concerned, a final product that's rotated 90 or 180 degrees is the same product.

in any one of 7 colours,

And I just discovered that no-colour (or grey) is a valid colour, so that makes 8.

 

[pbuk]

Not sure why you say this. As far as I am concerned, a final product that's rotated 90 or 180 degrees is the same product.

But not as far as the game is concerned:

Have you seen the shape generator? This shows that https://viewer.shapez.io?----CuCu is not the same as https://viewer.shapez.io?CuCu----.

And I just discovered that no-colour (or grey) is a valid colour, so that makes 8.

Of course: at the start of the (demo) game you only have grey. I have edited my calculation in #19.

 

[DaveC426913]

Hm.
I must have the rules wrong because, with my understanding, this product should be impossible:

This is how it says it is constructed (I have labeled the layers a and b for clarity):

Layer a must be the top layer. (smaller shape = higher layer.)

If I simply drop a on b, it will not form two layers; I know the rules are that, if it can combine two shapes into the same layer without overlap, it will do so.

So this should form a single layer and will look like this:

Tricky...

 

[DaveC426913]

I threw in my hat on this one. I went looking for hints on how to solve this type ans stumbled across the exact solution. Here it is in a compact, 2 cell-high format. I'd need to duplicate this about 50 times to get it to deliver in less than a few hours.

 

[erobz]

Hm.
I must have the rules wrong because, with my understanding, this product should be impossible:

View attachment 326326

This is how it says it is constructed (I have labeled the layers a and b for clarity):

View attachment 326328

Layer a must be the top layer. (smaller shape = higher layer.)

If I simply drop a on b, it will not form two layers; I know the rules are that, if it can combine two shapes into the same layer without overlap, it will do so.

So this should form a single layer and will look like this:
View attachment 326327

Tricky...

So you are finding that what I said in the bottom of post #12 to be the correct interpretation?

 

[DaveC426913]

So you are finding that what I said in the bottom of post #12 to be the correct interpretation?

No, that's incorrect.
The samples at the bottom of post 12 are both legal.

I guess the rules need to be relaxed to merely "no layer can be placed on top of an empty layer."In fact, this one is quite simple:

It's just:

Even this is legal:

It's just:

But this one is tricky:

If you simply stacked blue on top of green, you would actually get this:

because it will "melt" together if it can.

 

[erobz]

No, that's incorrect.
The samples at the bottom of post 12 are both legal.

I guess the rules need to be relaxed to merely "no layer can be placed on top of an empty layer."

White squares represent "empty" spots in a layer in my diagrams. By what you stated in #23 I would expect:

?

 

[DaveC426913]

White squares represent "empty" spots in a layer in my diagrams. By what you stated in #23 I would expect:

Unfortunately, white is a valid colour so you can't use white as null. And I recently found out that even the default grey is a valid colour. So, the way to represent null has to be to literally "not there at all".

Your shape is represented thus:

That is the case with the actual product I most recently built:

(The grey circle is actually just the background "placeholder".)

 

[erobz]

Unfortunately, white is a valid colour so you can't use white as null. And I recently found out that even the default grey is a valid colour.

So, the way to represent null has to be to literally "not there at all".

I get that, but the diagrams that I'm creating to get on the same page as you for valid configs. "a white square is empty quadrant in a layer". Thus I am correct that the figure on the left would automatically convert to the figure on the right.

It has significant "structural" implications for how we would count. How may "colors" or "shapes" there actually are to chose from is trivial to the counting process.

 

[DaveC426913]

I get that, but the diagrams that I'm creating to get on the same page as you for valid configs. "a white square is empty quadrant in a layer". Thus I am correct that the figure on the left would automatically convert to the figure on the right.

You are technically correct, but your choice of rendering is going to lead to misunderstandings, tears and heartbreak. Remember, we're not the only ones reading this thread.

 

[erobz]

You are technically correct, but your choice of rendering is going to lead to misunderstandings, tears and heartbreak. Remember, we're not the only ones reading this thread.

We've already changed it multiple times! The objective is to get to the base level abstraction of how to count configurations for this game.

EDIT:
Even now I'm still not sure we are in agreement based on the edits made in #26! It seems like this:

is just:

( Are there 3 white filled quadrants in this figure not shown?)

Disagrees with my assertion that:

 

[DaveC426913]

We've already changed it multiple times!

I know; I was originally using a shorthand, thinking I only represented what was needed, but it turns out that was wrong and that ambiguity has caused confusion.

Abstraction is one thing, but misrepresentation is not good for communication.

This is the minimal graphic required to represent valid permutations. It needs grey, it needs white and it needs null.

Even now I'm still not sure we are in agreement based on the edits made in #26!

Here is your product:

It is legal, and difficult to build.
But how it is built does not factor into the permutations.I'm also seeing a text version that looks like this:
RgRg|--Rg
----|Rb--

Which means:

Layer 1: squaRe-green, squaRe-green | empty, squaRe-green
Layer 2: empty, empty | squaRe-blue, empty
Personally, while that's good codification, I find it less than visually intuitive.

 

[erobz]

I know; I was originally using a shorthand, thinking I only represented what was needed, but it turns out that was wrong and that ambiguity has caused confusion.

Abstraction is one thing, but misrepresentation is not good for communication.

This is the minimal graphic required to represent valid permutations. It needs grey, it needs white and it needs null.

Here is your product:
View attachment 326394

It is legal, and difficult to build.
But how it is built does not factor into the permutations.

Ok, so you are saying the little blue square placed on an empty layer (grey placeholder) will not resize, and move to the base layer like shown in #23?

 

[DaveC426913]

Ok, so you are saying the little blue square placed on an empty layer (grey placeholder) will not resize, and move to the base layer like shown in #23?

Right. Mostly.
It can be done, but it's a process that involves cutting and re-combining and disposing of objects in a complex way. I could go into it if you want; it's all laid out in the game guide, but that's behind a passwall, so I'd have to copy and paste the section of the article.

And I just realized that vastly complicates the calculations of the total permutations. Not I'm no longer sure that there are simply static rules, so much as there are procedures (algorithms).

 

[erobz]

Right. Mostly.
It can be done, but it's a process that involves cutting and re-combining and disposing of objects in a complex way. I could go into it if you want; it's all laid out in the game guide, but that's behind a passwall, so I'd have to copy and paste the section of the article.

Not necessary. I thought you were saying it was not a valid config in 23. Forget I ever said anything.