Wyzwanie
Napisz funkcję, która przyjmuje dwie dodatnie liczby całkowite n i k jako argumenty i zwraca liczbę ostatnich osób pozostających poza n po odliczeniu każdego k tej osoby.
To wyzwanie dla golfa, więc wygrywa najkrótszy kod.
Problem
n osób (ponumerowanych od 1 do n ) stoi w kręgu i każdy k- ty jest odliczany, aż pozostanie jedna osoba (patrz odpowiedni artykuł na Wikipedii ). Określ liczbę tej ostatniej osoby.
Np. Dla k = 3 dwie osoby zostaną pominięte, a trzecia zostanie odliczona. Tj. Dla n = 7 liczby będą odliczane w kolejności 3 6 2 7 5 1 (szczegółowo 1 2 3 4 5 6 7 1 2 4 5 7 1 4 5 1 4 1 4 ), a zatem odpowiedź wynosi 4 .
Przykłady
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
{k block}
przez[0..n-1]
Cig(0,k) 0 k
zacząć? Przepraszam, jeśli zamieszczam te pytania w niewłaściwym miejscu.0 1 block
. Bardzo wygodnie to się dziejeg(1, k) (2-1) block
. Więc zaczyna sięg(1,k) 1
raczej niżg(0,k) 0
. Następnie po wykonaniu bloku wypycha następny element z tablicy (2
) i wykonuje blok ponownie itp.Maszyna rejestru Minsky'ego (25 stanów bez zatrzymania)
Nie jest to technicznie funkcja, ale jest w paradygmacie obliczeniowym, który sam w sobie nie ma funkcji ...
Jest to niewielka zmiana w głównym przypadku testowym mojego pierwszego wyzwania interpretacyjnego MRM :
Wprowadzanie do rejestrów
n
ik
; wyjście w rejestrzer
; zakłada się, żer=i=t=0
przy wejściu. Pierwsze dwie instrukcje zatrzymania to przypadki błędów.źródło
k=1
takr=0
. Hmm, muszę jeszcze raz o tym pomyśleć ...i
jest po prostu licząc od2
celun
, gdyr
jest rejestrem, który gromadzi się na wynik.Python, 36
Użyłem również formuły z wikipedii:
Przykłady:
źródło
Mathematica,
3836 bajtówTa sama formuła Wikipedii:
źródło
If[#<2,1,Mod[#0[#-1,#2]+#2,#,1]]&
C, 40 znaków
Jest to właściwie tylko formuła, którą podaje powyższy link w Wikipedii:
Dla odmiany, oto implementacja, która faktycznie uruchamia symulację (99 znaków):
źródło
j(n,k){return--n?(j(n,k)+k-1)%-~n+1:1;}
.dc, 27 bajtów
Wykorzystuje wznowienie z artykułu z Wikipedii. Wyjaśnienie:
źródło
J, 45 znaków
Uruchamia symulację.
Alternatywnie, korzystając ze wzoru (31 znaków):
Mam nadzieję, że Howardowi nie przeszkadza, że nieznacznie dostosowałem format wejściowy, aby pasował do czasownika dyadycznego w J.
Stosowanie:
źródło
GolfScript,
3224 bajtyZastosowanie: Oczekuje, że dwa parametry n i k znajdą się na stosie i pozostawia wartość wyjściową.
(podziękowania dla Petera Taylora za zasugerowanie iteracyjnego podejścia i wiele innych wskazówek)
Stare (rekurencyjne) podejście 32 znaków:
To jest mój pierwszy GolfScript, więc daj mi znać, co krytykujesz.
źródło
1-
ma specjalny kod operacyjny(
. Podobnie1+
jest)
. Nie musisz używać znaków alfabetu do przechowywania, więc możesz użyć np.^
ZamiastJ
i nie potrzebujesz po nim spacji. Masz znacznie więcej$
niż zwykle w dobrze golfowym programie: zastanów się, czy możesz je zmniejszyć za pomocą kombinacji\@.
.$
odniesienia.g
z artykułu z Wikipedii oraz użyj,
i/
.{,{\2$+\)%}*)\;}:f;
Upewnij się, że rozumiesz, dlaczego to działa;)k
do pętli, a następnie 2 więcej, aby odrzucić ją na końcu, możemy wciągnąć ją do środka za pomocą,+
aby uzyskać do 17 znaków:{{@+\)%}+\,*)}:f;
Wątpię, że można to poprawić.R, 48
Uruchomiona wersja z przykładami: http://ideone.com/i7wae
źródło
Groovy, 36 bajtów
źródło
Haskell, 68
Czy rzeczywista symulacja. Demonstracja:
źródło
Scala, 53 bajty
źródło
C, 88 znaków
Wykonuje symulację, nie oblicza wzoru.
Znacznie dłużej niż formuła, ale krócej niż inne symulacje C.
Uwagi:
1. Przydziela pamięć i nigdy nie zwalnia.
2. Przydziela
n*8
zamiastn*4
, ponieważ używamp[n]
. Można przydzielić(n+1)*4
, ale to więcej znaków.źródło
C ++, 166 bajtów
Gra w golfa:
Nie golfowany:
źródło
J
funkcji, używając operatora trójskładnikowego.intn
w twojej wersji golfowej nie da się skompilować#include <list>
J, 8 bajtów
źródło
Rubin, 39 bajtów
Wersja uruchomiona z przypadkami testowymi: http://ideone.com/pXOUc
źródło
Q, 34 bajty
Stosowanie:
źródło
Rubinowy, 34 bajty
źródło
Haskell, 29
Korzystanie z formuły z wikipedii.
źródło
JavaScript (ECMAScript 5), 48 bajtów
Korzystanie z ECMAScript 5, ponieważ była to najnowsza wersja JavaScript w momencie zadawania tego pytania.
Wersja ES6 (niekonkurująca), 33 bajty
Wyjaśnienie
Nie ma tu wiele do powiedzenia. Właśnie wdrażam funkcję, którą daje mi artykuł z Wikipedii.
źródło
05AB1E , 11 bajtów
Wypróbuj online!
źródło
8 , 82 bajty
Kod
SED (diagram efektu stosu) to:
n k -- m
Użycie i wyjaśnienie
Algorytm wykorzystuje tablicę liczb całkowitych takich jak ta: jeśli wartość ludzi wynosi 5, tablica będzie wynosić [1,2,3,4,5]
źródło
J , 24 bajty
Wypróbuj online!
Iteracyjne podejście oparte na rozwiązaniu do programowania dynamicznego.
Wyjaśnienie
źródło
J , 19 bajtów
Wypróbuj online!
Jak to działa
źródło
Dart , 33 bajty
Wypróbuj online!
źródło
Japt , 15 bajtów
Wypróbuj online!
Bajt może być zapisany przez 0-indeksowanie k , ale tak naprawdę nie jest to indeks, więc postanowiłem tego .
Wyjaśnienie:
źródło
Japt
-h
, 10 bajtówSpróbuj
źródło
PowerShell, 56 bajtów
Ważny! Skrypt wywołuje się rekurencyjnie. Zapisz skrypt jako
f.ps1
plik w bieżącym katalogu. Możesz także wywołać zmienną blokową skryptu zamiast pliku skryptu (patrz skrypt testowy poniżej). Te połączenia mają tę samą długość.Skrypt testowy:
Wydajność:
źródło