# Natural Pi #2 - River

## 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 ## 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.

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

# MATL, 48444237 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.

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

• Some people used to say, that convolution is the key to success! – flawr Dec 26 '16 at 21:25

# 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

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

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