News for hackers. Stuff that matters.
Re:Data structures and algorithms I actually used while work... by tzs on Wednesday July 15, 2020 @09:40AM (#23845050)
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.$$

There are no comments on this comment yet.