17 replies to this topic

[Lasse D]

I have just finished my own little program to check the common LEGO trivia of "how many combinations are there of X 2x4 bricks".

My findings are:
1: 1
2: 24
3: 1560
4: 119580
5: 10166403
6: 915103765

This took the program a little less than an hour to compute. Using http://oeis.org/A112389/list one can find the next two numbers:
7: 85747377755
8: 8274075616387

Many results on the Internet seem to have a typo when it comes to the number of combinations with 5 bricks, citing "10116403" rather than the correct "10166403".
This typo seems to come from the latest paper in the area: "On the entropy of LEGO" http://www.math.ku.d...apers/lego.html and has spread to pages like
- Brickpedia: http://lego.wikia.com/wiki/LEGO
- Classic castle: http://www.classic-c...hp?f=13&t=12780
- Opentopia: http://encycl.opentopia.com/term/Lego
45 or so other results according to google.


I would like to ask the community.
Do you think it's fair that we only count the number of combinations where all bricks are at perfect 90 degree angles? The round studs of LEGO bricks allow us to turn the bricks at any angle and using these bricks we can make many other interesting configurations than those found using these computer programs. Think for instance of the six bricks forming a hexagon.
If we count all combinations including hexagons and such, then I'm sure there are more than a billion combinations for six bricks. If the community agrees that this is a more correct way of counting, then I would like to give it a try to find the actual number.

[AndyC]

Surely if you allow the bricks to be placed at arbitrary angles you've basically got an infinite number of combinations, even with just two bricks?

[Lasse D]

Yes, but that's still only a single combination.

The ways the combinations have been counted have been by only considering 90 degree angles between the bricks (aka axis aligned), considering all other combinations as invalid. This restriction makes sense from a programming point of view as writing a program that finds all combinations is much easier once you restrict the combinations to be axis aligned. I say: Don't restrict the counting just because it's harder to write a program.

[lorax]

One would assume though, you would need to define what makes a combination.  So would you count every degree as a unique combination and what would be the purpose of the answer?  If you don't define what you consider a unique combination, how will you program for it?

[Lasse D]

 lorax, on 15 July 2012 - 08:59 AM, said:

One would assume though, you would need to define what makes a combination.  So would you count every degree as a unique combination and what would be the purpose of the answer?  If you don't define what you consider a unique combination, how will you program for it?

That's a good point.

I suggest we call any given (static) way of connecting the bricks a model.
Given a model, a congifuration is the set of all models which you can obtain by turning the model or the connections between bricks of the model.
A configuration is called axis aligned if it contains a model where all the bricks are axis-aligned.

The previous results count all axis-aligned configurations. I want to compute all configurations without the restriction of being axis-aligned.

From fiddling with bricks it's clear that these two numbers are equal for combinations with between 1 and 3 bricks. Once we have four bricks, we can start forming configurations which are not axis-aligned and thus not counted by the official numbers.

Edited by Lasse D, 15 July 2012 - 12:16 PM.

[CP5670]

Great thread. One way to exclude rotated versions is to define a configuration as the set of connection points between bricks, without caring about the positions of the bricks themselves. This will be independent of the coordinate system the model exists in or how it's rotated. There would still have to be some way of avoiding configurations with overlapping bricks though. Maybe you can consider two overhanging bricks as having "ghost" connections at their boundaries, in a 5x3 shape for each brick, which means that any two interlocking bricks always have at least two "connection" points, at least in the axis aligned case.

That paper is quite interesting as well, especially the argument on the lower bounds.

Quote

From fiddling with bricks it's clear that these two numbers are equal for combinations with between 1 and 3 bricks. Once we have four bricks, we can start forming configurations which are not axis-aligned and thus not counted by the official numbers.

I'm not sure what you mean here. The way you defined axis alignment, you can have one brick hanging off another brick by a single stud, and it can point in any direction relative to the first one. I guess we want to think of all of these as the same configuration, except for the two endpoint cases where the bricks are connected by two studs.

[Lasse D]

 CP5670, on 15 July 2012 - 07:54 PM, said:

I'm not sure what you mean here. The way you defined axis alignment, you can have one brick hanging off another brick by a single stud, and it can point in any direction relative to the first one. I guess we want to think of all of these as the same configuration, except for the two endpoint cases where the bricks are connected by two studs.

You have some good ideas about how to attack this problem. My program favors simply trying out all combinations, but getting all combinations with cycles seem to be a tough challenge.

I'm in a place with extremely poor ligting conditions right now (Denmark), but I will take some pictures tomorrow to better illustrate what I mean.
For 1 to 3 bricks you can try to combine them and see that no matter what you do, you can always turn the knobs and become axis-aligned.
For 4 bricks you can combine them at different angles. Now the question is: how many?

I will update with pics once I have light (and time to post said pics).

Update
Here we go.

In this picture we see 3 models all using the same configuration:


There are many useful configurations which are not axis-aligned, such as:

and


Notice that the latter configuration is a different configuration from this (which is axis-aligned because you can turn the bricks to be on the grid):


There are many of these non-axis-aligned configurations. You can simply shuffle the bricks around a bit to get a new configuration:


There are also configurations which are not axis-aligned, but still have freedom of movement for some bricks:


Now you might think that it is always possible to verify a configuration by attempting to create models where the angles are combinations of 60, 120, 129.4 and 50.6 degrees (corresponding to triangles, and maximally turned bricks), but that doesn't hold either:

Edited by Lasse D, 18 July 2012 - 01:24 PM.

[legomr]

What you are trying to do is a bit more difficult than (and also different from) the original effort since your algorithm to determine legal connections must be much more complex. The original could look at stud occupation to check if two bricks occupied the same space, but you will have to turn to geometry.

Also, tree pruning might become more difficult as you have to consider literally indefinite angle choices for different outcomes.

You won't find many truly new configurations, to boot. With very few exceptions, you basically change the question from "find the number of all possible connections (at aligned axes)" to "find all possible connections [...] plus the number of all connections made possible through rotating bricks around the single brick they are attached to". Truly new connections are really just the ones where rotation enables configurations that otherwise are illegal because two bricks would share the same space (see your last image). Right?

Edited by legomr, 18 July 2012 - 08:12 PM.

[davee123]

 legomr, on 18 July 2012 - 08:10 PM, said:

What you are trying to do is a bit more difficult than [...] the original

That's probably an understatement :)

With axis-aligned connections, you can grossly simplify the rules to the point where a computer representation of the bricks is easy to define. But this really pushes the boundary since you've got to do things like calculate whether or not the corners of the bricks collide with the studs of the bricks upon which they're attached-- not to mention the more obvious collision detection, and of course the plethora of possible angles.

Essentially, the algorithm is SIMPLE enough-- it's just recursive to a degree that I can't easily come up with a way to make it efficient. Essentially, for N bricks, you take all the known "configurations" of N-1 bricks, and attempt to add another brick at every possible connection point. That part sounds pretty easy. But for each possible connection point, you MIGHT have to consider MANY "models" that are possible with that one "configuration". Plus, you need to essentially explore "having 1 end connected" for the brick you're adding, and "having more than 1 end connected" for the brick you're adding.

I can imagine an algorithm to do this, but I just imagine it being VERY slow. The trick will be optimizing the algorithm, and PROVING that it really DOES explore all possibilities.

 legomr, on 18 July 2012 - 08:10 PM, said:

You won't find many truly new configurations, to boot.

Relatively speaking, perhaps-- but I wouldn't think that de-values the final result if someone's willing to do the work!  To me, it sounds somewhere around a master's degree thesis in programming or something. I'm not sure if it's really worth the effort for the number of curious minds out there, but it's more likely to simply be satisfying to accomplish! If you actively want to find the answer, and have a good solution for efficiency, I'd say go for it!

DaveE

Edited by davee123, 18 July 2012 - 10:06 PM.

[Lego Otaku]

Why not limit all connection to valid 90 degree connection, no stud in tube (since you'd have to tip the brick to make it fit), and see how many valid combination can you get out of it?

[Lasse D]

 legomr, on 18 July 2012 - 08:10 PM, said:

(...)
Also, tree pruning might become more difficult as you have to consider literally indefinite angle choices for different outcomes.

You won't find many truly new configurations, to boot. With very few exceptions, you basically change the question from "find the number of all possible connections (at aligned axes)" to "find all possible connections [...] plus the number of all connections made possible through rotating bricks around the single brick they are attached to". Truly new connections are really just the ones where rotation enables configurations that otherwise are illegal because two bricks would share the same space (see your last image). Right?

Correct. The program becomes much, much more complicated, but it annoys me that no one knows the correct answer.

 davee123, on 18 July 2012 - 10:03 PM, said:

With axis-aligned connections, you can grossly simplify the rules to the point where a computer representation of the bricks is easy to define. But this really pushes the boundary since you've got to do things like calculate whether or not the corners of the bricks collide with the studs of the bricks upon which they're attached-- not to mention the more obvious collision detection, and of course the plethora of possible angles.

Essentially, the algorithm is SIMPLE enough-- it's just recursive to a degree that I can't easily come up with a way to make it efficient. Essentially, for N bricks, you take all the known "configurations" of N-1 bricks, and attempt to add another brick at every possible connection point. That part sounds pretty easy. But for each possible connection point, you MIGHT have to consider MANY "models" that are possible with that one "configuration". Plus, you need to essentially explore "having 1 end connected" for the brick you're adding, and "having more than 1 end connected" for the brick you're adding.

I can imagine an algorithm to do this, but I just imagine it being VERY slow. The trick will be optimizing the algorithm, and PROVING that it really DOES explore all possibilities.



Relatively speaking, perhaps-- but I wouldn't think that de-values the final result if someone's willing to do the work!  To me, it sounds somewhere around a master's degree thesis in programming or something. I'm not sure if it's really worth the effort for the number of curious minds out there, but it's more likely to simply be satisfying to accomplish! If you actively want to find the answer, and have a good solution for efficiency, I'd say go for it!

DaveE

That's what worries me as well. What I really need are some good reductions to limit the search space. One such reduction is that I know there are no new configurations for less than 4 bricks. Now I only have to consider configurations with 4, 5 and 6 bricks!

 Lego Otaku, on 19 July 2012 - 06:45 AM, said:

Why not limit all connection to valid 90 degree connection, no stud in tube (since you'd have to tip the brick to make it fit), and see how many valid combination can you get out of it?

That's a restriction I make because LEGO doesn't consider "non-clicked" connections valid, so no use of tubes or half-on-connections for this experiment.

[legomr]

Well, I mean, if you allow rotation around a brick, you change the nature of the task completely. In addition to running through a tree hierarchy, it is now about looking for collisions in rotation spaces. That's a lot more complex and becomes a rather "untidy" problem.

I don't know why exactly the original "research" has been undertaken to calculate the number of permutations from combining six 2x4 bricks. But I assume that it was less about calculating the absolute number of brick combinations, which is of little meaning and just serves as a nerdy little example. Instead, I assume that the original programmers really just wanted to show off by proving a way to traverse a rather big tree structure. Consider how much memory you need to store all possible combinations, for example. Probably more than most computers even today have. The thing is that it's probably an interesting, classical problem in information science between memory usage, execution time (consider searching for a particular combination), etc. You can apply this to Lego bricks, but you can equally apply this to real-world problems.

For the new problem which adds rotation, the task becomes rather messy. It's not about purely traversing permutations or a tree hierarchy anymore, although that must still be part of it (but only to the extent that it was in the original problem). Now, there is the collision detection latched to it. Which is nothing new in itself. The new problem with unaligned axes is thus only about adding a number of special/exceptional cases.

[davee123]

 legomr, on 20 July 2012 - 04:07 PM, said:

I don't know why exactly the original "research" has been undertaken to calculate the number of permutations from combining six 2x4 bricks.

I believe the LEGO company originally asked someone to come up with the statistic in order to promote the brand. IE, demonstrate mathematically just how gigantic the possibilities are so that they could justify saying something like "effectively infinite", or what-have-you.

However, the original calculation was also very wrong. It was done in the 1970's sometime, when computing power wasn't where it is today. The person assigned to the task decided to see how many combinations there were with simply stacking bricks-- so no 2 bricks were on the same vertical level. Plus, nothing other than 90 degree rotations.

Then, in the ... early 2000's somewhere, someone realized that the calculation wasn't complete, and decided to do a research paper on it. Probably for a class project or thesis or something. I think that's the one that's linked to above. They decided to allow bricks at ANY level (not just stacked vertically), but still only limited it to 90 degree rotations.

 legomr, on 20 July 2012 - 04:07 PM, said:

Consider how much memory you need to store all possible combinations, for example. Probably more than most computers even today have.

Not outrageously so. Somewhere in the gigabyte range, depending on your data structure. Offhand, I can imagine 11 bits per brick, which is 66 bits per combination, which fits into 9 bytes-- about 7.6G. If you database the information, rather than keeping it in memory, that's peanuts. And there's probably a lot of optimizations you can do on that.

The newer algorithm by comparison is ... daunting. Speaking as a programmer, I'm not really sure how I'd approach the problem. Anything I can think of would probably take many years to complete. Kudos if you can figure out how to do it!

DaveE

[Lasse D]

As for the current configurations I can give a little insight into the memory usage.

Assume for simplicity that we are building configurations of size 6.
A brick has a position (x,y), a layer (z) and orientation.
We can assume the first brick is always at (0,0,0) and vertical. Now we only have to store 5 bricks.
Having the first brick at (0,0) makes any leagal brick be in the x/y interval of -15 to 15, so we need only 7 bits to represent an x or y position.
There are only 6 layers a brick can be at (3 bit), and the orientation is either vertical or horizontal (1 bit), so storing a brick requires:
5+5+3+1 = 14 bits or < 2 bytes.
Assume for simplicity that we use an array to store the bricks. This leads to 10 bytes for a configuration.
I got lazy and used stl set for storing configurations. I didn't check the maximal memory usage, but the program crashed on my 4GB laptop. Running it on a larger machine with more memory took less than an hour on a single 3.2GHz Xenon. This is a significan improvement over the full week than what it took the original program of the original paper (roughly one week on a machine using Java), so I expect that it might be feasible to find all configurations now.

You can do better using custom data structures (rather than stl set), but this was fast enough for me.

As for now, I will look into configurations of size 4 to get an idea of the nature of the problem.

[davee123]

I think it's possible to cram a 6-brick 90-degree orientation into 53 bits by identifying the connection points rather than X,Y,Z coordinates. In fact, you could do it in 51 bits (although... odd), and probably even less if you make some assumptions. Basically, identify the "stud you're going to connect to" with 4 bits, the "stud you're going to connect with" with 4 bits, the orientation (1 bit), and the "brick you're going to connect to", which grows from 0 bits at Brick 2 up to 3 bits by the time you get to Brick 6.

That's 7 bytes-- so with 915103765 different configurations, it yields about 5.97 gigabytes of storage?

Granted, that storage mechanism means a lot of interpreting, so you'd likely be using up more CPU per comparison than the X,Y,Z coordinate representation.

The non-grid representation would be... different. Certainly you could go with:

Brick N is an array of 'connections' identifying the stud/hole being connected from (4 bits), the brick being connected to (3 bits), the stud/hole being connected to (4 bits). You don't need an "orientation" anymore, because you would presumably determine that from the list of connected studs.

But then you may be storing extraneous connections (if 2 bricks are stacked exactly on top of each other, you KNOW all 8 studs are connected after identifying any 2 connected studs, and then you're uselessly storing 6 connections of 11 bits each).

Best case, you're storing 6 bricks in 55 bits. Worst case, you're storing 6 bricks in 440 bits. If it's evenly distributed, that means roughly 247.5 bits per connection (fits into 31 bytes). And with at LEAST 915103765 combinations, you're looking at 26.42 gigabytes. Certainly ... possible ... with a LOT of paging. But then you've got a whole chunk of processing that has to go on for each possibility for collision detection and viable angles.

Yeah, I would expect it to take ... months or years to calculate.

DaveE

[CP5670]

Quote

There are many of these non-axis-aligned configurations. You can simply shuffle the bricks around a bit to get a new configuration:

I see what you mean now. This type of configuration is certainly something we want to count. The connection point approach will easily account for it, but will include other cases with overlapping bricks that we don't want.

Quote

I think it's possible to cram a 6-brick 90-degree orientation into 53 bits by identifying the connection points rather than X,Y,Z coordinates. In fact, you could do it in 51 bits (although... odd), and probably even less if you make some assumptions. Basically, identify the "stud you're going to connect to" with 4 bits, the "stud you're going to connect with" with 4 bits, the orientation (1 bit), and the "brick you're going to connect to", which grows from 0 bits at Brick 2 up to 3 bits by the time you get to Brick 6.

This is basically the approach I described earlier. Even more than the storage though, the real problem is finding a way to easily detect and rule out any physically impossible configurations (where bricks overlap). There are many different models that share the same connection points (which we want to think of as a single equivalence class), but it's not clear how big such a class is. Specifically, if we have a "nonphysical" model, is there some way to ensure that there always exists some other, "physical" model with the same connection points?

I wonder if there is some explicit formula or recurrence relation for this problem, instead of having to enumerate all the individual cases with a computer program. It would be really cool to get some asymptotic bound as the brick count increases, like that paper does, but including the non-aligned cases too.

[Lasse D]

 davee123, on 20 July 2012 - 09:29 PM, said:

I think it's possible to cram a 6-brick 90-degree orientation into 53 bits by identifying the connection points rather than X,Y,Z coordinates. In fact, you could do it in 51 bits (although... odd), and probably even less if you make some assumptions. Basically, identify the "stud you're going to connect to" with 4 bits, the "stud you're going to connect with" with 4 bits, the orientation (1 bit), and the "brick you're going to connect to", which grows from 0 bits at Brick 2 up to 3 bits by the time you get to Brick 6.

That's 7 bytes-- so with 915103765 different configurations, it yields about 5.97 gigabytes of storage?

Granted, that storage mechanism means a lot of interpreting, so you'd likely be using up more CPU per comparison than the X,Y,Z coordinate representation.

The non-grid representation would be... different. Certainly you could go with:

Brick N is an array of 'connections' identifying the stud/hole being connected from (4 bits), the brick being connected to (3 bits), the stud/hole being connected to (4 bits). You don't need an "orientation" anymore, because you would presumably determine that from the list of connected studs.

But then you may be storing extraneous connections (if 2 bricks are stacked exactly on top of each other, you KNOW all 8 studs are connected after identifying any 2 connected studs, and then you're uselessly storing 6 connections of 11 bits each).

Best case, you're storing 6 bricks in 55 bits. Worst case, you're storing 6 bricks in 440 bits. If it's evenly distributed, that means roughly 247.5 bits per connection (fits into 31 bytes). And with at LEAST 915103765 combinations, you're looking at 26.42 gigabytes. Certainly ... possible ... with a LOT of paging. But then you've got a whole chunk of processing that has to go on for each possibility for collision detection and viable angles.

Yeah, I would expect it to take ... months or years to calculate.

DaveE

I'm working on a connection-based format for the problem with angles as there are only 8 place on a brick to which angled connections can be made. The nice thing about my (old) format is how easy (fast) it is to construct and compare combinations, and as CP5670 points out, it is a challenge to do fast comparisons using the connection based ideas. I have not profiled my code, but I suspect these comparisons take up a great part of the computation time.

You do not have to store all 900M combinations in memory at once.
For the old problem I only stored all combinations where the number of bricks for each layer was given (saving 3 bit pr. brick), taking them one by one.
As an example: "2 1 2 1" means 2 brick on layer 0, 1 on layer 1, 2 on layer 2 and 1 brick on the top layer.
To construct all these combinations I simply iterated through all combinations with 5 bricks from which you can add a single brick to get one of this type.
For this example that means the combinations of type "2 1 2", "2 1 1 1", and "1 1 2 1". This saved me roughly a factor 10 in space usage. (I could have used 55 bit just as in your suggestion since I save the 3 bytes for the layer of every brick, so the data structure should simply store 64 bit ints).

It's not the space usage I'm worried about. We can easily come up with great ideas to save space, custom search structures et al - it's the branching that makes me unruly!

Edited by Lasse D, 21 July 2012 - 03:11 AM.

[legomr]

Well, I was referring to keeping all combinations in memory, which I assume is the only way to keep searching through combinations tractable. I assume that 4GB is still the usual maximum amount of RAM most people have installed.

Anyway, for the original problem (axis-aligned combinations), I believe the storage can be done in 37 bits for six bricks. To illustrate, let's number the eight connection points (studs or anti-studs on the underside) on a brick as follows:

 -------
|(1) (2)|
|(3) (4)|
|(5) (6)|
|(7) (8)|
 -------

So the two black bricks in this image are connected 1-on-1,2-on-3. The two bricks in this image are connected 1-on-3,2-on-4,3-on-1,4-on-2.
The funny thing is that the connection 1-on-8,2-on-6 is the same as 1-on-1,2-on-3, just mirrored. It becomes clear that most connections are just mirrors of others. There are really just 17 unique base combinations to connect two bricks: 8 where the bricks are parallel, and 9 where the bricks are orthogonal. From these 17 different combinations, we can derive all others by mirroring along the short or long axis, or both, of the first brick.
So, we need five bits to store 17 different combinations plus one empty combination (when there is no brick connected at all), plus two bits for mirroring along two axes, plus one bit to designate whether the new brick is above or below the old brick.
So, the first two bricks are designated by the first eight plus eight for the third brick, plus eight for the fourth, etc., equals five times eight bits = 40 bits. Even better, for the very first combination of two bricks, we don't need the above-or-below bit because both cases are identical. In fact, we don't even need the mirror bits if we just remember to multiply the resulting number of total cases by four.

Ok, I hope that makes sense.

Edited by legomr, 21 July 2012 - 07:30 PM.