3 ms·
I sometimes suspect that everything is really just a sorting problem. For example, here is a shell script that takes an input file consisting of lines of the f
by tzs 6y ago
I sometimes suspect that everything is really just a sorting problem.
For example, here is a shell script that takes an input file consisting of lines of the form
X Y
where X and Y are integers representing the X and Y coordinates of live cells in a Conway's Life grid, and outputs the next generation in the same format. It runs in O(n log n) where n is the number of live cells, and it is really just sorting.
> alive.$$
while read cells
do
echo $cells >> alive.$$
set x $cells
x=$2
y=$3
echo $x $((y-1))
echo $x $((y+1))
echo $((x-1)) $((y-1))
echo $((x-1)) $y
echo $((x-1)) $((y+1))
echo $((x+1)) $((y-1))
echo $((x+1)) $y
echo $((x+1)) $((y+1))
done | sort | uniq -c > neighbors.$$
grep '^ *3' < neighbors.$$ | sed -e 's/^ *[0-9].//'
grep '^ *2' < neighbors.$$ | sed -e 's/^ *[0-9].//' > has2.$$
sort alive.$$ -o alive.$$
comm -12 has2.$$ alive.$$
rm has2.$$ neighbors.$$ alive.$$