W 1946 r. Erdos i Copeland udowodnili, że pewna liczba jest liczbą normalną , tzn. Cyfry w liczbach dziesiętnych są równomiernie rozmieszczone.
Użytkownicy wprowadzą sekwencję cyfr, a znajdziesz najmniejszą liczbę pierwszą zawierającą ten ciąg w bazie 10.
Przykład:
input -> output
"10" -> 101
"03" -> 103
"222" -> 2221
"98765" -> 987659
Najkrótszy kod w bajtach wygrywa. Wiem, że niektóre języki (matematyka, szałwia, pari-gp ...) mają wbudowane funkcje związane z liczbami pierwszymi. -50 bajtów, jeśli twój program nie polega na takich funkcjach. Nie próbuj oszukiwać, proszę, jeśli twój język ma już ogromną przewagę, nie rób bonusu.
Edytować
Według kilku poniższych komentarzy najmniejsza liczba pierwsza zawierająca „03” to 3. Czy to naprawdę robi różnicę? Jedyne, o czym myślę, to to, że może liczby są łatwiejsze w obsłudze niż łańcuchy.
W przypadkach takich jak „03” preferowanym wyjściem byłoby 103. Jednak nie uważam, aby była to podstawowa część twojego programu, więc możesz zignorować wszelkie początkowe zero, jeśli zapewni to mniejszą liczbę bajtów.
Odpowiedzi:
Golfscipt,
3332 bajty = wynik -18Wyjaśnienie:
2{...}{)}/
- zaczynając od2
, gdy coś jest prawdą, zwiększaj górę stosu;;x
- odrzucić wartości pośrednie zebrane przez{}{}/
i dane wejściowe, a następnie umieścić tam ostatnią testowaną wartość:x,2>
- zapisz wartość jakox
, a następnie utwórz listę od2
dox-1
{x\%!},!!
- zachowaj te, którex
są podzielne, a następnie przymusz do wartości logicznej (nie pustej)x`3?)!
- wyszukaj dane wejściowe w formie tekstowejx
(-1
jeśli nie znaleziono), zwiększaj, neguj.|
- lubźródło
Program Haskell, 97 znaków = 47 punktów
Funkcja Haskell, 75 znaków = 25 punktów
rodzaj
p
jest(Integral a, Show a) => [Char] -> a
. Jeśli podasz swój własny typ całkowy, możesz wyszukiwać przez infix we własnej reprezentacji tych wartości. StandardInteger
używa oczekiwanej notacji dziesiętnej dla liczb całkowitych.Niezbyt szybko. Kwadratowa w wartości (nie rozmiarze) wyniku.
wersja bez golfa:
przykład:
źródło
Java - 175 znaków.
źródło
indexOf(a[0])>=0)
i{System.out.println(n)
.boolean p=true
je czymś takimint p=1
i tak dalej.Mathematica 58
Względne czasy na moim komputerze Mac (2,7 GHz i7 z pamięcią 8 GB).
Znajdź najmniejszą liczbę pierwszą zawierającą „01”.
Znajdź najmniejszą liczbę pierwszą zawierającą „012345”.
Znajdź najmniejszą liczbę pierwszą zawierającą „0123456”.
źródło
StringFreeQ
go skrócić.Sage , 72
Działa w interaktywnym pytaniu
Primes().unrank(i)
dajei
czwartą liczbę pierwszą, przy czym 0 jest liczbą 2.źródło
R, 56 znaków -50 = 6
Weź dane jako standardowe. Przyrosty k, aż k jest liczbą pierwszą (testowane przez zsumowanie instancji, dla których k mod 2 do k są zerami, stąd FAŁSZ, ponieważ 0 zamienione w logiczną jest FAŁSZ) i zawiera ciąg podany jako dane wejściowe (testowany prostym grepem, tutaj grepl ponieważ chcemy logicznego wyniku).
Stosowanie:
źródło
Shell Oneliner (Coreutils): 45 znaków
Nie definiujemy tutaj funkcji ... tylko oneliner, który przyjmuje jeden argument
$n
i skanuje zakres liczb całkowitych (właściwie trochę więcej, aby skrócić kod). Wersja 55 znaków:Nie jest nawet zbyt wolny. Na
n=0123456
to zwraca201234563
się81.715s
. To imponująco szybkie jak na długi potok z dwoma procesorami łańcuchowymi.Usuwając dwie postacie (do 53) i jedną fajkę, możemy uruchomić ją jeszcze szybciej:
I wreszcie, trochę
sed
magii, aby sprowadzić go do 45 znaków , chociaż wydruk jest brzydki:źródło
J - 38 znaków -50 = -12 pkt
Zwykle w J używałbyś bardzo zoptymalizowanych wbudowanych funkcji liczb pierwszych, więc nie będę przepraszać za powolność działania.
Wyjaśniono:
>:@]^:(...)^:_&2
- Począwszy od 2, zwiększaj, aż(...)
zwraca false.(+.i.)@]
- Weź GCD licznika z każdą liczbą całkowitą mniejszą od niego. (Stosujemy konwencję GCD (X, 0) = X.)]=*/@
- Weź iloczyn wszystkich tych liczb i sprawdź równość licznika. Jeśli licznik jest liczbą pierwszą, lista zawierała wszystkie 1 s, z wyjątkiem GCD z 0; w przeciwnym razie będzie co najmniej jeden GCD, który jest większy niż 1, więc produkt będzie większy niż licznik.>./@(E.":)
- Sprawdź, czy reprezentacja ciągu licznika (":
) zawiera ciąg (E.
) w dowolnym punkcie.>./
jest funkcją maksimum i używamy jej, ponieważE.
zwraca wektor boolowski z wartością 1 wszędzie tam, gdzie podłańcuch zaczyna się w głównym ciągu.*:
- Logiczne NAND wyniki razem. Będzie to fałsz tylko wtedy, gdy oba dane wejściowe były prawdziwe, tj. Jeśli licznik był pierwszy i zawierał podłańcuch.Stosowanie:
Dla potomnych, oto wersja z wbudowanym prime (30 znaków, ale bez premii):
1 p:]
sprawdza licznik pod kątem pierwszeństwa zamiast sztuczki GCD.źródło
Brachylog (v2), 3 bajty w kodowaniu Brachylog
Wypróbuj online!
Podanie funkcji, przyjmowanie danych wejściowych z argumentu po prawej stronie, dawanie wyniku przez mutowanie argumentu po lewej stronie. (Jest to przeciwieństwo normalnej konwencji Brachylog; zobacz ten meta post, aby uzyskać więcej dyskusji. Zamiana argumentów na bardziej typową kolejność kosztowałaby trzy bajty.) Łącze TIO ma opakowanie, które wywołuje funkcję z odpowiednią konwencją wywoływania i drukuje wynik.
Wyjaśnienie
Niestety Brachylog jest tak odpowiedni dla tego problemu, że zgodnie z zasadami problemu nie mogę nawet próbować skorzystać z premii (co jak na ironię oznacza, że nie jest w stanie wygrać).
Jednym z powodów, dla których tak bardzo lubię Brachylog, jest to, że programowanie to komunikacja między człowiekiem a komputerem, a zatem „idealny” język pozwala po prostu bezpośrednio przetłumaczyć specyfikację problemu na angielski; pomysły, za pomocą których stwierdzono problem i za pomocą których napisany jest program, byłyby takie same. Brachylog może zaskakiwać często tym ideałem; pytanie tutaj brzmi: „znajdź najmniejszą liczbę pierwszą zawierającą podłańcuch”, i mogę dosłownie połączyć ze sobą pojęcia „najmniejsza liczba pierwsza, zawierająca podłańcuch” we właściwej kolejności i mieć działający program. W związku z tym Brachylog mówi o wiele więcej o naturze komunikacji niż język, w którym musiałbyś wyraźnie określić algorytm rozwiązania problemu; czasami rozmawiając z innymi ludźmi, próbujemy wyjaśnić problem, wyjaśniając kroki, które należy podjąć, aby go rozwiązać, ale jest to rzadkie. Dlaczego więc nasze języki powinny być inne?
źródło
JavaScript 83 bajty = 33 wynik
Gra w golfa:
Niegolfowany (trochę):
źródło
JavaScript (Node.JS) - 93 bajty = 43 punkty
W formie wyodrębnionej z rozsądnymi nazwami zmiennych:
źródło
Rdza 0,9 136 bajtów = 86 punktów
Bardzo wyraźne pomimo zwartości. Za dużo miejsca spędzonego na znalezieniu łańcucha. :(
Tutaj wersja bez białych znaków (136 znaków)
źródło
Japt, 10 bajtów
Spróbuj
źródło
Tidy , 37 bajtów
Wypróbuj online!
źródło
Perl 6 , 36-50 = -14 punktów
Wypróbuj online!
Biorąc pod uwagę,
$_%%one ^$_
że jedyne 2 bajty sąmniejszeniż.is-prime
, myślę, że warto dla bonusu. Upłynął limit czasu dla ostatniego przypadku testowego.Wyjaśnienie:
źródło
:$
Python 3 ,
8079 bajtów - 50 =3029 punktów-1 bajt dzięki kreatywnemu użyciu @ ASCII-only
%s
zamiaststr
Przypadek testowy „98765” nie został jeszcze potwierdzony ze względu na to, jak długo trwa testPotwierdzony dla przypadku testowego „98765” po kilku godzinach, ale z podobnym podejściem, które wykorzystuje ocenę zwarcia, aby uniknąć niektórych testów pierwotności, działa o wiele szybciej. Alternatywnie może to być ~ 2x tak szybko, jeśli wiemy, że „2” nie jest wejściem (możemy uniknąć sprawdzania liczb parzystych pod kątem pierwszeństwa) poprzez ustawieniei=3
początkowe ii+=2
w pętli, bez dodatkowych kosztów bajtowych.Wypróbuj online!
Objaśnienie
while
warunku ((x in"%s"%i)*all(i%j for j in range(2,i))-1
):(x in"%s"%i)
:True
/1
jeśli bieżący licznik zawiera żądaną sekwencję liczb;False
/0
inaczej.all(i%j for j in range(2,i))
:True
/1
jeśli bieżący licznik zawsze ma resztę, gdy jest dzielony przez dowolną liczbę całkowitą od 2 (włącznie) do siebie (wyłączny), tj. jest liczbą pierwszą;False
/0
inaczej.W
*
mnoży dwa warunki i działa jakoand
operatora - produktTrue
/1
wtedy i tylko wtedy, gdy oba te warunki sąTrue
/1
.-1
Działa jakonot
operator:False
/0
- 1 wyników w-1
, który jest uważany za prawdziwe, natomiastTrue
/1
- 1 powoduje0
, który jest uważany za fałszywy. Zatem pętla jest kontynuowana, podczas gdy liczba albo nie zawiera żądanej sekwencji liczb, albo nie jest liczbą pierwszą.Wymień
*
sięand
i dodać nawiasy wokół wszystkiego, ale-1
za to znacznie szybciej, równoważne rozwiązanie (czyli nieco dłużej).Rozwiązanie 76 bajtów - 50 = 26 punktów w Pythonie 2 podane tylko przez @ ASCII (wykorzystuje
``
zamiaststr()
,Wypróbuj online!
źródło
return I
JavaScript, 65-50 = 15 punktów
Wypróbuj online!
źródło