Natural Pi #2 - River

Question

Goal

Given an string with a train of hashes, calculate its total length and divide by the distance from start to finish.

Simulation

What are we simulating? According to this paper, the ratio of the length of a river to the distance between start and end is approximately Pi! (This may have been disproved empirically, but I could find the data and for this challenge we'll assume it is true).

How are we simulating this?

• Take a string input of whitespace and hashes
• Each hash will have two others adjacent to it
  • With the exception of the first and last hash which will have only 1
• Each character lies on a lattice point (x, y)
• x is the character's index in its line
  • eg c is the 4th character in 0123c567
• y is the character's line number
  • eg c is on the 3rd line:

 0line
 1line
 2line
 3c...

• Sum the distances between adjacent hashes, call it S
• Take the distance between the first and last hashes, call it D
• Return S/D

enter image description here

Specification

• Input
  • Flexible, take input in any of the standard ways (eg function parameter,STDIN) and in any standard format (eg String, Binary)
• Output
  • Flexible, give output in any of the standard ways (eg return, print)
  • White space, trailing and leading white space is acceptable
  • Accuracy, please provide at least 4 decimal places of accuracy (ie 3.1416)
• Scoring
  • Shortest code wins!

Test Cases

These are my approximations of the rivers. My approximations might be poor or these my be poor sample of the river population. Also, I did this calculations by hand; I could have miss calculated.

Yellow River

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

1.6519

Nile River

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

1.5498

Mississippi River

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

1.5257

TL;DR

These challenges are simulations of algorithms that only require nature and your brain (and maybe some re-usable resources) to approximate Pi. If you really need Pi during the zombie apocalypse, these methods don't waste ammo! There are nine challenges total.

• FlipTack: They're called hashes on their own. "Hashtag" is just the term for an inline tag signified with #<tag>
• xenia: I assume that the distance should be calculated using the Pythagorean theorem. Is this correct?
• xenia: Also, can we take the input as a list of lines?
• NonlinearFruit: @Loovjo ^^ It can be, it is Euclidean geometry so however you want to calculate it is fine. ^ Yes, input is flexible.
• Luis Mendo: @NonlinearFruit Thanks. Then it's probably that the ASCII versions are not sinuous enough :)

Answer 1

MATL, (削除) 48 (削除ここまで) (削除) 44 (削除ここまで) (削除) 42 (削除ここまで) (削除) 37 (削除ここまで) 33 bytes

Quite a few bytes saved thanks to rahnema1's idea (Octave answer) of collapsing two convolutions into one

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

This takes the input as a binary matrix, with ; as row separator. 1 corresponds to hash and 0 to space.

Try it online! Or verify all test cases.

Here's a format converter that takes inputs as 2D char arrays (again, with ; as separator) and produces string representations of the corresponding binary matrices.

Explanation

This was fun! The code uses (削除) three (削除ここまで) two 2D-convolutions, each for a different purpose:

1. To detect vertical and horizontal neighbours, which contribute a distance of 1, the required mask would be

   0 1 0
   1 0 1
   0 1 0
   

   But we only want each pair of neighbours to be detected once. So we take half the mask (and the last row of zeros can be removed):

   0 1 0
   1 0 0
   

   Similarly, to detect diagonal neighbours, which contribute a distance of sqrt(2), the mask would be

   1 0 1
   0 0 0
   1 0 1
   

   but by the same reasoning as above it becomes

   1 0 1
   0 0 0
   

   If this mask is multiplied by sqrt(2) and added to the first, the two convolutions can be replaced by one convolution with the combined mask

   sqrt(2) 1 sqrt(2)
   1 0 0
   

2. Start and end points are, by definition, the points with only one neighbour. To detect them we convolve with

   1 1 1
   1 0 1
   1 1 1
   

   and see which points give 1 as result.

To produce the combined mask of item 1 it's shorter to generate its square and then take the square root. The mask in item 2 is a predefined literal.

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: Some people used to say, that convolution is the key to success!

Answer 2

Octave, 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}

nearly same method as MATL answer but here kernel of convolutions is

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

that sqrt(2) =1.41 is for diagonal neighbors and 1 is for direct neighbors so when we sum values of the result over the river we get twice the real distance.
ungolfed version:

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 

Try (paste) it on Octave Online

• Luis Mendo: Your idea to lump the first two convolutions into one saved me a few bytes :)
• flawr: {[x y]=find(c<2&c>0),pdist([x y])}{2} is so damn clever!!!
• rahnema1: a good news is that we do not have restrictions of MATLAB!
• Luis Mendo: @flawr Agreed. That should go to the Octave golfing tips!
• rahnema1: @LuisMendo some entries included in tips

Answer 3

JavaScript (ES6), 178

Input as a string with newlines in rectangular form : each line padded with spaces to the same length (as in the examples)

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

Less golfed

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