Talk:Josephus problem

From Rosetta Code

Perl 6 Why do you start with prisoner 2 ??? Walterpachl 09:28, 15 November 2012 (UTC)

Isn't prisoner 2 the third prisoner, 0 being the first, and 1 being the second? --Grondilu 10:28, 15 November 2012 (UTC)
Thanks. I was misled by Scala (which should then be corrected Walterpachl 11:41, 15 November 2012 (UTC)

failings of languages not working with other languages

I don't feel that the criticism of REXX version 2 (mentioned in REXX version 1) not working for ooRexx serves any constructive purpose.   Rexx version 2 was written for Classic REXX (and indeed, was entered for REXX, not ooRexx);   ooRexx is a different language with different syntactic rules.   If this is agreeable, then there will be no need to criticize ooRexx programs that don't work with Classic REXXes,   C programs that don't work with C++,   BASIC programs that don't work with Run BASIC, etc.   Pointing out that a language won't work for another language has no useful purpose here, that's why there are different language entries (even among the same "language"),   using the least common denominator of statements may not reflect the richness or extensions of a language, those differences were created/implemented for some useful purpose.   There is no need to state that one program language won't work with a different program language, that observation should be obvious. -- Gerard Schildberger (talk) 05:29, 9 May 2013 (UTC)

For some reason category oorexx diverts to category REXX as if someone else has taken the decision to treat them alike. One moment... ...this was done here. Maybe you could leave a note for a chat with ShinTakezou? --Paddy3118 (talk) 06:06, 9 May 2013 (UTC)
To me and many others ooRexx *IS* not only a Rexx++ as you may call it but also a valid (classic) Rexx interpreter. Minor syntactic "glitches" as I would call them have been removed from the language definition by the ANSII REXX Committee. I tried to document all the little differences somewhere.

See the extensive discussion at http://rosettacode.org/wiki/Rosetta_Code:Village_Pump/Dialects#REXX.2C_ooRexx.2C_and_others

This is the first I've ever heard that many others think that ooRexx is a (valid) Classic REXX interpreter.   (Note that some IBM documents refer to standard REXX instead of Classic REXX).   I was always under the impression that all (if not most) REXXes which weren't object oriented (oRexx, and later, ooRexx), they later called Classic REXXes.   Note that those REXXes weren't called Classic until object-oriented REXXes were introduced.   Whereas oRexx and ooRexx may interpret most Classic REXXes correctly, that implies that some Classic REXXes won't/can't be interpreted/executed correctly/successfully.   I applaud the attempt at documenting the little differences, but the bigger differences are much more important to document.   Any attempt at grading these differences, no matter how small, just diminishes the importance of those differences.   What is important is that the programs will execute differently (and most probably show different or even incorrect results).   It is these differences (and enhancements) that make oRexx and ooRexx "not Classic":   notably the treatment of stems and stemmed variables: Classic REXX treats them as variables, oRexx and ooRexx treat them as objects.   Sometimes this is a very subtle (and almost imperceptible syntactically) difference, but the execution (evaluation of the expression) is markedly different.   Another sharp dividing line is the use of -- as the start of in line comments (not a part of Classic REXX, but Regina REXX has introduced it in release 3.4).   A = --B   is a valid Classic REXX statement, as unary operators are permitted.   [The use of multiple unary operators often come up with the use of the INTERPRET instruction (most often with "calculator"-type programs or those programs that allow the user to enter algebraic expressions such as for the truth table and the 24 game on Rosetta code), or with computer generated statements as with the 24 game/solve on Rosetta Code.   The use of in line comments may or may not be allowed in Regina REXX, depending upon which options are in effect, and/or which version of Regina REXX is being used.   Please don't think that I'm attempting to grade the differences or assign levels of importance to various incompatibilities, I'm not an expert in all the differences between Classic REXX and the object-oriented REXXes.   Another topic would be the limitiations of the various REXX interpreters;   I've not marked any REXX (program) examples as incorrect (if they wouldn't work on some REXXes);   some of these would be the use of long clauses, the use of some gylphs, the use of newer BIFs (built-in functions) and/or enhancement to some BIFs, etc. -- Gerard Schildberger (talk) 00:05, 10 May 2013 (UTC)
From this essay I gather 2 points:
Can you please give an example where the different implementation of stems does make a difference?
I thought that -- introduces a LINE comment. I AM SURPRISED that interpret 'x=3--1' gives x the value 3! Since I hardly ever use Interpret, I did not come across this.
I am really eager to learn and then know; I am not interested in fighting. Adding these incompatibilities to the list I (and others) collected would help a lot. --Walterpachl (talk) 10:12, 10 May 2013 (UTC)

I shall remove the "criticism right now. My words were meant to help other users. Yet I DO insist that Rexx programs that don't use the ++, i.e., the oo features, do have their proper place in the REXX category and only those that do (use them) should and do appear under ooRexx. --Walterpachl (talk) 07:42, 9 May 2013 (UTC)

What about those programs that use ooRexx enhancements, but not object-orientated (++) features?   Especially language constructs that no Classic REXX accept?   (Of course, if you think that ooRexx is a Classic Rexx, then this argument would be moot).   Should novices be expected to see a REXX program (in the REXX section) on Rosetta Code and then try to use a Classic REXX interpter and expect it to work?   This is one major reason that I pushed for a distinct oRexx and ooRexx section.   At that time, NetRexx already had its own section. -- Gerard Schildberger (talk) 00:05, 10 May 2013 (UTC)
I don't use any of the added features in my published programs - and you very often add their private implementation to your programs when needed. If you find that any of 'my' programs don't work on your REXXes, please let me/us know. I am ready to correct/improve them. I AM grateful when you point out logic errors I made as in this very task. NetRexx, by the way. is entirely different story. As to PL/I I took the effort of translating some of the REXX programs to that other beautiful language I know by heart. --Walterpachl (talk) 10:12, 10 May 2013 (UTC)
Is there anyone else interested in this particular language topic and could they voice their

opinion(s)? Thanks. --Walterpachl (talk) 07:59, 9 May 2013 (UTC)

I don't know REXX and its versions, but it seems that if this has been debated before and their is no resolution as yet then may I suggest that REXX ooREXX and netREXX etc be treated as separate languages the way the BASICs are? With separate Category: pages that might want to add that the other versions should be checked for compatability notices. If someone knows for example, that an ooREXX solution works for REXX then maybe they could add that as a note in the ooREXX solution. The idea being to have the REXXs have solutions where it would become common for people to add notes on what happened when they tried it on another version of REXX.
It may not have been obvious, but ooRexx and one NetRexx (example) programs were moved to their respective sections.   In that sense, the issue has been partly solved, if not by segregation only as viewed by looking at the example programs to see if they used object-oriented (++) features.   This didn't address the underlying problem of use none-classic REXX constructs for Classic REXX, however.   It seems to have come down to what is a Classic REXX interpreter? -- Gerard Schildberger (talk) 00:05, 10 May 2013 (UTC)
If it is possible to modify one version to work on multiple versions - and you check that it does; then this should be noted too.
Just a thought. --Paddy3118 (talk) 14:11, 9 May 2013 (UTC)
Yes, it's possible to modify REXX programs to execute under REXX, PL/I, Fortran, IBM assembler, and ooRexx.   It would be a fun and amusing exercise, but not practical   (kinda like programming in HQ9+, Brainf***, Befunge, or Whitespace).   Just to make clear what I meant, I meant the program would not be changed, the same version would execute as is under REXX, PL/I, Fortran, IBM assembler, and ooRexx.   Three main concerns:   one has to think in several languages (and know each of their limitations),   and have access to each of those compilers/interpreters, and take the time to test each of them.   I have access to seven "common" REXXes plus almost all flavors of Regina REXX, and it takes a lot just to check those versions out.   Indeed, three of them are too much trouble to test.   Another would be to think what statements are in common and not use those REXX statements that can't be (of won't be) acceptable in another language (and even if in the same language, if you catch my humor).   I don't program in that mode, it's too restrictive   (and as the ole joke goes, nobody's paying me enough).   I have never worked at a shop that said: "go ahead and program for our IBM FORTRAN H compiler, but don't you use any FORTRAN statements that won't work on a CDC or Cray Fortran compiler".   I'm sure that there are circumstances where that isn't the case, but most programmers try to code the most efficient (and productively) for a specific compiler/interpreter (unless they are in the business of selling software instead of just using it).   The closest I've ever got to restrictive programming is to make sure that my programs worked on all of our sysplex's software, and they were, for the most part, mostly in sync.   This meant that the (IBM) REXX compiler couldn't be used (mostly) because it wasn't available everywhere. -- Gerard Schildberger (talk) 00:09, 10 May 2013 (UTC)
I am asking for programs that run unmodified on all versions and that is quite easy. REXX->PL/I and others I'd call translation! REXX->ooRexx is also a translation when I use new features in order to simplify the algorithm. --Walterpachl (talk) 08:44, 11 May 2013 (UTC)
The Rexx programs that carry my name should work on all REXXes ( I cannot test them on others since I don't have any other - I had TSO Rexx till 12/2012). Addition on 10 May; My dream / vision is that all programs shown under REXX should work on ALL REXX implementations unless otherwise marked (No, I won't mark your programs that way - it's only a dream). Those under ooRexx will, of course, only work with ooRexx (and not Roo as was noted recently - I CAN catch your humor) --Walterpachl (talk) 10:27, 10 May 2013 (UTC)
All that is needed to see if a REXX program works under a Classic REXX is to (simply) run/execute the REXX program under a Classic REXX interpreter.   That would solve your (above) problem of   it should work on all REXXes.   Just executing a REXX program under ooRexx doesn't mean that it works under Classic REXX as well.   This seems like an obvious and simple thing to do.   If you can't/won't use a Classic REXX interpreter and you just have ooRexx, then enter that program under the ooRexx section.   That will ensure that your program will run/execute correctly (verifiably) under the appropriate language section.     -- Gerard Schildberger (talk) 18:54, 27 June 2020 (UTC)

Many of GS's REXX programs won't work on ooRexx because they use the things I mentioned: $ etc. as variable names and x= instead of x="" for assignment of the null string. When I try one of these programs I make the necessary little changes (c/$/d/* * and add the "") and I am off (and learn a lot from them) I dare not alter these programs though on rosetta (In one instance Gerard did it). And as already said: I see the proper place for my Rexx programs that don't use oo under REXX and those that do under ooRexx. By the way, I suggest that you look a little into Rexx, if I may. It's one of the best languages! --Walterpachl (talk) 15:07, 9 May 2013 (UTC)

I was going to add a considered comment but I can't be bothered in reopening the Rexx/ooRexx religious war; life's too short. I choose to ignore this trite argument about what is and what isn't Rexx --Alansam (talk) 00:32, 10 May 2013 (UTC)

In calling these arguments trite is just belittling the differences and ignore the substance of the issue(s).   The issue (argument) about what is and what isn't Rexx is a strawman argument.   The issue is:   what is and isn't   Classic REXX.     -- Gerard Schildberger (talk) 18:54, 27 June 2020 (UTC)

Formulae hidden to most browsers by under-tested cosmetic edits at 17:36, 21 April 2016

Under-tested cosmetic edits made to the task page at 17:36, 21 April 2016, including the injection of spaces around expressions in <math> tags, have left some task description formulae completely invisible to all browsers which display the graphic file version of formulae rather than processing the MathML (this is, in fact, the majority of browsers). The MediaWiki processor does not currently expect such spaces, and generates syntactically ill-formed HTML if they are introduced. Other aspects of these cosmetic edits may further compound the problem. Hout (talk) 20:06, 22 September 2016 (UTC)

seconded- It's a severe nuisance! I removed one math beautification and can clearly see "k=3" :-)Walterpachl
There is certainly a lot of accidental damage to repair ... (See http://rosettacode.org/wiki/User_talk:Rdm#Names_of_tasks_still_affected )
FWIW it may not always be necessary to entirely remove the <math> tag. In most cases you can restore visibility by just removing the two redundant spaces – one at the start and one at the end of the <math> contents, which began to be injected when the cosmetics campaign first kicked off about 6 months ago. In this case for example, <big><math> k=3 </math></big> causes invisibility on most browsers, but <big><math>k=3</math></big> (redundant flanking space removed) returns the contents to visibility.
The editor who has been introducing these spaces for six months, unaware that they were causing formulae to vanish from most browsers, explained that he found <math> tags easier to read when these spaces were added. Removing them again is enough to fix about 80% of the cases. The remaining cases seem to need a deeper 'undo' of the well-intentioned but under-tested and accidentally destructive cosmetic edit. Hout (talk) 08:14, 23 September 2016 (UTC)
Visibility of equations restored by Paddy3118 on 28 Oct 2016 Hout (talk) 18:08, 28 October 2016 (UTC)
Unfortunately, the edit by Paddy3118 on 28 Oct 2016 to fix the math markup also removed the 6508 assembly entry, the Julia recursive entry and many other minor edits in other entries. I don't have time to go in and try to fix them right now, but am loath to just roll back his edit. :-( --Thundergnat (talk) 18:31, 28 October 2016 (UTC)
Ah ... thanks for the heads up, I'll take a look Hout (talk) 18:34, 28 October 2016 (UTC)
OK – I think that's fixed, I've restored the 6508 and Julia etc contributions inadvertently lost in Paddy3118's edit, but kept his repair of the task description formulae Hout (talk) 18:44, 28 October 2016 (UTC)
Thanks! --Thundergnat (talk) 18:55, 28 October 2016 (UTC)
Please accept my Apologies guys. --Paddy3118 (talk) 14:11, 31 October 2016 (UTC)
No problem – happens easily, and easily fixed. Hout (talk) 14:24, 31 October 2016 (UTC)

Categorisation of solutions

The task description only mentions one way of going about solving this problem, but from the solutions given it seem to me that there's at least six different ways to solve it. To help me understand these solutions, I'm trying to make a list of them and what languages show them off in a particularly clear way. Can anyone help me do this?

I've tried to read every solution so far, and it's my understanding that all of the following solutions exist:

  • Solution 1: Use a circular list. This is the solution typically found in the Lisp approaches. The Echo Lisp solution gives some helpful comments for this.
  • Solution 2: Use array rotation. The Ruby example keeps this short and sweet.
  • Solution 3: Use nested loops or if statements in a loop that are as good as nested loops. I think that the goal here is to replicate modular arithmetic. I didn't quite understand this until I saw the Kotlin and Lua solutions, but once I understood it became quite clear that this is a popular approach. REXX has a well-commented example and so does MATLAB. I also think that this is what AWK and the many solutions adapted from it have done, but I'm less sure.
  • Solution 4: Use recursion. I've not studied these solutions yet, but there are solutions in Erlang, Sidef and Julia that are clearly doing this. I suspect that the Emacs Lisp solution is similar.
  • Solution 5: Use modular arithmetic modulo the decreasing length of the circle. Python and Visual Basic .NET do a good job of showing how to do this while actually making the circle smaller. Rust shows how to do this without having to recalculate the length of the circle.
  • Solution 6: Use modular arithmetic, but treat the circle as if it is growing. This is very much a mathematician's solution, so it's no surprise that R makes it very concise. I think that Ring takes the same approach.


However, there are quite a lot of solutions that I can't understand. I have no idea what approach any of the following have taken. Have I missed a category or two? Or is it just that I can't read the syntax?

--ReeceGoding (talk) 13:02, 24 June 2020 (UTC)

The Factor solution is a simple fold/reduce. I'll use the example from the task where n = 41 and k = 3.
First, create a range of numbers from 1 to 41.
{ 1 2 3 ... 41 }
Use 0 as the first element for the fold/reduce.
{ 0 1 2 3 ... 41 }
Now we have a 0 and a 1 we need to do something with.
Add k (which is 3) to 0 so now we have 3 and 1.
{ 3 1 2 3 ... 41 }
Take 3 modulo 1 which is zero. This is the result that will be used in the next iteration of the fold/reduce.
{ 0 2 3 4 ... 41 }
Now we have 0 and 2. Add 3 to 0, which is 3. Take 3 modulo 2 which is 1.
{ 1 3 4 5 ... 41 }
Now we have 1 and 3. Add 3 to 1, which is 4. Take 4 modulo 3 which is 1.
{ 1 4 5 6 ... 41 }
etc. Now whichever remainder you end up with via this process is the answer. I didn't write this solution and I'm not familiar with the Josephus problem, so I'm not sure if this fits into one of the categories above. Having a look at R and Ring, it seems like the Factor solution is doing the same thing, only using a fold instead of a loop. I believe Racket is also using a fold in the same way as Factor. --Chunes (talk) 14:34, 24 June 2020 (UTC)
Thanks! That definitely sounds right. --ReeceGoding (talk) 16:13, 24 June 2020 (UTC)
I think that you might also have explained what the jq solution is doing. --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 Haskell, Python[4 aka learning iter in python], REXX[version 2] as the last three I cannot get (plus Befunge, J, and Mathematica which I am quite happy to ignore). This is my analysis so far:

1. skipping: 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: 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: 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: 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: AutoHotkey, C#, C++, Frink, Formulae, Java (both), JavaScript[2], Julia[2], Kotlin, Lua, NanoQuery, Nim, Objeck, Oforth, Processing, Python[1], R[2], 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: 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: ALGOL 68, ANSI Standard BASIC, AppleScript[1,3(!!)], BASIC, Batch File, C (but not ULL), Common Lisp[1], Factor, Forth, 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: 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]!!! (well, just the survivor part is, I should say) Have now posted all 8 algorithms in Phix, just to annoy everyone (they are all quite short). --Pete Lomax (talk) 03:21, 27 June 2020 (UTC)

The Forth solution is another iterative mod maths solution like R, except it uses hard coded input. (Less stack shuffling that way?) --Chunes (talk) 04:07, 27 June 2020 (UTC)
Very impressive! Studying this will keep me busy for days.--ReeceGoding (talk) 18:16, 27 June 2020 (UTC)
In the new R solution, I found it odd that you wrote
It is 1-indexed, meaning that we will have a tough time using most solutions that exploit modular arithmetic.
(1) it is just below the existing R "Growing circle solution" which uses modular arithmetic, and
(2) Phix has 1-based indexes and it didn't bother me. Anyway, I added R[2] to "contractalot". --Pete Lomax (talk) 20:43, 30 June 2020 (UTC)
The previous solution is part of the reason why I said "most". As for 1-indexing causing problems, it's mostly to do with how you constantly have to account for modular arithmetic wanting to make things that your language wants to be 1 in to 0. It can be worked around, but it's yet another difficulty in an already hard problem.--ReeceGoding (talk) 21:35, 30 June 2020 (UTC)
(Modular arithmetic. Excuse me as I nab this for another reason supporting languages needing to start list indices from 0 😊) --Paddy3118 (talk) 23:16, 30 June 2020 (UTC)
Retrieved from "https://rosettacode.org/wiki/Talk:Josephus_problem?oldid=221915"