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

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

Community · Accepted Answer · 2017-04-13 12:39:12Z

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

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

Community · Accepted Answer · 2017-04-13 12:39:07Z

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

edc65 · Accepted Answer · 2016-12-26 21:54:27Z

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

Stack Exchange Network

current community

your communities

more stack exchange communities

Natural Pi #2 - River

Goal

Simulation

Specification

Test Cases

TL;DR

3 Answers 3

MATL, 48 44 42 37 33 bytes

Explanation

Octave, 99 bytes

JavaScript (ES6), 178

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf string math pi approximation or ask your own question.

Linked

Hot Network Questions

Natural Pi #2 - River

Goal

Simulation

Specification

Test Cases

TL;DR

3 Answers 3

MATL, 48 44 42 37 33 bytes

Explanation

Octave, 99 bytes

JavaScript (ES6), 178

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf string math pi approximation or ask your own question.

Linked

Related

Hot Network Questions