Czy ta liczba jest losowa?

18

Poprosiłem random.org dla 128 losowych liczb całkowitych od 0 do 2 32 - 1. Ponieważ generator liczb losowych był tak chętny, aby dać pierwsze 64 cyfr po pierwsze, są oczywiście bardziej przypadkowy niż inne 64.

Napisz pełny program lub funkcję, która zwraca prawdziwy wynik, gdy wprowadzona zostanie jedna z następujących 64 liczb całkowitych:

[1386551069, 1721125688, 871749537, 3410748801, 2935589455, 1885865030, 776296760, 614705581, 3841106923, 434616334, 1891651756, 1128215653, 256582433, 310780133, 3971028567, 2349690078, 489992769, 493183796, 3073937100, 3968540100, 777207799, 515453341, 487926468, 2597442171, 950819523, 1881247391, 3676486536, 3852572850, 3498953201, 2544525180, 297297258, 3783570310, 2485456860, 2866433205, 2638825384, 2405115019, 2734986756, 3237895121, 1560255677, 4228599165, 3106247743, 742719206, 2409129909, 3008020402, 328113612, 1081997633, 1583987616, 1029888552, 1375524867, 3913611859, 3488464791, 732377595, 431649729, 2105108903, 1454214821, 997975981, 1764756211, 2921737100, 754705833, 1823274447, 450215579, 976175934, 1991260870, 710069849]

I wynik falsey dla pozostałych 64 liczb:

[28051484, 408224582, 1157838297, 3470985950, 1310525292, 2739928315, 3565721638, 3568607641, 3857889210, 682782262, 2845913801, 2625196544, 1036650602, 3890793110, 4276552453, 2017874229, 3935199786, 1136100076, 2406566087, 496970764, 2945538435, 2830207175, 4028712507, 2557754740, 572724662, 2854602512, 736902285, 3612716287, 2528051536, 3801506272, 164986382, 1757334153, 979200654, 1377646057, 1003603763, 4217274922, 3804763169, 2502416106, 698611315, 3586620445, 2343814657, 3220493083, 3505829324, 4268209107, 1798630324, 1932820146, 2356679271, 1883645842, 2495921085, 2912113431, 1519642783, 924263219, 3506109843, 2916121049, 4060307069, 1470129930, 4014068841, 1755190161, 311339709, 473039620, 2530217749, 1297591604, 3269125607, 2834128510]

Każde wejście inne niż jedna z tych 128 liczb jest niezdefiniowanym zachowaniem.

Jeśli Twoje rozwiązanie zostanie znalezione programowo, udostępnij również kod użyty do jego wygenerowania!

To jest , więc wygrywa najkrótsze rozwiązanie w bajtach.

lirtosiast
źródło
19
Ponieważ generator liczb losowych jako pierwszy podał pierwsze 64 liczby, muszą być one bardziej losowe ಠ ___ ಠ
Luis Mendo
Można wyróżnić dwa zestawy modulo 834
CalculatorFeline
1
Te liczby nie są losowe.
CalculatorFeline,
"Maybe, not enough information."&33 bajty, odpowiada na pytanie.
CalculatorFeline,
3
@CatsAreFluffy Właściwie, dopóki dane wejściowe nie zawierają 0 lub 1 i żadne dwa elementy nie różnią się o 1, możesz je rozdzielić łańcuchem modulo. np. oddzielenie [4 20 79]od [8 18 100]może być wykonane przez [99 79 20 17 7 4](sprawdź, czy możesz dostrzec wzór). Jasne, początkowa połowa twojej odpowiedzi może użyć znacznie mniejszego modułu niż wejście, ale tylna połowa składa się z przesunięcia jednego elementu na raz.
Sp3000,

Odpowiedzi:

11

CJam, 53 52 47 bajtów

l~"X    0'ò"2/Dfb+:%"gÇâì6Ô¡÷Ç8nèS¡a"312b2b=

Są niedrukowalne, ale dwa ciągi można uzyskać przez

[88 9 48 5 39 5 29 1 242]:c
[8 103 199 226 236 54 212 15 161 247 199 56 110 232 83 161 97]:c

odpowiednio. To pokazuje również, że punkty kodowe są poniżej 256.

To jest odpowiedź łańcucha modulo, w której stosujemy następujące moduły do ​​wejściowej liczby całkowitej, w kolejności:

[1153 629 512 378 242 136]

Ponieważ ta lista zawiera liczby całkowite większe niż 255, lista jest kodowana za pomocą dwóch znaków. Dekodowanie odbywa się za pomocą 2/Dfb, który dzieli ciąg na kawałki o długości dwa i konwertuje każdy z podstawowej liczby 13 (np 88*13 + 9 = 1153.). Istnieją jednak dwa wyjątki od dekodowania:

  • Ostatni numer ( 136) nie jest uwzględniony (patrz poniżej),
  • Przedostatnia liczba jest reprezentowana przez pojedynczy znak, ponieważ liczba ( 242) jest mniejsza niż 256 i podzielenie tablicy o nieparzystej długości na fragmenty o rozmiarze 2 pozostawi tablicę o rozmiarze 1 na końcu. Dzięki @ MartinBüttner za tę wskazówkę!

Gdy moduły zredukują całkowitą liczbę wejściową do stosunkowo małej liczby, przeprowadzamy wyszukiwanie z tabeli. Ta tabela jest kodowana przez drugi ciąg znaków, który jest konwertowany na 312liczbę podstawową, a następnie dekodowany na bazę 2, którą indeksujemy. Ponieważ indeksowanie tablic CJam się zawija, możemy pominąć ostatni moduł, jak wspomniano wcześniej.

Wypróbuj online | Zestaw testowy

Sp3000
źródło
1
Jak wy, ludzie, wymyślacie magiczne moduły?
CalculatorFeline,
@CatsAreFluffy Po prostu prosty DFS z ograniczeniem liczby modułów. Moja obecna implementacja jest dość powolna, więc jeśli czuję, że program utknął na chwilę, próbuję innego początkowego punktu początkowego.
Sp3000,
Co to jest DFS? (Wikipedia nie pomaga.)
CalculatorFeline,
@CatsAreFluffy Głębokie wyszukiwanie
Sp3000,
Ach Właśnie użyłem chciwego algorytmu.
CalculatorFeline,
2

JavaScript (ES6) 233

Anonimowa funkcja zwraca 0 jako falsyi niezerową jakotruthy

x=>~"lnhp2wm8x6m9vbjmrqqew9v192jc3ynu4krpg9t3hhx930gu8u9n1w51ol509djycdyh077fd1fnrzv6008ipkh0704161jayscm0l6p4ymj9acbv5ozhjzxo3j1t20j9beam30yptco033c9s3a8jwnre63r29sfbvc5371ulvyrwyqx3kfokbu66mpy9eh" // newline added for readability
.search((x.toString(36)).slice(-3))

Sprawdzanie ostatnich 3 cyfr w reprezentacji liczb w bazie 36.

Ciąg kontrolny jest zbudowany, więc:

a=[1386551069, 1721125688, ... ]
H=x=>(x.toString(36)).slice(-3)
Q=a.map(x=>H(x)).join('')

Test

f=x=>~"lnhp2wm8x6m9vbjmrqqew9v192jc3ynu4krpg9t3hhx930gu8u9n1w51ol509djycdyh077fd1fnrzv6008ipkh0704161jayscm0l6p4ymj9acbv5ozhjzxo3j1t20j9beam30yptco033c9s3a8jwnre63r29sfbvc5371ulvyrwyqx3kfokbu66mpy9eh"
.search((x.toString(36)).slice(-3))

a=[1386551069, 1721125688, 871749537, 3410748801, 2935589455, 1885865030, 776296760, 614705581, 3841106923, 434616334, 1891651756, 1128215653, 256582433, 310780133, 3971028567, 2349690078, 489992769, 493183796, 3073937100, 3968540100, 777207799, 515453341, 487926468, 2597442171, 950819523, 1881247391, 3676486536, 3852572850, 3498953201, 2544525180, 297297258, 3783570310, 2485456860, 2866433205, 2638825384, 2405115019, 2734986756, 3237895121, 1560255677, 4228599165, 3106247743, 742719206, 2409129909, 3008020402, 328113612, 1081997633, 1583987616, 1029888552, 1375524867, 3913611859, 3488464791, 732377595, 431649729, 2105108903, 1454214821, 997975981, 1764756211, 2921737100, 754705833, 1823274447, 450215579, 976175934, 1991260870, 710069849]
b=[28051484, 408224582, 1157838297, 3470985950, 1310525292, 2739928315, 3565721638, 3568607641, 3857889210, 682782262, 2845913801, 2625196544, 1036650602, 3890793110, 4276552453, 2017874229, 3935199786, 1136100076, 2406566087, 496970764, 2945538435, 2830207175, 4028712507, 2557754740, 572724662, 2854602512, 736902285, 3612716287, 2528051536, 3801506272, 164986382, 1757334153, 979200654, 1377646057, 1003603763, 4217274922, 3804763169, 2502416106, 698611315, 3586620445, 2343814657, 3220493083, 3505829324, 4268209107, 1798630324, 1932820146, 2356679271, 1883645842, 2495921085, 2912113431, 1519642783, 924263219, 3506109843, 2916121049, 4060307069, 1470129930, 4014068841, 1755190161, 311339709, 473039620, 2530217749, 1297591604, 3269125607, 2834128510]

A.textContent=a.map(x=>f(x))
B.textContent=b.map(x=>f(x))
<table>
  <tr><th>first 64 - truthy</th></tr><tr><td id=A></td></tr>
  <tr><th>other 64 - falsy</th></tr><tr><td id=B></td></tr>
</table>  

edc65
źródło
1

Mathematica, 218 217 bajtów

Fold[Mod,#,{834,551,418,266,228,216,215,209,205,199,198,195,178,171,166,162,154,151,146,144,139,137,122,120,117,114,110,106,101,98,95,88,84,67,63,61,60,57,55,51,45,44,43,41,40,35,34,30,27,26,25,23,20,14,13,11,10,9}]<1

Z jakiegokolwiek powodu istnieje zestaw modułów, który pozwala nam rozróżnić dwa zestawy tylko po tym, czy po zastosowaniu modułów wynik jest zerowy, czy nie. Długa lista modułów została wygenerowana przez ten program:

Block[{data1, data2, n, mods}, 
 data1 = {1386551069, 1721125688, 871749537, 3410748801, 2935589455, 
   1885865030, 776296760, 614705581, 3841106923, 434616334, 
   1891651756, 1128215653, 256582433, 310780133, 3971028567, 
   2349690078, 489992769, 493183796, 3073937100, 3968540100, 
   777207799, 515453341, 487926468, 2597442171, 950819523, 1881247391,
    3676486536, 3852572850, 3498953201, 2544525180, 297297258, 
   3783570310, 2485456860, 2866433205, 2638825384, 2405115019, 
   2734986756, 3237895121, 1560255677, 4228599165, 3106247743, 
   742719206, 2409129909, 3008020402, 328113612, 1081997633, 
   1583987616, 1029888552, 1375524867, 3913611859, 3488464791, 
   732377595, 431649729, 2105108903, 1454214821, 997975981, 
   1764756211, 2921737100, 754705833, 1823274447, 450215579, 
   976175934, 1991260870, 710069849};
 data2 = {28051484, 408224582, 1157838297, 3470985950, 1310525292, 
   2739928315, 3565721638, 3568607641, 3857889210, 682782262, 
   2845913801, 2625196544, 1036650602, 3890793110, 4276552453, 
   2017874229, 3935199786, 1136100076, 2406566087, 496970764, 
   2945538435, 2830207175, 4028712507, 2557754740, 572724662, 
   2854602512, 736902285, 3612716287, 2528051536, 3801506272, 
   164986382, 1757334153, 979200654, 1377646057, 1003603763, 
   4217274922, 3804763169, 2502416106, 698611315, 3586620445, 
   2343814657, 3220493083, 3505829324, 4268209107, 1798630324, 
   1932820146, 2356679271, 1883645842, 2495921085, 2912113431, 
   1519642783, 924263219, 3506109843, 2916121049, 4060307069, 
   1470129930, 4014068841, 1755190161, 311339709, 473039620, 
   2530217749, 1297591604, 3269125607, 2834128510};
 n = 1;
 mods = {};
 While[Intersection[Mod[data1, n], Mod[data2, n]] != {}, n++];
 FixedPoint[
  (mods = Append[mods, n]; data1 = Mod[data1, n]; 
    data2 = Mod[data2, n]; n = 1;
    While[Intersection[Mod[data1, n], Mod[data2, n]] != {}, n++]; 
    n) &
  , n];
 {mods, {Fold[Mod, data1, mods], Fold[Mod, data2, mods]}}
 ]

Pierwsze wyjście to moduły, drugie i trzecie wyjście to dwie listy, po zastosowaniu modułów. Dwie długie listy to zestawy.

CalculatorFeline
źródło
2
Prawdopodobnie możesz skompresować część listy w ciąg.
njpipeorgan
1

PowerShell, v3 + 194 bajty

$args[0]%834%653-in(40..45+4,8,12,51,60,64,69,76,84,86,93,97,103,117+137..149+160,162,178+195..209+215..227+255,263+300..329+354,361,386,398,417,443,444+469..506+516,519,535,565,581,586,606,618)

Trochę innego podejścia, więc pomyślałem, że to opublikuję. Nie wygra najkrócej, ale może dać komuś pomysł na skrócenie kodu.

Nadal bierzemy wejściową liczbę całkowitą $args[0]i stosujemy do niej operacje modulo, więc nie ma w tym nic innego. W powyższym przykładzie używamy -inoperatora (stąd wymaganie v3 +), więc wyświetli to Truewartości, które są w prawdziwym przypadku testowym.

Jednak staram się znaleźć wynikowe tablice, w których możemy wykorzystać funkcję ..zakresu, aby skrócić liczbę bajtów, ale nadal mieć wyraźne tablice między wartościami prawdy i falseya. Możemy to zrobić, ponieważ zachowanie inne niż wejście true / falsey jest niezdefiniowane, więc jeśli zakres przechwytuje wartości poza wejściem true / falsey, nie ma znaczenia wyjście.

Jak dotąd jest to dość ręczny proces, ponieważ celem jest znalezienie modułu, w którym jedna z tablic typu prawda lub falsey ma duże odstępy między liczbami, a druga tablica zawiera duże ilości liczb w tym odstępie. Do tej pory działałem głównie intuicyjnie i intuicyjnie, ale w końcu mogę napisać brutal-forcer, aby to rozwiązać. Powyżej jest najkrótszy, jaki dotychczas (głównie ręcznie) znalazłem.

AdmBorkBork
źródło