Naturalne Pi # 2 - Rzeka

Cel

Biorąc pod uwagę ciąg z ciągiem skrótów, oblicz jego całkowitą długość i podziel przez odległość od początku do końca.

Symulacja

Co symulujemy? Według tego artykułu stosunek długości rzeki do odległości między początkiem a końcem wynosi w przybliżeniu Pi! (Być może zostało to obalone empirycznie, ale mogłem znaleźć dane i dla tego wyzwania założymy, że to prawda).

Jak to symulujemy?

Weź ciąg znaków spacji i skrótów
Do każdego skrótu będą przylegały dwa inne
- Z wyjątkiem pierwszego i ostatniego skrótu, który będzie miał tylko 1
Każda postać leży na kracie (x, y)
x jest indeksem znaku w linii
- np. cjest czwartą postacią w0123c567
y jest numerem wiersza znaku
- np. cjest na 3. linii:

      0line
      1line
      2line
      3c...

Zsumuj odległości między sąsiednimi skrótami, nazwij to S
Określ odległość między pierwszym a ostatnim hashem, nazwij to D
Powrót S/D

Specyfikacja

Wejście
- Elastyczny, przyjmuj dane wejściowe na dowolny ze standardowych sposobów (np. Parametr funkcji, STDIN) i w dowolnym standardowym formacie (np. Ciąg, Binarny)
Wynik
- Elastyczny, daje wydruk w dowolny ze standardowych sposobów (np. Zwrot, wydruk)
- Dopuszczalne są białe pola, końcowe i białe znaki wiodące
- Dokładność, proszę podać co najmniej 4 miejsca dziesiętne dokładności (tj. 3.1416)
Punktacja
- Najkrótszy kod wygrywa!

Przypadki testowe

Takie są moje przybliżenia rzek. Moje przybliżenia mogą być słabe lub te mogą być kiepską próbą populacji rzeki. Te obliczenia wykonałem też ręcznie; Mogłem przegapić obliczenia.

Żółta Rzeka

        ### ####           
       #   #    #          
       #       #          #
       #       #         # 
       #       #        #  
      #         #      #   
##   #          # #####    
  ##  #          #         
    ##

1.6519

rzeka Nil

1.5498

rzeka Mississippi

1.5257

TL; DR

Wyzwania te są symulacjami algorytmów, które wymagają jedynie natury i twojego mózgu (i być może pewnych zasobów wielokrotnego użytku) do przybliżenia Pi. Jeśli naprawdę potrzebujesz Pi podczas apokalipsy zombie, te metody nie marnują amunicji ! Łącznie jest dziewięć wyzwań .

— Nieliniowe Owoce
źródło

Sami nazywają się hashe. „Hashtag” jest tylko terminem oznaczającym #<tag>

— wstawkę

Zakładam, że odległość powinna być obliczona za pomocą twierdzenia Pitagorasa. Czy to jest poprawne?

— Loovjo,

Czy możemy również traktować dane wejściowe jako listę wierszy?

— Loovjo,

@Loovjo ^^ Może być, jest to geometria euklidesowa, więc jednak chcesz ją obliczyć, jest w porządku. ^ Tak, wprowadzanie danych jest elastyczne.

— NielinioweOwoce

@NonlinearFruit Thanks. To prawdopodobnie jest tak, że wersje ASCII nie są wystarczająco faliste :)

— Luis Mendo

Odpowiedzi:

MATL , 48 44 42 37 33 bajtów

Dość kilka bajtów zaoszczędzonych dzięki pomysłowi rahnema1 (odpowiedź Octave) na złożenie dwóch zwojów w jeden

t5BQ4B&vX^Z+*ssGt3Y6Z+1=*&fdwdYy/

Pobiera to dane wejściowe jako macierz binarną z ;separatorem wierszy. 1odpowiada skrótowi i 0spacji.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Oto konwerter formatu, który pobiera dane wejściowe jako tablice ;znaków 2D (ponownie jako separator) i tworzy reprezentacje łańcuchowe odpowiednich macierzy binarnych.

Wyjaśnienie

To była zabawa! Kod wykorzystuje ~~trzy~~ dwa zwoje 2D, każdy w innym celu:

1Wymagana maska byłaby do wykrywania pionowych i poziomych sąsiadów, którzy dzielą odległość
```
0 1 0
1 0 1
0 1 0
```
Chcemy jednak, aby każda para sąsiadów była wykrywana tylko raz. Więc bierzemy połowę maski (a ostatni rząd zer można usunąć):
```
0 1 0
1 0 0
```
Podobnie, aby wykryć ukośnych sąsiadów, którzy dzielą odległość sqrt(2), maska byłaby
```
1 0 1
0 0 0
1 0 1
```
ale z tego samego powodu co powyżej
```
1 0 1
0 0 0
```
Jeśli ta maska zostanie pomnożona sqrt(2)i dodana do pierwszej, dwa zwoje można zastąpić jednym zwojem połączoną maską
```
sqrt(2) 1  sqrt(2)
1       0        0
```
Punkty początkowe i końcowe są z definicji punktami tylko z jednym sąsiadem. Aby je wykryć, rozmawiamy z nimi
```
1 1 1
1 0 1
1 1 1
```
i zobacz, które punkty dają 1wynik.

Aby utworzyć połączoną maskę elementu 1, krócej jest wygenerować jej kwadrat, a następnie wziąć pierwiastek kwadratowy. Maska w punkcie 2 to predefiniowany literał.

t     % Take input matrix implicitly. Duplicate
5B    % 5 in binary: [1 0 1]
Q     % Add 1; [2 1 2]
4B    % 4 in binary: [1 0 0]
&v    % Concatenate vertically
X^    % Square root of each entry
Z+    % 2D convolution, maintaining size
*     % Multiply, to only keep results corresponding to 1 in the input
ss    % Sum of all matrix entries. This gives total distance
Gt    % Push input again. Duplicate
3Y6   % Predefined literal. This gives third mask
Z+    % 2D convolution, maintaining size
1=    % Values different than 1 are set to 0
*     % Multiply, to only keep results corresponding to 1 in the input
&f    % Push array of row indices and array of column indices of nonzeros
d     % Difference. This is the horizontal difference between start and end
wd    % Swap, difference. This is the vertical difference between start and end 
Yy    % Hypothenuse. This gives total distance in straight line
/     % Divide. Display implicitly

— Luis Mendo
źródło

Niektórzy mówili, że splot jest kluczem do sukcesu !

— flawr

Oktawa, 99 bajtów

@(a)sum((c=conv2(a,[s=[q=2^.5 1 q];1 0 1;s],'same').*a)(:))/2/{[x y]=find(c<2&c>0),pdist([x y])}{2}

metoda prawie taka sama jak odpowiedź MATL, ale tutaj jest jądro zwojów

1.41 ,  1  , 1.41
1    ,  0  , 1 
1.41 ,  1  , 1.41

to sqrt(2) =1.41jest dla diagonalnych sąsiadów i 1 dla bezpośrednich sąsiadów, więc kiedy sumujemy wartości wyniku nad rzeką, otrzymujemy dwukrotność rzeczywistej odległości.
wersja bez golfa :

a=logical([...
0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 
1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0 0 
0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]);
sq = sqrt(2);
kernel = [...
    sq ,  1  , sq
    1  ,  0  , 1 
    sq ,  1  , sq];
%2D convolution
c=conv2(a,kernel,'same').*a;
#river length
river_length = sum(c (:))/2;
#find start and end points
[x y]=find(c<2&c>0);
# distance between start and end points
dis = pdist([x y]);
result = river_length/ dis

Wypróbuj (wklej) w Octave Online

— rahnema1
źródło

Twój pomysł połączenia dwóch pierwszych zwojów w jeden pozwolił mi zaoszczędzić kilka bajtów :)

— Luis Mendo,

{[x y]=find(c<2&c>0),pdist([x y])}{2}jest cholernie sprytny !!!

— flawr

dobrą wiadomością jest to, że nie mamy ograniczeń MATLAB!

— rahnema1

@flawr Zgoda. To powinno przejść do wskazówek golfowych Octave !

— Luis Mendo,

@LuisMendo niektóre wpisy zawarte w poradach

— rahnema1

JavaScript (ES6), 178

Wprowadź jako ciąg znaków z nowymi liniami w kształcie prostokąta : każda linia jest wypełniona spacjami do tej samej długości (jak w przykładach)

r=>r.replace(/#/g,(c,i)=>([d=r.search`
`,-d,++d,-d,++d,-d,1,-1].map((d,j)=>r[i+d]==c&&(--n,s+=j&2?1:Math.SQRT2),n=1),n||(v=w,w=i)),w=s=0)&&s/2/Math.hypot(v%--d-w%d,~(v/d)-~(w/d))

Mniej golfa

r=>(
  r.replace(/#/g, // exec the following for each '#' in the string
    (c,i) => // c: current char (=#), i: current position
    ( // check in 8 directions
      // note: d starts as the offset to next row, prev x position
      // and is incremented up to offset to next row, succ x position
      // note 2: there are 2 diagonal offsets, then 2 orthogonal offsets
      //         then other 2 diagonal, then 2 more orthogonal
      [d=r.search`\n`,-d, ++d,-d, ++d,-d, 1,-1].map( // for each offset
        (d,j) => // d: current offset, j: array position (0 to 7)
        r[i+d] == c && // if find a '#' at current offset ...
          ( 
            --n, // decrement n to check for 2 neighbors or just 1
            s += j & 2 ? 1 : Math.SQRT2 // add the right distance to s
          ),
      n = 1), // n starts at 1, will be -1 if 2 neighbors found, else 0
      // if n==0 we have found a start or end position, record it in v and w
      n || (v=w, w=i)
   ),
  w=s=0), // init s and w, no need to init v
  // at the end 
  // d is the length of a line + 1
  // s is twice the total length of the river
  // v and w can be used to find the x,y position of start and end
  s/2/Math.hypot(v%--d-w%d,~(v/d)-~(w/d))
)

Test

F=
r=>r.replace(/#/g,(c,i)=>([d=r.search`\n`,-d,++d,-d,++d,-d,1,-1].map((d,j)=>r[i+d]==c&&(--n,s+=j&2?1:Math.SQRT2),n=1),n||(v=w,w=i)),w=s=0)&&s/2/Math.hypot(v%--d-w%d,~(v/d)-~(w/d))

Yellow=`        ### ####           
       #   #    #          
       #       #          #
       #       #         # 
       #       #        #  
      #         #      #   
##   #          # #####    
  ##  #          #         
    ##                     `

Nile=`         #     
         #     
          #    
           #   
           #   
          #    
         #     
        #      
        #  #   
        # # #  
         #  #  
            #  
          ##   
         #     
         #     
        #      
        #      
       #       
       #       
       #       
       #       
   #  #        
  # ##         
  #            
  #            
   #           
    #          
     #         
     #         
      #        
     #         
    #          
     #         
      #        `

Missi=` ###            
#   #           
     #          
     #          
    #           
   #            
  #             
  #             
  #             
   #            
    #           
     #          
      #         
       #        
        #       
        #       
        #       
         #      
          #     
           #    
          #     
       ###      
      #         
       #        
      #         
     #          
    #           
    #           
    #           
    #           
     #          
      ##        
        #       
        #       
         ##     
           ##   
             ## 
               #
              # 
             #  
            #   
           #    
          #     
         #      
        #       
        #       
        #       
        #       
        #       
       #        
      #         
     #          
      #         
       #        
        ####    
            #   
             #  `
console.log('Yellow River',F(Yellow))
console.log('Nile River',F(Nile))
console.log('Mississippi River',F(Missi))

Rozwiń fragment kodu

— edc65
źródło