As further proof of my unsuitability to be a child minder (see previous post) I found myself playing with an Ikea LILLABO 20-piece basic set train.

The train set has 16 pieces of track (12 curves, two straight pieces and a two part bridge) and 4 pieces of train. What I wondered was... how many possible looping train tracks can be made using all 16 pieces?

The answer is... 9. Here's a picture of the 9 different layouts.

The picture was generated using a little program written in Processing. The bridge is red, the straight pieces are green and the curves are blue or magenta depending on whether they are oriented clockwise or anticlockwise. The curved pieces can be oriented in either way.

To generate those layouts I wrote a small program which runs through all the possible layouts and determines which form a loop. The program eliminates duplicate layouts (such as those that are mirror images of each other).

It outputs a list of instructions for building loops. These instructions contain 15 characters C (clockwise curve), A (anticlockwise curve), S (straight piece) and B (the entire bridge). Here are the building instructions for all the shapes in the picture above:

PS You can actually create more possible layouts than these because the Ikea pieces have a lot of play in them and can be abused to form other shapes. But where's the fun in that?

PPS Ikea can actually double the fun by adding just two more pieces. If they added two more curved pieces the number of possible tracks doubles to 18. If they added four curved pieces then the number of possible tracks goes to 130.

PPPS Here's the code

PPPS Here's how I determined that a full circle was made up of eight curved pieces with a radius of one straight piece:

The train set has 16 pieces of track (12 curves, two straight pieces and a two part bridge) and 4 pieces of train. What I wondered was... how many possible looping train tracks can be made using all 16 pieces?

The answer is... 9. Here's a picture of the 9 different layouts.

The picture was generated using a little program written in Processing. The bridge is red, the straight pieces are green and the curves are blue or magenta depending on whether they are oriented clockwise or anticlockwise. The curved pieces can be oriented in either way.

To generate those layouts I wrote a small program which runs through all the possible layouts and determines which form a loop. The program eliminates duplicate layouts (such as those that are mirror images of each other).

It outputs a list of instructions for building loops. These instructions contain 15 characters C (clockwise curve), A (anticlockwise curve), S (straight piece) and B (the entire bridge). Here are the building instructions for all the shapes in the picture above:

AAAACCAAAASSAAB

CCCCCCSSAAAAAAB

CAAAAACASSAAAAB

CAAAAASCASAAAAB

CAAAAASSCAAAAAB

AAACAACAAASSAAB

ACAAAASACSAAAAB

ACAAAASSACAAAAB

AACAAASSAACAAAB

PS You can actually create more possible layouts than these because the Ikea pieces have a lot of play in them and can be abused to form other shapes. But where's the fun in that?

PPS Ikea can actually double the fun by adding just two more pieces. If they added two more curved pieces the number of possible tracks doubles to 18. If they added four curved pieces then the number of possible tracks goes to 130.

PPPS Here's the code

use strict;

use warnings;

# ----------------------------------------------------------------------------

# Program to determine all the possible valid closed loop train tracks

# possible using the Ikea Lillabo 20-piece basic train set (see

# http://www.ikea.com/gb/en/catalog/products/30064359). Note that

# although this is 20-piece there are only actually 16 pieces of track

# (the train itself is in four pieces).

#

# Written by John Graham-Cumming (http://www.jgc.org/)

#

# Released under the General Public License, version 2

#

# v1.0 - First public release

# ----------------------------------------------------------------------------

# Universal constant derived from 1 Kings 7:23 :-)

my $PI = 3.1415927;

# The length of a single straight piece. For the purposes of the

# program this is set at one but could be made into a real value if

# you wanted to output actual track lengths.

my $unit = 1;

# The number of curved pieces that make a full circle. Determined

# empirically. And the angle of the segment determined by a single

# curved piece in a circle.

my $curves_in_circle = 8;

my $radians_in_curve = 2 * $PI / $curves_in_circle;

# The 15 possible pieces: a straight edge (which has $unit length) and

# is used as the measurement for everything else, a bridge (which is

# twice the length of the straight edge; it is actually supplied in

# two pieces but for the purposes of this program is considered to be

# a single piece) and a curve (using $radians_in_curve above the

# length of the straight line between the ends of the curve is

# calculated).

#

# Each entry consists of three parts:

#

# length: the length in a straight line between the ends of the piece

# at its centre.

#

# angle: the angle (in radians) between the straight line through the

# piece and a tangent to the curve at the piece's start. This only

# applies to curved pieces where the straight line is the line joining

# its two endpoints.

#

# count: how many of these pieces are supplied.

#

# Note that curves can be placed in either a clockwise or

# anticlockwise direction. The program detects this by looking at the

# angle. If it's non-zero then the piece has two orientations.

my %pieces = (

Bridge => { length => $unit * 2,

angle => 0,

count => 1 },

Straight => { length => $unit,

angle => 0,

count => 2 },

# Here's a curved piece, the angle a is $radians_in_curve, the

# length l of a side is $unit. So length is the distance between

# the points labelled s and f. Bisect the angle a you get a right

# angle triangle with hypotenuse of length $unit and angle at the

# vertex of $radians_in_curve/2. So the angle b is $PI/2 -

# $radians_in_curve/2. By simple trigonometry the length is twice

# $unit * cos($PI/2-$radians_in_curve/2).

#

# s

# C

# . . C

# . b C

# l . . C

# . C

# . . C

# . a C

# . . . . . . . C

# o f

#

# To calculate the angle to the tangent at point s (the angle c),

# note that the angle formed by os and the tangent is a right angle

# (since os comes from the centre of the circle). So b+c is $PI/2

# but b is $PI/2 - $radians_in_curve/2 and so c is

# $radians_in_curve/2

#

# s

# .

# . . .

# . b c .

# l . . .

# . .

# . . .

# . a .

# . . . . . . . . . . .

# o f

#

Curve => { length => 2 * $unit * cos($PI/2-$radians_in_curve/2),

angle => $radians_in_curve/2,

count => 16 }

);

# This structure contains the position of the end of the current

# placed track (the X and Y coordinates) and the angle of the end of

# the piece of track in radians to the horizontal. Initially this is

# defined as location (0,0) and with an angle of 0.

#

# The goal will be to place pieces such that the cursor ends up at the

# %origin.

my %origin = (

angle => 0,

x => 0,

y => 0

);

# Some basic test tracks to make sure that the code does what I

# expect. This hash contains track layouts and the expected final

# position of the cursor for tests

my %tests = (

B => { x => 2 * $unit, y => 0, angle => 0 },

S => { x => $unit, y => 0, angle => 0 },

C => { x => 0.707, y => 0.293, angle => 0.785 },

A => { x => 0.707, y => -0.293, angle => -0.785 },

AA => { x => 1, y => -1, angle => -1.570 },

CC => { x => 1, y => 1, angle => 1.570 },

BSS => { x => 4 * $unit, y => 0, angle => 0 },

CCCC => { x => 0, y => 2 * $unit, angle => 0 },

AAAA => { x => 0, y => -2 * $unit, angle => -3.14 },

CCCCCCCC => \%origin,

CCCCCCCCCCCCCCCC => \%origin,

AAAAAAAA => \%origin,

AAAAAAAAAAAAAAAA => \%origin,

BCCCCCCSSAAAAAA => \%origin,

CCCCSCCCCS => \%origin,

CCCCACCACCCCACCA => \%origin

);

foreach my $t (sort keys %tests) {

my %ac = %origin;

my @as = split( '', $t );

build_track( \%ac, \@as );

if ( !cursor_match( \%ac, $tests{$t} ) ) {

die "Test $t failed: $ac{x} $ac{y} $ac{angle}\n";

}

}

# To avoid getting the same track in different directions we keep

# track of tracks that we've found for testing. The keys of this hash

# are the strings that describe the track layout (e.g. CCCCCCSSAAAAAA

# without the bridge piece).

my %found;

# Since there are only two interesting pieces of track (curve and

# straight) the algorithm for trying out all the combinations of

# pieces is broken into two parts. The outer loop runs through all

# combinations of curved pieces joined together with each piece

# getting to go clockwise or anticlockwise. This is done by

# generating all binary numbers between 0 and 2^12-1 (i.e. all 12 bit

# binary numbers) and using the bits to indicate whether a track piece

# goes clockwise (a 0) or anticlockwise (a 1).

#

# To avoid seeing the same track twice in symmetrical layouts the

# curved pieces are constrained to always finish with an anticlockwise

# piece. This is done by making the top bit in this loop be 0 by

# reducing the top number to 2^11-1

foreach my $curve (0..2**($pieces{Curve}{count}-1)-1) {

# Create an array containing the instructions for inserting

# pieces. The array is alpha and has entries B, C, A and S. A means

# add curved piece anticlockwise, S means add straight piece, C

# means a curved piece clockwise and B a bridge. This array will be

# fed into move_cursor to build the final track.

#

# The following piece of code uses the sprintf function to extract

# the bits from the $curve value into an array and then transform a

# 0 bit to A and a 1 bit to C.

my @instructions = map {$_?'C':'A'}

split( '', sprintf( "%0$pieces{Curve}{count}b", $curve ) );

# Then for each combination of curved pieces it's just a question of

# inserting the straight pieces in all possible positions. If there

# are 12 curved pieces then there are 13 possible places each

# straight piece can be inserted.

#

# To make it possible to modify the number of straight pieces the

# program doesn't assume that there are only two (which could just

# have been done with a pair of loops). So an array is initialized

# that will contain the positions of the n straight pieces and it is

# used to create the combinations.

#

# The initial position of the straight pieces is 0 and then 0

# (assuming just two) indicating that they are inserted before the

# first curved piece.

my @straight;

foreach my $i (0..$pieces{Straight}{count}-1) {

$straight[$i] = 0;

}

# Now run through all the possible valid straight positions and

# insert them into the curved positions

while (1) {

my @in = @instructions;

# Add the straight pieces to the list of 'instructions' at the

# appropriate places and then place the pieces. This creates a

# new array, @build, containing the track layout.

my @build;

my $s = 0;

my $c = 0;

while ( ( $s < $pieces{Straight}{count} ) ||

( $c < $pieces{Curve}{count} ) ) {

if ( $s < $pieces{Straight}{count} ) {

if ( $straight[$s] == $c ) {

push @build, ('S');

$s += 1;

next;

}

}

if ( $c < $pieces{Curve}{count} ) {

push @build, ($in[$c]);

$c += 1;

}

}

# Now add the bridge at end. Since there's only one bridge this

# simplification is made and it makes no difference to the outcome

# since all other combinations of straights and curves will be

# generated.

push @build, ('B');

my %cursor = %origin;

build_track( \%cursor, \@build );

# Finally see if this track layout results in a loop. The test

# for this is simple: is the last piece (represented by the

# %cursor) at the %origin position and orientation?

#

# If it matches in one direction then pop off the bridge, reverse

# the track, push back the bridge and try to rebuild. This will

# eliminate tracks that don't actually match up because the final

# piece approaches the bridge from the wrong direction.

if ( cursor_match( \%cursor, \%origin ) ) {

pop @build;

%cursor = %origin;

my $build1 = join('',@build);

@build = reverse @build;

my $build2 = join('',@build);

push @build, ('B');

my $build1a = $build1;

$build1a =~ tr [AC] [CA];

my $build2a = $build2;

$build2a =~ tr [AC] [CA];

if ( !exists( $found{$build1} ) ) {

build_track( \%cursor, \@build );

if ( cursor_match( \%cursor, \%origin ) ) {

my $build3 = undef;

if ( $build1 =~ /^(.*)SS(.*)$/ ) {

$build3 = join('',reverse split('',$1)) .

'SS' . join('',reverse split('',$2));

}

if ( !defined( $build3 ) ||

!exists( $found{$build3} ) ) {

print @build, "\n";

$found{$build1} = 1;

$found{$build2} = 1;

$found{$build1a} = 1;

$found{$build2a} = 1;

if ( defined( $build3 ) ) {

$found{$build3} = 1;

}

}

}

}

}

# Move the straight pieces to their next positions, this is where

# the while loop will exit once all the positions have been tried.

foreach my $i (0..$pieces{Straight}{count}-1) {

my $j = $pieces{Straight}{count}-1-$i;

if ( $straight[$j] < $pieces{Curve}{count} ) {

$straight[$j] += 1;

last;

} else {

$straight[$j] = -1;

}

}

foreach my $i (1..$pieces{Straight}{count}-1) {

if ( $straight[$i] == -1 ) {

$straight[$i] = $straight[$i-1];

}

}

my $terminate = 1;

foreach my $i (0..$pieces{Straight}{count}-1) {

if ( $straight[$i] != $pieces{Curve}{count} ) {

$terminate = 0;

last;

}

}

if ( $terminate ) {

last;

}

}

}

# Subroutine used to place a piece of track. It updates a %cursor

# hash passed to it

sub move_cursor

{

my ( $c, # Reference to the %cursor hash to be updated

$p, # Name of the piece be added

$h ) = @_; # Handedness for curved piece (1 or -1), omit if

# non-curved

if ( !defined( $h ) ) {

$h = 0;

}

$c->{x} += $pieces{$p}{length} * cos($c->{angle} +

$h * $pieces{$p}{angle});

$c->{y} += $pieces{$p}{length} * sin($c->{angle} +

$h * $pieces{$p}{angle});

if ( $h != 0 ) {

$c->{angle} += 2 * $h * $pieces{$p}{angle};

}

}

# Subroutine to build an entire track from a list of track pieces

# (with single character identifiers)

sub build_track

{

my ( $c, # Reference to the %cursor to update

$in ) = @_; # Reference to the list of build instructions

# This maps the characters in the @$in array into piece names and

# handedness (for the curved pieces). Note that direction is

# missing for the straight pieces and the undefined value is used in

# the following loop and passed to move_cursor for those

# pieces. move_cursor knows how to deal with this.

my %m = (

'A' => { piece => 'Curve', direction => -1 },

'B' => { piece => 'Bridge' },

'C' => { piece => 'Curve', direction => 1 },

'S' => { piece => 'Straight' } );

foreach my $i (@$in) {

move_cursor( $c, $m{$i}{piece}, $m{$i}{direction} );

}

}

# Determine whether two cursors represent the same position and

# orientation. Return 1 if so, 0 otherwise.

sub cursor_match

{

my ( $c, $d ) = @_; # References to two %cursor hashes

my $dx = round($$c{x}-$$d{x});

my $dy = round($$c{y}-$$d{y});

my $da = round(($$c{angle}-$$d{angle})/$PI);

$da -= int($da);

return ( ( $dx == 0 ) &&

( $dy == 0 ) &&

( $da == 0 ) );

}

# Perform rounding on a number to two decimal places

sub round

{

my ( $a ) = @_;

return int($a*100 + 0.5*($a <=> 0))/100;

}

PPPS Here's how I determined that a full circle was made up of eight curved pieces with a radius of one straight piece:

**Update**I received a message from Ikea about this:

Dear John

Thank you for sharing our passion for childrens products. It is very good for us to get input like this. I will forward your idea to the product developer who is responsible for our toys and maybe this improvements will be something for us to concider.

Thanks again for taking your time to give us feed back.

Best regards

Maria ThÃ¶rn

Range manager childrens IKEA

## Comments

The small difference there is that the paths can overlap in arbitrary ways, but it's the same sort of path-routing fun.

That said, bravo. Just the sort of analysis that I have to explain to my wife why I find it so interesting.

While Ikea is very creative with their attempts to innovate. It is to save costs and to improve the company, not to better the customers enjoyment. Especially when the enjoyment will most likely go unnoticed by the end user, in this case a 5 year old kid.

As is it will generate many impossible tracks like AAAASAAAAAAAASAAAAB.

I'm trying to improve it but I'm not a native perl developer.

However I don't quite understand why you made your program so complicated, instead of just looping through all the combinations/permutations? Was this so it would run faster? Did you add bits as you tried it out?

I was looking for exactly this kind of problem. Doing some of my own research, I found more than 9 layouts, in fact I found 104. These haven't been checked on doubles, and consider the bridge to be two straights. Nevertheless, I think your list of 9 is not complete. I will give a missed layout at the end of this post. But to introduce you to the error I see, consider the track coded by:

AAAA.AC.AAAA.AC

(I call it a doughnut for lack of a better word, periods are only for style)

I noted that each connection point has a certain angle, and for each angle there are either 2 or 4 parallel points.

Your solutions 1, 2 and 6 in the picture are not derived from this doughnut. I'd like to call them "independents". Interestingly, design no.6 in the picture was new to me!

All other layouts are derived from the doughnut by introducing the bridge at a certain connection point. To avoid doubles, we only have to put the bridge in the beginning of the string, and place the two other straights elsewhere on parallel connection points.

Yours (minus the three "independents"):

1. CAAAAACASSAAAAB

2. CAAAAASCASAAAAB

3. CAAAAASSCAAAAAB

4. ACAAAASACSAAAAB

5. ACAAAASSACAAAAB

6. AACAAASSAACAAAB

Mine on the left and your corresponding to the right (in reverse)

BAAAASS.AC.AAAA.AC = 1. CAAAAACASSAAAAB

BAAAAS.AC.SAAAA.AC = 2. CAAAAASCASAAAAB

BAAAA.AC.SSAAAA.AC = 3. CAAAAASSCAAAAAB

ABAAA.ASSC.AAAA.AC = ACAAAAACSSAAAAB missing

ABAAA.ASC.ASAAA.AC = 4. ACAAAASACSAAAAB

ABAAA.AC.ASSAAA.AC = 5. ACAAAASSACAAAAB

AABAA.AC.AASSAA.AC = 6. AACAAASSAACAAAB

AAABA.AC.AAASSA.AC = 6. AACAAASSAACAAAB

AAAAB.AC.AAAASS.AC = 5. ACAAAASSACAAAAB

AAAAB.AC.AAAAS.ACS = 4. ACAAAASACSAAAAB

AAAAB.AC.AAAA.ACSS = ACAAAAACSSAAAAB missing (same as above)

AAAA.ABC.AAAA.ASSC = 3. CAAAAASSCAAAAAB

ASAAA.ABC.AAAA.ASC = 2. CAAAAASCASAAAAB

ASSAAA.ABC.AAAA.AC = 1. CAAAAACASSAAAAB

The unidentified layout would be similar to 1. (listed here) but with the bridge and straight tracks interchanged (it's the only one that is a non-symmetrical)

--

Also, as noted, there are many more designs if you allow the bridge to be taken apart. The tracks in between can be easily strutted. Note that we can consider the identical problem with kart track layouts. With kart tracks it is the bridge that needs "struts" only in the figure 8 and in all other designs counts as 2 straights. So, it is natural to consider the bridge to be two "straights" as well. Alternatively, solve it for the simple kart layouts (http://ow.ly/RXCkG at Amazon).

--

In this post, I showed that your program has a "bug" (it did not produce all possible layouts modulo symmetry and rotation).

--

I also learned how to identify layouts written in different ways, by considering the Bridge to be "the first piece" and looking for the layout clockwise or anticlockwise which has the most A's following it.

--

I indicated that the bridge can be thought of as two straights. This will give more designs not shown. I am curious to see these other layouts (strutted in case of train set, flat in case of kart race set).

--

Thank you so much.

I couldn't wait on your program's output :-P. So, I scrutinized my list by hand and the following 23 designs remained (no rotations or mirror images):

Final list - Total layouts: 23.

Of these 23, 3 are the independents (AA,BB and CC), and the other 20 are modified doughnuts (adding 4 straights in various places). Layouts marked * were found by you and allow the whole bridge in one or two positions (B=SS).

S = Straight, A = Anticlockwise curve, C = Clockwise curve

AA. [SSAAAAAASSCCCCCC] - figure 8

01. [SSAAAAACSSAAAAAC]*

02. [SSAAAACASSAAAACA]*

BB. [SSAAAACCAAAASSAA] - figure L

03. [SSAAAASACSAAAAAC]*

04. [SSAAAASCASAAAACA]*

05. [SSAAAASSACAAAAAC]*

06. [SSAAACAASSAAACAA]*

CC. [SSAAACAACAAASSAA] - figure M

07. [SAAAAACSASAAAASC]

08. [SAAAAASCSAAAAASC]

09. [SAAAACSASAAAACSA]

10. [SAAAACSASAAASACA]

11. [SAAAASACSAAAASAC]

12. [SAAACASASAAACASA]

13. [SAAACASASAAASCAA]

14. [SAAACSAASAAACSAA]

15. [SAAACSAASAASACAA]

16. [SAAASAACSAAASAAC]

17. [SAAASACASAAASACA]

18. [SAAASASCAAAAACSA]

19. [SAACAASASAACAASA]

20. [SAACASAASAACASAA]

I hope you'll verify my list (did I miss anything?) and make the accompanying pictures for easy reference. In the mean time, these 23 designs can be a lot of fun to build.

In fact, there are a few more designs which do not use all available tracks.

[AAAAAAAA] - circle

[AAAASAAAAS] - small ellipse

[AAAASSAAAASS] - ellipse

[AAASASAAASAS] - diamond

[AASAASAASAAS] - square

[AAAA.AC.AAAA.AC] - doughnut

Modifying the doughnut gives a number of other designs by adding only 2 straights. To get these, take any doughnut design in the list above, and remove two parallel straights between which are at least 4 A's. For some designs this gives as much as 4 derivative layouts using only 2 straights. I did not yet determine all these designs, but for any practical purposes I consider them included . . .

Enjoy your day,

Cuc

I don't see any new layouts where the bridge is treated as a single item. Do you?

you're right, the longer list does not contain any new designs with the Bridge in a different place. It contains all possible layouts with the bridge in one piece or used as two separate pieces (remember the slot-car racing tracks, for which it is really all the other designs that do not form a problem, but only the figure-8 needs strutting.) So, there are 14 alternative designs. I would like to see pictures of them. I tried with primitive means (Windows Paint), but the results don't look presentable. I am thinking of making a paper model of the tracks and taking pictures . . .

Just to be sure you understood, note that by changing the bridge in

AAAASSACAAAAACB, we get

ACAAAAACSSAAAAB, which was missing from your layouts.

Yours, Cuc.

I published the code to draw the layouts here: http://blog.jgc.org/2010/01/ikea-lillabo-processing-code.html but to save you the time I put all the layouts you had found (23 of them including my 9) and here's the picture of that: http://i.imgur.com/Cjm9l9T.png

You say that ACAAAAACSSAAAAB is missing from my layouts. Here's a picture of it: http://i.imgur.com/r2X0UzT.png

For ease of comparison here's yours and mine together: http://i.imgur.com/Sc1ckNo.png Now we get into a question of whether these two are different. In my layouts I allowed swapping of the bridge and two straights and considered them the same layout. Also the tracks are double sided so it's possible to transform your layout into mine by flipping it over.

So I'm not sure yours is totally different to mine. Thoughts?

About http://i.imgur.com/r2X0UzT.png. You write "In my layouts I allowed swapping of the bridge and two straights and considered them the same layout." With this criterion, yes, they are identical. Ultimately, it's a matter of taste.

Please, note that in all the other original layouts, swapping the bridge with the two straights can be done by a geometric transformation of the layout: taking a mirror image or a rotation or a combination. (Yes, you will need both sides of the tracks.) But only in this layout, you actually have to switch them. So, that's why I thought that you "missed" it.

Thank you for following up with your questions. I realize you had a different goal with your original program.

Cuc.