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.

NonlinearFruit

Posted 2016-12-26T15:41:10.627

Reputation: 5 334

3They're called hashes on their own. "Hashtag" is just the term for an inline tag signified with #<tag> – FlipTack – 2016-12-26T15:42:37.483

1I assume that the distance should be calculated using the Pythagorean theorem. Is this correct? – Loovjo – 2016-12-26T15:47:33.263

Also, can we take the input as a list of lines? – Loovjo – 2016-12-26T15:48:22.680

@Loovjo ^^ It can be, it is Euclidean geometry so however you want to calculate it is fine. ^ Yes, input is flexible. – NonlinearFruit – 2016-12-26T15:49:31.443

Can the input be a matrix of zeros and ones? – Luis Mendo – 2016-12-26T16:55:42.677

@LuisMendo Yes, that would be fine – NonlinearFruit – 2016-12-26T19:13:53.120

Can we return a rational number? – LegionMammal978 – 2016-12-26T21:25:02.323

Does the paper really say pi? The outputs look more similar to pi/2 – Luis Mendo – 2016-12-26T22:58:39.173

@LuisMendo I believe it does say pi (but I don't have access to it anymore). Several articles about this paper say that the average sinuosity is 3.14. This particular article suggests that, empirically, the average sinuosity of rivers is around 1.94.

– NonlinearFruit – 2016-12-27T00:24:39.187

1@NonlinearFruit Thanks. Then it's probably that the ASCII versions are not sinuous enough :) – Luis Mendo – 2016-12-27T00:25:48.740

@LegionMammal978 Accuracy, please provide at least 4 decimal places of accuracy – NonlinearFruit – 2016-12-27T00:36:29.267

Answers

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:

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

Luis Mendo

Posted 2016-12-26T15:41:10.627

Reputation: 87 464

2Some people used to say, that convolution is the key to success! – flawr – 2016-12-26T21:25:19.857

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

rahnema1

Posted 2016-12-26T15:41:10.627

Reputation: 5 435

Your idea to lump the first two convolutions into one saved me a few bytes :) – Luis Mendo – 2016-12-26T23:18:19.500

{[x y]=find(c<2&c>0),pdist([x y])}{2} is so damn clever!!! – flawr – 2016-12-26T23:32:02.550

a good news is that we do not have restrictions of MATLAB! – rahnema1 – 2016-12-26T23:46:52.440

@flawr Agreed. That should go to the Octave golfing tips!

– Luis Mendo – 2016-12-27T00:31:06.193

@LuisMendo some entries included in tips – rahnema1 – 2016-12-27T11:00:47.517

@rahnema1 Great! Since the tips question asks for one tip per answer, I suggest you move the rows part to a new answer. The rest of the current answer can be left as is, because it's all related to indexing in Octave – Luis Mendo – 2016-12-27T13:02:19.397

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

edc65

Posted 2016-12-26T15:41:10.627

Reputation: 31 086

Natural Pi #2 - River

Goal

Simulation

Specification

Test Cases

TL;DR

Answers

MATL, 48 44 42 37 33 bytes

Explanation

Octave, 99 bytes

JavaScript (ES6), 178