골
해시 열이있는 문자열이 주어지면 전체 길이를 계산하고 처음부터 끝까지의 거리로 나눕니다.
시뮬레이션
우리는 무엇을 시뮬레이션하고 있습니까? 이 논문 에 따르면 시작과 끝 사이의 거리에 대한 강의 길이의 비율은 대략 Pi입니다! (이것은 경험적으로 반증되었을 수도 있지만 데이터를 찾을 수 있으며이 과제에 대해서는 사실이라고 가정합니다).
우리는 이것을 어떻게 시뮬레이트합니까?
- 공백과 해시 문자열 입력
- 각 해시에는 두 개의 다른 해시가 있습니다.
- 첫 번째와 마지막 해시를 제외하고는 1 만 있습니다.
- 각 문자는 격자 점에 있습니다
(x, y)
x
줄의 문자 색인- 예를 들면
c
4 성격이다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
필요한 마스크는 다음과 같습니다.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
-
시작점과 끝점은 정의상 이웃이 하나 뿐인 점입니다. 우리가 그것들을 발견하기 위해
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))