juj/cube_folding.py

## cube_folding.py
# Usage: python cube_folding.py input.txt
import math, sys

lines = open(sys.argv[1] if len(sys.argv) > 1 else 'input.txt', 'r').read().split('\n')

# Remove instructions line from input
lines = lines[:-1]
if len(lines[-1]) == 0: lines.pop() # Remove possible empty line between map and instructions

# Compute cube surface area
area = sum(len(x.strip()) for x in lines)
print('Surface area of cube:', area)

# Compute individual side length
side = int(math.sqrt(area/6))
print('Side length:', side)

# Calculate 2D map size
height = len(lines)
print('Height:', height)
width = max([len(x) for x in lines])
print('Width:', width)

# Returns character on the map at x,y
def get(x,y):
  if x < 0 or y < 0 or y >= len(lines) or x >= len(lines[y]):
    return ' '
  return lines[y][x]

# Returns 1 if given coordinate falls outside a cube edge
def is_outside(x, y):
  if get(x, y) == ' ':
    return 1
  return 0

# Find all the internal corners in this shape
# Internal corners can be identified by looking at neighboring 2x2 shapes and finding where exactly
# three of the positions are inside the map, and one is outside
inner_corners = []
for y in range(height-1):
  s = ''
  for x in range(width-1):
    s += get(x,y)
    count = is_outside(x, y) + is_outside(x+1, y) + is_outside(x, y+1) + is_outside(x+1, y+1)
    if count == 1:
      inner_corners += [(x,y)]
  print(s)

print('Shape has internal corners at:')
print(str(inner_corners))
print('\n')

dirs = [(1,0), (0,1), (-1,0), (0,-1)] # Given a heading 0-3, which way would we travel? (same convention as problem input)

# Finds on the contours of the 2D map the heading that the edge is winding. This is done by compressing the
# four inside/outside states of a 2x2 block into a bitmask, and indexing an array to look up the clockwise heading
def cw_heading(x,y):
  kind = is_outside(x,y) | (is_outside(x+1,y) << 1) | (is_outside(x,y+1) << 2) | (is_outside(x+1,y+1)<<3)
  heading = [-1, 3, 0, 0, 2, 3, -1, 0, 1, -1, 1, 1, 2, 3, 2, -1][kind]
  assert heading >= 0
  return heading

# Same as above, but CCW winding. -1 values in the array are for cases that cannot occur.
def ccw_heading(x,y):
  kind = is_outside(x,y) | (is_outside(x+1,y) << 1) | (is_outside(x,y+1) << 2) | (is_outside(x+1,y+1)<<3)
  heading = [-1, 2, 3, 2, 1, 1, -1, 1, 0, -1, 3, 2, 0, 0, 3, -1][kind]
  assert heading >= 0
  return heading

# paint the winding of the edges. Outmap receives the ascii art picture. N.b. outmap
# is expanded by one to top and left to allow for the ascii drawing to expand outside
# the cube edges for better visuals.
outmap = Matrix = [[get(x-1,y-1) for x in range(width+1)] for y in range(height+1)]

ch_small = ord('a') # Draw edges with A, B, C, etc.
ch_large = ord('A')

# Draws a character on the output map
def plot(x, y, ch):
  x += 1
  y += 1
  if x >= 0 and y >= 0 and x < len(outmap[0]) and y < len(outmap): outmap[y][x] = ch

# Tracks which cube edges we have traversed in 1st pass of the algorithm, to avoid redoing
# them in the 2nd pass
plotted_edges = []

# Tests if a given cube edge has already been traversed
def has_been_plotted(sx, sy, ex, ey):
  return (sx, sy, ex, ey) in plotted_edges or (ex, ey, sx, sy) in plotted_edges

# The main body of the algorithm, pass_number=1 or 2
def fill_corners(pass_number):
  global ch_small, ch_large, plotted_edges
  # Stitch edges of the cube, starting at each internal corner in turn
  for x, y in inner_corners:
    # Start CW and CCW winding cursors initially at the same internal corners
    cw_x = x
    cw_y = y
    cw_dir = cw_heading(x, y) # Look at the 2x2 neighborhood of the corner to see which heading the cursor should have
    ccw_x = x
    ccw_y = y
    ccw_dir = ccw_heading(x, y) # Same for CCW cursor

    while True:
      # Travel CW and CCW cursors one cube edge forward
      cw_x_end = cw_x + dirs[cw_dir][0] * side
      cw_y_end = cw_y + dirs[cw_dir][1] * side
      ccw_x_end = ccw_x + dirs[ccw_dir][0] * side
      ccw_y_end = ccw_y + dirs[ccw_dir][1] * side
      new_cw_dir = cw_heading(cw_x_end, cw_y_end)
      new_ccw_dir = ccw_heading(ccw_x_end, ccw_y_end)

      if pass_number == 2: # 2nd pass should skip over cube edges that have already been processed in 1st pass
        # Skip CW cursor over already processed edges
        while has_been_plotted(cw_x, cw_y, cw_x_end, cw_y_end):
          cw_x = cw_x_end
          cw_y = cw_y_end
          cw_dir = new_cw_dir
          cw_x_end = cw_x + dirs[cw_dir][0] * side
          cw_y_end = cw_y + dirs[cw_dir][1] * side
          new_cw_dir = cw_heading(cw_x_end, cw_y_end)
          if cw_x == ccw_x and cw_y == ccw_y: # If CW and CCW cursors meet up, 2nd pass is done
            return
        # Skip CCW cursor over already processed edges
        while has_been_plotted(ccw_x, ccw_y, ccw_x_end, ccw_y_end):
          ccw_x = ccw_x_end
          ccw_y = ccw_y_end
          ccw_dir = new_ccw_dir
          ccw_x_end = ccw_x + dirs[ccw_dir][0] * side
          ccw_y_end = ccw_y + dirs[ccw_dir][1] * side
          new_ccw_dir = ccw_heading(ccw_x_end, ccw_y_end)
          if cw_x == ccw_x and cw_y == ccw_y: # CW and CCW cursors meet up?
            return

      # We found a new edge to stitch up.
      print(f'Edge {cw_x}x{cw_y}->{cw_x_end}x{cw_y_end} maps to edge {ccw_x}x{ccw_y}->{ccw_x_end}x{ccw_y_end}')

      # Draw the common edges with the same ascii letters
      # (from inside this loop you would generate the walk mapping (x,y,heading) -> (new_x, new_y, new_heading)
      # for traveling
      for i in range(side+1):
        x = cw_x + dirs[cw_dir][0]*i
        y = cw_y + dirs[cw_dir][1]*i
        plot(x, y, chr(ch_small) if i < side/2 else chr(ch_large)) # First half gets lowercase chars
        x = ccw_x + dirs[ccw_dir][0]*i
        y = ccw_y + dirs[ccw_dir][1]*i
        plot(x, y, chr(ch_small) if i < side/2 else chr(ch_large)) # Draw second half in uppercase chars

      # Remember that this edge has now been traversed, to avoid redoing it in the second pass
      plotted_edges += [(cw_x, cw_y, cw_x_end, cw_y_end), (ccw_x, ccw_y, ccw_x_end, ccw_y_end)]

      ch_small += 1
      ch_large += 1

      # 1st pass: if both cursors come to an external corner at the same time (i.e. both corners
      # will rotate), this stitching run finishes here, and we'll move to the next internal corner.
      # (second pass ignores this logic)
      if pass_number == 1 and new_cw_dir != cw_dir and new_ccw_dir != ccw_dir:
        break

      # Retire old CW/CCW cursors and replace them with the ones for next iteration
      cw_x = cw_x_end
      cw_y = cw_y_end
      cw_dir = new_cw_dir
      ccw_x = ccw_x_end
      ccw_y = ccw_y_end
      ccw_dir = new_ccw_dir

      if pass_number == 2: # Second pass only needs to process starting from one arbitrary corner
        break

# Kick off the actual algorithm run in two passes
fill_corners(1)
# Run the second pass to resolve the corner case of 11th shape, see details at https://youtu.be/qWgLdNFYDDo
# For the AoC problem this can be skipped, if problem input is not this special case
fill_corners(2)

# Print out the stitched map
for y in range(len(outmap)):
  s = ''
  for x in range(len(outmap[0])):
    s += outmap[y][x]
  print(s)

## shape1.txt
            ......
            ......
            ......
            ......
            ......
            ......
........................
........................
........................
........................
........................
........................
            ......
            ......
            ......
            ......
            ......
            ......

move instructions

## shape10.txt
                  ......
                  ......
                  ......
                  ......
                  ......
                  ......
........................
........................
........................
........................
........................
........................
                  ......
                  ......
                  ......
                  ......
                  ......
                  ......

move instructions

## shape11.txt
............
............
............
............
............
............
      ............
      ............
      ............
      ............
      ............
      ............
            ............
            ............
            ............
            ............
            ............
            ............

move instructions

## shape2.txt
      ......
      ......
      ......
      ......
      ......
      ......
........................
........................
........................
........................
........................
........................
......
......
......
......
......
......

move instructions

## shape3.txt
            ......
            ......
            ......
            ......
            ......
            ......
........................
........................
........................
........................
........................
........................
      ......
      ......
      ......
      ......
      ......
      ......

move instructions

## shape4.txt
                  ......
                  ......
                  ......
                  ......
                  ......
                  ......
........................
........................
........................
........................
........................
........................
......
......
......
......
......
......

move instructions

## shape5.txt
                  ......
                  ......
                  ......
                  ......
                  ......
                  ......
........................
........................
........................
........................
........................
........................
      ......
      ......
      ......
      ......
      ......
      ......

move instructions

## shape6.txt
..................
..................
..................
..................
..................
..................
            ..................
            ..................
            ..................
            ..................
            ..................
            ..................

move instructions

## shape7.txt
............
............
............
............
............
............
      ..................
      ..................
      ..................
      ..................
      ..................
      ..................
            ......
            ......
            ......
            ......
            ......
            ......

move instructions

## shape8.txt
............
............
............
............
............
............
      ..................
      ..................
      ..................
      ..................
      ..................
      ..................
                  ......
                  ......
                  ......
                  ......
                  ......
                  ......

move instructions

## shape9.txt
            ......
            ......
            ......
            ......
            ......
            ......
..................
..................
..................
..................
..................
..................
            ............
            ............
            ............
            ............
            ............
            ............

move instructions
	# Usage: python cube_folding.py input.txt
	import math, sys

	lines = open(sys.argv[1] if len(sys.argv) > 1 else 'input.txt', 'r').read().split('\n')

	# Remove instructions line from input
	lines = lines[:-1]
	if len(lines[-1]) == 0: lines.pop() # Remove possible empty line between map and instructions

	# Compute cube surface area
	area = sum(len(x.strip()) for x in lines)
	print('Surface area of cube:', area)

	# Compute individual side length
	side = int(math.sqrt(area/6))
	print('Side length:', side)

	# Calculate 2D map size
	height = len(lines)
	print('Height:', height)
	width = max([len(x) for x in lines])
	print('Width:', width)

	# Returns character on the map at x,y
	def get(x,y):
	if x < 0 or y < 0 or y >= len(lines) or x >= len(lines[y]):
	return ' '
	return lines[y][x]

	# Returns 1 if given coordinate falls outside a cube edge
	def is_outside(x, y):
	if get(x, y) == ' ':
	return 1
	return 0

	# Find all the internal corners in this shape
	# Internal corners can be identified by looking at neighboring 2x2 shapes and finding where exactly
	# three of the positions are inside the map, and one is outside
	inner_corners = []
	for y in range(height-1):
	s = ''
	for x in range(width-1):
	s += get(x,y)
	count = is_outside(x, y) + is_outside(x+1, y) + is_outside(x, y+1) + is_outside(x+1, y+1)
	if count == 1:
	inner_corners += [(x,y)]
	print(s)

	print('Shape has internal corners at:')
	print(str(inner_corners))
	print('\n')

	dirs = [(1,0), (0,1), (-1,0), (0,-1)] # Given a heading 0-3, which way would we travel? (same convention as problem input)

	# Finds on the contours of the 2D map the heading that the edge is winding. This is done by compressing the
	# four inside/outside states of a 2x2 block into a bitmask, and indexing an array to look up the clockwise heading
	def cw_heading(x,y):
	kind = is_outside(x,y) \| (is_outside(x+1,y) << 1) \| (is_outside(x,y+1) << 2) \| (is_outside(x+1,y+1)<<3)
	heading = [-1, 3, 0, 0, 2, 3, -1, 0, 1, -1, 1, 1, 2, 3, 2, -1][kind]
	assert heading >= 0
	return heading

	# Same as above, but CCW winding. -1 values in the array are for cases that cannot occur.
	def ccw_heading(x,y):
	kind = is_outside(x,y) \| (is_outside(x+1,y) << 1) \| (is_outside(x,y+1) << 2) \| (is_outside(x+1,y+1)<<3)
	heading = [-1, 2, 3, 2, 1, 1, -1, 1, 0, -1, 3, 2, 0, 0, 3, -1][kind]
	assert heading >= 0
	return heading

	# paint the winding of the edges. Outmap receives the ascii art picture. N.b. outmap
	# is expanded by one to top and left to allow for the ascii drawing to expand outside
	# the cube edges for better visuals.
	outmap = Matrix = [[get(x-1,y-1) for x in range(width+1)] for y in range(height+1)]

	ch_small = ord('a') # Draw edges with A, B, C, etc.
	ch_large = ord('A')

	# Draws a character on the output map
	def plot(x, y, ch):
	x += 1
	y += 1
	if x >= 0 and y >= 0 and x < len(outmap[0]) and y < len(outmap): outmap[y][x] = ch

	# Tracks which cube edges we have traversed in 1st pass of the algorithm, to avoid redoing
	# them in the 2nd pass
	plotted_edges = []

	# Tests if a given cube edge has already been traversed
	def has_been_plotted(sx, sy, ex, ey):
	return (sx, sy, ex, ey) in plotted_edges or (ex, ey, sx, sy) in plotted_edges

	# The main body of the algorithm, pass_number=1 or 2
	def fill_corners(pass_number):
	global ch_small, ch_large, plotted_edges
	# Stitch edges of the cube, starting at each internal corner in turn
	for x, y in inner_corners:
	# Start CW and CCW winding cursors initially at the same internal corners
	cw_x = x
	cw_y = y
	cw_dir = cw_heading(x, y) # Look at the 2x2 neighborhood of the corner to see which heading the cursor should have
	ccw_x = x
	ccw_y = y
	ccw_dir = ccw_heading(x, y) # Same for CCW cursor

	while True:
	# Travel CW and CCW cursors one cube edge forward
	cw_x_end = cw_x + dirs[cw_dir][0] * side
	cw_y_end = cw_y + dirs[cw_dir][1] * side
	ccw_x_end = ccw_x + dirs[ccw_dir][0] * side
	ccw_y_end = ccw_y + dirs[ccw_dir][1] * side
	new_cw_dir = cw_heading(cw_x_end, cw_y_end)
	new_ccw_dir = ccw_heading(ccw_x_end, ccw_y_end)

	if pass_number == 2: # 2nd pass should skip over cube edges that have already been processed in 1st pass
	# Skip CW cursor over already processed edges
	while has_been_plotted(cw_x, cw_y, cw_x_end, cw_y_end):
	cw_x = cw_x_end
	cw_y = cw_y_end
	cw_dir = new_cw_dir
	cw_x_end = cw_x + dirs[cw_dir][0] * side
	cw_y_end = cw_y + dirs[cw_dir][1] * side
	new_cw_dir = cw_heading(cw_x_end, cw_y_end)
	if cw_x == ccw_x and cw_y == ccw_y: # If CW and CCW cursors meet up, 2nd pass is done
	return
	# Skip CCW cursor over already processed edges
	while has_been_plotted(ccw_x, ccw_y, ccw_x_end, ccw_y_end):
	ccw_x = ccw_x_end
	ccw_y = ccw_y_end
	ccw_dir = new_ccw_dir
	ccw_x_end = ccw_x + dirs[ccw_dir][0] * side
	ccw_y_end = ccw_y + dirs[ccw_dir][1] * side
	new_ccw_dir = ccw_heading(ccw_x_end, ccw_y_end)
	if cw_x == ccw_x and cw_y == ccw_y: # CW and CCW cursors meet up?
	return

	# We found a new edge to stitch up.
	print(f'Edge {cw_x}x{cw_y}->{cw_x_end}x{cw_y_end} maps to edge {ccw_x}x{ccw_y}->{ccw_x_end}x{ccw_y_end}')

	# Draw the common edges with the same ascii letters
	# (from inside this loop you would generate the walk mapping (x,y,heading) -> (new_x, new_y, new_heading)
	# for traveling
	for i in range(side+1):
	x = cw_x + dirs[cw_dir][0]*i
	y = cw_y + dirs[cw_dir][1]*i
	plot(x, y, chr(ch_small) if i < side/2 else chr(ch_large)) # First half gets lowercase chars
	x = ccw_x + dirs[ccw_dir][0]*i
	y = ccw_y + dirs[ccw_dir][1]*i
	plot(x, y, chr(ch_small) if i < side/2 else chr(ch_large)) # Draw second half in uppercase chars

	# Remember that this edge has now been traversed, to avoid redoing it in the second pass
	plotted_edges += [(cw_x, cw_y, cw_x_end, cw_y_end), (ccw_x, ccw_y, ccw_x_end, ccw_y_end)]

	ch_small += 1
	ch_large += 1

	# 1st pass: if both cursors come to an external corner at the same time (i.e. both corners
	# will rotate), this stitching run finishes here, and we'll move to the next internal corner.
	# (second pass ignores this logic)
	if pass_number == 1 and new_cw_dir != cw_dir and new_ccw_dir != ccw_dir:
	break

	# Retire old CW/CCW cursors and replace them with the ones for next iteration
	cw_x = cw_x_end
	cw_y = cw_y_end
	cw_dir = new_cw_dir
	ccw_x = ccw_x_end
	ccw_y = ccw_y_end
	ccw_dir = new_ccw_dir

	if pass_number == 2: # Second pass only needs to process starting from one arbitrary corner
	break

	# Kick off the actual algorithm run in two passes
	fill_corners(1)
	# Run the second pass to resolve the corner case of 11th shape, see details at https://youtu.be/qWgLdNFYDDo
	# For the AoC problem this can be skipped, if problem input is not this special case
	fill_corners(2)

	# Print out the stitched map
	for y in range(len(outmap)):
	s = ''
	for x in range(len(outmap[0])):
	s += outmap[y][x]
	print(s)
	......
	......
	......
	......
	......
	......
	........................
	........................
	........................
	........................
	........................
	........................
	......
	......
	......
	......
	......
	......

	move instructions
	............
	............
	............
	............
	............
	............
	............
	............
	............
	............
	............
	............
	............
	............
	............
	............
	............
	............

	move instructions
	..................
	..................
	..................
	..................
	..................
	..................
	..................
	..................
	..................
	..................
	..................
	..................

	move instructions