Josephus — Bonus: A Gema Solution

Gema is an unusual text-processing language based on pattern-matching. Gema has no data structures except strings, so this implementation uses recursively defined patterns that perform textual substitutions on a string representation of the rebels.

init — construct string of rebels

!!! initialize the list of rebels
init:\A1\Z=1
init:\A<D>\Z=@init{@sub{$1;1}} $1

@init{1}
1
@init{4}
1 2 3 4
@init{40}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

kill — kill the M'th rebel

I implement modular arithmetic by rotating the string.

!!! kill the $m'th (x him) and rotate him to the end
kill:1 <D> *=* x
kill:<D> x *=@kill{$1 * x}
kill:<D> <D> *=@kill{@sub{$1;1} * $2}

@init{4}
1 2 3 4
@kill{3 @init{4}}
4 1 2 x
@kill{3 @kill{3 @init{4}}}
x 4 1 x
@kill{3 @kill{3 @kill{3 @init{4}}}}
1 x x x

josephus — kill until solved

josephus:* <D>* <D>*=@josephus{@kill{$m $0}}
josephus:*<D>*=$2

@set{m;3}
@josephus{@init{4}}
1
@josephus{@init{40}}
28

Complete Program

ARGV:\N-n\n<D>\n=@set{n;$1}
ARGV:\N-m\n<D>\n=@set{m;$1}

\A=@josephus{@init{$n}}\n@end{}
?=

init:\A1\Z=1
init:\A<D>\Z=@init{@sub{$1;1}} $1

kill:1 <D> *=* x
kill:<D> x *=@kill{$1 * x}
kill:<D> <D> *=@kill{@sub{$1;1} * $2}
josephus:* <D>* <D>*=@josephus{@kill{$m $0}}
josephus:*<D>*=$2

Running the Program

$ gema -f josephus-1.gema -n 40 -m 3
28
$ gema -f josephus-1.gema -n 41 -m 3
31

Commented Source

! original version: no -all or -graphic

!!! main routine
ARGV:\N-n\n<D>\n=@set{n;$1}
ARGV:\N-m\n<D>\n=@set{m;$1}

! invoke josephus at beginning of input
\A=@josephus{@init{$n}}\n@end{}
! discard any extraneous input bytes
?=

!!! initialize the list of rebels
init:\A1\Z=1
init:\A<D>\Z=@init{@sub{$1;1}} $1

!!! kill the $m'th (x him) and rotate him to the end
! killing the first guy is trivial
kill:1 <D> *=* x
! if the first guy is already dead, rotate him to the end
! and then kill again without decrementing the kill count
kill:<D> x *=@kill{$1 * x}
! otherwise, rotate the front guy with killing him, and
! then recursively kill $m-1 more guys
kill:<D> <D> *=@kill{@sub{$1;1} * $2}
!!! solve the josephus problem; we're done when only one guy is left alive
! if there are at least two guys left alive, we kill one and then recur
josephus:* <D>* <D>*=@josephus{@kill{$m $0}}
! if there is only one guy left alive, return him!
josephus:*<D>*=$2