O serii

Po pierwsze, możesz potraktować to jak każde inne wyzwanie związane z golfem i odpowiedzieć na nie, nie martwiąc się serią. Istnieje jednak tabela wyników dla wszystkich wyzwań. Możesz znaleźć tabelę liderów wraz z kilkoma więcej informacji o serii w pierwszym poście .

Chociaż mam szereg pomysłów w szeregu, przyszłe wyzwania nie są jeszcze ustalone. Jeśli masz jakieś sugestie, daj mi znać w odpowiednim poście z piaskownicą .

Hole 4: The Bertrand Paradox

Bertrand paradoksem jest ciekawy problem, który pokazuje, jak różne metody zbierania losowe akordy w kółko może dawać różne dystrybucje akordów, ich środkowych i ich długości.

W tym wyzwaniu należy wygenerować losowe akordy koła jednostkowego, stosując metodę „właściwą”, tj. Taką, która wytwarza rozkład akordów niezmienny przy skalowaniu i translacji. W powiązanym artykule w Wikipedii „Metoda 2” jest taką metodą.

Oto dokładne zasady:

• Powinieneś wziąć jedną dodatnią liczbę całkowitą,N która określa liczbę akordów, które powinny zostać zwrócone. Wyjściem powinna być lista Nakordów, każdy określony jako dwa punkty na okręgu jednostki, podany przez ich kąt biegunowy w radianach.
• Twój kod powinien mieć możliwość zwrócenia co najmniej 2 ²⁰ różnych wartości dla każdego z dwóch kątów . Jeśli dostępne RNG ma mniejszy zasięg, musisz najpierw zbudować RNG o wystarczająco dużym zasięgu na górze wbudowanego lub musisz wdrożyć własny odpowiedni RNG . Ta strona może być do tego pomocna.
• Dystrybucja akordów musi być nie do odróżnienia od tej wyprodukowanej przez „Method 2” w powiązanym artykule Wikipedii. Jeśli wdrażasz inny algorytm do wybierania akordów, dołącz dowód poprawności. Niezależnie od tego, jaki algorytm wybierzesz do wdrożenia, teoretycznie musi on być w stanie wygenerować dowolny prawidłowy akord w okręgu jednostki (z wyjątkiem ograniczeń bazowego PRNG lub typów danych o ograniczonej precyzji).
• Wdrożenie powinno wykorzystywać i zwracać albo liczby zmiennoprzecinkowe (o szerokości co najmniej 32 bity), albo liczby o stałym punkcie (o szerokości co najmniej 24 bity), a wszystkie operacje arytmetyczne powinny być dokładne z dokładnością do co najmniej 16 ul .

Możesz napisać pełny program lub funkcję i pobrać dane wejściowe za pomocą STDIN (lub najbliższej alternatywy), argumentu wiersza poleceń lub argumentu funkcji i wygenerować wynik za pomocą STDOUT (lub najbliższej alternatywy), wartości zwracanej funkcji lub parametru funkcji (wyjściowej).

Dane wyjściowe mogą być w dowolnym dogodnym formacie listy lub ciągu, o ile poszczególne liczby są wyraźnie rozróżnialne, a ich całkowita liczba jest zawsze równa.

To jest kod golfowy, więc wygrywa najkrótsze przesłanie (w bajtach). I oczywiście najkrótsze zgłoszenie na użytkownika wejdzie również do ogólnej tabeli liderów serii.

Wyobrażanie sobie

Możesz użyć poniższego fragmentu, aby wyrenderować wygenerowane linie i sprawdzić ich rozkład. Wystarczy wkleić listę par kątów w polu tekstowym. Fragment powinien być w stanie obsłużyć prawie każdy format listy, o ile liczby są prostymi liczbami dziesiętnymi (bez notacji naukowej). Zalecam użycie co najmniej 1000 linii, aby uzyskać dobry pomysł na dystrybucję. Podałem również kilka przykładowych danych dla różnych metod przedstawionych w poniższym artykule.

function draw() {
  document.getElementById("output").innerHTML = svg
}

function drawLines() {
  lines = document.getElementById("lines").value;
  var e = prefix;
  //e += '<circle cx="' + offset + '" + cy="' + offset + '" r="' + radius + '" stroke="black" fill="white"/>';
  lines = lines.match(/-?(?:\d*\.\d+|\d+\.\d*|\d+(?!\.))/g);
  for (i = 0; i < lines.length; i+=2)
  {
    t1 = parseFloat(lines[i]);
    t2 = parseFloat(lines[i+1]);
    x1 = Math.cos(t1);
    y1 = Math.sin(t1);
    x2 = Math.cos(t2);
    y2 = Math.sin(t2);
    e += '<path stroke="black" stroke-opacity="0.2" d="M ' + (x1 * radius + offset) + ' ' + (y1 * radius + offset) + ' L ' + (x2 * radius + offset) + ' ' + (y2 * radius + offset) + '"/>';
  }
  e += suffix;
  svg = e;
  draw();
}
var prefix = '<svg height="450" width="450">',
  suffix = "</svg>",
  scale = 0.95,
  offset = 225,
  radius = scale*offset,
  svg = "";

svg {
  position: absolute;
}

Paste line specifications here
<br>
<input id="lines" type="textarea" size="60" oninput='drawLines()' />
<br>
<br>
<div id="output"></div>

Przykładowe dane wygenerowane za pomocą metody 1.

Przykładowe dane wygenerowane za pomocą metody 2.

Przykładowe dane wygenerowane za pomocą metody 3.

Tabela liderów

Pierwszy post z serii generuje tabelę wyników.

Aby upewnić się, że Twoje odpowiedzi się pojawią, zacznij każdą odpowiedź od nagłówka, używając następującego szablonu Markdown:

# Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:

# Ruby, <s>104</s> <s>101</s> 96 bytes

(Język nie jest obecnie wyświetlany, ale fragment go wymaga i analizuje, a w przyszłości mogę dodać tabelę wyników według języków).

Kod maszynowy IA-32, 54 bajty

Hexdump kodu:

68 00 00 00 4f 0f c7 f0 50 db 04 24 58 d8 34 24
f7 d9 78 f1 d9 c0 dc c8 d9 e8 de e1 d9 fa d9 c9
d9 f3 dc c0 d9 eb de ca d8 c1 dd 1a dd 5a 08 83
c2 10 e2 d1 58 c3

Wykorzystuje (nieco zmodyfikowany) algorytm opisany przez Wikipedię. W pseudokodzie:

x = rand_uniform(-1, 1)
y = rand_uniform(-1, 1)
output2 = pi * y
output1 = output2 + 2 * acos(x)

Korzystam z zakresu, -1...1ponieważ łatwo jest tworzyć losowe liczby w tym zakresie: rdrandinstrukcja generuje liczbę całkowitą pomiędzy -2^31i 2^31-1, którą można łatwo podzielić przez 2 ^ 31.

Powinienem był użyć tego zakresu 0...1dla drugiej liczby losowej (x), do której jest wprowadzany acos; jednakże część ujemna jest symetryczna z częścią dodatnią - liczby ujemne wytwarzają akordy, których rozpiętość jest większa niż pi radianów, ale dla zilustrowania paradoksu Bertranda nie ma to znaczenia.

Ponieważ zestaw instrukcji 80386 (lub x87) nie ma dedykowanej acosinstrukcji, musiałem wyrazić obliczenia tylko za pomocą ataninstrukcji:

acos(x) = atan(sqrt(1-x^2)/x)

Oto kod źródłowy, który generuje powyższy kod maszynowy:

__declspec(naked) void __fastcall doit1(int n, std::pair<double, double>* output)
{
    _asm {
        push 0x4f000000;        // [esp] = float representation of 2^32

    myloop:
        rdrand eax;             // generate a random number, -2^31...2^31-1
        push eax;               // convert it
        fild dword ptr [esp];   // to floating-point
        pop eax;                // restore esp
        fdiv dword ptr [esp];   // convert to range -1...1
        neg ecx;
        js myloop;              // do the above 2 times

        // FPU stack contents:  // x           | y
        fld st(0);              // x           | x   | y
        fmul st(0), st;         // x^2         | x   | y
        fld1;                   // 1           | x^2 | x | y
        fsubrp st(1), st;       // 1-x^2       | x   | y
        fsqrt;                  // sqrt(1-x^2) | x   | y
        fxch;                   // x           | sqrt(1-x^2) | y
        fpatan;                 // acos(x)     | y
        fadd st, st(0);         // 2*acos(x)   | y
        fldpi;                  // pi          | 2*acos(x) | y
        fmulp st(2), st;        // 2*acos(x)   | pi*y
        fadd st, st(1);         // output1     | output2
        fstp qword ptr [edx];   // store the numbers
        fstp qword ptr [edx + 8];

        add edx, 16;            // advance the output pointer
        loop myloop;            // loop

        pop eax;                // restore stack pointer
        ret;                    // return
    }
}

Aby wygenerować dwie liczby losowe, kod używa zagnieżdżonej pętli. Aby zorganizować pętlę, kod wykorzystuje ecxrejestr (licznik pętli zewnętrznej) jako dodatni. Tymczasowo neguje ecx, a następnie robi to ponownie, aby przywrócić pierwotną wartość. jsInstrukcja powtarza pętlę gdy ecxjest ujemny (to zdarza się tylko raz).

Pyth, 25 23 22 bajtów

Port odpowiedzi C ++ 11 programu rcrmn. To jest moje pierwsze użycie Pytha i miałem dużo zabawy!

VQJ,*y.n0O0.tOZ4,sJ-FJ

Wersja 23-bajtowa:

VQJ*y.n0O0K.tOZ4+JK-JKd

Wytnij bajt, zmieniając program, aby używał foldów + sum i ustawiał J na krotkę, usuwając K.

Oryginalny:

VQJ**2.n0O0K.tO0 4+JK-JKd

Odetnij 2 bajty dzięki @orlp.

Wyjaśnienie:

VQ                         loop as many times as the input number
  J,                       set J to the following tuple expression
    *y.n0O0                2 * .n0 (pi) * O0 (a random number between 0 and 1)
            .tOZ4          .tOZ 4 (acos of OZ (a random number))
                 ,sJ-FJ    print the sum of J and folding J using subtraction in parenthesis, separated by a comma, followed by another newline

Julia, 48 bajtów

n->(x=2π*rand(n);y=acos(rand(n));hcat(x+y,x-y))

Wykorzystuje algorytm metody 2, podobnie jak większość dotychczasowych odpowiedzi. Tworzy funkcję lambda, która pobiera liczbę całkowitą i zwraca tablicę nx 2. Aby to nazwać, nadaj mu nazwę, npf=n->... .

Niegolfowane + wyjaśnienie:

function f(n::Int64)
    # The rand() function returns uniform random numbers using
    # the Mersenne-Twister algorithm

    # Get n random chord angles
    x = 2π*rand(n)

    # Get n random rotations
    y = acos(rand(n))

    # Bind into a 2D array
    hcat(x+y, x-y)
end

Bardzo podoba mi się wygląd wizualizacji, więc dołączę jedną. To wynik f(1000).

Pyth, 22 bajty

Port odpowiedzi C ++. Miałem kolejne 23 bajtowe rozwiązanie (teraz 22!), Ale była to prawie kopia odpowiedzi pyth @ kirbyfan64sos z optymalizacjami, więc musiałem trochę przemyśleć i wyjść poza pole i kreatywnie (ab) użyć operatora fold.

m,-Fdsdm,y*.nZOZ.tOZ4Q

Zauważ, że to nie działa teraz z powodu błędu w operatorze składania po wprowadzeniu reduce2. Zgłaszam prośbę.

m             Map    
 ,            Tuple of
  -Fd         Fold subtraction on input
  sd          Fold addition on input
 m      Q     Map over range input
  ,           Tuple           
   y          Double
    *         Product
     .nZ      Pi
     OZ       [0, 1) RNG
  .t  4       Acos
    OZ        [0, 1) RNG

Dla refence było to moje inne rozwiązanie, które działa w ten sam sposób: VQKy*.nZOZJ.tOZ4,+KJ-KJ

IDL, 65 bajtów

Oczywiście jest to ten sam algorytm co @rcrmn, mimo że wyprowadziłem go niezależnie przed przeczytaniem ich odpowiedzi.

read,n
print,[2,2]#randomu(x,n)*!pi+[-1,1]#acos(randomu(x,n))
end

Funkcja losowa IDL korzysta z Mersenne Twister, która ma okres 2 ¹⁹⁹³⁷ -1.

EDYCJA: Uruchomiłem 1000 akordów przez powyższy wizualizator, oto zrzut ekranu wyniku:

C ++ 11, 214 bajtów

#include<random>
#include<iostream>
#include<cmath>
int main(){using namespace std;int n;cin>>n;random_device r;uniform_real_distribution<> d;for(;n;--n){float x=2*M_PI*d(r),y=acos(d(r));cout<<x+y<<' '<<x-y<<';';}}

Jest to więc prosta implementacja właściwego algorytmu ze strony wikipedii. Głównym problemem tutaj w golfie są och, tak cholernie długie nazwy, jakie mają losowe klasy generatorów. Ale w przeciwieństwie do dobrego starego, jest przynajmniej odpowiednio jednolity.

Wyjaśnienie:

#include<random>
#include<iostream>
#include<cmath>
int main()
{
    using namespace std;
    int n;
    cin>>n; // Input number
    random_device r; // Get a random number generator
    uniform_real_distribution<> d;   // Get a uniform distribution of 
                                     // floats between 0 and 1
    for(;n;--n)
    {
        float x = 2*M_PI*d(r),       // x: Chosen radius angle
              y = acos(d(r));        // y: Take the distance from the center and 
                                     // apply it an inverse cosine, to get the rotation

        cout<<x+y<<' '<<x-y<<';';    // Print the two numbers: they are the rotation
                                     // of the radius +/- the rotation extracted from
                                     // the distance to the center
    }
}

APL, 46 bajtów

f←{U←⍵ 2⍴∊{(○2×?0)(¯1○?0)}¨⍳⍵⋄⍉2⍵⍴∊(+/U)(-/U)}

Mój pierwszy program APL w historii! Z pewnością można go znacznie poprawić (ponieważ brakuje mi ogólnego rozumienia APL), więc wszelkie sugestie byłyby fantastyczne. Tworzy to funkcję, fktóra przyjmuje na wejściu liczbę całkowitą, oblicza pary punktów cięciwy przy użyciu metody 2 i drukuje każdą parę oddzieloną znakiem nowej linii.

Możesz spróbować online !

Wyjaśnienie:

f←{ ⍝ Create the function f which takes an argument ⍵

    ⍝ Define U to be an ⍵ x 2 array of pairs, where the first
    ⍝ item is 2 times a random uniform float (?0) times pi (○)
    ⍝ and the second is the arccosine (¯1○) of another random
    ⍝ uniform float.

    U ← ⍵ 2 ⍴ ∊{(○2×?0)(¯1○?0)}¨⍳⍵

    ⍝ Create a 2 x ⍵ array filled with U[;1]+U[;2] (+/U) and
    ⍝ U[;1]-U[;2] (-/U). Transpose it into an ⍵ x 2 array of
    ⍝ chord point pairs and return it.

    ⍉ 2 ⍵ ⍴ ∊(+/U)(-/U)
}

Uwaga: Moje poprzednie 19-bajtowe rozwiązanie było nieprawidłowe, ponieważ zwróciło (x, y) zamiast (x + y, xy). Obfituje smutek.

Java, 114 bajtów

n->{for(;n-->0;){double a=2*Math.PI*Math.random(),b=Math.acos(Math.random());System.out.println(a+b+" "+(a-b));}};

Podstawowa implementacja w java. Użyj jako wyrażenia lambda.

Przykładowe użycie

Rubinowy, 72 bajty

Mój pierwszy golf tutaj! Użyłem tego samego kodu, co wszyscy, mam nadzieję, że to w porządku

gets.chomp.to_i.times{puts"#{x=2*Math::PI*rand},#{x+2*Math.acos(rand)}"}

Java, 115 123

Jest to w zasadzie to samo co większość innych, ale potrzebuję oceny Java dla tej dziury, więc oto:

void i(int n){for(double x;n-->0;System.out.println(x+2*Math.acos(Math.random())+" "+x))x=2*Math.PI*Math.random();}

W pastebin można znaleźć 1000 przykładowych akordów , oto pierwsze pięć z jednego przebiegu:

8.147304676211474 3.772704020731153
8.201346559916786 3.4066194978900106
4.655131524088468 2.887965593766409
4.710707820868578 3.8493686706403984
3.3839198612642423 1.1604092552846672

CJam, 24 22 bajtów

Podobnie jak w przypadku innych algorytmów, tutaj jest wersja w CJam.

{2P*mr_1dmrmC_++]p}ri*

Wejście 1000 daje rozkład taki jak:

Jak to działa

Algorytm jest po prostu x = 2 * Pi * rand(); print [x, x + 2 * acos(rand())]

{                 }ri*        e# Run this loop int(input) times
 2P*mr                        e# x := 2 * Pi * rand()
      _                       e# copy x
       1dmr                   e# y := rand()
           mC                 e# z := acos(y)
             _++              e# o := x + z + z
                ]             e# Wrap x and o in an array
                 p            e# Print the array to STDOUT on a new line

Aktualizacja : 2 bajty zapisane dzięki Martinowi!

Wypróbuj tutaj

Python 3, 144 117 bajtów

(dzięki Blckknght za lambda wskaźnik)

Korzystając z tej samej metody co inni:

import math as m;from random import random as r;f=lambda n:[(x,x+2*m.acos(r()))for x in(2*m.pi*r()for _ in range(n))]

Z dokumentacji Python:

Python wykorzystuje Mersenne Twister jako główny generator. Daje 53-bitowe precyzyjne ruchy i ma okres 2 ¹⁹⁹³⁷ -1.

Wynik

>>> f(10)
[(4.8142617617843415, 0.3926824824852387), (3.713855302706769, 1.4014527571152318), (3.0705105305032188, 0.7693910749957577), (1.3583477245841715, 0.9120275474824304), (3.8977143863671646, 1.3309852045392736), (0.9047010644291349, 0.6884780437147916), (3.333698164797664, 1.116653229885653), (3.0027328050516493, 0.6695430795843016), (5.258167740541786, 1.1524381034989306), (4.86435124286598, 1.5676690324824722)]

I tak dalej.

Wyobrażanie sobie

Perl, 60

#!perl -l
use Math::Trig;print$x=2*pi*rand,$",$x+2*acos rand for 1..<>

R 60 56 53 49 bajtów

Dodatkowe 4 bajty dzięki @JayCe i zmianie na funkcję.

Korzystanie z tej samej podstawowej formuły co pozostałe. R domyślnie używa metody Mersenne-Twister, ale inne można ustawić. Zwraca listę rozdzieloną spacjami.

function(n,y=acos(runif(n)))runif(n)*2*pi+c(y,-y)

Wypróbuj online!

SmileBASIC, 62 bajty

INPUT N
FOR I=1TO N
X=PI()*2*RNDF()Y=ACOS(RNDF())?X+Y,X-Y
NEXT