Pi Natural # 2 - Río

12

Objetivo

Dada una cadena con un tren de hashes, calcule su longitud total y divida por la distancia de principio a fin.

Simulación

¿Qué estamos simulando? Según este documento , ¡la relación entre la longitud de un río y la distancia entre el inicio y el final es aproximadamente Pi! (Esto puede haber sido refutado empíricamente, pero pude encontrar los datos y para este desafío asumiremos que es cierto).

¿Cómo estamos simulando esto?

  • Tome una entrada de cadena de espacios en blanco y hashes
  • Cada hash tendrá otros dos adyacentes.
    • Con la excepción del primer y último hash que tendrá solo 1
  • Cada personaje se encuentra en un punto reticular (x, y)
  • x es el índice del personaje en su línea
    • por ejemplo, ces el cuarto personaje en0123c567
  • y es el número de línea del personaje
    • Por ejemplo, cestá en la tercera línea:
      0line
      1line
      2line
      3c...
  • Suma las distancias entre hashes adyacentes, llámalo S
  • Toma la distancia entre el primer y el último hash, llámalo D
  • Regreso S/D

ingrese la descripción de la imagen aquí

Especificación

  • Entrada
    • Flexible, tome la entrada en cualquiera de las formas estándar (por ejemplo, parámetro de función, STDIN) y en cualquier formato estándar (por ejemplo, cadena, binario)
  • Salida
    • Flexible, dé salida en cualquiera de las formas estándar (por ejemplo, devolución, impresión)
    • El espacio en blanco, el espacio en blanco final y posterior es aceptable
    • Precisión, proporcione al menos 4 decimales de precisión (es decir 3.1416)
  • Puntuación
    • ¡El código más corto gana!

Casos de prueba

Estas son mis aproximaciones de los ríos. Mis aproximaciones pueden ser pobres o estas pueden ser una muestra pobre de la población del río. Además, hice estos cálculos a mano; Podría haber calculado la señorita.

Río Amarillo

        ### ####           
       #   #    #          
       #       #          #
       #       #         # 
       #       #        #  
      #         #      #   
##   #          # #####    
  ##  #          #         
    ##                     
1.6519

el rio Nilo

         #     
         #     
          #    
           #   
           #   
          #    
         #     
        #      
        #  #   
        # # #  
         #  #  
            #  
          ##   
         #     
         #     
        #      
        #      
       #       
       #       
       #       
       #       
   #  #        
  # ##         
  #            
  #            
   #           
    #          
     #         
     #         
      #        
     #         
    #          
     #         
      #        
1.5498

río Mississippi

 ###            
#   #           
     #          
     #          
    #           
   #            
  #             
  #             
  #             
   #            
    #           
     #          
      #         
       #        
        #       
        #       
        #       
         #      
          #     
           #    
          #     
       ###      
      #         
       #        
      #         
     #          
    #           
    #           
    #           
    #           
     #          
      ##        
        #       
        #       
         ##     
           ##   
             ## 
               #
              # 
             #  
            #   
           #    
          #     
         #      
        #       
        #       
        #       
        #       
        #       
       #        
      #         
     #          
      #         
       #        
        ####    
            #   
             #  
1.5257

TL; DR

Estos desafíos son simulaciones de algoritmos que solo requieren la naturaleza y su cerebro (y tal vez algunos recursos reutilizables) para aproximarse a Pi. Si realmente necesitas Pi durante el apocalipsis zombie, ¡estos métodos no desperdician munición ! Hay nueve desafíos en total.

Fruta no lineal
fuente
3
Se llaman hashes por su cuenta. "Hashtag" es el término para una etiqueta en línea con el significado#<tag>
FlipTack
1
Supongo que la distancia debe calcularse utilizando el teorema de Pitágoras. ¿Es esto correcto?
Loovjo
Además, ¿podemos tomar la entrada como una lista de líneas?
Loovjo
@Loovjo ^^ Puede ser, es geometría euclidiana, así que, sin embargo, si quieres calcularlo, está bien. ^ Sí, la entrada es flexible.
NonlinearFruit
1
@NonlinearFruit Gracias. Entonces es probable que las versiones ASCII no sean lo suficientemente sinuosas :)
Luis Mendo

Respuestas:

6

MATL , 48 44 42 37 33 bytes

Muchos bytes guardados gracias a la idea de rahnema1 (respuesta de octava) de colapsar dos convoluciones en una

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

Esto toma la entrada como una matriz binaria, con un ;separador de filas. 1corresponde al hash y 0al espacio.

Pruébalo en línea! O verificar todos los casos de prueba .

Aquí hay un convertidor de formato que toma entradas como matrices de caracteres 2D (nuevamente, con un ;separador) y produce representaciones de cadena de las matrices binarias correspondientes.

Explicación

¡Esto fue divertido! El código usa tres dos convoluciones 2D, cada una para un propósito diferente:

  1. Para detectar vecinos verticales y horizontales, que contribuyen a una distancia de 1, la máscara requerida sería

    0 1 0
    1 0 1
    0 1 0
    

    Pero solo queremos que cada par de vecinos sea detectado una vez. Entonces tomamos la mitad de la máscara (y la última fila de ceros se puede eliminar):

    0 1 0
    1 0 0
    

    Del mismo modo, para detectar vecinos diagonales, que contribuyen a una distancia de sqrt(2), la máscara sería

    1 0 1
    0 0 0
    1 0 1
    

    pero por el mismo razonamiento que el anterior se convierte

    1 0 1
    0 0 0
    

    Si esta máscara se multiplica por sqrt(2)y se agrega a la primera, las dos circunvoluciones se pueden reemplazar por una con la máscara combinada

    sqrt(2) 1  sqrt(2)
    1       0        0
    
  2. Los puntos de inicio y fin son, por definición, los puntos con un solo vecino. Para detectarlos nos involucramos con

    1 1 1
    1 0 1
    1 1 1
    

    y ver qué puntos dan 1como resultado.

Para producir la máscara combinada del elemento 1 es más corto generar su cuadrado y luego sacar la raíz cuadrada. La máscara en el elemento 2 es un literal predefinido.

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
fuente
2
Algunas personas decían que la convolución es la clave del éxito .
flawr
4

Octava, 99 bytes

@(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}

casi el mismo método que la respuesta MATL pero aquí el núcleo de convoluciones es

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

eso sqrt(2) =1.41es para vecinos diagonales y 1 para vecinos directos, de modo que cuando sumamos valores del resultado sobre el río obtenemos el doble de la distancia real.
versión sin golf :

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 

Pruébalo (pégalo) en Octave Online

rahnema1
fuente
Su idea de agrupar las dos primeras circunvoluciones en una me salvó unos pocos bytes :)
Luis Mendo
{[x y]=find(c<2&c>0),pdist([x y])}{2}es tan inteligente !!!
falla
¡Una buena noticia es que no tenemos restricciones de MATLAB!
rahnema1
2
@flawr De acuerdo. ¡Eso debería ir a los consejos de golf de Octave !
Luis Mendo
@LuisMendo algunas entradas incluidas en los consejos
rahnema1
2

JavaScript (ES6), 178

Ingrese como una cadena con nuevas líneas en forma rectangular : cada línea rellena con espacios a la misma longitud (como en los ejemplos)

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))

Menos golf

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))
)

Prueba

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))

edc65
fuente