Earlier this week, I asked about how to speed up my method for checking if a bitboard contains a polyomino. The definition I'm using for polyomino is any arrangement of squares such that they are all connected edgewise. I'm not disqualifying one because I've seen a mirrored or rotated version of it already or because it's been flipped over or has hole. A user showed that it could be done quicker with a lookup table to count the number of islands of 0s (I think most people use 1s, but a lot of my existing logic uses 0s). After toying around with the idea for a while, it got me thinking: Would it be possible to use the lookup table directly? For example, if I gave it 100, it would give me the 100th polyomino. Because right now I'm running a for loop over each ulong and checking each one until I find what I'm looking for. The gaps between polyominoes can be very large, the biggest one being about 4 quintillion apart. So it would be nice to skip over ones I don't need and only focus on the polyominoes. I've asked the user in a comment and they said it would be possible and they said yes unless I misunderstood them so I'm creating this post. Of course, anybody is welcome to answer it.
This is the code from the previous post that creates the lookup table.
/// <summary>
/// Map from the long-form state code for each state to the state number
/// see expandState.
///
/// This is only used during state table construction.
/// </summary>
Dictionary<string, ushort> stateNumbers = new Dictionary<string, ushort>();
/// <summary>
/// Packed map from (state*256 + next_row_byte) -> transition
///
/// transition is next_state + (island_count<<12), where island_count is the
/// number of islands cut off from the further rows
/// </summary>
List<ushort> transitions = new List<ushort>();
/// <summary>
/// The byte representing a row of all water. Note that this code counts
/// 0-islands, not 1-islands
/// </summary>
const byte ALL_WATER = (byte)0xFF;
#region Disjoint Set
/*
* Disjoint set the proper way. The sets are integers in an array:
* For each integer i
* - i === 0 => set is uninitialized (not yet a set)
* - i < 0 => set is a link to ~i
* - i >= 0 => set is of size i
*/
// find with path compression.
int find(int[] sets, int s)
{
int parent = sets[s];
if (parent > 0)
{
return s;
}
else if (parent < 0)
{
parent = find(sets, ~parent);
sets[s] = ~parent;
return parent;
}
else
{
sets[s] = 1;
return s;
}
}
// union by size
bool union(int[] sets, int x, int y)
{
x = find(sets, x);
y = find(sets, y);
if (x == y)
{
return false;
}
int szx = sets[x];
int szy = sets[y];
if (szx < szy)
{
sets[y] += szx;
sets[x] = ~y;
}
else
{
sets[x] += szy;
sets[y] = ~x;
}
return true;
}
#endregion
/// <summary>
/// Expands the specified state code.
///
/// A state code is a string of digits.
/// 0 => water
/// x => island number x. new islands are numbered from left to right
/// </summary>
/// <param name="stateCode">The state code to expand.</param>
/// <param name="nextrow">the lower 8 bits represent the next row. 0-bits are land</param>
/// <returns>The transition code for the transition from stateCode to nextrow</returns>
ushort expandState(string stateCode, int nextrow)
{
// convert the next row into a disjoint set array
// if you want to count 1-islands instead of 0-islands, change `~nextrow` into `nextrow` below,
// and fix the ALL_WATER constant
int[] sets = new int[8];
for (int i = 0; i < 8; ++i)
{
sets[i] = (~nextrow >> i) & 1;
}
for (int i = 0; i < 7; ++i)
{
if (((~nextrow >> i) & 3) == 3)
{
union(sets, i, i + 1);
}
}
// map from state code island to first attached set in sets
int[] links = [-1, -1, -1, -1, -1, -1, -1, -1];
int topIslandCount = 0;
for (int i = 0; i < 8; ++i)
{
char digit = stateCode[i];
int topisland = digit - '1';
topIslandCount = Math.Max(topIslandCount, topisland + 1);
if (sets[i] != 0 && topisland >= 0)
{
// connection from prev row to nextrow
int bottomSet = links[topisland];
if (bottomSet < 0)
{
// this island is not yet connected
links[topisland] = i;
}
else
{
// the top island is already connected. union bottom sets
union(sets, bottomSet, i);
}
}
}
// count the number of top-row islands that don't connect to the next row.
int cutOffCount = 0;
for (int i = 0; i < topIslandCount; ++i)
{
if (links[i] < 0)
{
++cutOffCount;
}
}
// turn the new union-find array into a state code
char nextSet = '1';
char[] newChars = "00000000".ToCharArray();
for (int i = 0; i < 8; ++i)
{
links[i] = -1;
}
for (int i = 0; i < 8; ++i)
{
if (sets[i] != 0)
{
int set = find(sets, i);
int link = links[set];
if (link >= 0)
{
newChars[i] = newChars[link];
}
else
{
newChars[i] = nextSet++;
links[set] = i;
}
}
}
string newStateCode = new string(newChars);
// get the state number
if (stateNumbers.ContainsKey(newStateCode))
{
// state already exists and is/will be expanded
return (ushort)(stateNumbers[newStateCode] | (cutOffCount << 12));
}
ushort newState = (ushort)stateNumbers.Count;
stateNumbers.Add(newStateCode, newState);
// fill out the state table
while (transitions.Count <= (newState + 1) * 256)
{
transitions.Add(0);
}
for (int i = 0; i < 256; ++i)
{
transitions[newState * 256 + i] = expandState(newStateCode, i);
}
return (ushort)(newState | (cutOffCount << 12));
}
int startState = expandState("00000000", ALL_WATER);
Console.WriteLine(startState);
Console.WriteLine(stateNumbers.Count);
int Count0Islands(ulong bitboard)
{
int state = 0;
int count = 0;
for (int i = 0; i < 8; ++i)
{
var transition = transitions[state * 256 + (int)(bitboard & 0xFF)];
count += transition >> 12;
state = transition & 0xFFF;
bitboard >>= 8;
}
// transition to ALL_WATER to count last islands
count += transitions[state * 256 + ALL_WATER] >> 12;
return count;
}
ulong[] tests = {
0x7e220a7e4a58580Ful,
0x7e22087e4a58580Ful,
0xFFFFFFFFFFFFFFFFul,
0x813c425a5a423c81ul
};
foreach (ulong test in tests)
{
Console.WriteLine();
Console.WriteLine();
for (int row = 0; row < 8; ++row)
{
int rowByte = (int)(test >> (row * 8)) & 0xFF;
string rowStr = Convert.ToString(rowByte, 2).PadLeft(8, '0');
rowStr = rowStr.Replace("1", " ");
rowStr = rowStr.Replace("0", "#");
Console.WriteLine(rowStr);
}
Console.WriteLine();
Console.WriteLine("Islands: " + Count0Islands(test));
}
The table I made for you last time is a finite state transducer that processes row bitmasks are returns island counts.
This is not quite what you need. In order to generate the Nth polymino bitboard, we need to:
If we start at the start state with a polymino number N, we can descend through 8 transitions along the Nth path to the accepting state. The 8 row bitmasks on those transitions can then be used to construct the Nth polymino.
Here's what you can add to your/my existing FST generator to make the polymino generator table and generate polyminoes.
This table is somewhat bigger, with 5126 states, 652583 transitions and about 16 bytes per transition, so about 10MB.
/// <summary>
/// checker_state + next_row_number * 4096 + have_islands*65536 -> generator_state
/// </summary>
Dictionary<int, ushort> genStateNumbers = new Dictionary<int, ushort>();
/// <summary>
/// Generator states. These for a DFA that accepts all 8-row polyminoes.
/// State 0 is used as both the unique start state and the unique accept state
/// </summary>
List<List<GenTransitionInfo>> genStates = new List<List<GenTransitionInfo>>();
/// <summary>
/// Fill out a state in the generator table if it doesn't exist
/// Return the state number
/// </summary>
ushort makeGenState(int nextRowNumber, int checkerState, int haveIslands) {
int stateKey = checkerState + nextRowNumber * 4096 + haveIslands * 65536;
if (genStateNumbers.ContainsKey(stateKey)) {
return genStateNumbers[stateKey];
}
ushort newGenState = (ushort)genStates.Count;
genStateNumbers.Add(stateKey, newGenState);
var tlist = new List<GenTransitionInfo>();
genStates.Add(tlist);
int transitionsOffset = checkerState*256;
ulong totalPaths = 0;
for (int i = 0; i < 256; ++i) {
var transition = transitions[transitionsOffset + i];
int nextCheckerState = transition & 0x0FFF;
var newIslands = (transition >> 12) + haveIslands;
if (newIslands > (i == ALL_WATER ? 1 : 0)) {
// we are destined to get too many islands this way.
continue;
}
if (nextRowNumber == 7) {
// all transitions for row 7 have to to the accept state
// calculate total number of islands
newIslands += transitions[nextCheckerState * 256 + ALL_WATER] >> 12;
if (newIslands == 1) {
totalPaths += 1;
tlist.Add(new GenTransitionInfo { nextRow = (byte)i, nextState = 0, cumulativePaths = totalPaths });
}
} else {
ushort nextGenState = makeGenState(nextRowNumber + 1, nextCheckerState, newIslands);
ulong newPaths = genStates[nextGenState].LastOrDefault().cumulativePaths;
if (newPaths > 0) {
totalPaths += newPaths;
tlist.Add(new GenTransitionInfo { nextRow = (byte)i, nextState = nextGenState, cumulativePaths = totalPaths });
}
}
}
return newGenState;
}
// generate the DFA
makeGenState(0, startState, 0);
ulong TOTAL_POLYMINOES = genStates[0].LastOrDefault().cumulativePaths;
ulong getNthPolimyno(ulong n) {
int state = 0;
ulong poly = 0;
for (int row=0; row < 8; ++row) {
var tlist = genStates[state];
// binary search to find the transition that contains the nth path
int hi = tlist.Count - 1;
int lo = 0;
while (hi > lo) {
int test = (lo + hi) >> 1;
if (n >= tlist[test].cumulativePaths) {
// test is too low
lo = test + 1;
} else {
// test is high enough
hi = test;
}
}
if (lo > 0) {
n -= tlist[lo - 1].cumulativePaths;
}
var transition = tlist[lo];
poly = (poly<<8) | transition.nextRow;
state = transition.nextState;
}
return poly;
}
// TEST
Console.WriteLine("Total Polyminoes: " + TOTAL_POLYMINOES);
Console.WriteLine("Total Generator States: " + genStates.Count);
Console.WriteLine("Total Transitions: " + genStates.Sum(x => x.Count));
Random rand = new Random();
for (int i=0; i < 10; ++i) {
// Genterate a random ulong from 0 to TOTAL_POLYMINOES
ulong n = (ulong)rand.NextInt64((long) TOTAL_POLYMINOES);
ulong poly = getNthPolimyno(n);
Console.WriteLine();
Console.WriteLine("Polymino " + n + " is:");
for (int row = 0; row < 8; ++row)
{
int rowByte = (int)(poly >> (row * 8)) & 0xFF;
string rowStr = Convert.ToString(rowByte, 2).PadLeft(8, '0');
rowStr = rowStr.Replace("1", " ");
rowStr = rowStr.Replace("0", "#");
Console.WriteLine(rowStr);
}
}
struct GenTransitionInfo {
public byte nextRow;
public ushort nextState;
public ulong cumulativePaths;
}
Testing code is included, and produces output like:
Total Polyminoes: 51016818604894742
Total Generator States: 5126
Total Transitions: 652583
Polymino 42260088568217858 is:
#######
# #
# ####
######
# ####
#### ##
### #
# # #
Polymino 17307633173140022 is:
# # ####
##### #
# # # #
# # ####
####
# #
### ###
# #### #
Note that there are exactly 51016818604894742 different 64-bit bitboard polyminoes. Getting this number is the real reason I've gone to all this trouble :)
You can search for this number to see where it's come up before!