Code

3 files changed, 148 insertions, 0 deletions

diff --git a/naive.py b/naive.py
new file mode 100644
index 0000000..5f9b0fc
--- /dev/null
+++ b/naive.py
@@ -0,0 +1,47 @@
+cubes = [
+    tuple(int(n) for n in line.strip().split(","))
+    for line in open("input").readlines()
+]
+
+
+def neighbors(cube):
+    x, y, z = cube
+    return {(x + 1, y, z), (x - 1, y, z), (x, y + 1, z), (x, y - 1, z), (x, y, z + 1), (x, y, z - 1)}
+
+
+n = 0
+for cube in cubes:
+    for neighbor in neighbors(cube):
+        if neighbor not in cubes:
+            n += 1
+print(n)
+
+xmax = max(x for x, _, _ in cubes) + 1
+xmin = min(x for x, _, _ in cubes) - 1
+ymax = max(y for _, y, _ in cubes) + 1
+ymin = min(y for _, y, _ in cubes) - 1
+zmax = max(z for _, _, z in cubes) + 1
+zmin = min(z for _, _, z in cubes) - 1
+
+
+def in_boundary(cube):
+    x, y, z = cube
+    return xmin <= x <= xmax and ymin <= y <= ymax and zmin <= z <= zmax
+
+
+n = 0  # result
+visited = set(cubes)
+queue = [(xmax, ymax, zmax)]
+while queue:
+    cube = queue.pop(0)
+    for neighbor in neighbors(cube):
+        if not in_boundary(neighbor):
+            continue
+        if neighbor in cubes:
+            n += 1
+        if neighbor in visited:
+            continue
+        visited.add(neighbor)
+        queue.append(neighbor)
+
+print(n)
diff --git a/solution.dyalog b/solution.dyalog
new file mode 100644
index 0000000..7958b28
--- /dev/null
+++ b/solution.dyalog
@@ -0,0 +1,48 @@
+⎕IO←0
+]box on
+
+⍝ Part 1
+cubes←⍎¨⊃⎕NGET'input'1
+movements←{⍵,-⍵}↓(3 3⍴4↑1)
+sides←,cubes∘.+movements
+≢sides~cubes
+
+⍝ Part 2
+mins←(↑⌊/cubes)-1 1 1
+maxs←(↑⌈/cubes)+1 1 1
+in_boundary←{0≡+/((⍵<mins),(⍵>maxs))}
+count←0
+cubes{ ⍝ https://dfns.dyalog.com/n_bfs.htm
+	0=≢⍵:count
+	head←1↑⍵ ⋄ tail←1↓⍵
+	neighbors←movements+¨head
+	next←{(in_boundary¨⍵)/⍵}neighbors
+	count⊢←count+(+/{(↓⍵)∊cubes}¨neighbors)
+	(⍺,head)∇((tail∪next)~⍺)
+}↓maxs
+
+⍝ search visualization
+_←⎕ED 'grid'
+visualize←{
+	grid⊢←(maxs+1 1 1)⍴' '
+	cubes{ ⍝ https://dfns.dyalog.com/n_bfs.htm
+		0=≢⍵:count
+		head←1↑⍵ ⋄ tail←1↓⍵
+		grid[|head]⊢←'O'
+		_←⎕DL .001
+		grid[|head]⊢←'X'
+		neighbors←movements+¨head
+		next←{(in_boundary¨⍵)/⍵}neighbors
+		count⊢←count+(+/{(↓⍵)∊cubes}¨neighbors)
+		(⍺,head)∇((tail∪next)~⍺)
+	}↓maxs
+}
+
+⍝ layer visualization
+_←⎕ED 'layergrid'
+render←{
+    {
+        layergrid⊢←⍵
+        _←⎕DL 0.3
+    }¨↓↓grid
+}
diff --git a/translation.py b/translation.py
new file mode 100644
index 0000000..32d2028
--- /dev/null
+++ b/translation.py
@@ -0,0 +1,53 @@
+import sys
+import numpy as np
+import functools
+
+sys.setrecursionlimit(100000)
+
+# Part 1
+# cubes←⍎¨⊃⎕NGET'input'1
+cubes = [eval(f"({line})") for line in open("input").readlines()]
+
+# movements←{⍵,-⍵}↓(3 3⍴4↑1)
+movements = (lambda w: np.vstack([w, -w]))(np.identity(3, dtype=int))
+
+# sides←,cubes∘.+movements
+sides = [tuple(c + m) for c in cubes for m in movements]
+
+# ≢sides~cubes
+print(sum(1 for side in sides if side not in cubes))
+
+# Part 2
+# mins←(↑⌊/cubes)-1 1 1
+mins = tuple(min(c) - 1 for c in zip(*cubes))
+# maxs←(↑⌈/cubes)+1 1 1
+maxs = tuple(max(c) + 1 for c in zip(*cubes))
+# in_boundary←{0≡+/((⍵<mins),(⍵>maxs))}
+in_boundary = lambda c: 0 == functools.reduce(
+    lambda a, b: a + b,
+    (int(c[i] < mins[i] or c[i] > maxs[i]) for i in range(3)),
+    0,
+)
+# count←0
+count = 0
+
+
+def rec(left, right):
+    global count
+    # 0=≢⍵:count
+    if not right:
+        return count
+    # head←1↑⍵ ⋄ tail←1↓⍵
+    head, tail = right[0], right[1:]
+    # neighbors←movements+¨head
+    neighbors = [tuple(head + m) for m in movements]
+    # next←{(in_boundary¨⍵)/⍵}neighbors
+    next = set(filter(in_boundary, neighbors))
+    # count⊢←count+(+/{(↓⍵)∊cubes}¨neighbors)
+    count += sum((n in cubes) for n in neighbors)
+    # (⍺,head)∇((tail∪next)~⍺)
+    return rec(left | set([head]), list((set(tail) | next) - left))
+
+
+# cubes{...}↓maxs
+print(rec(set(cubes), [maxs]))