Problema de Josefo (contando)

29

O desafio

Escreva uma função que leva dois inteiros positivos n e k como argumentos e retorna o número da última pessoa remanescente de n após a contagem a cada k pessoa -ésimo.

Este é um desafio do código-golfe, portanto o código mais curto vence.

O problema

n pessoas (numeradas de 1 a n ) estão em pé em círculo e cada k- ésimo é contado até que uma única pessoa permaneça (consulte o artigo correspondente da wikipedia ). Determine o número dessa última pessoa.

Por exemplo, para k = 3, duas pessoas serão puladas e a terceira será contada. Ou seja, para n = 7, os números serão contados na ordem 3 6 2 7 5 1 (em detalhes 1 2 3 4 5 6 7 1 2 4 5 7 1 4 5 1 4 1 4 ) e, portanto, a resposta é 4 .

Exemplos

J(7,1) = 7      // people are counted out in order 1 2 3 4 5 6 [7]
J(7,2) = 7      // people are counted out in order 2 4 6 1 5 3 [7]
J(7,3) = 4      // see above
J(7,11) = 1
J(77,8) = 1
J(123,12) = 21
Howard
fonte

Respostas:

5

GolfScript, 17 bytes

{{@+\)%}+\,*)}:f;

Pega n kna pilha e deixa o resultado na pilha.

Dissecação

Isso usa a recorrência g(n,k) = (g(n-1,k) + k) % ncom g(1, k) = 0(conforme descrito no artigo da Wikipedia) com a recursão substituída por uma dobra.

{          # Function declaration
           # Stack: n k
  {        # Stack: g(i-1,k) i-1 k
    @+\)%  # Stack: g(i,k)
  }+       # Add, giving stack: n {k block}
  \,*      # Fold {k block} over [0 1 ... n-1]
  )        # Increment to move from 0-based to 1-based indexing
}:f;
Peter Taylor
fonte
Você pode adicionar uma explicação, por favor?
Sherlock9
@ Sherlock9, consegui descobrir o que estava fazendo, apesar de quase 3,5 anos se passaram. Quem disse que o GolfScript é somente leitura? ;)
Peter Taylor
Ahem. s / leitura / gravação /
Peter Taylor
Desculpe. Eu só comecei a aprender Golfscript há dois ou três dias e, toda vez que leio seu código, fiquei pensando que havia perdido alguma coisa. ... Ok, ainda estou perdendo alguma coisa, como fazer dobrar {k block}para [0..n-1]você g(0,k) 0 kcomeçar? Desculpe, se estou postando essas perguntas no lugar errado.
Sherlock9
@ Sherlock9, fold funciona em pares, então a primeira coisa que faz é avaliar 0 1 block. Muito convenientemente, isso acontece g(1, k) (2-1) block. Então está começando em g(1,k) 1vez de g(0,k) 0. Depois de executar o bloco, ele empurra o próximo item da matriz ( 2) e executa o bloco novamente etc.
Peter Taylor
14

Minsky Register Machine (25 estados sem interrupção)

Não é tecnicamente uma função, mas está em um paradigma de computação que não possui funções em si ...

Essa é uma pequena variação no caso de teste principal do meu primeiro desafio de interpretação de MRM : Problema de Josephus como máquina de registro de Minsky

Entrada em registros ne k; saída no registro r; assume-se que r=i=t=0na entrada. As duas primeiras instruções de interrupção são casos de erro.

Peter Taylor
fonte
Eu acho que você precisa ajustar sua máquina levemente. Se eu o leio corretamente, a saída é indexada a zero, não é?
219 Howard
Eu estava pensando de outra maneira: se k=1então r=0. Hmm, eu tenho que pensar sobre esta uma vez ...
Howard
Como eu li seu diagrama, ié simplesmente contar a partir 2de nquando ré o registro que acumula o resultado.
219 Howard
@ Howard, procurei os comentários que fiz quando escrevi isso pela primeira vez e você está certo. Ops. Agora corrigido (acredito - testará mais detalhadamente mais tarde).
Peter Taylor
7

Python, 36

Eu também usei a fórmula da wikipedia:

J=lambda n,k:n<2or(J(n-1,k)+k-1)%n+1

Exemplos:

>>> J(7,3)
4
>>> J(77,8)
1
>>> J(123,12)
21
grc
fonte
6

Mathematica, 38 36 bytes

Mesma fórmula da Wikipedia:

1~f~_=1
n_~f~k_:=Mod[f[n-1,k]+k,n,1]
Mr.Wizard
fonte
11
If[#<2,1,Mod[#0[#-1,#2]+#2,#,1]]&
Alephalpha # 7/15
5

C, 40 caracteres

Essa é basicamente a fórmula que o artigo da Wikipedia acima fornece:

j(n,k){return n>1?(j(n-1,k)+k-1)%n+1:1;}

Para variedade, aqui está uma implementação que realmente executa a simulação (99 caracteres):

j(n,k,c,i,r){char o[999];memset(o,1,n);for(c=k,i=0;r;++i)(c-=o[i%=n])||(o[i]=!r--,c=k);
return i;}
caixa de pão
fonte
4
Salvar um personagem: j(n,k){return--n?(j(n,k)+k-1)%-~n+1:1;}.
Ugoren
5

dc, 27 bytes

[d1-d1<glk+r%1+]dsg?1-skrxp

Usa a recorrência do artigo da Wikipedia. Explicação:

# comment shows what is on the stack and any other effect the instructions have
[   # n
d   # n, n
1-  # n-1, n
d   # n-1, n-1, n
1<g # g(n-1), n ; g is executed only if n > 1, conveniently g(1) = 1
lk+ # g(n-1)+(k-1), n; remember, k register holds k-1
r%  # g(n-1)+(k-1) mod n
1+  # (g(n-1)+(k-1) mod n)+1
]
dsg # code for g; code also stored in g
?   # read user input => k, n, code for g
1-  # k-1, n, code for g
sk  # n, code for g; k-1 stored in register k
r   # code for g, n
x   # g(n)
p   # prints g(n)
Geoff Reedy
fonte
4

J, 45 caracteres

j=.[:{.@{:]([:}.]|.~<:@[|~#@])^:(<:@#)>:@i.@[

Executa a simulação.

Como alternativa, usando a fórmula (31 caracteres):

j=.1:`(1+[|1-~]+<:@[$:])@.(1<[)

Espero que Howard não se importe de ter ajustado um pouco o formato de entrada para se adequar a um verbo diádico em J.

Uso:

   7 j 3
4
   123 j 12
21
Gareth
fonte
4

GolfScript, 32 24 bytes

:k;0:^;(,{))^k+\%:^;}/^)

Uso: espera que os dois parâmetros n e k estejam na pilha e deixe o valor de saída.

(obrigado a Peter Taylor por sugerir uma abordagem iterativa e muitas outras dicas)

A abordagem antiga (recursiva) de 32 caracteres:

{1$1>{1$(1$^1$(+2$%)}1if@@;;}:^;

Este é o meu primeiro GolfScript, então, por favor, deixe-me saber suas críticas.

Cristian Lupascu
fonte
11
1-tem opcode especial (. Da mesma forma 1+é ). Você não precisa usar caracteres alfabéticos para armazenamento; portanto, você pode usar, por exemplo, em ^vez de, Je não precisar de um espaço depois dele. Você tem muito mais programas $do que o habitual em um programa bem disputado: considere se você pode reduzi-los usando alguma combinação de \@..
21412 Peter Taylor
@ Petereteray Muito obrigado por essas ótimas dicas! É muito difícil entender todos os operadores do Golfscript e eu ignorei esses dois. Somente aplicando as duas primeiras sugestões, eu consigo diminuir o código em 5 caracteres. Também tentarei remover as $referências.
Cristian Lupascu
11
Além disso, a recursão não é realmente coisa do GolfScript. Tente virar e fazer um loop. Eu posso reduzi-lo para 19 caracteres (embora não testado) dessa maneira. Dica: desenrole a função gdo artigo da Wikipedia e use ,e /.
Peter Taylor
11
{,{\2$+\)%}*)\;}:f;Certifique-se de entender por que ele funciona;)
Peter Taylor
11
Um truque final: em vez de usar 2 caracteres para acessar kdentro do loop e mais 2 para descartá-lo no final, podemos puxá-lo para dentro usando +até 17 caracteres: {{@+\)%}+\,*)}:f;duvido que possa ser melhorado.
Peter Taylor
3

Groovy, 36 bytes

def j(n,k){n>1?(j(n-1,k)+k-1)%n+1:1}
Prince John Wesley
fonte
2

Haskell, 68

j n=q$cycle[0..n]
q l@(i:h:_)k|h/=i=q(drop(k-1)$filter(/=i)l)k|1>0=i

Faz a simulação real. Demonstração:

GHCi> j 7 1
7
GHCi> j 7 2
7
GHCi> j 7 3
4
GHCi> j 7 11
1
GHCi> j 77 8
1
GHCi> j 123 12
21

deixou de girar contra-relógio
fonte
2

Scala, 53 bytes

def?(n:Int,k:Int):Int=if(n<2)1 else(?(n-1,k)+k-1)%n+1
Prince John Wesley
fonte
1

C, 88 caracteres

Faz a simulação, não calcula a fórmula.
Muito mais longo que a fórmula, mas mais curto que a outra simulação C.

j(n,k){
    int i=0,c=k,r=n,*p=calloc(n,8);
    for(;p[i=i%n+1]||--c?1:--r?p[i]=c=k:0;);
    return i;
}

Notas:
1. Aloca memória e nunca libera.
2. Aloca em n*8vez de n*4, porque eu uso p[n]. Pode alocar (n+1)*4, mas são mais caracteres.

Ugoren
fonte
1

C ++, 166 bytes

Golfe:

#include<iostream>
#include <list>
int j(int n,int k){if(n>1){return(j(n-1,k)+k-1)%n+1;}else{return 1;}}
int main(){intn,k;std::cin>>n>>k;std::cout<<j(n,k);return 0;}

Ungolfed:

#include<iostream>
#include <list>
int j(int n,int k){
    if (n > 1){
        return (j(n-1,k)+k-1)%n+1;
    } else {
        return 1;
    }
}
int main()
{
    int n, k;
    std::cin>>n>>k;
    std::cout<<j(n,k);
    return 0;
}
Michelfrancis Bustillos
fonte
2
Você pode salvar bytes na Jfunção, usando o operador ternário.
Yytsi
intnna sua versão Golfed não irá compilar
Felipe Nardi Batista
você pode remover o espaço em#include <list>
Felipe Nardi Batista 24/10
1

J, 8 bytes

1&|.&.#:

       1&|.&.#: 10
    5

       1&|.&.#: 69
    11

        1&|.&.#: 123456
    115841

        1&|.&.#: 123245678901234567890x NB. x keeps input integral
    98917405212792722853

All credit to Roger Hui, co-inventor of J and all-round uber-genius
www.jsoftware.com for free j software across many platforms

Explanation
    (J works right-to-left)
     #:       convert input to binary
     &.       a&.b <=> perform b, perform a, perform reverse of b
     1&|.     rotate bitwise one bit left

So
    1&|.&.#: 10

    a. #:            convert input (10) TO binary -> 1 0 1 0
    b. 1&|.          rotate result 1 bit left -> 0 1 0 1
    c. due to the &. perform convert FROM binary -> 5 (answer)
Richard Donovan
fonte
11
Não é necessário receber duas entradas?
Erik the Outgolfer
1

Ruby, 39 bytes

def J(n,k)
n<2?1:(J(n-1,k)+k-1)%n+1
end

Versão em execução com casos de teste: http://ideone.com/pXOUc

Cristian Lupascu
fonte
1

Q, 34 bytes

f:{$[x=1;1;1+mod[;x]f[x-1;y]+y-1]}

Uso:

q)f .'(7 1;7 2;7 3;7 11;77 8;123 12)
7 7 4 1 1 21
tmartin
fonte
1

Ruby, 34 bytes

J=->n,k{n<2?1:(J(n-1,k)+k-1)%n+1}
Hauleth
fonte
0

Haskell, 29

Usando a fórmula da wikipedia.

1#_=1
n#k=mod((n-1)#k+k-1)n+1
alefalpha
fonte
0

JavaScript (ECMAScript 5), 48 bytes

Usando o ECMAScript 5, já que essa era a versão mais recente do JavaScript no momento em que essa pergunta foi feita.

function f(a,b){return a<2?1:(f(a-1,b)+b-1)%a+1}

Versão ES6 (não concorrente), 33 bytes

f=(a,b)=>a<2?1:(f(a-1,b)+b-1)%a+1

Explicação

Não há muito a dizer aqui. Estou apenas implementando a função que o artigo da Wikipedia me fornece.

Luke
fonte
0

05AB1E , 11 bytes

L[Dg#²<FÀ}¦

Experimente online!

L           # Range 1 .. n
 [Dg#       # Until the array has a length of 1:
     ²<F }  #   k - 1 times do:
        À   #     Rotate the array
          ¦ #   remove the first element
Riley
fonte
0

Oitavo , 82 bytes

Código

: j >r >r a:new ( a:push ) 1 r> loop ( r@ n:+ swap n:mod ) 0 a:reduce n:1+ rdrop ;

O SED (diagrama de efeito de pilha) é:n k -- m

Uso e explicação

O algoritmo usa uma matriz de números inteiros como este: se o valor das pessoas for 5, a matriz será [1,2,3,4,5]

: j \ n k -- m
    >r                               \ save k
    >r a:new ( a:push ) 1 r> loop    \ make array[1:n]
    ( r@ n:+ swap n:mod ) 0 a:reduce \ translation of recursive formula with folding using an array with values ranging from 1 to n
    n:1+                             \ increment to move from 0-based to 1-based indexing
    rdrop                            \ clean r-stack
;

ok> 7 1 j . cr
7
ok> 7 2 j . cr
7
ok> 7 3 j . cr
4
ok> 7 11 j . cr
1
ok> 77 8 j . cr
1
ok> 123 12 j . cr
21
Chaos Manor
fonte
0

J , 24 bytes

1+1{1([:|/\+)/@,.1|.!.0#

Experimente online!

Uma abordagem iterativa baseada na solução de programação dinâmica.

Explicação

1+1{1([:|/\+)/@,.1|.!.0#  Input: n (LHS), k (RHS)
                       #  Make n copies of k
                 1|.!.0   Shift left by 1 and fill with zero
    1          ,.         Interleave with 1
             /@           Reduce using
           +                Addition
        |/\                 Cumulative reduce using modulo
  1{                      Select value at index 1
1+                        Add 1
milhas
fonte
0

J , 19 bytes

1+(}:@|.^:({:@])i.)

Experimente online!

Como funciona

1+(}:@|.^:({:@])i.)   Left: k, Right: n
                i.    Generate [0..n-1]
        ^:            Repeat:
   }:@|.                Rotate left k items, and remove the last item
          ({:@])        n-1 (tail of [0..n-1]) times
1+                    Add one to make the result one-based
Bubbler
fonte
0

Japonês , 15 bytes

_é1-V Å}h[Uõ] Ì

Experimente online!

Um byte pode ser salvo pela indexação 0 k , mas, na verdade, não é um índice, então decidi contra isso.

Explicação:

         [Uõ]      :Starting with the array [1...n]
_      }h          :Repeat n-1 times:
 é1-V              : Rotate the array right 1-k times (i.e. rotate left k-1 times)
      Å            : Remove the new first element
              Ì    :Get the last value remaining
Kamil Drakari
fonte
0

Japonês -h, 10 bytes

õ
£=éVn1¹v

Tente

Shaggy
fonte
0

PowerShell, 56 bytes

param($n,$k)if($n-lt2){1}else{((.\f($n-1)$k)+$k-1)%$n+1}

Importante! O script se chama recursivamente. Então salve o script comof.ps1 arquivo no diretório atual. Além disso, você pode chamar uma variável de bloco de script em vez de arquivo de script (consulte o script de teste abaixo). Isso chama tem o mesmo comprimento.

Script de teste:

$f = {

param($n,$k)if($n-lt2){1}else{((&$f($n-1)$k)+$k-1)%$n+1}

}

@(
    ,(7, 1, 7)
    ,(7, 2, 7)
    ,(7, 3, 4)
    ,(7, 11, 1)
    ,(77, 8, 1)
    ,(123,12, 21)
) | % {
    $n,$k,$expected = $_
    $result = &$f $n $k
    "$($result-eq$expected): $result"
}

Saída:

True: 7
True: 7
True: 4
True: 1
True: 1
True: 21
confuso
fonte