4 ms·
As sad as it is, I get 90% of my algorithm work done with sorted arrays and binary search. Rarely I need more fancy stuff.
by nipxx 6y ago
As sad as it is, I get 90% of my algorithm work done with sorted arrays and binary search. Rarely I need more fancy stuff.
- tzs 6y agoI 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.$$