62
\$\begingroup\$

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: The Mountain 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:Test Case Pic The first one has length 5000/2 = 2500 and the second one has length 3700.

This is , so the shortest answer in bytes wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – rigged Dec 22 '17 at 0:33
  • 1
    \$\begingroup\$ May the mountain be horizontal? \$\endgroup\$ – user202729 Dec 22 '17 at 1:54
  • \$\begingroup\$ Yes, there can be horizontal segments on the mountain. However it will go to 0 at some point. \$\endgroup\$ – rigged Dec 22 '17 at 1:55
  • 1
    \$\begingroup\$ But should they be lit? \$\endgroup\$ – user202729 Dec 22 '17 at 2:01
  • \$\begingroup\$ They are not lit. The light, being perfectly horizontal, can only run parallel to them and never strike them. I edited the problem to clarify this. \$\endgroup\$ – rigged Dec 22 '17 at 2:05
14
\$\begingroup\$

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?

A poorly drawn mountain

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

\$\endgroup\$
12
\$\begingroup\$

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

\$\endgroup\$
10
\$\begingroup\$

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.

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

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
\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 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]. \$\endgroup\$ – Jonathan Allan Dec 31 '17 at 20:45
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Think we can take a reverse list (we are allowed to take x and y as separate lists), so you can drop the [::-1]. \$\endgroup\$ – Jonathan Allan Dec 31 '17 at 20:46
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ The input can be two lists of values. I have asked the OP a while ago and they said it's fine. \$\endgroup\$ – Mr. Xcoder Dec 31 '17 at 19:34
  • \$\begingroup\$ I feel like there are too many s and s. \$\endgroup\$ – Jonathan Allan Dec 31 '17 at 19:36
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.