태그 보관물: approximation

approximation

내추럴 파이 # 2-강

해시 열이있는 문자열이 주어지면 전체 길이를 계산하고 처음부터 끝까지의 거리로 나눕니다.

시뮬레이션

우리는 무엇을 시뮬레이션하고 있습니까? 이 논문 에 따르면 시작과 끝 사이의 거리에 대한 강의 길이의 비율은 대략 Pi입니다! (이것은 경험적으로 반증되었을 수도 있지만 데이터를 찾을 수 있으며이 과제에 대해서는 사실이라고 가정합니다).

우리는 이것을 어떻게 시뮬레이트합니까?

  • 공백과 해시 문자열 입력
  • 각 해시에는 두 개의 다른 해시가 있습니다.
    • 첫 번째와 마지막 해시를 제외하고는 1 만 있습니다.
  • 각 문자는 격자 점에 있습니다 (x, y)
  • x 줄의 문자 색인
    • 예를 들면 c4 성격이다0123c567
  • y 캐릭터의 줄 번호입니다
    • 예를 들어 c세 번째 줄에 있습니다.
      0line
      1line
      2line
      3c...
  • 인접한 해시 사이의 거리를 합한 다음 호출하십시오. S
  • 첫 번째 해시와 마지막 해시 사이의 거리를 가져 와서 D
  • 반환 S/D

여기에 이미지 설명을 입력하십시오

사양

  • 입력
    • 유연성, 표준 방식 (예 : 함수 매개 변수, STDIN) 및 표준 형식 (예 : 문자열, 이진)으로 입력
  • 산출
    • 유연하고 표준적인 방법으로 출력합니다 (예 : 반환, 인쇄)
    • 공백, 후행 및 선행 공백이 허용됩니다.
    • 정확도, 정밀도의 적어도 4 소수점을 제공하십시오 (예 3.1416)
  • 채점
    • 최단 코드 승리!

테스트 사례

이것들은 강의 근사치입니다. 나의 근사치가 나쁘거나 이것들은 강 인구에 대한 저조한 ​​표본이다. 또한 저는이 계산을 손으로했습니다. 계산을 놓칠 수 있습니다.

황하

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

나일 강

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

미시시피 강

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

TL; DR

이러한 과제는 Pi를 근사화하기 위해 자연과 두뇌 (및 일부 재사용 가능한 리소스) 만 필요한 알고리즘 시뮬레이션입니다. 좀비 종말 중에 Pi가 정말로 필요하다면,이 방법들은 탄약을 낭비 하지 않습니다 ! 총 9 가지 과제 가 있습니다 .



답변

MATL , 48 44 42 37 33 바이트

rahnema1의 아이디어 (옥타브 답변) 덕분에 두 개의 회선이 하나로 축소 되어 상당히 많은 바이트가 절약 되었습니다.

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

이것은 입력 ;을 행 분리 자로 이진 행렬 로 가져옵니다. 1해시와 0공간에 해당 합니다.

온라인으로 사용해보십시오! 또는 모든 테스트 사례를 확인하십시오 .

다음 은 입력을 2D char 배열 ( ;분리 자로 사용)로 가져와 해당 이진 행렬의 문자열 표현을 생성 하는 형식 변환기입니다 .

설명

이것은 재미 있었다! 이 코드는 서로 다른 목적을 위해 가지 2D 컨볼 루션을 사용합니다 .

  1. 의 거리를 제공하는 수직 및 수평 이웃을 감지하려면 1필요한 마스크는 다음과 같습니다.

    0 1 0
    1 0 1
    0 1 0
    

    그러나 각 이웃 은 한 번만 탐지 되기를 원합니다 . 따라서 우리는 마스크의 절반을 취합니다 (그리고 마지막 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
    
  2. 시작점과 끝점은 정의상 이웃이 하나 뿐인 점입니다. 우리가 그것들을 발견하기 위해

    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


답변

옥타브, 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 위한 것이고 직접적인 이웃을위한 것입니다. 그래서 우리가 강 너머로 결과 값을 합하면 실제 거리의 두 배가됩니다.
ungolfed 버전 :

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 에서 사용해보십시오 (붙여 넣기).


답변

자바 스크립트 (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))


답변