This puzzle (first published here) is based on finding groups of tessellated tiles (inspired by floor tiles I saw on a recent vacation).
The tiles had be laid in sets of 9 tiles, 3 by 3, i.e. a Tile is made up of 9 tiles. The capitalisation indicates whether it is a set of 9 tiles or a single tile. The Tiles had been laid so that they tessellate i.e. there are no gaps between the Tiles, and they align in columns or rows or both.
The Tiles had been laid in different orientations i.e. the same Tile may have been rotated by 90, 180 or 270 degrees.
The 9 tiles in a Tile are a selection from 9 different tiles, there may be duplicates of one or more tiles within any Tile, i.e. not all tiles are present in each Tile.
The puzzle input represents a section of the floor such that there may be partial Tiles at the edges of the area but none of the Tiles have been cut where they join. Each square represents a tile although the orientation of the tile on the floor has been obscured.
The challenge is to determine the minimum number of different Tiles that can be used to create this layout, and which tiles make up each unique Tile.
This article contains spoilers!
In fact, the whole article is a spoiler as it contains solutions to the puzzle. If you are trying to solve the puzzle yourself and just want some pointers to get you started, stop reading when you have enough, and return if you get stuck again, or just want to compare your solution to mine!
Finding Tile Possibilities
We can start be taking the data and splitting into separate events, one for each row of tiles.
| makeresults
| fields - _time
| eval _raw="E E H I H H D C I B G D
H F H B B I C D H H I D
I C B G E B I G E F B F
C I G A I F D C B G E I
A H H A C H G I G A D D
E A E F F A D H H A A H
F E H A E H D G A A F E
E B D D A E B B G H B H
B E B I H I C C I H I H
I I F D H G B A E F C D
B C H G A A G E H A F E
E B H F I D G B D D H H"
| multikv noheader=t
| fields _rawAs well as breaking a chunk of data into separate line-events, the multikv command will also attempt to extract key-value pairs from each line, but we do not need them in this case, so we just keep the _raw field.
Now, within each event, separate out the tiles.
| rex max_match=0 "(?<tile>\w)"
| fields - _rawGive each row a number e.g. the x coordinate.
``` Set x as row offset ```
| streamstats count as x current=fNote that by using current=f on the streamstats command, the counts will begin at zero.
Join the tiles again to form lines (this is just to make them easier to handle).
``` Join tiles to form lines (rows) ```
| eval line=mvjoin(tile,"")
| fields x lineSince the Tiles are made from 3 rows of tiles, group the lines in threes.
| streamstats list(line) as tuple window=3Now, drop the first two lines (as they have insufficient rows in them).
``` Drop fiirst two lines ```
| where x > 1Reset the x-coordinate to cater for the skipped rows.
``` Reset x as row offset ```
| eval x=x-2Create the left y-coordinate of the Tiles.
| eval y=mvrange(0,len(line)-2)We can skip the final 2 tiles since they will be insufficient tiles to their right to form a complete Tile.
Expand the y-coordinate, and generate the Tiles.
| mvexpand y
``` Create Tile options ```
| eval Tile=mvappend(substr(mvindex(tuple,0), y+1, 3),substr(mvindex(tuple,1), y+1, 3),substr(mvindex(tuple,2), y+1, 3))
| fields x y TileCreate a signature
Since the Tiles may have been rotated elsewhere on the floor, create a signature for each tile so that we can find identical Tiles. We do this by first creating the four possible rotations of each Tile.
``` Generate 0, 90, 180 and 270 degree rotations ```
| eval rotation=mvrange(0,4)
| mvexpand rotation
| fields - _mkv_child tupleConvert each Tile to a single line.
``` Convert Tile to single line ```
| eval unTile=mvjoin(Tile,"")Depending on the rotation, re-order the characters (tiles) in the line.
``` Depending on rotation, re-order characters ```
| eval unTile=case(rotation=0, unTile, rotation=1, substr(unTile,7, 1).substr(unTile, 4, 1).substr(unTile,1, 1).substr(unTile,8, 1).substr(unTile, 5, 1).substr(unTile,2, 1).substr(unTile,9, 1).substr(unTile, 6, 1).substr(unTile,3, 1), rotation=2, substr(unTile,9, 1).substr(unTile, 8, 1).substr(unTile,7, 1).substr(unTile,6, 1).substr(unTile, 5, 1).substr(unTile,4, 1).substr(unTile,3, 1).substr(unTile, 2, 1).substr(unTile,1, 1), rotation=3, substr(unTile,3, 1).substr(unTile, 6, 1).substr(unTile,9, 1).substr(unTile,2, 1).substr(unTile, 5, 1).substr(unTile,8, 1).substr(unTile,1, 1).substr(unTile, 4, 1).substr(unTile,7, 1))By putting the lines in the same order, we can create the same signature for a Tile no matter what rotation was used on the floor.
``` Sort rotated lines ... ```
| sort 0 x y unTile
``` ... to create a signature for the Tile ```
| eventstats list(unTile) as signature by x y
| eval signature=mvjoin(signature,"")Find most frequent signatures
The most frequent signatures represent the Tiles which have been repeated most, and the assumption is that these are likely to be amongst the fewest needed to complete the final layout.
``` Find most frequent signature ```
| eventstats count by signature
| eventstats max(count) as most_frequentSince the Tiles are 3-by-3, we can take the modulus-3 of the x and y coordinates of the "top-left" tile within each Tile to see if the Tiles have been aligned by row or column or both.
``` Find modulus-3 of x and y ```
| eval mod_y=y % 3
| eval mod_x=x % 3If there is only one unique modulus-3 of the x coordinate for the most frequent Tile, assume the Tiles will be aligned in rows; if there is only one unique modulus-3 of the y coordinate for the most frequent Tile, assume the Tiles will be aligned in columns.
``` Find unique modulus-3 for x and y for most frequent signature ```
| eventstats values(eval(if(count=most_frequent,mod_y,null()))) as most_frequent_mod_y values(eval(if(count=most_frequent,mod_x,null()))) as most_frequent_mod_xBy joining the values, create a field that can be compared to each Tile's mod_x and mod_y, (a "joined" single value is the same as the single value).
``` Join multivalues to enable comparison with single value ```
| eval most_frequent_mod_x=mvjoin(most_frequent_mod_x,",")
| eval most_frequent_mod_y=mvjoin(most_frequent_mod_y,",")Using the modulus-3 of the most frequent Tile(s), we can filter the signatures so that the remaining Tiles share the same alignment as most frequent Tile(s).
``` Filter by most frequent alignment ```
| where mod_y=most_frequent_mod_y or mod_x=most_frequent_mod_xIt turns out that the alignment of the most frequent Tiles is by column - in fact, all Tiles appear to be column-aligned. (Where a Tile signature appears only once, it will appear to be column-aligned, but also it will appear to be row-aligned.)
Find Tiles which fit into columns
For Tiles to fit into the floor tessellation, the Tile must be in the same column as the most frequent Tile(s) and the row must have the same modulus-3 as the most frequent Tile(s) in that column. Determine the possible column and row modulus-3 combinations associated with each Tile.
``` Create a column/row modulus-3 combination ```
| eval y_mod_x=y.",".mod_xFind the alignment possibilities for most frequent signature.
``` Find the possible alignments for the most frequent Tile ```
| eventstats values(eval(if(count=most_frequent,y_mod_x,null()))) as alignmentsFilter the Tiles which match one of the alignments of the most frequent Tile.
``` Filter where Tile alignment matches the alignments of the most frequent Tile ```
| where isnotnull(mvfind(alignments, y_mod_x))Find incomplete Tiles for columns
Having found the complete Tiles which share alignment with the most frequent Tile(s), determine the incomplete Tiles and see if they can be made up from the complete Tiles we have already found.
Start by finding the top and bottom row of each complete Tile.
``` Find top and bottom of each aligned column ```
| eventstats min(x) as min_x_y max(x) as max_x_y by yHow do we use this to find the incomplete Tiles, especially when this data has already been removed? We have to go back almost to the beginning and branch the search using the appendpipe command.
...
``` Join tiles to form lines (rows) ```
| eval line=mvjoin(tile,"")
| fields x line
| appendpipe
[
| streamstats list(line) as tuple window=3
``` Drop fiirst two lines ```
| where x > 1
...
``` Find top and bottom of each aligned column ```
| eventstats min(x) as min_x_y max(x) as max_x_y by y
``` Drop redundant fields ```
| fields - mod_y dc_mod_x dc_mod_y most_frequent mod_x count
]Split the original lines into groups of three tiles. (If the line field is empty, the event came from the branch and the y field should be preserved.)
``` Split the lines into groups of three ```
| eval y=if(len(line)>0,mvrange(0,len(line)-2),y)
| mvexpand y
``` Create Tile row options ```
| eval row=substr(line, y+1, 3)Copy the top and bottom row number (x index) for each column of complete Tiles.
``` Copy top and bottom for each column of Tiles ```
| eventstats max(max_x_y) as max_x_y min(min_x_y) as min_x_y by yFilter out the complete tiles to just keep the 3-tile groups which are not part of the complete Tiles in the column.
``` Filter out complete Tiles ```
| where x<min_x_y or x>max_x_y+2Determine whether the Tile rows are above or below the complete Tiles in the columns.
``` Determine whether Tile row is top or bottom of column of Tiles ```
| eval position=if(x<min_x_y, "T", "B")List the Tile rows for at the top and bottom of the columns.
``` List Tile rows depending on whether they are top or bottom of column of Tiles ```
| stats list(row) as partial by y positionCreate partial Tiles, filling in the unknown tiles with lowercase o's (or some other distinguishing character), either above or below as appropriate.
``` Create partial Tile with o's for "unknown" tiles ```
| eval Tile=if(position="T", if(mvcount(partial)=2,"ooo","oooooo").mvjoin(partial,""),mvjoin(partial,"").if(mvcount(partial)=2,"ooo","oooooo"))Matching with Complete Tiles
To see if the complete Tiles that we have already found can be used to make up the partial Tiles at the top and bottom of the columns, we need to determine the possible partial Tiles for the complete Tiles. For the columns, this is similar to creating the partial Tiles for the unknown Tiles we have just done, but we need to try all rotations of the complete Tiles.
So, retracing our steps again, going back to the list of complete Tile signatures we generated earlier, and deduplicate the signatures and their rotations.
...
``` Filter where Tile alignment matches the alignments of the most frequent Tile ```
| where isnotnull(mvfind(alignments, y_mod_x))
``` Deduplicate the signature and unTiled rotations ```
| dedup signature unTile
| fields signature unTileFor each rotation, there are 4 possible incomplete Tiles which might fit at the top or bottom of the columns with complete Tiles, either with one or two rows from the complete Tile.
``` For each rotated Tile, there are 4 possible incomplete Tiles for column alignment, 1 or 2 rows kept above and 1 or 2 rows kept below ```
| eval position=split("TB","")
| mvexpand position
| eval keep=mvrange(1,3)
| mvexpand keepCreate partial Tiles using lowercase o's for the "unknown" tiles.
``` Create partial Tile with o's for "unknown" tiles ```
| eval Tile=if(position="T", if(keep=2,"ooo".substr(unTile,4),"oooooo".substr(unTile,7)),if(keep=2,substr(unTile,1,6)."ooo",substr(unTile,1,3)."oooooo"))Now we just need to bring these together with the partial Tiles from the columns to see if we can match them i.e. can the known complete Tiles be used to complete this part of the pattern. The problem is that neither of these last two searches have all the information we need.
Joining two searches from the same base
We could save either or both of these searches to lookup files, but can we join them in a single search? (We may not have sufficient permissions to create lookup files, nor want to leave spurious lookup files around.)
We have already seen that we can use the appendpipe command to branch the event pipeline, to allow additional processing of the events. We can do this multiple times and, if we tag each branch, we can bring back just the branches we need to join them.
Start by using this concept to refactor finding the incomplete Tiles. First tag the main search as the "trunk" before using the appendpipe command to branch the event pipeline.
...
``` Join tiles to form lines (rows) ```
| eval line=mvjoin(tile,"")
| fields x line
``` Tag the main search as the "Trunk" ```
| eval branch="Trunk"
| appendpipe
[
| streamstats list(line) as tuple window=3
``` Drop fiirst two lines ```
| where x > 1
...Now tag this branched event pipeline as "Complete Tiles".
...
``` Find top and bottom of each aligned column ```
| eventstats min(x) as min_x_y max(x) as max_x_y by y
``` Drop redundant fields ```
| fields - mod_y dc_mod_x dc_mod_y most mod_x count
``` Tag this branch as "Complete Tiles" ```
| eval branch="Complete Tiles"
]Branch a new event pipeline, and select the branches you want to work with, before deduplicate the signatures and their rotations.
| appendpipe
[
``` Select the branches to work with ```
| where branch="Trunk" or branch="Complete Tiles"
``` Deduplicate the signature and unTiled rotations ```
| dedup signature unTile
| fields signature unTile
...Create the partial Tiles for the top and bottom of the column (as we did before), before tagging this branched event pipeline as "Partial column Tiles".
...
``` Create partial Tile with o's for "unknown" tiles ```
| eval Tile=if(position="T", if(mvcount(partial)=2,"ooo","oooooo").mvjoin(partial,""),mvjoin(partial,"").if(mvcount(partial)=2,"ooo","oooooo"))
``` Tag this branch as "Partial column Tiles" ```
| eval branch="Partial column Tiles"
]Now, select the branch you want for the results.
| where branch="Partial column Tiles"This gives the same results as earlier. So, now we can check that all the partial Tiles have a match from our complete Tiles.
| where branch="Partial complete Tiles" or branch="Partial column Tiles"
| eventstats values(signature) as signature by Tile
| where branch="Partial column Tiles"So, we now know that the columns with complete Tiles in can be made up from the known complete Tiles.
Find incomplete Tiles for incomplete columns
Now we need to check the incomplete columns. That is, the columns of partial Tiles either side of the columns of complete Tiles. For these columns, we do not know the row offsets so we need to check for all three possibilities on both sides. (We will assume that there will be at least one group of three rows on either side which match to the corresponding partial Tiles from the set of complete Tiles. This will help determine the row offset present in the partial columns.)
Start by copying the leftmost and rightmost starting points of the complete Tiles from "Complete Tiles".
| appendpipe
[
``` Select the branches to work with ```
| where branch="Trunk" or branch="Complete Tiles"
``` Copy leftmost and rightmost starting point for complete Tiles ```
| eventstats min(y) as min_y max(y) as max_y
``` Drop redundant branch ```
| where branch="Trunk"Get the left- and right- most tiles from each line which are not covered by the complete Tile columns.
``` Get left- and right- most tiles not covered by complete Tiles ```
| eval left_tiles=substr(line,1,min_y)
| eval right_tiles=substr(line,max_y+4)Gather the lines into groups of three, dropping the first two lines and resetting the x coordinate (as done previously).
``` Group lines in threes ```
| streamstats list(left_tiles) as left_partial list(right_tiles) as right_partial window=3
``` Drop fiirst two lines ```
| where x > 1
``` Reset x as row offset ```
| eval x=x-2Create partial rows for the left and right using lowercase o's for the unknown tiles, and join them as a single line for easier comparison.
``` Create partial rows for left and right with o's for "unknown" tiles, and join as single line ```
| eval left_partial=mvjoin(mvmap(left_partial,if(len(left_partial)=1,"oo".left_partial,"o".left_partial)),"")
| eval right_partial=mvjoin(mvmap(right_partial,if(len(right_partial)=1,right_partial."oo",right_partial."o")),"")Expand into two events each, one for left and one for right.
``` Expand as two events, one for left and one for right ```
| eval position=split("LR","")
| mvexpand position
| eval Tile=if(position="L",left_partial,right_partial)
| fields x position TileTag this branched event pipeline as "Partial complete Tiles"
``` Tag this branch as "Partial complete Tiles" ```
| eval branch="Partial complete Tiles"
]Check the result by selecting this new branch.
| where branch="Partial complete Tiles"
| fields - _mkv_child _mkv_parent
| fields x position TileMatch incomplete Tiles to partial complete Tiles
In order to match with complete Tiles, create partial Tiles where the left and right columns have been replaced by lowercase o's. Start by selecting the "Complete Tiles".
| appendpipe
[
``` Select the branch to work with ```
| where branch="Complete Tiles"Deduplicate the signatures and their rotations (as we did earlier).
``` Deduplicate the signature and unTiled rotations ```
| dedup signature unTile
| fields signature unTileThis time, for each rotation, there are 4 possible incomplete Tiles which might fit at the left or right of the columns with complete Tiles, either with one or two columns from the complete Tile.
``` For each rotated Tile, there are 4 possible incomplete Tiles for column alignment, 1 or 2 columns kept left and 1 or 2 columns kept right ```
| eval position=split("LR","")
| mvexpand position
| eval keep=mvrange(1,3)
| mvexpand keepCreate partial Tiles using lowercase o's for the "unknown" tiles.
``` Create partial Tile with o's for "unknown" tiles ```
| eval Tile=if(position="L", if(keep=2,"o".substr(unTile,2,2)."o".substr(unTile,5,2)."o".substr(unTile,8,2),"oo".substr(unTile,3,1)."oo".substr(unTile,6,1)."oo".substr(unTile,9,1)),if(keep=2,substr(unTile,1,2)."o".substr(unTile,4,2)."o".substr(unTile,7,2)."o",substr(unTile,1,1)."oo".substr(unTile,4,1)."oo".substr(unTile,7,1)."oo"))Tag this branched event pipeline as "Partial column partial Tiles".
``` Tag this branch as "Partial column partial Tiles" ```
| eval branch="Partial column partial Tiles"
]Now we can check which of the partial Tiles left and right have a match from our partial complete Tiles.
| where branch="Partial column partial Tiles" or branch="Partial complete Tiles"
| eventstats values(signature) as signature values(keep) as keep by Tile
| where branch="Partial complete Tiles" and isnotnull(signature)
| fields - _mkv_child _mkv_parent
| fields x position Tile signatureFinally, check the corners
We can see that partial complete Tiles can be used to the left and right of the complete Tile columns, leaving just the top and bottom not being covered (yet). Determine how many tiles are still uncovered by complete Tiles.
| eventstats min(x) as min_x max(x) as max_x by positionRefactor so this is another branch.
...
| eval branch="Partial column partial Tiles"
]
| appendpipe
[
``` Select the branches to work with ```
| where branch="Partial column partial Tiles" or branch="Partial complete Tiles"
...
| eventstats min(x) as min_x max(x) as max_x by position
``` Tag this branch as "Partial column partial complete Tiles" ```
| eval branch="Partial column partial complete Tiles"
]Combine "Partial column partial complete Tiles" with the "trunk" to determine the "missing" corner tiles.
| where branch="Trunk" or branch="Partial column partial complete Tiles"Duplicate the events from the "Trunk" so we can extract the left and right tiles. (The position field is currently null in the "Trunk" events.)
``` Duplicate the events from the "Trunk" so we can extract the left and right tiles. ```
| eval position=if(isnull(position),split("LR",""),position)
| mvexpand positionSince the partial columns could be aligned by different rows, copy the minimum x, maximum x and rows to keep by position (left or right).
``` Copy the minimum x, maximum x and rows to keep by position (left or right). ```
| eventstats min(min_x) as min_x max(max_x) as max_x values(keep) as keep by positionNow we just need to keep the relevant lines from the "Trunk". (Field x is null on the other branch.)
``` Keep the relevant lines from the "Trunk". ```
| where x<min_x or x>max_x+2Create a partial row with o's for "unknown" tiles.
``` Create a partial row with o's for "unknown" tiles. ```
| eval partial=if(position="L",if(keep=1,"oo".substr(line,1,1),"o".substr(line,1,2)),if(keep=1,substr(line,11,1)."oo",substr(line,11,2)."o"))Determine whether partial rows are part of the top or bottom of the partial column (again, these could be different for left and right partial columns).
``` Determine whether partial rows are part of the top or bottom of the partial column. ```
| eval tb=if(x<min_x,"T","B")List the partial rows by position (left or right) and whether they are top or bottom rows.
``` List the partial rows by position (left or right and top or bottom) ```
| stats list(partial) as partial by position tbCreate partial Tiles for the corners.
``` Create partial Tiles for the corners. ```
| eval partial=if(tb="T",if(mvcount(partial)=1,"oooooo","ooo").mvjoin(partial,""),mvjoin(partial,"").if(mvcount(partial)=1,"oooooo","ooo"))Refactor to create this as another branch.
...
``` Tag this branch as "Partial column partial complete Tiles" ```
| eval branch="Partial column partial complete Tiles"
]
| appendpipe
[
``` Select the branches to work with ```
| where branch="Trunk" or branch="Partial column partial complete Tiles"
...Tag this branched event pipeline as "Partial corner Tiles".
...
``` Create partial Tiles for the corners. ```
| eval partial=if(tb="T",if(mvcount(partial)=1,"oooooo","ooo").mvjoin(partial,""),mvjoin(partial,"").if(mvcount(partial)=1,"oooooo","ooo"))
``` Tag this branch as "Partial corner Tiles" ```
| eval branch="Partial corner Tiles"
]Find corners of complete Tiles
Just like before, we now need to find the possible matching corners from the known complete Tiles to see if they will complete the pattern. Start by creating another branch and select the relevant branches.
...
``` Tag this branch as "Partial corner Tiles" ```
| eval branch="Partial corner Tiles"
]
| appendpipe
[
``` Select the branches to work with ```
| where branch="Complete Tiles" or branch="Partial column partial complete Tiles"Duplicate the events from the "Complete Tiles" branch so we can extract the left and right tiles.
``` Duplicate the events from the "Complete Tiles" branch so we can extract the left and right tiles. ```
| eval position=if(isnull(position),split("LR",""),position)
| mvexpand positionCopy the values from the "Partial column partial complete Tiles" branch so we know which part of the Tiles we need for matching.
``` Copy the minimum x, maximum x and rows to keep by position (left or right). ```
| eventstats min(min_x) as min_x max(max_x) as max_x values(keep) as keep by positionDuplicate the events from the "Complete Tiles" branch again, so we can extract the top and bottom corners.
``` Duplicate the events from the "Complete Tiles" branch so we can extract the corner tiles. ```
| eval tb=split("TB","")
| mvexpand tbReduce fields and events in the pipeline.
``` Reduce fields and events in pipeline ```
| dedup signature unTile position tb
| fields signature unTile position tb keep min_x max_xCreate partial Tiles for the corners of the complete Tiles. It is easier/clearer to do this by selecting the relevant rows, then the columns.
``` Create partial Tiles for the corners. ```
| eval partial=if(tb="T",if(min_x=1,"oooooo".substr(unTile,7),"ooo".substr(unTile,4)),if(max_x=7,substr(unTile,1,6)."ooo",substr(unTile,1,3)."oooooo"))
| eval partial=if(position="L",if(keep=1,"oo".substr(partial,3,1)."oo".substr(partial,6,1)."oo".substr(partial,9,1),"o".substr(partial,2,2)."o".substr(partial,5,2)."o".substr(partial,8,2)),if(keep=1,substr(partial,1,1)."oo".substr(partial,4,1)."oo".substr(partial,7,1)."oo",substr(partial,1,2)."o".substr(partial,4,2)."o".substr(partial,7,2)."o"))Tag this branch as "Partial corner complete Tiles".
``` Tag this branch as "Partial corner complete Tiles" ```
| eval branch="Partial corner complete Tiles"
]Now to check whether the corners can be covered by the complete Tiles, select the relevant branches.
| where branch="Partial corner Tiles" or branch="Partial corner complete Tiles"Copy the signature(s) of matching partial Tiles.
| eventstats values(signature) as signature by partialFinally, check that all the corner partial Tiles is matched with at least one complete Tile (signature).
| where branch="Partial corner Tiles"
| fields partial signature position tb
| fields - _mkv_child _mkv_parentSolution
Though this process, we have shown that only four complete Tiles are required to make up the pattern of tiles. This can be shown visually here (where I have colour-coded the same Tiles).
Summary
In summary, the key to solving this puzzle is to break it down into manageable chunks. Using "tagged branches" is one way of being able to separate, reuse and combine the different result sets, without the need for separate stores e.g. csv files, kv stores, summary indexes, etc.
Have questions or thoughts? Comment on this article or in Slack #puzzles channel. Whichever you prefer.
