Saturday 25 November 2017

Technical Problem to solve - "Blockfinder".

I have a technical problem that needs to be solved as part of a larger project that has been in the works for a while. Code development needed.


Objective

From a given set of tiles build a 2 x 4 block of 8 that have matching edges.


After encoding each tile pattern as four characters. A different 2 x 4 layout (not same as above) can be shown as:


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) tile.txt file describes a set of tiles each wit4 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
                          | 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: 

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


Not all of these need to be tested as tiles can be checked against their neighbours before rotations in place are attempted. If a tile has none of the same edge keys as its neighbour then they would never work next to each other in the same layout. A logical test can be constructed to see if any 8 tile layout is likely to actually work before rotations are applied.

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: