How lit is this mountain?

Question

A mountain is defined to be a set of line segments whose first point has coordinates (0,a) where a > 0, and whose last point has coordinates (b,0), where b > 0. All intermediate points have a y-coordinate (ordinate) strictly greater than 0. You are given the points on the mountain sorted in ascending order of x-coordinate (abscissa). Note that two points can have the same x-coordinate, producing a vertical segment of the mountain. If you are given two points with the same x-coordinate, they should be connected in the order they are given. In addition, there can be horizontal segments of the mountain These horizontal segments are not lit, no matter what. All coordinates are nonnegative integers.

The question: what is the total length of the mountain that would be lit, assuming the sun is an infinite vertical plane of light located to the right of the mountain? This number does not need to be rounded, but if it is rounded, include at least four decimal places. I have included a picture: Here, the lines that are bolded represent the segments that are lit. Note that in the input, P appears before Q (PQ is a vertical line segment) so the previous point is connected to P and not Q.

You may take input in any reasonable format, like a list of lists, a single list, a string, etc.

Test case:

(0,3000)
(500, 3500)
(2500, 1000)
(5000,5000)
(9000,2000)
(9000,3500)
(10200,0)

Output: 6200.0000

There are two lit-up segments here, as shown in this image: The first one has length 5000/2 = 2500 and the second one has length 3700.

This is code-golf, so the shortest answer in bytes wins.

Answer 1

Python 2,  134 131 128 124 120 117 109  107 bytes

p=input();s=0
for X,Y in p[1:]:x,y=p.pop(0);n=y-max(zip(*p)[1]);s+=n*(1+((X-x)/(y-Y))**2)**.5*(n>0)
print s

Try it online!

Takes input as a list of tuples / two-element lists of floating-point numbers.

Explanation

We basically iterate through the pairs of points in the graph, and if \$y_1 > y_2\$, then we calculate how much of the line is exposed to light. The pairwise iteration is performed with a for loop to get the next point, \$(x_2, y_2)\$, popping the first element in the list each time to retrieve the current point, \$(x_1, y_1)\$.

Maths – What part of the line segment is exposed to light?

Let \$(x_1, y_1)\$ be the coordinates of the current point. Let \$y_{max}\$ be the maximum height of a point after the current one (local maxima after the current point) and \$(x_2, y_2)\$ be the coordinates of the next point. In order to calculate the length exposed to the sun, \$L\$, we ought to find \$x_3\$, as shown in the diagram. Naturally, if \$y_1 \le y_{max}\$, the segment is not exposed to light at all.

In the triangle formed, the line segment of length \$x_3\$ is parallel to the base, of length \$x_2 - x_1\$, so all three angles are congruent. Therefore, from the Fundamental Theorem of Similarity (case Angle-Angle), we can deduce that \$\frac{x_3}{x_2 - x_1} = \frac{y_1-y_{max}}{y_1}\$. Hence, \$x_3 = \frac{(y_1-y_{max})(x_2 - x_1)}{y_1}\$. Then, we can apply the Pythagorean Theorem to find that:

$$L = \sqrt{(y_1-y_{max})^2+x_3^2}$$

By joining the two formulas, we arrive at the following expression, which is the core of this approach:

$$L = \sqrt{(y_1-y_{max})^2+\left(\frac{(y_1-y_{max})(x_2 - x_1)}{y_1}\right)^2}$$ $$L = \sqrt{(y_1-y_{max})^2\left(1+\frac{(x_2 - x_1)^2}{y_1^2}\right)}$$

Code – How does it work?

p=input();s=0                             # Assign p and s to the input and 0 respectively.
for X,Y in p[1:]:                         # For each point (X, Y) in p with the first
                                          # element removed, do:
    x,y=p.pop(0)                          # Assign (x, y) to the first element of p and
                                          # remove them from the list. This basically
                                          # gets the coordinates of the previous point.
    n=y-max(zip(*p)[1])                   # Assign n to the maximum height after the
                                          # current one, subtracted from y.
    s+=n*(1+((X-x)/(y-Y))**2)**.5         # Add the result of the formula above to s.
                                 *(n>0)   # But make it null if n < 0 (if y is not the
                                          # local maxima of this part of the graph).
print s                                   # Output the result, s.

Changelog

• Gradually optimised the formula for golfing purposes.

• Saved 1 byte thanks to FlipTack.

• Saved 2 bytes by removing the unnecessary condition that y>Y, since if the local maxima of the Y-coordinate after the current point subtracted from y is positive, then that condition is redundant. This unfortunately invalidates FlipTack’s golf, though.

• Saved 3 bytes by changing the algorithm a bit: instead of having a counter variable, incrementing it and tailing the list, we remove the first element at each iteration.

• Saved 8 bytes thanks to ovs; changing (x,y),(X,Y) in the loop condition with a list.pop() technique.

• Saved 2 bytes thanks to Ørjan Johansen (optimised the formula a little bit).

Answer 2

JavaScript, 97 bytes

a=>a.reduceRight(([p,q,l=0,t=0],[x,y])=>[x,y,y>t?(y-t)/(s=y-q)*Math.hypot(x-p,s)+l:l,y>t?y:t])[2]

f=a=>a.reduceRight(([p,q,l=0,t=0],[x,y])=>[x,y,y>t?(y-t)/(s=y-q)*Math.hypot(x-p,s)+l:l,y>t?y:t])[2];
t=[[0, 3000], [500, 3500], [2500, 1000], [5000, 5000], [9000, 2000], [9000, 3500], [10200, 0]];
console.log(f(t));

( 5 bytes may be saved, if taking reversed version of input is considered valid. )

Answer 3

APL+WIN, 48 bytes

+/((h*2)+(((h←-2-/⌈\m)÷-2-/m←⌽⎕)×(⌽-2-/⎕))*2)*.5

Prompts for a list of x coordinates followed by a list of y coordinates

Explanation

h←-2-/⌈\m difference between successive vertical maxima viewed from the right (1)

-2-/m←⌽⎕ vertical difference between points (2)

⌽-2-/⎕ horizontal difference between points (3)

The lit vertical distances = h and the lit horizontal distances are (3)*(1)/(2). The rest is Pythagoras.

Answer 4

Swift, 190 bytes

import Foundation
func f(a:[(Double,Double)]){var t=0.0,h=t,l=(t,t)
a.reversed().map{n in if l.0>=n.0&&n.1>l.1{t+=max((n.1-h)/(n.1-l.1)*hypot(n.0-l.0,n.1-l.1),0)
h=max(n.1,h)}
l=n}
print(t)}

Try it online!

Explanation

import Foundation                  // Import hypot() function
func f(a:[(Double,Double)]){       // Main function
  var t=0.0,h=0.0,l=(0.0,0.0)      // Initialize variables
  a.reversed().map{n in            // For every vertex in the list (from right to left):
    if l.0>=n.0&&n.1>l.1{          //   If the line from the last vertex goes uphill:
      t+=max((n.1-h)/(n.1-l.1)     //     Add the fraction of the line that's above the
        *hypot(n.0-l.0,n.1-l.1),0) //     highest seen point times the length of the line
                                   //     to the total
      h=max(n.1,h)}                //     Update the highest seen point
    l=n}                           //   Update the last seen point
  print(t)}                        // Print the total

Answer 5

Python 2, 122 120 bytes

k=input()[::-1]
m=r=0
for(a,b),(c,d)in zip(k,k[1:]):
 if d>m:r+=(b>=m or(m-b)/(d-b))*((a-c)**2+(b-d)**2)**.5;m=d
print r

Try it online!

Answer 6

Python 2, 89 bytes

M=t=0
for x,y in input()[::-1]:
 if y>M:t+=(y-M)*abs((x-X)/(y-Y)+1j);M=y
 X,Y=x,y
print t

Try it online!

Takes in a list of pairs of floats. Based off ovs's solution.

Answer 7

APL (Dyalog Unicode), 31 bytes^SBCS

Uses Graham's formula.

Anonymous prefix function taking 2×n matrix of data as right argument. The first row contains x-values from right to left, and the second row the corresponding y-values.

{+/.5*⍨(×⍨2-/⌈\2⌷⍵)×1+×⍨÷⌿2-/⍵}

Try it online!

{…} anonymous lambda where ⍵ is the argument:

 2-/⍵ deltas (lit. pairwise minus-reductions)

 ÷⌿ ^Δx⁄_Δy (lit. vertical division reduction)

 ×⍨ square (lit. multiplication selfie)

 1+ one added to that

 (…)× multiply the following with that:

  2⌷⍵ second row of the argument (the y values)

  ⌈\ running maximum (highest height met until now, going from right)

  2-/ deltas of (lit. pairwise minus-reduction)

  ×⍨ square (lit. multiplication selfie)

 .5*⍨square-root (lit. raise that to the power of a half)

 +/ sum

Answer 8

Jelly, 23 bytes

ṀÐƤḊ_⁸«©0×⁹I¤÷⁸I¤,®²S½S

A dyadic link taking a list of y values on the left and a list of the respective x values on the right (as explicitly allowed by the OP in comments)

Try it online!

How?

The fraction of a (sloping) section that is lit is the same fraction that would be lit if it were a vertical drop. Note that since squaring occurs to evaluate slope lengths the calculated heights along the way may be negative (also in the below the run-lengths of the lit slopes are calculated as negative divided by negative).

ṀÐƤḊ_⁸«©0×⁹I¤÷⁸I¤,®²S½S - Link:list, yValues; list, xValues
 ÐƤ                     - for suffixes of the yValues:       e.g. [ 3000, 3500, 1000, 5000, 2000, 3500,    0]
Ṁ                       -   maximum                               [ 5000, 5000, 5000, 5000, 3500, 3500,    0]
   Ḋ                    - dequeue                                 [ 5000, 5000, 5000, 3500, 3500,    0]
     ⁸                  - chain's left argument, yValues          [ 3000, 3500, 1000, 5000, 2000, 3500,    0]
    _                   - subtract                                [ 2000, 1500, 4000,-1500, 1500,-3500,    0]
        0               - literal zero
      «                 - minimum (vectorises)                    [    0,    0,    0,-1500,    0,-3500,    0]
       ©                - copy to the register for later
            ¤           - nilad followed by link(s) as a nilad:
          ⁹             -   chain's right argument, xValues  e.g. [    0,  500, 2500, 5000, 9000, 9000, 10200]
           I            -   incremental differences               [  500, 2000, 2500, 4000,    0, 1200]
         ×              - multiply (vectorises)                   [    0,    0,    0,-6000000, 0,-4200000, 0]
                ¤       - nilad followed by link(s) as a nilad:
              ⁸         -   chain's left argument, yValues        [ 3000, 3500, 1000, 5000, 2000, 3500,    0]
               I        -   incremental differences               [  500,-2500, 4000,-3000, 1500,-3500]
             ÷          - divide (vectorises)                     [    0,    0,    0, 2000,    0, 1200,    0]
                  ®     - recall from the register                [    0,    0,    0,-1500,    0,-3500,    0]
                 ,      - pair (i.e. lit slope [runs, rises])     [[0, 0, 0,    2000, 0,    1200, 0], [0, 0, 0,   -1500, 0,    -3500, 0]]
                   ²    - square (vectorises)                     [[0, 0, 0, 4000000, 0, 1440000, 0], [0, 0, 0, 2250000, 0, 12250000, 0]]            
                    S   - sum (vectorises)                        [  0,   0,   0, 6250000,   0, 13690000,   0]
                     ½  - square root (vectorises)                [0.0, 0.0, 0.0,  2500.0, 0.0,   3700.0, 0.0]
                      S - sum                                     6200.0

---

25 byte monadic version taking a list of [x,y] co-ordinates:

ṀÐƤḊ_«0
Z©Ṫµ®FI×Ç÷I,DzS½S

Try this one.

Answer 9

Kotlin, 178 bytes

fun L(h:List<List<Double>>)=with(h.zip(h.drop(1))){mapIndexed{i,(a,b)->val t=a[1]-drop(i).map{(_,y)->y[1]}.max()!!;if(t>0)t*Math.hypot(1.0,(a[0]-b[0])/(a[1]-b[1]))else .0}.sum()}

Try it online!

The testing part is very much not golfed :)