# How lit is this mountain? 🔥

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 , so the shortest answer in bytes wins.

• Hint: When finding the length of a segment, there are three points you need to consider: the two endpoints, and the point that is "blocking" it (in the 2nd picture, that would be (9000,3500) which determines the length of the 3-4-5 segment. Let the two points on the main segment be (x1, y1) and (x2,y2). The point which is "blocking" it is (x3, y3). Assume y2 < y3 <= y1. Then the length of the segment is ((y1 - y3)/(y1 - y2))*sqrt((x1 - x2)^2 + (y1 - y2)^2). This is essentially the distance formula, multiplied by the fraction of the segment which is actually used. Dec 22, 2017 at 0:33
• May the mountain be horizontal? Dec 22, 2017 at 1:54
• Yes, there can be horizontal segments on the mountain. However it will go to 0 at some point. Dec 22, 2017 at 1:55
• But should they be lit? Dec 22, 2017 at 2:01
• Good idea about scanning in a hand-drawn picture for a challenge. Jan 19, 2018 at 19:33

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

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

• Never seen reduceRight in code golf befor elol May 6 at 1:44
• @emanresuA I would strongly recommend ES rename reduceRight to foldr.
– tsh
May 6 at 3:35

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

• Would +/.5*⍨(h*2)+×⍨((h←-2-/⌈\m)÷-2-/m←⌽⎕)×⌽-2-/⎕ work? Dec 22, 2017 at 18:50
• Unfortunately my old APL+WIN version does not have the ⍨ operator so I cannot say Dec 22, 2017 at 19:27
• @Cows quack Managed to try it in an old version of Dyalog Unicode (v13) and your suggestion does work Dec 23, 2017 at 11:00

# 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


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

• Since we are allowed to take a list of x values and a list of y values as two inputs I'm pretty sure we could take a list of co-ordinates in reverse, removing the need for [::-1]. Dec 31, 2017 at 20:45

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

• Think we can take a reverse list (we are allowed to take x and y as separate lists), so you can drop the [::-1]. Dec 31, 2017 at 20:46

# Jelly,  23  21 bytes

-2 thanks to caird coinheringaahing

ṀÐƤḊ_⁸«©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                            0
«               - minimum (vectorises)                    [    0,    0,    0,-1500,    0,-3500,    0]
©              - copy to the register for later
}          - apply to right:                     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]
{      - apply to left:                     e.g. [ 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


Try this one.

• The input can be two lists of values. I have asked the OP a while ago and they said it's fine. Dec 31, 2017 at 19:34
• I feel like there are too many ⁸s and ⁹s. Dec 31, 2017 at 19:36
• 21 bytes Feb 21, 2021 at 16:33
• @cairdcoinheringaahing thanks, I didn't know what { and } did back then. Feb 21, 2021 at 20:54

# APL (Dyalog Unicode), 31 bytesSBCS

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

# J, 46 bytes

1#.((2([:%:@+&*:/-)/\,.)*>./\@]%&(2-~/\])])&|.


Try it online!

Takes x coord list as left arg, y coord list as right arg.

Could save 5 bytes if reversed lists were allowed.

Though solved independently, the approach I landed on is almost identical to Adam's APL approach.

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