ASCII Arc Length: How long is a piece of string?

3

0

Given an ASCII representation of a piece of string, determine its length.

Input

An multi-line ASCII rendering of a piece of string, which runs from top to bottom, with one 'node' (corner) on each line of input. The delimiter may be assumed to be CR, LF, CRLF, or LFCR. Input may be accepted from STDIN, Command Line Argument, Function Parameter, or whatever daft method your language of choice necessitates if none of the prior are applicable.

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

Each line in the context of the previous tells you the position of one of the nodes on the string. The first line always has exactly one hash #, so the position is trivially found. Each following line has a hash '#' on the node itself, and on all calls which must be included to make the string 'complete' (attached to itself). All positions will be between 0 and 9 inclusive, but the difference is what realy matters.

For example, the string defined by the sequence 1, 3, 6, 5, 1, 3, 4 has the following nodes:

 #
   #
      #
     #
 #
   #
 #
     #
    #

Which we must join up on a line by line basis starting from the top (nodes marked with X for clarity, they will be hashes in actual imputs). This means, the first line has no hashes, and each following line has exactly as many hashes as are rquired to 'connect' the previous node to the current with hashes. This can be thought of as putting a hash in every space between the two nodes (on the lower line) and then removing any that appear on the line above. Example:

 X
  #X
    ##X
     X
 X###
   X
 X#
   ##X
    X

There will be no fewer than 2 lines, and no more than 100. The input will be padded with spaces to form a rectangle of width 10 (excluding the line delimiters). You may require a trailing new-line be present or absent, but declare any such requirements in your answer.

Computing the Arc Length

You must output the arc length of this string. You compute the arc length by taking the distances between each consequtive nodes. The distance between one node and the next is sqrt(d^2 + 1) where d is the difference in position (that is, the current position minus the previous). For example, the sequence 4, 8, 2, 3, 4, 4 has differences 4, -6, 1, 1, 0, which gives distances (rounded to 2 dp) 4.12, 6.08, 1.41, 1.41, 1 by squaring, adding one, and square-rooting. The arc length is then the sum of these distances, 14.02.

You must reduce the result of the square-root to 2 decimal places before summing (this is to allow sqrt tables and make answers consistent/comparable across systems; see below).

Using the input example at the top`

  #    2 -1  1.41
 #     1 +0  1.00
 #     1 +4  4.12
  #### 5 -5  5.10
##     0 +3  3.16
  ##   3 -2  2.24
 #     1 +2  2.24
  ##   3 -1  1.41
  #    2

            20.68 (total)

Output

You must output the arc length as exactly one number, or a decimal string represenation with 2 decimal places of precision. Numerical output must be rounded, but I'm not going to quibble about minute floating point inaccuracies.

SQRT Table

This is a table of the rounded squareroots you must conform to. You can either use this table itself, or verify that your system conforms to the results.

1  1.00
2  1.41
5  2.24
10 3.16
17 4.12
26 5.10
37 6.08
50 7.07
65 8.06
82 9.06

Powershell to produce this table:

0..9 | % {"" + ($_ * $_ + 1) + " " + [System.Math]::Sqrt($_ * $_ +1).ToString("0.00")}

Test Cases

Input:

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

Output: 20.68

Input:

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

Output: 49.24

Input:

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

Output: 44.34

Test Code

A larger test case and a C# solver and example generator can be found as a Gist.

Victory Criterion

This is code-golf, the shortest code will win.

VisualMelon

Posted 2017-06-02T10:14:18.647

Reputation: 3 810

"where d is the difference in position" - Can you elaborate on that? Maybe it's just too early but, reading through your examples, I can't see how you're arriving at the d for each value in the sequences. – Shaggy – 2017-06-02T11:20:30.823

@shaggy I thought the examples would be sufficient, but I'll try to come up with some sensible wording. They are the literally the position minus the previous position. – VisualMelon – 2017-06-02T11:55:19.983

@user202729 sorry for confusion, thought I'd explained that better... (made some edits that hopefully clarify). B is correct, you can think of it as filling in the hashes, starting at the top, and working your way down. – VisualMelon – 2017-06-02T12:46:05.543

Answers

1

JavaScript (ES6), 158 bytes

-1 byte thanks to @VisualMelon

s=>s.split`
`.map(s=>(s=s.replace(/./g,(m,i)=>m>" "?i:""),n=s[0]>n?s.slice(-1):s[0]),n=p=0).reduce((t,v,i)=>(r=i&&t+(((p-v)**2+1)**.5*100+.5|0)/100,p=v,r),0)

Output is sometimes not exact (0.999 instead of 1) due to floating-point imprecision, but rounding was done part-way through the steps in order to match the square root table.

Test Snippet

Note that trailing spaces on each line are ignored, so they can be omitted from the input.

f=
s=>s.split`
`.map(s=>(s=s.replace(/./g,(m,i)=>m>" "?i:""),n=s[0]>n?s.slice(-1):s[0]),n=p=0).reduce((t,v,i)=>(r=i&&t+(((p-v)**2+1)**.5*100+.5|0)/100,p=v,r),0)
<textarea id=I rows=15 cols=12></textarea><br>
<button onclick="O.value=f(I.value)">Run</button> <input id=O disabled>

Justin Mariner

Posted 2017-06-02T10:14:18.647

Reputation: 4 746

Input and output look fine to me! I'm dreadful at JS, but do you need d? Would (p-v)**2 not work? Unless another surprise answer pops out of the ether, I'll accept this in a couple of days. – VisualMelon – 2017-06-15T17:37:02.450

@VisualMelon Yeah, I was stuck on using d*d since that was shorter than d**2. Will update when I'm at a computer. – Justin Mariner – 2017-06-15T17:40:08.790