Python, +57 points

I chose a penrose (aperiodic) tiling composed of two different shaped rhombuses, meeting 3-8 per vertex. The simulation is graphical (via pygame) and interactive. Comments indicate two places in the code where algorithm implementation was taken from another source.

Penrose rhombii in Python, +97 points

I chose a penrose tiling composed of two different shaped rhombuses, meeting 3-8 per vertex. This penrose tiling is proven aperiodic elsewhere. The simulation is graphical (via pygame) and interactive. Comments indicate two places in the code where algorithm implementation was taken from another source.

#!/usr/bin/env python -O # tiling generation code originally from http://preshing.com/files/penrose.py import sys import math import time import cairo import cmath import random import pygame #TODO: command line parameters #------ Configuration -------- IMAGE_SIZE = (1200, 1200) OFFX = 600 OFFY = 600 RADIUS = 600 if __debug__: NUM_SUBDIVISIONS = 5 else: NUM_SUBDIVISIONS = 7 #----------------------------- goldenRatio = (1 + math.sqrt(5)) / 2 class Triangle(): def __init__(self, parent = None, color = 0, corners = []): self.parent = parent self.other_half = None # immediate neighbor 0 is on BA side, 1 is on AC side self.neighbors = [None, None] # all_neighbors includes diagonal neighbors self.all_neighbors = set() # child 0 is first on BA side, 1 is second, 2 is on AC side self.children = [] self.color = color if __debug__: self.debug_color = (random.random(),random.random(),random.random()) self.state = random.randint(0,1) self.new_state = 0 self.corners = corners self.quad = None def __repr__(self): return "Triangle: state=" + str(self.state) + \ " color=" + str(self.color) + \ " parent=" + ("yes" if self.parent else "no") + \ " corners=" + str(self.corners) # break one triangle up into 2-3 smaller triangles def subdivide(self): result = [] A,B,C = self.corners if self.color == 0: # Subdivide red triangle P = A + (B - A) / goldenRatio result = [Triangle(self, 0, (C, P, B)), Triangle(self, 1, (P, C, A))] else: # Subdivide blue triangle Q = B + (A - B) / goldenRatio R = B + (C - B) / goldenRatio result = [Triangle(self, 1, (Q, R, B)), Triangle(self, 0, (R, Q, A)), Triangle(self, 1, (R, C, A))] self.children.extend(result) return result; # identify the left and right neighbors of a triangle def connect_immediate(self): o = None n = self.neighbors if self.parent: if self.color == 0: # red child if self.parent.color == 0: # red parent if self.parent.neighbors[0]: if self.parent.neighbors[0].color == 0: # red left neighbor o = self.parent.neighbors[0].children[0] else: # blue left neighbor o = self.parent.neighbors[0].children[1] n[0] = self.parent.children[1] if self.parent.other_half: n[1] = self.parent.other_half.children[0] else: # blue parent if self.parent.neighbors[0]: if self.parent.neighbors[0].color == 0: # red left neighbor o = self.parent.neighbors[0].children[0] else: # blue left neighbor o = self.parent.neighbors[0].children[1] n[0] = self.parent.children[0] n[1] = self.parent.children[2] else: # blue child if self.parent.color == 0: # red parent if self.parent.neighbors[1]: if self.parent.neighbors[1].color == 0: # red right neighbor o = self.parent.neighbors[1].children[1] else: # blue right neighbor o = self.parent.neighbors[1].children[2] n[0] = self.parent.children[0] if self.parent.neighbors[0]: if self.parent.neighbors[0].color == 0: # red left neighbor n[1] = self.parent.neighbors[0].children[1] else: # blue left neighbor n[1] = self.parent.neighbors[0].children[0] else: # blue child of blue parent if self.corners[2] == self.parent.corners[1]: # first blue child if self.parent.other_half: o = self.parent.other_half.children[0] n[0] = self.parent.children[1] if self.parent.neighbors[0]: if self.parent.neighbors[0].color == 0: # red left neighbor n[1] = self.parent.neighbors[0].children[1] else: #blue left neighbor n[1] = self.parent.neighbors[0].children[0] else: # second blue child if self.parent.neighbors[1]: if self.parent.neighbors[1].color == 0: # red right neighbor o = self.parent.neighbors[1].children[1] else: # blue right neighbor o = self.parent.neighbors[1].children[2] if self.parent.other_half: n[0] = self.parent.other_half.children[2] n[1] = self.parent.children[1] self.other_half = o if o: self.state = self.other_half.state if __debug__: self.debug_color = self.other_half.debug_color #TODO: different seed triangle configurations # Create wheel of red triangles around the origin triangles = [[]] for i in xrange(10): B = cmath.rect(RADIUS, (2*i - 1) * math.pi / 10)+OFFX+OFFY*1j C = cmath.rect(RADIUS, (2*i + 1) * math.pi / 10)+OFFX+OFFY*1j if i % 2 == 0: B, C = C, B # Make sure to mirror every second triangle triangles[0].append(Triangle(None, 0, (OFFX+OFFY*1j, B, C))) # identify the neighbors of the starting triangles for i in xrange(10): if i%2: triangles[0][i].neighbors[0] = triangles[0][(i+9)%10] triangles[0][i].neighbors[1] = triangles[0][(i+1)%10] else: triangles[0][i].neighbors[1] = triangles[0][(i+9)%10] triangles[0][i].neighbors[0] = triangles[0][(i+1)%10] # Perform subdivisions for i in xrange(NUM_SUBDIVISIONS): triangles.append([]) for t in triangles[i]: triangles[i+1].extend(t.subdivide()) for t in triangles[i+1]: t.connect_immediate() # from here on, we only deal with the most-subdivided triangles tris = triangles[NUM_SUBDIVISIONS] # make a dict of every vertex, containing a list of every triangle sharing that vertex vertices = {} for t in tris: for c in t.corners: if c not in vertices: vertices[c] = [] vertices[c].append(t) # every triangle sharing a vertex are neighbors of each other for v,triset in vertices.iteritems(): for t in triset: t.all_neighbors.update(triset) # combine mirrored triangles into quadrilateral cells quads = [] total_neighbors = 0 for t in tris: if t.quad == None and t.other_half != None: quads.append(t) q = t q.corners = (q.corners[0], q.corners[1], q.other_half.corners[0], q.corners[2]) q.quad = q q.other_half.quad = q q.all_neighbors.update(q.other_half.all_neighbors) q.all_neighbors.remove(q.other_half) q.all_neighbors.remove(q) total_neighbors += len(q.all_neighbors) # clean up quads who still think they have triangles for neighbors for q in quads: new_neighbors = set() for n in q.all_neighbors: if len(n.corners)==3: if n.other_half: if len(n.other_half.corners)==4: new_neighbors.add(n.other_half) else: new_neighbors.add(n) q.all_neighbors = new_neighbors # # adopt your other half's neighbors, minus them and yourself. mark other half as dead. # for t in tris: # if t.other_half: # t.all_neighbors.update(t.other_half.all_neighbors) # t.all_neighbors.remove(t) # if t.other_half and t.other_half in t.all_neighbors: # t.all_neighbors.remove(t.other_half) # if t.other_half and not t.dead_half: # t.other_half.dead_half = True pygame.init() screen = pygame.display.set_mode(IMAGE_SIZE, 0, 32) pygame.display.set_caption("Penrose Life") pygame.display.flip() paused = False fast = False randomize = True found_oscillator = 0 randomized_tick = 0 tick = 0 timed_tick = 0 timed_tick_time = time.clock() render_countdown = 0 history_length = 45 quad_history = [[0]*len(quads)]*history_length quad_pointer = 0 myfont = pygame.font.SysFont("monospace", 15) guidish = random.randint(0,99999999) while True: tick += 1 if tick - randomized_tick > 1000 and render_countdown == 0: randomize = True edited = False step = False if found_oscillator > 0 and render_countdown == 0: print "Potential p" + str(found_oscillator) + " osillator" render_countdown = found_oscillator if render_countdown == 0: # don't handle input while rendering an oscillator for event in pygame.event.get(): if event.type == pygame.QUIT: sys.exit(0) elif event.type == pygame.KEYDOWN: # print event if event.scancode == 53: # escape sys.exit(0) elif event.unicode == " ": # randomize randomize = True edited = True elif event.unicode == "p": # pause paused = not paused elif event.unicode == "f": # fast fast = not fast elif event.unicode == "s": # step paused = True step = True elif event.type == pygame.MOUSEBUTTONDOWN: # click to toggle a cell x = event.pos[0] y = event.pos[1] for q in quads: poly = [(c.real,c.imag) for c in q.corners] # http://www.ariel.com.au/a/python-point-int-poly.html n = len(poly) inside = False p1x,p1y = poly[0] for i in range(n+1): p2x,p2y = poly[i % n] if y > min(p1y,p2y): if y <= max(p1y,p2y): if x <= max(p1x,p2x): if p1y != p2y: xinters = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x if p1x == p2x or x <= xinters: inside = not inside p1x,p1y = p2x,p2y if inside: edited = True q.state = 0 if q.state==1 else 1 if randomize and render_countdown == 0: randomized_tick = tick randomize = False for q in quads: q.state = random.randint(0,1) edited = True if (not fast) or (tick%25==0) or edited or render_countdown > 0: # draw filled quads for q in quads: cs = [(c.real,c.imag) for c in q.corners] if __debug__: color = q.debug_color color = (int(color[0]*256)<<24)+(int(color[1]*256)<<16)+(int(color[2]*256)<<8)+0xFF else: if q.state == 0: color = 0xFFFFFFFF else: color = 0x000000FF pygame.draw.polygon(screen, color, cs, 0) # draw edges for q in quads: if len(q.corners)==3: exit(1) cs = [(c.real,c.imag) for c in q.corners] width = 3 pygame.draw.lines(screen, 0x7F7F7FFF, 1, cs, int(width)) now = time.clock() speed = (tick-timed_tick)/(now-timed_tick_time) timed_tick_time = now timed_tick = tick screen.blit(screen, (0, 0)) label = myfont.render("%4.2f/s"%speed, 1, (255,255,255)) screen.fill(pygame.Color("black"), (0, 0, 110, 15)) screen.blit(label, (0, 0)) pygame.display.update() if __debug__: break if paused and not step and render_countdown == 0: time.sleep(0.05) continue # screenshot if render_countdown > 0: filename = "oscillator_p%03d_%08d_%03d.png" % (found_oscillator, guidish, found_oscillator - render_countdown) pygame.image.save(screen,filename) render_countdown -= 1 if render_countdown == 0: guidish = random.randint(0,99999999) found_oscillator = 0 randomize = True continue # calculate new cell states based on the Game of Life rules for q in quads: a = sum([n.state for n in q.all_neighbors]) q.new_state = q.state # dead cells with three neighbors spawn if q.state == 0 and a == 3: q.new_state = 1 # live cells only survive with two or three neighbors elif a < 2 or a > 3: q.new_state = 0 # update cell states for q in quads: q.state = q.new_state this_state = [q.state for q in quads] # don't bother checking if render_countdown == 0: # compare this board state to the last N-1 states for i in range(1,history_length): if quad_history[(quad_pointer-i)%history_length] == this_state: if i == 1 or i == 2: # stalled board or p2 oscillator (boring) randomize = True break #TODO: give up if the "oscillator" includes border cells #TODO: identify cases of two oprime oscillators overlapping elif i > 2: found_oscillator = i break # don't keep looking # remember this board state quad_history[quad_pointer] = this_state quad_pointer = (quad_pointer+1)%history_length if __debug__: filename = "penrose.png" pygame.image.save(screen,filename) time.sleep(1) 

#!/usr/bin/env python -O # tiling generation code originally from http://preshing.com/files/penrose.py import sys import math import time import cairo import cmath import random import pygame #TODO: command line parameters #------ Configuration -------- IMAGE_SIZE = (1200, 1200) OFFX = 600 OFFY = 600 RADIUS = 600 if __debug__: NUM_SUBDIVISIONS = 5 else: NUM_SUBDIVISIONS = 7 #----------------------------- goldenRatio = (1 + math.sqrt(5)) / 2 class Triangle(): def __init__(self, parent = None, color = 0, corners = []): self.parent = parent self.other_half = None # immediate neighbor 0 is on BA side, 1 is on AC side self.neighbors = [None, None] # all_neighbors includes diagonal neighbors self.all_neighbors = set() # child 0 is first on BA side, 1 is second, 2 is on AC side self.children = [] self.color = color if __debug__: self.debug_color = (random.random(),random.random(),random.random()) self.state = random.randint(0,1) self.new_state = 0 self.corners = corners self.quad = None def __repr__(self): return "Triangle: state=" + str(self.state) + \ " color=" + str(self.color) + \ " parent=" + ("yes" if self.parent else "no") + \ " corners=" + str(self.corners) # break one triangle up into 2-3 smaller triangles def subdivide(self): result = [] A,B,C = self.corners if self.color == 0: # Subdivide red triangle P = A + (B - A) / goldenRatio result = [Triangle(self, 0, (C, P, B)), Triangle(self, 1, (P, C, A))] else: # Subdivide blue triangle Q = B + (A - B) / goldenRatio R = B + (C - B) / goldenRatio result = [Triangle(self, 1, (Q, R, B)), Triangle(self, 0, (R, Q, A)), Triangle(self, 1, (R, C, A))] self.children.extend(result) return result; # identify the left and right neighbors of a triangle def connect_immediate(self): o = None n = self.neighbors if self.parent: if self.color == 0: # red child if self.parent.color == 0: # red parent if self.parent.neighbors[0]: if self.parent.neighbors[0].color == 0: # red left neighbor o = self.parent.neighbors[0].children[0] else: # blue left neighbor o = self.parent.neighbors[0].children[1] n[0] = self.parent.children[1] if self.parent.other_half: n[1] = self.parent.other_half.children[0] else: # blue parent if self.parent.neighbors[0]: if self.parent.neighbors[0].color == 0: # red left neighbor o = self.parent.neighbors[0].children[0] else: # blue left neighbor o = self.parent.neighbors[0].children[1] n[0] = self.parent.children[0] n[1] = self.parent.children[2] else: # blue child if self.parent.color == 0: # red parent if self.parent.neighbors[1]: if self.parent.neighbors[1].color == 0: # red right neighbor o = self.parent.neighbors[1].children[1] else: # blue right neighbor o = self.parent.neighbors[1].children[2] n[0] = self.parent.children[0] if self.parent.neighbors[0]: if self.parent.neighbors[0].color == 0: # red left neighbor n[1] = self.parent.neighbors[0].children[1] else: # blue left neighbor n[1] = self.parent.neighbors[0].children[0] else: # blue child of blue parent if self.corners[2] == self.parent.corners[1]: # first blue child if self.parent.other_half: o = self.parent.other_half.children[0] n[0] = self.parent.children[1] if self.parent.neighbors[0]: if self.parent.neighbors[0].color == 0: # red left neighbor n[1] = self.parent.neighbors[0].children[1] else: #blue left neighbor n[1] = self.parent.neighbors[0].children[0] else: # second blue child if self.parent.neighbors[1]: if self.parent.neighbors[1].color == 0: # red right neighbor o = self.parent.neighbors[1].children[1] else: # blue right neighbor o = self.parent.neighbors[1].children[2] if self.parent.other_half: n[0] = self.parent.other_half.children[2] n[1] = self.parent.children[1] self.other_half = o if o: self.state = self.other_half.state if __debug__: self.debug_color = self.other_half.debug_color #TODO: different seed triangle configurations # Create wheel of red triangles around the origin triangles = [[]] for i in xrange(10): B = cmath.rect(RADIUS, (2*i - 1) * math.pi / 10)+OFFX+OFFY*1j C = cmath.rect(RADIUS, (2*i + 1) * math.pi / 10)+OFFX+OFFY*1j if i % 2 == 0: B, C = C, B # Make sure to mirror every second triangle triangles[0].append(Triangle(None, 0, (OFFX+OFFY*1j, B, C))) # identify the neighbors of the starting triangles for i in xrange(10): if i%2: triangles[0][i].neighbors[0] = triangles[0][(i+9)%10] triangles[0][i].neighbors[1] = triangles[0][(i+1)%10] else: triangles[0][i].neighbors[1] = triangles[0][(i+9)%10] triangles[0][i].neighbors[0] = triangles[0][(i+1)%10] # Perform subdivisions for i in xrange(NUM_SUBDIVISIONS): triangles.append([]) for t in triangles[i]: triangles[i+1].extend(t.subdivide()) for t in triangles[i+1]: t.connect_immediate() # from here on, we only deal with the most-subdivided triangles tris = triangles[NUM_SUBDIVISIONS] # make a dict of every vertex, containing a list of every triangle sharing that vertex vertices = {} for t in tris: for c in t.corners: if c not in vertices: vertices[c] = [] vertices[c].append(t) # every triangle sharing a vertex are neighbors of each other for v,triset in vertices.iteritems(): for t in triset: t.all_neighbors.update(triset) # combine mirrored triangles into quadrilateral cells quads = [] total_neighbors = 0 for t in tris: if t.quad == None and t.other_half != None: quads.append(t) q = t q.corners = (q.corners[0], q.corners[1], q.other_half.corners[0], q.corners[2]) q.quad = q q.other_half.quad = q q.all_neighbors.update(q.other_half.all_neighbors) q.all_neighbors.remove(q.other_half) q.all_neighbors.remove(q) total_neighbors += len(q.all_neighbors) # clean up quads who still think they have triangles for neighbors for q in quads: new_neighbors = set() for n in q.all_neighbors: if len(n.corners)==3: if n.other_half: if len(n.other_half.corners)==4: new_neighbors.add(n.other_half) else: new_neighbors.add(n) q.all_neighbors = new_neighbors # # adopt your other half's neighbors, minus them and yourself. mark other half as dead. # for t in tris: # if t.other_half: # t.all_neighbors.update(t.other_half.all_neighbors) # t.all_neighbors.remove(t) # if t.other_half and t.other_half in t.all_neighbors: # t.all_neighbors.remove(t.other_half) # if t.other_half and not t.dead_half: # t.other_half.dead_half = True pygame.init() screen = pygame.display.set_mode(IMAGE_SIZE, 0, 32) pygame.display.set_caption("Penrose Life") pygame.display.flip() paused = False fast = False randomize = True found_oscillator = 0 randomized_tick = 0 tick = 0 timed_tick = 0 timed_tick_time = time.clock() render_countdown = 0 history_length = 45 quad_history = [[0]*len(quads)]*history_length quad_pointer = 0 myfont = pygame.font.SysFont("monospace", 15) guidish = random.randint(0,99999999) while True: tick += 1 if tick - randomized_tick > 1000 and render_countdown == 0: randomize = True edited = False step = False if found_oscillator > 0 and render_countdown == 0: print "Potential p" + str(found_oscillator) + " osillator" render_countdown = found_oscillator if render_countdown == 0: # don't handle input while rendering an oscillator for event in pygame.event.get(): if event.type == pygame.QUIT: sys.exit(0) elif event.type == pygame.KEYDOWN: # print event if event.scancode == 53: # escape sys.exit(0) elif event.unicode == " ": # randomize randomize = True edited = True elif event.unicode == "p": # pause paused = not paused elif event.unicode == "f": # fast fast = not fast elif event.unicode == "s": # step paused = True step = True elif event.type == pygame.MOUSEBUTTONDOWN: # click to toggle a cell x = event.pos[0] y = event.pos[1] for q in quads: poly = [(c.real,c.imag) for c in q.corners] # http://www.ariel.com.au/a/python-point-int-poly.html n = len(poly) inside = False p1x,p1y = poly[0] for i in range(n+1): p2x,p2y = poly[i % n] if y > min(p1y,p2y): if y <= max(p1y,p2y): if x <= max(p1x,p2x): if p1y != p2y: xinters = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x if p1x == p2x or x <= xinters: inside = not inside p1x,p1y = p2x,p2y if inside: edited = True q.state = 0 if q.state==1 else 1 if randomize and render_countdown == 0: randomized_tick = tick randomize = False for q in quads: q.state = random.randint(0,1) edited = True if (not fast) or (tick%25==0) or edited or render_countdown > 0: # draw filled quads for q in quads: cs = [(c.real,c.imag) for c in q.corners] if __debug__: color = q.debug_color color = (int(color[0]*256)<<24)+(int(color[1]*256)<<16)+(int(color[2]*256)<<8)+0xFF else: if q.state == 0: color = 0xFFFFFFFF else: color = 0x000000FF pygame.draw.polygon(screen, color, cs, 0) # draw edges for q in quads: if len(q.corners)==3: exit(1) cs = [(c.real,c.imag) for c in q.corners] width = 3 pygame.draw.lines(screen, 0x7F7F7FFF, 1, cs, int(width)) now = time.clock() speed = (tick-timed_tick)/(now-timed_tick_time) timed_tick_time = now timed_tick = tick screen.blit(screen, (0, 0)) label = myfont.render("%4.2f/s"%speed, 1, (255,255,255)) screen.fill(pygame.Color("black"), (0, 0, 110, 15)) screen.blit(label, (0, 0)) pygame.display.update() if __debug__: break if paused and not step and render_countdown == 0: time.sleep(0.05) continue # screenshot if render_countdown > 0: filename = "oscillator_p%03d_%08d_%03d.png" % (found_oscillator, guidish, found_oscillator - render_countdown) pygame.image.save(screen,filename) render_countdown -= 1 if render_countdown == 0: guidish = random.randint(0,99999999) found_oscillator = 0 randomize = True continue # calculate new cell states based on the Game of Life rules for q in quads: a = sum([n.state for n in q.all_neighbors]) q.new_state = q.state # dead cells with three neighbors spawn if q.state == 0 and a == 3: q.new_state = 1 # live cells only survive with two or three neighbors elif a < 2 or a > 3: q.new_state = 0 # update cell states for q in quads: q.state = q.new_state this_state = [q.state for q in quads] # don't bother checking if render_countdown == 0: # compare this board state to the last N-1 states for i in range(1,history_length): if quad_history[(quad_pointer-i)%history_length] == this_state: if i == 1 or i == 2: # stalled board or p2 oscillator (boring) randomize = True break #TODO: give up if the "oscillator" includes border cells #TODO: identify cases of two oprime oscillators overlapping elif i > 2: found_oscillator = i break # don't keep looking # remember this board state quad_history[quad_pointer] = this_state quad_pointer = (quad_pointer+1)%history_length if __debug__: filename = "penrose.png" pygame.image.save(screen,filename) time.sleep(1)