12

To wyzwanie dla gliniarzy i rabusiów . Wątek gliniarzy do tego wyzwania jest tutaj

Ciekawe pytanie do przemyślenia to:

Jeśli mam ciąg liczb, ile z nich muszę podać, zanim stanie się jasne, o jakiej sekwencji mówię?

Na przykład, jeśli chcę mówić o dodatnich liczbach całkowitych w kolejności od , mógłbym powiedzieć , ale czy to naprawdę wystarczy? $1$ $1,2,3, \dots$

Mam jeden sposób na udzielenie odpowiedzi na to pytanie i bycie golfistą. To wymaga golfa. Podano wystarczającą liczbę sekwencji, jeśli najkrótszy kod, który je tworzy, tworzy wszystkie warunki sekwencji. Jeśli myślimy o tym w kategoriach golfa kodu, oznacza to, że dostarczyłeś wystarczającą liczbę przypadków testowych, tak aby najkrótszy kod, który przechodzi przez przypadki testowe, wykonał pożądane zadanie.

Wyzwanie

To wyzwanie jest wyzwaniem dla gliniarzy i rabusiów . W którym gliniarze będą prezentować przypadki testowe, a złodzieje będą musieli znaleźć krótszy sposób na sfałszowanie przypadków testowych niż zamierzona sekwencja. Gliniarze przedstawią następujące rzeczy:

Fragment kodu, który przyjmuje dodatnią liczbę całkowitą jako dane wejściowe i tworzy liczbę całkowitą jako dane wyjściowe. Kod ten może mieć wartość zero lub jeden indeksowany, ale powinno być jasne, czym jest indeksowanie. Ten kod określi twoją sekwencję.
Wszelkie odpowiednie wymagania dotyczące platformy lub języka, które mogą mieć wpływ na wynik, na przykład rozmiar longinta.
Liczba wraz z pierwszymi członami sekwencji obliczonymi przez kod. Będą one działać jako „przypadki testowe”. $n$ $n$

Rabusie znajdą program w tym samym języku, który jest krótszy niż ten przedstawiony i przejdzie wszystkie przypadki testowe (produkuje takie same dane wyjściowe dla pierwszych danych wejściowych jak kod gliniarza). Kod rabusia musi również różnić się wyjściem z programu policjanta dla pewnej liczby większej niż . $n$ $n$

Punktacja

Rabusie zostaną punktowani w liczbie znalezionych pęknięć, przy czym im więcej pęknięć, tym lepiej. Odpowiedź można złamać ponownie, znajdując poprawną odpowiedź krótszą niż oryginalne pęknięcie. Jeśli odpowiedź zostanie złamana po raz drugi, punkt zostanie przyznany drugiemu crackerowi, a nie pierwszemu.

sequence cops-and-robbers

— Ad Hoc Garf Hunter
źródło

2

Czy nie pozwalamy rabusiom pokonać się nawzajem za złamanie odpowiedzi (tj. Najkrótszy crack w wygrywającym języku)

— fəˈnɛtɪk

@ fəˈnɛtɪk Sounds, dobrze, że to dodałem.

— Ad Hoc Garf Hunter

6

cQuents , odpowiedź Stephena , 3 bajty

z~$

Wypróbuj online!

Jak to działa

z     Last item in the sequence
 ~    Concat
  $   Current index

Wygląda sekwencji powinno być identyczne, ale to daje 12345678910do n = 10natomiast "::$daje 1234567891.

— Bubbler
źródło

5

JavaScript, odpowiedź fəˈnɛtɪk (17 bajtów)

x=>"11237"[x]||22

$x\ge 6$ undefined||22

Testowanie

let f=x=>"11237"[x]||22

for (x of [1,2,3,4,5,6,7]) {
  console.log(x + ' -> ' + f(x))
}

Rozwiń fragment kodu

Alternatywnie, wypróbuj online!

— Pan Xcoder
źródło

4

Haskell , odpowiedź Laikoni , 15 bajtów

b n=n*div(n+1)2

Wypróbuj online!

Zazwyczaj zwracałem uwagę na coś takiego w komentarzu, ale potem pomyślałem, że gliniarze i złodzieje są trochę bardziej poderżnięci.

To tylko odpowiedź BMO minus specjalny przypadek b 42. Ponieważ oryginał Laikoni przechodzi przez zmiennoprzecinkowy, nie jest to konieczne: po prostu znajdź liczbę wystarczająco dużą, aby podać w niej błędy zaokrąglania, ale nie dokładną Integerarytmetykę. Na przykład:

a 100000000000000000000000 = 4999999999999999580569600000000000000000000000
b 100000000000000000000000 = 5000000000000000000000000000000000000000000000

— Ørjan Johansen
źródło

Myślałem, że może to być możliwe (stąd napisałem, że można go przepisać dla wymaganych terminów), ale nie znalazłem wartości, dla której działa. Ładnie wykonane!

— ბიმო

4

Python 2 , odpowiedź xnora , 43 bajty

$n = 69$

f=lambda n,p=2:n<1or-~f(n-(~-2**p%p<2),p+1)

Wypróbuj online!

Kredyty

Ogromne uznanie dla tego cracku musi pochodzić od @ Mr.Xcodera, który jako pierwszy opublikował komentarz na temat możliwego ataku przy użyciu tej metody oraz do @PoonLevi, który znalazł 44-bajtowe rozwiązanie.

W jaki sposób?

Teoria

$p$ $a$ $p$

\begin{matrix} (1) & a^{p - 1} \equiv 1 (\mod p) \end{matrix}

$a^{p-1}\equiv 1 \pmod p\tag{1}$

W szczególności dla : $a=2$

2^{p - 1} \equiv 1 (\mod p)

$2^{p-1}\equiv 1 \pmod p$

Istnieje więc dodatnia liczba całkowita taka, że: $k$

2^{p - 1} = k p + 1

$2^{p-1}=kp+1$

Który prowadzi do:

2^{p} = 2 k p + 2

$2^p=2kp+2$

2^{p} - 1 = 2 k p + 1

$2^p-1=2kp+1$

\begin{matrix} (2) & 2^{p} - 1 \equiv 1 (\mod p) \end{matrix}

$2^p-1\equiv 1 \pmod p\tag{2}$

Ta ostatnia formuła jest tą, z której pochodzi kod Pythona i obecnie obowiązuje dla , mimo że nie jest względnie pierwsze. $p=2$ $2$

A teraz najważniejsze: odwrotność małego twierdzenia Fermata nie jest prawdziwa. Możemy mieć dla pewnej liczby złożonej . Takie liczby są nazywane pseudopierwszymi liczbami Fermata w celu . Pseudopierwsze Fermata do zasady 2 są również znane jako liczby Pouleta . $a^{n-1}\equiv 1 \pmod n$ $n$ $a$

Pierwszy pseudopierwszy Fermat do podstawy (lub pierwszy numer Pouleta) to , dla których mamy: $2$ $n = 341=11\times 31$

2^{341 - 1} \equiv 1 (\mod 341)

$2^{341-1}\equiv 1 \pmod{341}$

2^{341} - 1 \equiv 1 (\mod 341)

$2^{341}-1\equiv 1 \pmod{341}$

Oznacza to, że nasz algorytm zwróci zamiast oczekiwanej 69- ^tej liczby pierwszej . $341$ $347$

Realizacja

@PoonLevi znalazł następujące 44-bajtowe rozwiązanie, które jest bezpośrednio oparte na : $(2)$

f=lambda n,p=1:n and-~f(n-(~-2**p%p==1),p+1)

Używając <2zamiast ==1, zapisujemy 1 bajt, ale wprowadzamy do sekwencji, ponieważ : $1$ $2^1-1\equiv 0 \pmod 1$

f=lambda n,p=1:n and-~f(n-(~-2**p%p<2),p+1)

Wypróbuj online!

Zaczynając od , otrzymujemy oczekiwane warunki o 1, ponieważ wykonujemy jedną iterację mniej: $p=2$

f=lambda n,p=2:n and-~f(n-(~-2**p%p<2),p+1)

Wypróbuj online!

Ostatnią sztuczką jest użycie n<1orzamiast n and. Jest to tak samo długie, ale powoduje, że ostatnia iteracja zwraca True zamiast 0 , dlatego dodaje brakujące przesunięcie do każdego terminu.

— Arnauld
źródło

Gratulacje dla was wszystkich! To jest rozwiązanie, które miałem na myśli. Myślę, że to zabawne, że z motywacji wyzwania „Jeśli mam ciąg liczb, ile z nich muszę podać, zanim stanie się jasne, o której sekwencji mówię?”, Pierwszych 50 liczb pierwszych najwyraźniej nie wystarczy - kosmita grający w Pythona założyłby, że mówisz o innej sekwencji.

— xnor

@xnor Uwielbiam pomysł „obcego golfisty z Pythona”

— dylnan

3

Python 3 , crashoz , 45 bajtów

lambda n:int(60*math.sin(n/10-2))
import math

Wypróbuj online!

Wyrażenie x*60-x**3*10+x**5/2-x**7/84to szereg Taylora dla do wyrażenia , pomnożony przez 60. Jest to wystarczająco dokładne na użytych danych wejściowych, ale w przypadku wyższych wartości oba będą się rozchodzić w miarę, jak skrócone terminy stają się bardziej odpowiednie. $sin(x)$ $x^7$

— xnor
źródło

3

JavaScript (ES6), odpowiedź Arnaulda (10 bajtów)

n=>8*n*n|n

Wypróbuj online!

— ngn
źródło

2

Haskell , odpowiedź Laikoni , 26 22 bajtów

_{-4 bajty, nie używając infixdiv , dzięki Laikoni !}

b 42=0;b n=n*div(n+1)2

Wypróbuj online!

Wyjaśnienie

Dla termin można przepisać, ponieważ daje nam wystarczającą liczbę bajtów do dopasowania wzorca na co prowadzi do pęknięcia w obrębie 28 bajtów: $0 \leq n \leq 20$ ceiling(realToFrac n/2)div(n+1)2 $n > 20$

b 42=0

— ბიმო
źródło

Ach, nie myślałem o tym. Mam inne podejście, które prowadzi do pęknięcia 20 bajtów, na wypadek, gdybyś chciał trochę więcej łamigłówek. Również ((n+1)`div`2)-> div(n+1)2.

— Laikoni

@Laikoni: Tak, jeszcze tego nie ujawniaj! Ups, tak, minęło sporo czasu, odkąd grałem w golfa, zaktualizuję go.

— ბიმო

2

> <> , odpowiedź crashoz 203 bajtów

:l2-$g:0=?;n:





M
-
B
"
BM
",
7M
!"
BBM
!",
7CM
!"-
BBBM
!!",
7BBMM
!!,,
7BBBMM
!!,,
7BBBMM
!!!,,
7BBBBMM
!!!,,
7BBBBMM
!!!!,,
7BBBBBMM
!!!!,,
7BBBBBMM
!!!!!,,
7BBBBBBMM

Wypróbuj online!

Zamierzałem zrobić coś sprytnego z faktem, że powyższe liczby nieparzyste / parzyste n=20były takie same, z wyjątkiem powtarzającego się elementu w środku, ale łatwiej było po prostu na stałe zakodować każdy element.

Wejście odbywa się za pośrednictwem -vflagi. Nie drukuje nic dla elementów powyżej 34.

— Jo King
źródło

2

Pascal (FPC) , odpowiedź AlexRacera , 80 bajtów

var n,m:word;begin read(n);while n<>0 do begin n:=n div 2;m:=m+n;end;write(m)end.

Wypróbuj online!

Gdy wyjścia są identyczne, ale gdy powyższy kod wyprowadza , podczas gdy kod AlexRacera wyprowadza . $0\le n\le 120$ $n=128$ $127$ $126$

To wydaje się późną odpowiedzią, ale i tak dziękuję @AlexRacer za dobrą łamigłówkę!

— r_64
źródło

1

Wow, to jest nawet krótsze niż to, co miałem. Witamy w PPCG!

— AlexRacer,

1

JavaScript, odpowiedź fəˈnɛtɪk (12 bajtów)

Działa to dla podanych wartości, ale zawodzi w przypadku wielu innych wartości (np. ) z powodu błędów precyzji. $x=6$

x=>2.72**x|0

Testowanie

g=
x=>2.72**x|0

tmp=[0,1,2,3,4]
console.log(tmp.map(g).join(','))

Rozwiń fragment kodu

Alternatywnie, wypróbuj online!

— Pan Xcoder
źródło

1

JavaScript, odpowiedź fəˈnɛtɪk (17 bajtów)

Możesz zobaczyć w linku TIO lub wyniku fragmentu stosu, że nie powiedzie się dla wpisów wyższych niż . $15$

x=>2.7182819**x|1

Jeśli dokładność byłaby wymagana tylko dla (pierwszych wartości), to działałby również dla 16 bajtów. $n\le 14$ $15$ x=>Math.exp(x)|1

Testowanie

f=x=>2.7182819**x|1
g=x=>(3-(5/63)**.5)**x|1

tmp=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]
console.log(tmp.map(f).join(","))
console.log(tmp.map(g).join(","))

Rozwiń fragment kodu

Alternatywnie, wypróbuj online!

— Pan Xcoder
źródło

1

Łuska , pękanie 5 bajtów BMO z 3 2 bajtami

-1 dzięki BMO ( LdΣ-> LΣponieważ, gdy podano a Tnum, Lwykonuje „długość reprezentacji ciągu”)

LΣ

Wypróbuj online!

Cyfrowa długość liczb trójkątnych * odpowiada a następnie różni się przy ... kiedy daje a daje . $a(0)\cdots a(23)$ $a(24)$
LΣ $3$ ←d+16 $4$

_{* Gdzie ma cyfrową długość (nie ) $T(0)=0$ $1$ $0$}

— Jonathan Allan
źródło

Gratulacje, to było moje dokładne rozwiązanie! Jednak właśnie zauważyłem, że dla TNum s Li Ld są równoważne, oszczędzając bajt;)

— ბიმო

Ach, szukałem „cyfry” na wiki, aby spróbować znaleźć długość cyfrową, ale nie zauważyłem, że Lzastępuje to „długość reprezentacji ciągu” Tnum.

— Jonathan Allan

(Należy pamiętać, że są one równoważne tylko nieujemnym liczbom całkowitym - wystarczy do tego.)

— Jonathan Allan

1

> <> , Odpowiedź Aidena F. Pierce'a , 36 bajtów

v101786
i5844
419902
%
>l{:}g:0=?;o:

Wypróbuj online!

Inne rozwiązanie z każdą wartością zakodowaną na stałe w wierszu. Ponieważ pierwotna odpowiedź była również w większości zakodowana, nie czuję się z tego powodu winny.

— Jo King
źródło

0

JavaScript, odpowiedź fəˈnɛtɪk , 23 bajty

Zwraca dla . $0$ $n\ge 14$

x=>14-`${73211e9}`[x]|0

Wypróbuj online!

W jaki sposób?

Wyrażenie `${73211e9}`rozwija się do łańcucha "73211000000000", zapewniając tablicę przeglądową 14 wartości, które są odejmowane od 14, co daje oczekiwaną sekwencję.

Dla wynikiem jest: $n\ge 14$

(14 - undefined) | 0
=== NaN | 0
=== 0

21 bajtów

Zwraca NaNdla , który może, ale nie musi, być uważany za poprawny wynik. $n\ge 14$

x=>14-`${73211e9}`[x]

Wypróbuj online!

— Arnauld
źródło

Hardcoding the Cops and Rabbers (Rabusie)

Wyzwanie

Punktacja

cQuents , odpowiedź Stephena , 3 bajty

Jak to działa

JavaScript, odpowiedź fəˈnɛtɪk (17 bajtów)

Testowanie

Haskell , odpowiedź Laikoni , 15 bajtów

Python 2 , odpowiedź xnora , 43 bajty

Kredyty

W jaki sposób?

Teoria

Realizacja

Python 3 , crashoz , 45 bajtów

JavaScript (ES6), odpowiedź Arnaulda (10 bajtów)

Haskell , odpowiedź Laikoni , 26 22 bajtów

Wyjaśnienie

> <> , odpowiedź crashoz 203 bajtów

Pascal (FPC) , odpowiedź AlexRacera , 80 bajtów

JavaScript, odpowiedź fəˈnɛtɪk (12 bajtów)

Testowanie

JavaScript, odpowiedź fəˈnɛtɪk (17 bajtów)

Testowanie

Łuska , pękanie 5 bajtów BMO z 3 2 bajtami

> <> , Odpowiedź Aidena F. Pierce'a , 36 bajtów

JavaScript, odpowiedź fəˈnɛtɪk , 23 bajty

W jaki sposób?

21 bajtów