Skip to content

Instantly share code, notes, and snippets.

@davidar
Created March 24, 2023 08:52
Show Gist options
  • Save davidar/621180c13c27294f99033531f921df65 to your computer and use it in GitHub Desktop.
Save davidar/621180c13c27294f99033531f921df65 to your computer and use it in GitHub Desktop.
"""
Polykite Tiling Explorer
Author: OpenAI GPT-4
Description:
This script explores the tiling properties of polykites, specifically those with 8 components.
It generates all possible polykites with 8 components, canonicalizes them to avoid duplicate
analysis, and then computes their isohedral numbers to identify interesting candidates for further
mathematical exploration.
The script is based on the following functions:
1. generate_all_polykites: Generates all possible polykites with a given number of components.
2. canonicalize: Computes the canonical representation of a polykite to avoid duplicate analysis.
3. isohedral_number: Computes the isohedral number of a polykite by attempting to tile the plane using backtracking.
4. get_coordinates: Extracts the coordinates of the vertices of a polykite.
5. tile_plane: Checks if a given tiling of a polykite covers the entire plane within a specified bounding box.
6. backtrack: Backtracking function used within the isohedral_number function to explore all possible tilings of a polykite.
7. get_transformations: Generates a list of possible transformations to apply to a polykite.
8. apply_transformation: Applies a given transformation (rotation, reflection, and translation) to a polykite.
9. can_place: Checks if a transformed polykite can be placed at a specific position without overlapping other polykites.
10. main: Serves as the integration point for all the other functions.
Please note that this implementation is a high-level representation and might require adjustments
based on your specific needs, libraries, and representation of polykites.
"""
import networkx as nx
def generate_all_polykites(n_kites):
def recursive_generate(current_polykite, remaining_kites):
if remaining_kites == 0:
yield current_polykite
else:
for edge in current_polykite.edges():
new_polykite = add_kite_to_edge(current_polykite, edge)
if new_polykite and not has_self_intersection(new_polykite):
yield from recursive_generate(new_polykite, remaining_kites - 1)
def add_kite_to_edge(polykite, edge):
new_polykite = polykite.copy()
node1, node2 = edge
neighbors1 = [n for n in polykite.neighbors(node1) if n != node2]
neighbors2 = [n for n in polykite.neighbors(node2) if n != node1]
if not neighbors1 or not neighbors2:
return None
new_node = max(new_polykite.nodes()) + 1
new_polykite.add_node(new_node)
new_polykite.add_edge(new_node, node1)
new_polykite.add_edge(new_node, node2)
for neighbor in neighbors1:
if neighbor not in neighbors2:
new_polykite.add_edge(new_node, neighbor)
break
return new_polykite
def has_self_intersection(polykite):
# Check if any nodes have more than two neighbors
for node in polykite.nodes():
if len(list(polykite.neighbors(node))) > 2:
return True
return False
# Start with a single kite as the base polykite
initial_polykite = create_kite()
return list(recursive_generate(initial_polykite, n_kites - 1))
def create_kite():
kite = nx.Graph()
kite.add_nodes_from(range(4))
kite.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)])
return kite
def canonicalize(polykite):
def get_coordinates(polykite):
coordinates = []
for node, data in polykite.nodes(data=True):
coordinates.append(data['pos'])
return coordinates
def normalize_coordinates(coords):
min_x, min_y = min(coords, key=lambda p: (p[0], p[1]))
return [(x - min_x, y - min_y) for x, y in coords]
def rotate_90(coords):
return [(y, -x) for x, y in coords]
def reflect(coords):
return [(-x, y) for x, y in coords]
coordinates = get_coordinates(polykite)
normalized_coordinates = normalize_coordinates(coordinates)
canonical_form = normalized_coordinates
for _ in range(3):
normalized_coordinates = rotate_90(normalized_coordinates)
canonical_form = min(canonical_form, normalized_coordinates)
reflected_coordinates = reflect(normalized_coordinates)
canonical_form = min(canonical_form, reflected_coordinates)
return canonical_form
def isohedral_number(polykite):
def tile_plane(polykite, current_tiling):
# Define a bounding box for the area of the plane we want to check for tiling
bounding_box = (-10, -10, 10, 10)
# Initialize an empty plane grid
plane = [[False for _ in range(bounding_box[2] - bounding_box[0] + 1)] for _ in range(bounding_box[3] - bounding_box[1] + 1)]
# Fill the grid with the current tiling
for tiled_polykite in current_tiling:
for node, data in tiled_polykite.nodes(data=True):
x, y = data['pos']
if bounding_box[0] <= x <= bounding_box[2] and bounding_box[1] <= y <= bounding_box[3]:
plane[y - bounding_box[1]][x - bounding_box[0]] = True
# Check if the entire grid is covered
for row in plane:
for cell in row:
if not cell:
return False
return True
def backtrack(polykite, current_tiling):
if tile_plane(polykite, current_tiling):
return True
# Try to place a new copy of the polykite in the plane
for transformation in get_transformations(polykite):
new_polykite = apply_transformation(polykite, transformation)
if can_place(new_polykite, current_tiling):
current_tiling.append(new_polykite)
if backtrack(polykite, current_tiling):
return True
current_tiling.pop()
return False
def get_transformations(polykite):
# Generate possible translations, rotations, and reflections of the polykite
transformations = []
for dx in range(-10, 11):
for dy in range(-10, 11):
for angle in [0, 90, 180, 270]:
for reflection in [False, True]:
transformations.append((dx, dy, angle, reflection))
return transformations
def apply_transformation(polykite, transformation):
dx, dy, angle, reflection = transformation
transformed_polykite = polykite.copy()
# Apply translation
for node in transformed_polykite.nodes():
x, y = transformed_polykite.nodes[node]['pos']
transformed_polykite.nodes[node]['pos'] = (x + dx, y + dy)
# Apply rotation
for node in transformed_polykite.nodes():
x, y = transformed_polykite.nodes[node]['pos']
if angle == 90:
transformed_polykite.nodes[node]['pos'] = (-y, x)
elif angle == 180:
transformed_polykite.nodes[node]['pos'] = (-x, -y)
elif angle == 270:
transformed_polykite.nodes[node]['pos'] = (y, -x)
# Apply reflection if needed
if reflection:
for node in transformed_polykite.nodes():
x, y = transformed_polykite.nodes[node]['pos']
transformed_polykite.nodes[node]['pos'] = (-x, y)
return transformed_polykite
def can_place(polykite, current_tiling):
# Check if the polykite can be placed in the current tiling without overlaps or gaps
for existing_polykite in current_tiling:
for node1, data1 in polykite.nodes(data=True):
for node2, data2 in existing_polykite.nodes(data=True):
if data1['pos'] == data2['pos']:
return False
return True
current_tiling = [polykite]
isohedral_count = 0
while backtrack(polykite, current_tiling):
isohedral_count += 1
return isohedral_count
def main():
polykites = generate_all_polykites(8)
seen_polykites = set()
for polykite in polykites:
canonical_polykite = canonicalize(polykite)
if canonical_polykite not in seen_polykites:
seen_polykites.add(canonical_polykite)
iso_number = isohedral_number(polykite)
if iso_number >= 64:
print(f"Found polykite with isohedral number >= 64: {canonical_polykite}")
# Further analyze the polykite with other mathematical techniques
if __name__ == "__main__":
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment