Skip to content

Instantly share code, notes, and snippets.

@akinomyoga

akinomyoga/README.md

Last active February 9, 2023 14:11
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save akinomyoga/4599a4df82351f40dce53653f7745762 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save akinomyoga/4599a4df82351f40dce53653f7745762 to your computer and use it in GitHub Desktop.
Download ZIP
Efficient Conway's Game of Life in Bash
Raw
README.md

Conway's Game of Life in Bash script

I wrote a Bash script using the full capability of Bash features. I was motivated by @ytaki0801 posting a script of Conway's Game of Life in POSIX sh on Twitter. They also have implementations in other languages.

I was afraid that the resulting program would run very slowly, so I chose an implementation by the bit vector representing the states of 64 cells per integer. The Bash implementation turned out to be much faster than I expected, but it should be noted that this good performance owes to the choice of the algorithm but not to the Bash features.

  • conway.bash is the first version. Bash 5.2 is required.
  • conway.bash43 is a slightly modified version that works in Bash 4.3 and above.
  • conway-v2.bash is a performance-improved version.
Raw
conway-v2.bash
#!/usr/bin/env bash
# Copyright 2023, Koichi Murase <[email protected]>.
#
# usage: You can run this script in a terminal. Send Ctrl+C (SIGINT)
# to stop the program.
((BASH_VERSINFO[0]*100+BASH_VERSINFO[1]>=502)) || { echo 'bash >= 5.2 is required.' >&2; exit 1; }
IFS=,
set -f
shopt -s checkwinsize patsub_replacement &>/dev/null
printf '\e[?47h\e[?25l\e7\e[;40;97m'
trap "printf '\e[m\e8\e[?47l\e[?25h'" 0
trap '(:);p=init' WINCH
kill -WINCH "$$"
init() {
((X=(COLUMNS+63)/64,A=X*LINES,S=COLUMNS-(X-1)*64-1))
local LM='0' Lc='~0'
((S)) && LM='-1<<'$((64-S)) Lc='~('$LM')'
local -a buff=()
for ((i=0;i<A;i++)); do
((l=!(i%X),r=!((i+1)%X)))
buff+=(
"b=a[$i]"
"c=b<<1&${LM[!r]:-~1}|a[$((i+1-r*X))]>>$((r?S:63))&${Lc[!r]:-1}"
"d=b>>1&~(1<<63)|a[$((i-1+l*X))]<<$((l?S:63))&1<<63"
"x$i=b^c^d" "y$i=c&d|b&(c|d)")
done
for ((i=0;i<A;i++)); do
buff+=(
"b=x$i" "c=x$(((i-X+A)%A))" "d=x$(((i+X)%A))"
"e=y$i" "f=y$(((i-X+A)%A))" "g=y$(((i+X)%A))" "h=c&d|b&(c|d)"
"m=b^c^d"
"n=e^f^g^h"
"t=m&n&~((e|f)&(g|h))"
"u=~(m|n|e&f&g&h)&(e|f|g|h)"
"a[$i]=t|u&a[$i]")
done
eval "step=\"\${buff[*]}\""
p='((step))'
printf -v R '%*s' "$((X-1))"; R=${R//?/%s}%.$((S+1))s
local -a H=({' ','*'}{' ','*'}{' ','*'}{' ','*'})
eval "$(printf 'H%x=${H[%d]};' {0..15}{,})"
RAND64='RANDOM^RANDOM<<15^RANDOM<<30^RANDOM<<45^RANDOM<<60'
eval "a=(); let 'a['{0..$((A-1))}']=RAND64'"
}
let j=196 D=0 'C[D++]=j+='{6,-36,1,-6,36,-1}{,,,,} j=0
while :; do
eval "$p"
printf -v s '%016x,' "${a[@]}"
eval "s=${s//[!,]/'$H'&}"
printf %s $'\e[?2026h\e[H\e[38;5;'"${C[j++/100%D]}m"
printf "$R" $s
printf %s $'\e[H\e[?2026l'
done
Raw
conway.bash
#!/usr/bin/env bash
# Copyright 2023, Koichi Murase <[email protected]>.
# Press Ctrl+C to stop!
((BASH_VERSINFO[0]*100+BASH_VERSINFO[1]>=502)) || { echo 'bash >= 5.2 is required.' >&2; exit 1; }
shopt -s checkwinsize patsub_replacement
type -P tput &>/dev/null && { tput xenl || tput xn; } &>/dev/null; ((xenl_margin=!!$?))
printf '\e[?47h\e[?25l\e7\e[;40;97m'
trap "printf '\e[m\e8\e[?47l\e[?25h'" 0
trap '(:);p=init' WINCH
kill -WINCH "$$"
init() {
((X=(COLUMNS+63)/64,A=X*LINES,S=COLUMNS-(X-1)*64-1,LM=S==0?0:-1<<64-S,RM=~(1<<63)))
R=$'\e[?2026h\e[H\e[38;5;${C[j++/100%D]}m'
for ((y=0;y<LINES;y++)); do
R=$R'${s:'$((y*X*64))':'$((COLUMNS-(y==LINES-1?xenl_margin:0)))'}'
done
R=$R$'\e[H\e[?2026l'
eval "a=(); let 'a['{0..$((A-1))}']=RAND64'"
p="let i={0..$((A-1))},ADD3 i={0..$((A-1))},NEXT"
}
RAND64='RANDOM^RANDOM<<15^RANDOM<<30^RANDOM<<45^RANDOM<<60'
ADD3='
l=(i+1)%X?(a[i]<<1&~1|a[i+1]>>63&1):(a[i]<<1&LM|a[i+1-X]>>S&~LM),
r=i%X?(a[i]>>1&RM|a[i-1]<<63&~RM):(a[i]>>1&RM|a[i-1+X]<<S&~RM),
b[i]=a[i]^l^r,
e[i]=l&r|a[i]&(l|r)'
NEXT='
c=b[(i-X+A)%A],d=b[(i+X)%A],
g=e[(i-X+A)%A],h=e[(i+X)%A],
f=c&d|b[i]&(c|d),
m=b[i]^c^d,
n=e[i]^f^g^h,
t=m&n&~((e[i]|f)&(g|h)),
u=~(m|n|e[i]&f&g&h)&(e[i]|f|g|h),
a[i]=t|u&a[i]'
H=({' ','*'}{' ','*'}{' ','*'}{' ','*'})
let j=196 D=0 'C[D++]=j+='{6,-36,1,-6,36,-1}{,,,,} j=0
while :; do
eval "$p"
printf -v s %016x "${a[@]}"
eval "s=${s//?/'${H[0x'&']}'}"
eval "printf %s \"$R\""
done
Raw
conway.bash43
#!/usr/bin/env bash
# Copyright 2023, Koichi Murase <[email protected]>.
# Press Ctrl+C to stop!
((BASH_VERSINFO[0]*100+BASH_VERSINFO[1]>=403)) || { echo 'bash >= 4.3 is required.' >&2; exit 1; }
shopt -s checkwinsize
type -P tput &>/dev/null && { tput xenl || tput xn; } &>/dev/null; ((xenl_margin=!!$?))
printf '\e[?47h\e[?25l\e7\e[;40;97m'
trap "printf '\e[m\e8\e[?47l\e[?25h'" 0
trap '(:);p=init' WINCH
kill -WINCH "$$"
init() {
((X=(COLUMNS+63)/64,A=X*LINES,S=COLUMNS-(X-1)*64-1,LM=S==0?0:-1<<64-S,RM=~(1<<63)))
R=$'\e[?2026h\e[H\e[38;5;${C[j++/100%D]}m'
for ((y=0;y<LINES;y++)); do
R=$R'${s:'$((y*X*64))':'$((COLUMNS-(y==LINES-1?xenl_margin:0)))'}'
done
R=$R$'\e[H\e[?2026l'
eval "a=(); let 'a['{0..$((A-1))}']=RAND64'"
p="let i={0..$((A-1))},ADD3 i={0..$((A-1))},NEXT"
}
RAND64='RANDOM^RANDOM<<15^RANDOM<<30^RANDOM<<45^RANDOM<<60'
ADD3='
l=(i+1)%X?(a[i]<<1&~1|a[i+1]>>63&1):(a[i]<<1&LM|a[i+1-X]>>S&~LM),
r=i%X?(a[i]>>1&RM|a[i-1]<<63&~RM):(a[i]>>1&RM|a[i-1+X]<<S&~RM),
b[i]=a[i]^l^r,
e[i]=l&r|a[i]&(l|r)'
NEXT='
c=b[(i-X+A)%A],d=b[(i+X)%A],
g=e[(i-X+A)%A],h=e[(i+X)%A],
f=c&d|b[i]&(c|d),
m=b[i]^c^d,
n=e[i]^f^g^h,
t=m&n&~((e[i]|f)&(g|h)),
u=~(m|n|e[i]&f&g&h)&(e[i]|f|g|h),
a[i]=t|u&a[i]'
H=({' ','*'}{' ','*'}{' ','*'}{' ','*'})
let j=196 D=0 'C[D++]=j+='{6,-36,1,-6,36,-1}{,,,,} j=0
while :; do
eval "$p"
printf -v s %016x "${a[@]}"
for h in {0..9} {a..f}; do s=${s//$h/${H[0x$h]}}; done
eval "printf %s \"$R\""
done
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment