94 lines
2.8 KiB
Nim
94 lines
2.8 KiB
Nim
import math, sequtils, strutils
|
|
|
|
type
|
|
Bit = 0..1
|
|
BitMatrix = seq[seq[Bit]] # Two-dimensional array of 0/1.
|
|
Neighbors = array[2..9, Bit] # Neighbor values.
|
|
|
|
const Symbols = [Bit(0): '.', Bit(1): '#']
|
|
|
|
|
|
func toBitMatrix(s: openArray[string]): BitMatrix =
|
|
## Convert an array of 01 strings into a BitMatrix.
|
|
for row in s:
|
|
assert row.allCharsInSet({'0', '1'})
|
|
result.add row.mapIt(Bit(ord(it) - ord('0')))
|
|
|
|
|
|
proc `$`(m: BitMatrix): string =
|
|
## Return the string representation of a BitMatrix.
|
|
for row in m:
|
|
echo row.mapIt(Symbols[it]).join()
|
|
|
|
# Templates to allow using double indexing.
|
|
template `[]`(m: BitMatrix; i, j: Natural): Bit = m[i][j]
|
|
template `[]=`(m: var BitMatrix; i, j: Natural; val: Bit) = m[i][j] = val
|
|
|
|
|
|
func neighbors(m: BitMatrix; i, j: int): Neighbors =
|
|
## Return the array of neighbors.
|
|
[m[i-1, j], m[i-1, j+1], m[i, j+1], m[i+1, j+1],
|
|
m[i+1, j], m[i+1, j-1], m[i, j-1], m[i-1, j-1]]
|
|
|
|
func transitions(p: Neighbors): int =
|
|
## Return the numbers of transitions from P2 to P9.
|
|
for (i, j) in [(2, 3), (3, 4), (4, 5), (5, 6),
|
|
(6, 7), (7, 8), (8, 9), (9, 2)]:
|
|
result += ord(p[i] == 0 and p[j] == 1)
|
|
|
|
func thinned(m: BitMatrix): BitMatrix =
|
|
## Return a thinned version of "m".
|
|
const Pair1 = [2, 8]
|
|
const Pair2 = [4, 6]
|
|
let rowMax = m.high
|
|
let colMax = m[0].high
|
|
result = m
|
|
|
|
while true:
|
|
var changed = false
|
|
|
|
for step in 1..2:
|
|
let (p1, p2) = if step == 1: (Pair1, Pair2) else: (Pair2, Pair1)
|
|
var m = result
|
|
for i in 1..<rowMax:
|
|
for j in 1..<colMax:
|
|
|
|
# Check criteria.
|
|
if m[i, j] == 0: # criterion 0.
|
|
continue
|
|
let p = m.neighbors(i, j)
|
|
if sum(p) notin 2..6: # criterion 1.
|
|
continue
|
|
if transitions(p) != 1: # criterion 2.
|
|
continue
|
|
if p[p1[0]] + p[p2[0]] + p[p2[1]] == 3 or # criterion 3.
|
|
p[p1[1]] + p[p2[0]] + p[p2[1]] == 3: # criterion 4.
|
|
continue
|
|
|
|
# All criteria satisfied. Store a 0 in "result".
|
|
result[i, j] = 0
|
|
changed = true
|
|
|
|
if not changed: break
|
|
|
|
|
|
when isMainModule:
|
|
|
|
const Input = ["00000000000000000000000000000000",
|
|
"01111111110000000111111110000000",
|
|
"01110001111000001111001111000000",
|
|
"01110000111000001110000111000000",
|
|
"01110001111000001110000000000000",
|
|
"01111111110000001110000000000000",
|
|
"01110111100000001110000111000000",
|
|
"01110011110011101111001111011100",
|
|
"01110001111011100111111110011100",
|
|
"00000000000000000000000000000000"]
|
|
|
|
let input = Input.toBitMatrix()
|
|
let output = input.thinned()
|
|
echo "Input image:"
|
|
echo input
|
|
echo()
|
|
echo "Output image:"
|
|
echo output
|