Objective
From a given set of tiles build a 2 x 4 block of 8 that have matching edges.
On the top row the tiles join with keys K,G,G. Between the two rows of tiles joining keys are G,R,R,P. Between the bottom row of tiles the joining keys are R,G,G. In the centre of each tile is a description :
[ TileNumber r n ] # n is rotation between 0..3
Which represents the tile number and rotation in the layout. The dot in the corner of each tile confirms the rotational layout between zero and three. This layout would be summarised as
B8:0x595c:T13R2,T15R3,T7R3,T9R3,T12R3,T4R1,T3R3,T5R0
Inputs
1) A tile.txt file describes a set of tiles each with 4 sides. On each of four sides (north, south, east, west) is a key character/number. Tiles are to be assembled into a 2 x 4 layout where the side edge keys match.Sample tile.txt file :
#Tiles with Corner colours type Normalised ns we base rotation 28 Mar 13,
#TileNumber,North,East,South,West,Tyle Type,Normalised,NS pairs,WE pairs,Base roatation
1,4,0,1,9,e,1,"4,1","0,9",1
2,8,9,8,8,i,1,"8,8","9,8",0
3,6,9,7,7,i,2,"6,7","9,7",0
4,0,1,9,4,e,2,"0,9","1,4",2
5,9,8,7,8,i,3,"9,7","8,8",0
5,9,8,7,8,i,3,"9,7","8,8",0
| Base rotation needed to put edge sides downwards
----- EW pair ( duplicate information )
----- NS pair ( duplicate information )
- number of tile when each tile type starts at 1
- tile type i=interior, e=edge, c=corner
N E S W - edge keys 1=a,2=b,7=g,8=h .. etc
N - tile number
Colour key 0 = outside edge of puzzle. Each edge tile will have one 0 edge, each corner tile has 2 of 0 sides.
2) A textfile that contains one Hex number on each line.
Each line is a Hex value that has 8 bits set within a 40bit value (for a 40 tile deck). Max Deck size is currently 64 but may go up to 256 in a future project.
EG: A textfile will look like these lines ( order is not important )
0x1242408300
0x1244000318
0x1244000b08
...
The set bits in the number represent the number of the tile in the tile file that is to be used in the (Block 8 tiles ) B8 layout. Hex to binary conversion shows the tiles for this sample ....
$ bc -l
bc 1.06
ibase=16 # << set hex input
obase=2 # << set binary output
C # << input test number
1100 # << result
1242408300 # << actual hex number
1001001000010010000001000001100000000 #<< binary result
Rightmost bit is counted as "1" to match tile number 1 in the tile file.
<< MSB -------- ----- LSB >
40 36 32 28 24 20 16 12 8 4 1 << bit number
| | | | | | | | | |
...1 ..1. .1.. ..1. .1.. .... 1... ..11 .... .... << Extracted bits
...| ..|. .|.. ..|. .|.. .... |... ..|| .... ....
0001 0010 0100 0010 0100 0000 1000 0011 0000 0000 << Binary number
1 2 4 2 4 0 8 3 0 0 << Hex digits 1 for each 4 bits
Tiles in sample 0x1242408300 layout would be
9, 10, 16, 23, 26, 31, 34, 37
3) A clue string is provided in the format "aaaa/bbbb/ccdd" which represents the edge keys on the top most unmatched edge, bottommost unmatched edge and the two shorter sides. For the layout and above the clue string would be :
rwbr/kook/rogr
When a B8 tile layout and its rotations are found the clue string is checked to ensure that the outer boundary keys match the clue string. Layouts that correctly represent a B8 but fail the clue string should be reported. All the lines should have at least one layout that matches the clue string.
Task
Find a B8 layout of tiles for each hex number in the textfile.
A B8 layouts is reported using the following single line notation. A layout and other possible outcomes would be reported as:
Given eight tiles there are
8*7*6*5*4*3*2*1 = 8! = 40,320 possible tile layout orders.
B8:0x1242408300:T13R2,T15R3,T7R3,T9R3,T12R3,T4R1,T3R3,T5R0
B8:0x1242408360:Fail Too many bits
B8:0x1242408b08:Fail No layout found
B8:0x1242408b08:Fail Clue string mismatch: T13R2,T15R3,T7R3,.....Outline size of task
Arrange and rotate 8 tiles to find layout which has inner edge matches and outer face matches with a clue string.Given eight tiles there are
8*7*6*5*4*3*2*1 = 8! = 40,320 possible tile layout orders.
Each tile can have 4 possible rotations leading to
4*4*4*4*4*4*4*4 = 4^8 = 65,536 different sets of rotations
Multiplying rotations and layout orders there are :
2,642,411,520 possible ways of organising eight tiles.
Time for 2.6 billion simple loops in Perl and c++
$ time perl -e 'foreach(1..40320){ foreach (1..65536) {$t+=1}};print"t=$t\n";'
t=2642411520
real 2m35.544s
user 2m35.265s
sys 0m0.165s
$# Same loops coded in c++ run in about 4% of the time.
$ make cpptime ; time cpptime
c++ cpptime.cpp -o cpptime
t=2642411520
real 0m5.930s
user 0m5.913s
Hint
There are two distinct stages to this problem. First is to find out specific layouts of cards that could possibly join together, and secondly to find the rotations that fit any given layout into a solution.If possible layouts are generated in standard permutation fashion as follows:
1 2 3 4 5 6 7 8
1 2 3 4 5 6 8 7
1 2 3 4 5 7 6 8
1 2 3 4 5 7 8 6
A test can be performed to see if cards 1 & 2 can possibly match, if not then the next 5041 layouts starting 1 2 can be discarded as well as the 720 after that that start 2 1. Similarly for columns 2 and 3, large jumps of 720 rows can be made down the rows of permutations without having to test a layout in depth.
Column - Number of rows with the same number in the that column.
[1] - 5040
[2] - 720
[3] - 121
[4] - 24
[5] - 6
[6] - 1
[7] - 1
As can be seen the first row that starts 2 1 is on row 5041.
Row
Number Perm order
Technology to be used
- Perl and/or c++
- Multi-tasking via threads, openMP or standard libraries encouraged 8 or 12 way processors available.
- 8GB memory, 5TB HDD and/or 250GB SSD.
- Typical time to solution 0.01 second or better per layout.
- Any c++ should be "standards compliant" and self contained at src level and (highly desirable) to be adjustable to work on W10 or Mac or Ubuntu.
- Code should be structured so that it can be trivially built into a larger program or as stand alone utility.
No comments:
Post a Comment