Anonymous user
Talk:Josephus problem: Difference between revisions
m
→Categorisation of solutions: Indices.
m (→Categorisation of solutions: Indices.) |
|||
| (27 intermediate revisions by 7 users not shown) | |||
Line 45:
:::::: 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. --[[User:Walterpachl|Walterpachl]] ([[User talk:Walterpachl|talk]]) 08:44, 11 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. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk: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)
Line 52 ⟶ 54:
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 --[[User:Alansam|Alansam]] ([[User talk: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 '''<u>Classic</u> REXX'''. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk: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 ==
Line 59 ⟶ 62:
:: 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
: Visibility of equations restored by [[User:Paddy3118|Paddy3118]] on 28 Oct 2016 [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 18:08, 28 October 2016 (UTC)
:: Unfortunately, the edit by [[User:Paddy3118|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. :-( --[[User:Thundergnat|Thundergnat]] ([[User talk:Thundergnat|talk]]) 18:31, 28 October 2016 (UTC)
::: Ah ... thanks for the heads up, I'll take a look [[User:Hout|Hout]] ([[User talk: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 [[User:Paddy3118|Paddy3118]]'s edit, but kept his repair of the task description formulae [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 18:44, 28 October 2016 (UTC)
:::: Thanks! --[[User:Thundergnat|Thundergnat]] ([[User talk:Thundergnat|talk]]) 18:55, 28 October 2016 (UTC)
:::Please accept my Apologies guys. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 14:11, 31 October 2016 (UTC)
:::: No problem – happens easily, and easily fixed. [[User:Hout|Hout]] ([[User talk: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 [https://rosettacode.org/wiki/Josephus_problem#EchoLisp Echo Lisp] solution gives some helpful comments for this.
*Solution 2: Use array rotation. The [https://rosettacode.org/wiki/Josephus_problem#Ruby 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 [https://rosettacode.org/wiki/Josephus_problem#Kotlin Kotlin] and [https://rosettacode.org/wiki/Josephus_problem#Lua Lua] solutions, but once I understood it became quite clear that this is a popular approach. [https://rosettacode.org/wiki/Josephus_problem#REXX REXX] has a well-commented example and so does [https://rosettacode.org/wiki/Josephus_problem#MATLAB MATLAB]. I also think that this is what [https://rosettacode.org/wiki/Josephus_problem#AWK 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 [https://rosettacode.org/wiki/Josephus_problem#Erlang Erlang], [https://rosettacode.org/wiki/Josephus_problem#Sidef Sidef] and [https://rosettacode.org/wiki/Josephus_problem#Julia Julia] that are clearly doing this. I suspect that the [https://rosettacode.org/wiki/Josephus_problem#Emacs_Lisp Emacs Lisp] solution is similar.
*Solution 5: Use modular arithmetic modulo the decreasing length of the circle. [https://rosettacode.org/wiki/Josephus_problem#Python Python] and [https://rosettacode.org/wiki/Josephus_problem#Visual_Basic_.NET Visual Basic .NET] do a good job of showing how to do this while actually making the circle smaller. [https://rosettacode.org/wiki/Josephus_problem#Rust 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 [https://rosettacode.org/wiki/Josephus_problem#R R] makes it very concise. I think that [https://rosettacode.org/wiki/Josephus_problem#Ring 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?
*[https://rosettacode.org/wiki/Josephus_problem#AutoHotkey AutoHotkey]
*[https://rosettacode.org/wiki/Josephus_problem#C.23 C#]
*[https://rosettacode.org/wiki/Josephus_problem#Elixir Elixir]
*[https://rosettacode.org/wiki/Josephus_problem#Factor Factor]
*[https://rosettacode.org/wiki/Josephus_problem#Fortran Fotran]
*[https://rosettacode.org/wiki/Josephus_problem#Haskell Haskell]
*[https://rosettacode.org/wiki/Josephus_problem#JavaScript JavaScript]
*[https://rosettacode.org/wiki/Josephus_problem#jq jq]
*[https://rosettacode.org/wiki/Josephus_problem#REBOL REBOL]
*[https://rosettacode.org/wiki/Josephus_problem#Scala Scala]
--[[User:ReeceGoding|ReeceGoding]] ([[User talk: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.
: <code>{ 1 2 3 ... 41 }</code>
: Use 0 as the first element for the fold/reduce.
: <code>{ 0 1 2 3 ... 41 }</code>
: 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.
: <code>{ 3 1 2 3 ... 41 }</code>
: Take 3 modulo 1 which is zero. This is the result that will be used in the next iteration of the fold/reduce.
: <code>{ 0 2 3 4 ... 41 }</code>
: Now we have 0 and 2. Add 3 to 0, which is 3. Take 3 modulo 2 which is 1.
: <code>{ 1 3 4 5 ... 41 }</code>
: Now we have 1 and 3. Add 3 to 1, which is 4. Take 4 modulo 3 which is 1.
: <code>{ 1 4 5 6 ... 41 }</code>
: 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. --[[User:Chunes|Chunes]] ([[User talk:Chunes|talk]]) 14:34, 24 June 2020 (UTC)
::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 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<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], 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<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, 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<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]!!! (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). --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|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?) --[[User:Chunes|Chunes]] ([[User talk:Chunes|talk]]) 04:07, 27 June 2020 (UTC)
:Very impressive! Studying this will keep me busy for days.--[[User:ReeceGoding|ReeceGoding]] ([[User talk: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". --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|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.--[[User:ReeceGoding|ReeceGoding]] ([[User talk: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 😊) --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 23:16, 30 June 2020 (UTC)
| |||