Wie kann ich diese vorberechnete Nachschlagetabelle verwenden, um eine 1:1-Zuordnung von Polyominoes zu erstellen? ⇐ C#

[Guest]

Anfang dieser Woche habe ich gefragt, wie ich meine Methode zur Überprüfung, ob ein Bitboard ein Polyomino enthält, beschleunigen kann. Die Definition, die ich für Polyomino verwende, ist jede Anordnung von Quadraten, sodass sie alle hochkant verbunden sind. Ich disqualifiziere eines nicht, weil ich bereits eine gespiegelte oder gedrehte Version davon gesehen habe oder weil es umgedreht wurde oder ein Loch hat. Ein Benutzer hat gezeigt, dass es mit einer Nachschlagetabelle schneller geht, um die Anzahl der Nulleninseln zu zählen (ich denke, die meisten Leute verwenden Einsen, aber viele meiner bestehenden Logiken verwenden Nullen). Nachdem ich eine Weile mit der Idee herumgespielt hatte, kam mir die Frage: Wäre es möglich, die Nachschlagetabelle direkt zu verwenden? Wenn ich zum Beispiel 100 gebe, erhalte ich das 100. Polyomino. Denn im Moment lasse ich eine for-Schleife über jedes Ulong laufen und überprüfe jedes einzelne, bis ich finde, wonach ich suche. Die Lücken zwischen Polyominoes können sehr groß sein, wobei die größte Lücke etwa 4 Billionen voneinander entfernt ist. Daher wäre es schön, diejenigen zu überspringen, die ich nicht benötige, und mich nur auf die Polyominoes zu konzentrieren. Ich habe den Benutzer in einem Kommentar gefragt und er sagte, es wäre möglich und er sagte ja, es sei denn, ich habe ihn falsch verstanden, also erstelle ich diesen Beitrag. Natürlich kann jeder gerne darauf antworten.
Dies ist der Code aus dem vorherigen Beitrag, der die Nachschlagetabelle erstellt.

Code: Select all

/// 
/// Map from the long-form state code for each state to the state number
/// see expandState.
///
/// This is only used during state table construction.
/// 
Dictionary stateNumbers = new Dictionary();

/// 
/// Packed map from (state*256 + next_row_byte) -> transition
///
/// transition is next_state + (island_count 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

/// 
/// 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
/// 
/// The state code to expand.
/// the lower 8 bits represent the next row.   0-bits are land
/// The transition code for the transition from stateCode to nextrow
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 >= 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));
}