Talk:Josephus problem: Difference between revisions
→Categorisation of solutions
ReeceGoding (talk | contribs) No edit summary |
|||
Line 122:
::Thanks! That definitely sounds right. --[[User:ReeceGoding|ReeceGoding]] ([[User talk:ReeceGoding|talk]]) 16:13, 24 June 2020 (UTC)
::I think that you might also have explained what the jq solution is doing. --[[User:ReeceGoding|ReeceGoding]] ([[User talk:ReeceGoding|talk]]) 16:41, 24 June 2020 (UTC)
This certainly piqued my interest! Factor notes above will help me too. I have spent the day scouring the entries and am left with Forth, Haskell, Python[4 aka learning iter in python], REXX[version 2] as the last four I cannot get (plus Befunge, J, and Mathematica which I am quite happy to ignore). This is my analysis so far:
;1. skipping<nowiki>:</nowiki> 360 assembly, 6502 Assembly, AWK, EchoLisp, ERRE, MATLAB, NetRexx, Phix, PHP, PL/I, REXX[version 1].
:Method: all prisoners stay where they are, executioner walks round and round, skipping over more & more dead bodies (slowest of the lot, by quite some margin)
;2. linked list<nowiki>:</nowiki> AArch64 Assembly, Ada, ARM Assembly, Common Lisp[2, probably], Fortran, JavaScript[1] (albeit dbl-lnk), Python[3].
:Method: like skipping, all prisoners stay where they are, but the executioner uses the links to speed things up a bit.
;3. sliding queue<nowiki>:</nowiki> Clojure, Crystal, D (both), Eiffel, Elixir, Erlang, friendly interactive shell, Go, jq, Perl, PowerShell, PureBasic (albeit one at a time), Raku, REBOL, Ruby, Scala, Sidef[1], Tcl.
:Method: all skipped prisoners rejoin the end of the queue which sidles left, executioner stays put until the queue gets too short.
;4. contractacycle<nowiki>:</nowiki> AppleScript[2], Groovy
:Method: executioner walks along killing every k'th prisoner; queue contracts to remove gaps while he walks back. (reverts to one at a time once queue too small, as next)
;5. contractalot<nowiki>:</nowiki> AutoHotkey, C#, C++, Frink, Formulae, Java (both), JavaScript[2], Julia[2], Kotlin, Lua, NanoQuery, Nim, Objeck, Oforth, Processing, Python[1], Rust, Seed7, Swift, VBScript, Vedit, VisualBasic.NET, XPL0, zkl.
:Method: executioner walks round and round, queue contracts after every kill. (This is a mix of your 3 and 5, but not MATLAB or REXX or AWK)
;6. recursive<nowiki>:</nowiki> Emacs Lisp, Icon, Julia[1], PARI/GP, PicoLisp (less the optms.n), Sidef[2] (Your 4, but not Erlang)
:Method: recursive mod maths madness - only handles the lone survivor case.
;7. iterative<nowiki>:</nowiki> ALGOL 68, ANSI Standard BASIC, AppleScript[1,3(!!)], BASIC, Batch File, C (but not ULL), Common Lisp[1], Factor, FreeBASIC, Modula-2, Python[2], R, Racket, Ring, SequenceL, ZX Spectrum Basic
:Method: iterative mod maths madness - but hey, it will be extremely fast. Unlike recursive, it can also deliver >1 survivor, one at a time. (Your 6)
;8. iterative2<nowiki>:</nowiki> Icon[2]
:Method: What do you call a deer with no eyes? ... no idea
:I will be quite shocked if there are no glaring errors in the above. I was gobsmacked to realise that AppleScript[3] (aka composition of pure functions) is actually the exact same algorithm as AppleScript[1]! When I'm done I'll post all 8 algorithms in Phix, just to annoy everyone (they are all quite short). --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 03:21, 27 June 2020 (UTC)
| |||