Natural Pi # 2 - Река

Цель

Получив строку с последовательностью хэшей, вычислите ее общую длину и разделите на расстояние от начала до конца.

моделирование

Что мы моделируем? Согласно этой статье , отношение длины реки к расстоянию между началом и концом составляет приблизительно Pi! (Возможно, это было опровергнуто эмпирически, но я мог бы найти данные, и для этого вызова мы предположим, что это правда).

Как мы моделируем это?

Возьмите строку ввода пробела и хэшей
Каждый хеш будет иметь два других смежных с ним
- За исключением первого и последнего хеша, который будет иметь только 1
Каждый символ лежит на точке решетки (x, y)
x это индекс персонажа в его строке
- например, c4-й символ в0123c567
y номер строки персонажа
- Например, cнаходится на 3-й строке:

      0line
      1line
      2line
      3c...

Суммируйте расстояния между соседними хешами, назовите это S
Возьмите расстояние между первым и последним хешами, назовите его D
Возвращение S/D

Спецификация

вход
- Гибкость, принимать входные данные любым из стандартных способов (например, параметр функции, STDIN) и в любом стандартном формате (например, String, Binary)
Выход
- Гибкость, вывод на печать любым из стандартных способов (например, возврат, печать)
- Пробел, конечный и ведущий пробел приемлем
- Точность, укажите не менее 4 знаков после запятой (т.е. 3.1416)
счет
- Самый короткий код выигрывает!

Тестовые случаи

Это мои приближения рек. Мои приближения могут быть плохими, или они могут быть плохой выборкой населения реки. Кроме того, я сделал эти вычисления вручную; Я мог бы рассчитать мисс.

Желтая река

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

1.6519

река Нил

1.5498

Река Миссисипи

1.5257

TL; DR

Эти проблемы представляют собой симуляции алгоритмов, которые требуют только природы и вашего мозга (и, возможно, некоторых ресурсов многократного использования) для приближения Pi. Если вам действительно нужен Пи во время апокалипсиса зомби, эти методы не теряют патронов ! Всего девять задач .

code-golf string math pi approximation NonlinearFruit
источник

Они называются хешами сами по себе. «Hashtag» - это просто термин для встроенного тега, обозначенного#<tag>

FlipTack

Я предполагаю, что расстояние должно быть рассчитано с использованием теоремы Пифагора. Это верно?

Loovjo

Кроме того, мы можем принять входные данные в виде списка строк?

Loovjo

@Loovjo ^^ Может быть, это евклидова геометрия, поэтому, как бы вы ни рассчитывали, все в порядке. ^ Да, ввод гибкий.

НелинейныйФрукт

@NonlinearFruit Спасибо. Тогда, вероятно, версии ASCII недостаточно извилистые :)

Luis Mendo

Ответы:

MATL , 48 44 42 37 33 байта

Сохранено довольно много байтов благодаря идее rahnema1 (октавский ответ) о том, чтобы свести две извилины в одну

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

Это принимает входные данные в виде двоичной матрицы с ;разделителем строк. 1соответствует хешу и 0пространству.

Попробуйте онлайн! Или проверьте все тестовые случаи .

Вот преобразователь формата, который принимает входные данные в виде двумерных массивов символов (опять же, с ;разделителем) и создает строковые представления соответствующих двоичных матриц.

объяснение

Это было весело! В коде используются ~~три~~ две 2D-свертки, каждая из которых предназначена для разных целей:

Для обнаружения вертикальных и горизонтальных соседей, которые дают расстояние 1, требуемая маска будет
```
0 1 0
1 0 1
0 1 0
```
Но мы хотим, чтобы каждая пара соседей была обнаружена только один раз. Итак, мы берем половину маски (и последний ряд нулей можно удалить):
```
0 1 0
1 0 0
```
Точно так же, чтобы обнаружить диагональных соседей, которые вносят расстояние sqrt(2), маска будет
```
1 0 1
0 0 0
1 0 1
```
но по тем же соображениям, что и выше, становится
```
1 0 1
0 0 0
```
Если эту маску умножить sqrt(2)и добавить к первой, две свертки можно заменить одной сверткой с комбинированной маской
```
sqrt(2) 1  sqrt(2)
1       0        0
```
Начальная и конечная точки по определению являются точками только с одним соседом. Чтобы обнаружить их, мы сворачиваем с
```
1 1 1
1 0 1
1 1 1
```
и посмотреть, какие точки дают 1в результате.

Чтобы создать комбинированную маску из предмета 1, короче создать ее квадрат, а затем взять квадратный корень. Маска в пункте 2 является предопределенным литералом.

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

Луис Мендо
источник

Некоторые люди говорили, что свертка является ключом к успеху !

flawr

Октава, 99 байт

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

почти тот же метод, что и ответ MATL, но здесь ядро сверток

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

это sqrt(2) =1.41для диагональных соседей и 1 для прямых соседей, поэтому, когда мы суммируем значения результата по реке, мы получаем двойное реальное расстояние.
версия без золота :

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

Попробуйте (вставьте) это в Octave Online

rahnema1
источник

Ваша идея объединить первые две свертки в одну сэкономила мне несколько байтов :)

Луис Мендо

{[x y]=find(c<2&c>0),pdist([x y])}{2}чертовски умный !!!

flawr

Хорошей новостью является то, что у нас нет ограничений MATLAB!

rahnema1

@flawr Согласен. Это должно идти к подсказкам гольфа Октавы !

Луис Мендо

@LuisMendo некоторые записи включены в советы

rahnema1

JavaScript (ES6), 178

Ввод в виде строки с символами новой строки в прямоугольной форме : каждая строка дополняется пробелами одинаковой длины (как в примерах)

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

Меньше гольфа

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

Тестовое задание

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
источник