Squiggles

A forum where anything goes. Introduce yourselves to other members of the forums, discuss how your name evolves when written out in the Game of Life, or just tell us how you found it. This is the forum for "non-academic" content.
Post Reply
pcallahan
Posts: 490
Joined: April 26th, 2013, 1:04 pm

Squiggles

Post by pcallahan » February 7th, 2020, 10:06 pm

The idea is to start with tiles based on matching points like parentheses. The points along the bottom of each tile are connected with circular arcs. E.g., ()(()) would connect positions 0 and 1, 2 and 5, 3 and 4. When you place these tiles together, you may get one or more closed curves. Which ones pair up to form a simple closed curve without holes?

I think this is a versatile tile matching rule that is easy to check visually. That is, you can immediately see if the result is a simple closed curve without holes.
t.png
t.png (182.37 KiB) Viewed 1459 times
The Python script to create it using imagemagick.

Code: Select all

def parens(n):
  for res in parens_recur(n * 2, 0, []):
    yield res

def parens_recur(n, depth, sofar):
  if n == len(sofar):
    yield "".join(sofar)
  else:
    if len(sofar) + depth < n:
      sofar.append("(")
      for res in parens_recur(n, depth + 1, sofar):
        yield res
      sofar.pop()
    if depth > 0:
      sofar.append(")")
      for res in parens_recur(n, depth - 1, sofar):
        yield res
      sofar.pop()

def links(paren_string):
  stack = []
  for i in range(len(paren_string)):
    if paren_string[i] == '(':
      stack.append(i)
    else:
      yield (stack.pop(), i)

def perm(links):
  links = list(links)
  ix = [0] * len(links) * 2
  for i, j in links:
    ix[i], ix[j] = j, i
  return ix

def rotate(links):
  return [len(links) - i -1 for i in links[::-1]]

def loops(uplinks, downlinks):
  seen = [False for x in uplinks]
  loops = []
  for i in range(len(uplinks)):
    if not seen[i]:
      loop = []
      j = i
      while not seen[j]:
        seen[j] = True
        loop.append(j)
        j = uplinks[j]
        seen[j] = True
        loop.append(j)
        j = downlinks[j]
      loops.append(loop)
  return loops

def to_curve(loops, scale, x, y):
  yield "-fill black -stroke none -draw 'fill-rule evenodd translate %5.3f %5.3f path \"" % (x, y)
  for loop in loops:
    n = len(loop)
    yield 'M %5.3f 0' % (loop[0] * scale)
    for i in range(n):
      x1 = loop[i] * scale
      x2 = loop[(i + 1) % n] * scale
      sweep = ((0 if x1 > x2 else 1) + i) % 2
      radius = abs(x2 - x1) * 0.5
      yield 'A %5.3f %5.3f 0 0 %5.3f %5.3f 0' % (radius, radius, sweep, x2)
    yield ' Z'
  yield "\"'"

def to_upper(links, scale, x, y):
  edges = [i + (1 - (i % 2) * 2) for i in range(len(links))]
  yield "-fill black -stroke none -draw 'fill-rule evenodd translate %5.3f %5.3f path \"" % (x, y)
  for loop in loops(links, edges):
    n = len(loop)
    yield 'M %5.3f 0' % (loop[0] * scale)
    for i in range(n):
      x1 = loop[i] * scale
      x2 = loop[(i + 1) % n] * scale
      sweep = ((0 if x1 > x2 else 1) + i) % 2
      radius = abs(x2 - x1) * 0.5
      if i % 2 == 0:
        yield 'A %5.3f %5.3f 0 0 %5.3f %5.3f 0' % (radius, radius, sweep, x2)
      else:
        yield 'L %5.3f 0' % x2
    yield ' Z'
  yield "\"'"

n = 5
allix = [perm(links(s)) for s in parens(n)]

'''
for i in range(len(allix)):
  for j in range(len(allix)):
    print("*" if 1 == len(loops(allix[i], rotate(allix[j]))) else ".", end=' ')
  print()
  '''

def nextpos(x, y):
   x += 85
   if x > 1700:
     x = 50
     y += 90
   return x, y

x = 50
y = 100
lines = ["magick -size 1800x1800 canvas:none "]
for i in range(len(allix)):
  lines.extend(to_upper(allix[i], 7, x, y))
  lines.append("-fill none -stroke blue -draw 'translate %5.3f %5.3f rectangle %5.3f 0 %5.3f %5.3f'" %
               (x, y, -5, (2 * n - 1) * 8 + 5, -n * 8 - 5))
  x, y = nextpos(x, y)

x = 50
y += 90

for i in range(len(allix)):
  for j in range(len(allix)):
    path = loops(allix[i], rotate(allix[j]))
    if len(path) == 1:
      lines.extend(to_curve(path, 7, x, y))
      lines.append("-fill none -stroke blue -draw 'translate %5.3f %5.3f rectangle %5.3f 0 %5.3f %5.3f'" %
               (x, y, -5, (2 * n - 1) * 8 + 5, -n * 8 - 5))
      lines.append("-fill none -stroke blue -draw 'translate %5.3f %5.3f rectangle %5.3f 0 %5.3f %5.3f'" %
               (x, y, -5, (2 * n - 1) * 8 + 5, n * 8 - 5))
      x, y = nextpos(x, y)
  lines.append("-fill red -draw 'translate %5.3f %5.3f rectangle 20 -3 26 3'" % (x, y)) 
  x, y = nextpos(x, y)
lines.append("t.png")

print(" \\\n".join(lines))

User avatar
PkmnQ
Posts: 936
Joined: September 24th, 2018, 6:35 am
Location: Server antipode

Re: Squiggles

Post by PkmnQ » February 8th, 2020, 12:43 am

Sure like tiling, don’t you. This actually looks pretty good, if I had these in real life I would start matching them together to see what they would look like.
How to XSS:

Code: Select all

Function(‘a’+’lert(1)’)()

pcallahan
Posts: 490
Joined: April 26th, 2013, 1:04 pm

Re: Squiggles

Post by pcallahan » February 8th, 2020, 12:32 pm

PkmnQ wrote:
February 8th, 2020, 12:43 am
Sure like tiling, don’t you.
You noticed!
This actually looks pretty good, if I had these in real life I would start matching them together to see what they would look like.
Well, if you have a printer, these ones are sized for printing and cutting. I haven't done it myself with these, at least not recently.
all42.png
all42.png (152.49 KiB) Viewed 1424 times
I had an idea for these kinds of matching tiles a few years ago, unconnected to Life or universality. I was thinking that you could make a set of flash cards for matching things, e.g. words and definitions, or words in foreign languages. If you place two matching cards together, you get a "valid" pattern, e.g. connected without holes, or maybe some other easily checked rule, and if not, you get something that violates the rule. This has advantages over matching by color:
  • At a glance, it's harder to guess how two of these cards will line up, as compared to red matches red, or jigsaw nub matches dent.
  • Patterns can be chosen that are not transitive. A matches B, B matches C, but C does not match A.
I never made the flashcards, but the idea stuck. I had some Postscript code for this that I lost, and I realized I can do it with svg paths and generate pictures with imagemagick.

Each tile is based on matched parentheses. The above use 5 matched pairs for a total of 42. The number of ways to match parentheses grows with n according to the Catalan numbers 1, 2, 5, 14, 42, 132, ...

Here's a picture of all combinations for n=4. Note that the lower tiles are rotated 180 degrees (the way it would work in real life).
t.png
t.png (96.29 KiB) Viewed 1417 times
On the subject of universality, what if we had a rotatable tiles with a pattern like this along each of their 4 sides, and an easily stated rule for validity, such as "connected with exactly 2 holes" or "two connected components with a hole in exactly one of them." What is the smallest tile set we need to implement universal Wang tiles?

pcallahan
Posts: 490
Joined: April 26th, 2013, 1:04 pm

Re: Squiggles

Post by pcallahan » February 9th, 2020, 3:41 pm

Here's one I've only sketched out, but what if we connect corners instead of sides with non-crossing arcs. Then which corner placements result in single closed curves without holes. For this size, there are 14 possible corner tiles. And here are some examples of combining them.
Screen Shot 2020-02-09 at 11.36.35 AM.png
Screen Shot 2020-02-09 at 11.36.35 AM.png (191.57 KiB) Viewed 1384 times
The simplest analysis might be to treat pairs of corner curves as edge curves and then see how those combine.

pcallahan
Posts: 490
Joined: April 26th, 2013, 1:04 pm

Re: Squiggles

Post by pcallahan » February 12th, 2020, 4:49 pm

I just realized that the simple connected "blobs" are actually spanning trees of the boundary nodes (a node is just the interval of black space on each boundary). This is true for the corner tiles above as well as the original tiles.

This explains some of the requirements for connectivity. If there are n nodes, there must be exactly n-1 edges that connect them. If there are fewer, you cannot connect all the nodes. If there are more, there must be a cycle somewhere (a hole in the blob). That is a necessary but not sufficient condition. You can have n-1 edges that make two disconnected blobs, one of which has a hole in it.

hkoenig
Posts: 126
Joined: June 20th, 2009, 11:40 am

Re: Squiggles

Post by hkoenig » February 12th, 2020, 9:08 pm

Interesting. Here's a not well thought out game idea--

Use two or three colors for the black blobs. If I calculate correctly, there would be 90 tiles with two colors, 300 with three, and 1400 with four. Then the object of a two person (or more?) game would be to build a complete four tile pattern, drawing tiles randomly and passing if unable to play. Winner is the player making the most completed patterns, or first to complete N patterns.

Second would be same sort of coloring with 3, but allow any matching edges, so patterns can grow. Players score the size of the closed blobs created.

pcallahan
Posts: 490
Joined: April 26th, 2013, 1:04 pm

Re: Squiggles

Post by pcallahan » February 13th, 2020, 12:49 pm

hkoenig wrote:
February 12th, 2020, 9:08 pm
Interesting. Here's a not well thought out game idea--

Use two or three colors for the black blobs. If I calculate correctly, there would be 90 tiles with two colors, 300 with three, and 1400 with four. Then the object of a two person (or more?) game would be to build a complete four tile pattern, drawing tiles randomly and passing if unable to play. Winner is the player making the most completed patterns, or first to complete N patterns.

Second would be same sort of coloring with 3, but allow any matching edges, so patterns can grow. Players score the size of the closed blobs created.
It's worth a try. I like the idea of building card decks that score hands based on intrinsic properties instead of arbitrary rules. Aside from simply connected curves, you can make comparisons based on number of components and holes. You could work out the probabilities to make it similar to a standard card game. Alternatively, if you could play test it, you might arrive at some rules intuitively.

pcallahan
Posts: 490
Joined: April 26th, 2013, 1:04 pm

Re: Squiggles

Post by pcallahan » February 16th, 2020, 1:53 pm

Simple connected blobs without holes can be applied to recognize still life neighborhoods in CGOL. This illustrates the idea at a schematic level, but you could just as easily use thicker lines to make blobs.

Use an approach like the petal tiles to collect neighbor counts, but instead of representing a live cell with a petal, represent it as the absence of one side of an octagon. Then, the number of connected components of octagon vertices is the same as the number of absent edges. I.e., remove an edge and you get a simple connected path, remove 2 and you get two connected paths, remove 3 and so forth. For example:
Screen Shot 2020-02-16 at 9.39.30 AM.png
Screen Shot 2020-02-16 at 9.39.30 AM.png (36.53 KiB) Viewed 1270 times
Visually, the absent edges aren't as easy to see as petals or dots, but only two additional tiles are needed to recognize them. A straight line for connecting 2 components, and a y for connecting 3 components. If the number of components is not 2 or 3, then you will get either a cycle, a disconnected component, or both.
Screen Shot 2020-02-16 at 9.43.02 AM.png
Screen Shot 2020-02-16 at 9.43.02 AM.png (146.13 KiB) Viewed 1270 times
This stretches the concept of a tiling, and I'm not sure it helps that much beyond counting dots, which is already about as easy as recognizing connected blobs. It's a little more magical (a disadvantage in analysis, but maybe a plus for a puzzle) and I wanted to take the idea to its conclusion.

That leaves open the question of recognizing dead cell neighborhoods of 0, 1, 2, 4, 5, and 6. There are some problems here, the first being that a 0 neighborhood already gives an octagon with a cycle. We could just declare that cycle valid by fiat but then why not just count dots. There are some alternatives, like requiring the internal tile to connect the octagon, or using a present edge to represent a live neighbor. Unfortunately, all of these require more tiles and I am not sure it's worth pursuing.

Update: For example, to recognize 2 present edges (as opposed to two absent edges) two different middle connectors are needed. (Top row) The leftmost 3 below use the same connector, rotated, but the rightmost requires a different one to avoid creating a loop with the adjacent edges. To recognize 4 present edges (bottom row), two different middle connectors also suffice, assuming the neighbors are grouped as in viewtopic.php?f=7&t=2188&start=100#p88361
Screen Shot 2020-02-16 at 3.26.06 PM.png
Screen Shot 2020-02-16 at 3.26.06 PM.png (149.43 KiB) Viewed 1247 times
Recognizing 5 or 6 present edges is the same as recognizing 3 or 2 absent edges respectively.

Post Reply