Transparent Origami

Not a very interesting problem. Just an exercise in bug avoidance.

Problem statement: given a sequence of “folds” (horizontal or vertical lines) which mirror each point in ${\mathbb{Z}}^2$ (provide an equivalence relation), reduce a set of input points to their canonical equivalence class representation (smallest positive value or whatever).

Algorithmically I don’t think you can get around $\mathcal{O}(nk)$ with $n$ points and $k$ folds without doing some assumptions (i.e. that the points are bounded to be “small” or the folds coprime)? My first thought was we could do some modulus trick, but since the transformation changes depending on the original value, I’m not so sure that works.

So my low-effort solution is just:

aoc = __import__('aoc-common').aoc()
import sys
import numpy as np
import scipy.ndimage as ndi
import itertools as itt
import functools as fnt
import collections as coll
import re

text = aoc.input_text(13)
expr = re.compile('^fold along ([xy])=(\d+)', re.M)

# fuck it, we'll hard commit to input assumptions.
pts, folds = text.split('\n\n')
pts = np.array(pts.replace(',', '\n').split(), np.int64).reshape(-1, 2).T
folds = ((m.group(1), int(m.group(2))) for m in expr.finditer(folds))

# pts[0] are x-coords, pts[1] are y-coords.

def dofold(pts, axis, coord):
  axis = int(axis == 'y')
  pts[axis] = np.where(pts[axis] < coord, pts[axis], 2*coord - pts[axis])
  return np.unique(pts, axis=1)

pts = dofold(pts, *next(folds))

print(f'answer to part 1: {pts.shape[1]}')

for ax,c in folds:
  pts = dofold(pts, ax, c)

A = np.ones(tuple(np.max(pts, 1) + 1), 'u1') * 32
A[tuple(pts)] = ord('#')

# nah, fuck you AoC, I'm not going to do a visual ascii decoder.
answer2 = ...
print(f'answer to part 2: {answer2}')

for r in A.T:
  print(r.tobytes().decode())

In the end I just print out the points as ASCII art:

[franksh@moso aoc2021] python day13-transparent-origami.py 
answer to part 1: 607
answer to part 2: Ellipsis
 ##  ###  #### #    ###  #### #### #   
#  # #  #    # #    #  # #       # #   
#    #  #   #  #    #  # ###    #  #   
#    ###   #   #    ###  #     #   #   
#  # #    #    #    #    #    #    #   
 ##  #    #### #### #    #    #### ####