6
\$\begingroup\$

This was originally a question from interviewstreet.com over a decade ago

You are given an array (or whatever - your choice of input) of positive integers \$y_1,\ldots,y_n\$ that represents \$n\$ line segments, where segment \$i\$ has endpoints \$(i, 0)\$ and \$(i, y_i)\$. Imagine that from the top of each segment a horizontal ray is shot to the left, and this ray stops when it touches another segment or it hits the \$y\$-axis. Construct an array of \$n\$ integers, \$v_1,\ldots,v_n\$, where \$v_i\$ is equal to the length of ray shot from the top of segment \$i\$. Define \$V(y_1,\ldots,y_n)=v_1+\cdots+v_n\$.

For example starting with \$3,2,5,3,3,4,1,2\$, then \$v_1,\ldots,v_8=1,1,3,1,1,3,1,2\$ as shown in this picture, and so \$V(3,2,5,3,3,4,1,2)=1+1+3+1+1+3+1+2=13\$ here.

sticks

For each permutation \$p\$ of \$1,\ldots,n\$, you can calculate \$V(y_{p_1},\ldots,y_{p_n})\$. You can then take the average across all possible permutations.

Write a program or function that gives the expected value of \$V(y_{p_1},\ldots,y_{p_n})\$ for a uniformly random permutation \$p\$ of \$1,\ldots,n\$. Include a complexity measure for your approach, such as \$O(n)\$ or \$O(n!)\$ and explain why.

This is , so the shortest answer in bytes wins. Standard rules apply and default loopholes are forbidden.

Test examples include

Input y             Output E[V]
3,2,5,3,3,4,1,2     15.25
1,2,3               4.333333
3,3,3               3
2,2,3               4
10,2,4,4            6
10,10,10,5,10       5.8
1,2,3,4,5,6         11.15
Improve this question
New contributor
Henry is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
6
  • \$\begingroup\$ @doubleunary Those three steps would give an answer, but perhaps there might be shorter calculations that combine some steps. \$\endgroup\$ Commented 22 hours ago
  • \$\begingroup\$ Welcome to Code Golf and nice first challenge! Please note that for code-golf most answers are likely to use the worst possible time complexity. (Or even worse than the worst, if that saves a byte.) \$\endgroup\$ Commented 22 hours ago
  • \$\begingroup\$ Was it taken almost verbatim from HackerRank? \$\endgroup\$ Commented 21 hours ago
  • 1
    \$\begingroup\$ @Arnauld It was on interviewstreet.com in 2012. The web archive has it on HackerRank only in 2021 \$\endgroup\$ Commented 21 hours ago
  • 1
    \$\begingroup\$ The HackerRank TOS states that all materials are copyrighted. \$\endgroup\$ Commented 20 hours ago

6 Answers 6

Reset to default
3
\$\begingroup\$

Jelly, \$O(n \log n)\$ 13 bytes or \$O(n^2)\$ 12 bytes

\$O(n \log n)\$ 13 bytes

ĠẈṚÄ‘÷@ƊS×L‘$

A monadic Link that accepts a list of heights and yields the expected total visible distance.

Try it online! Or see the test-suite.

How?

Note that the actual height values are irrelevant; what matters is the count of each distinct height and for each of these how many lines are equal or greater in value.

By linearity of expectation, we can compute the contribution each line has by what could be in the gaps between it and other lines of equal or greater height.

If the number of lines is \$n\$, and there are \$m\$ distinct heights with ordered counts \$C\$ with suffix-sums \$S\$ then:

$$\Bbb E[V] = (n + 1) \sum_{i=1}^{m}\frac{C_i}{S_i + 1}$$

ĠẈṚÄ‘÷@ƊS×L‘$ - Link: list of positive integers, Heights
Ġ             - group indices by ascending value (O(n log n))
 Ẉ            - length of each -> C
  Ṛ           - reverse -> Rev(C)
       Ɗ      - last three links as a monad - f(Rev(C)):
   Ä          -   cumulative sums {Rev(C)} (O(n)) -> Rev(S)
    ‘         -   increment each of {those}
     ÷@       -   divide {Rev(C)} by {those} (vectorises)
        S     - sum {those}
            $ - last two links as a monad - f(Heights):
          L   -   length {Heights} -> n
           ‘  -   increment -> n+1
         ×    - {sum result} multiplied by {n+1}

\$O(n^2)\$ in 12 bytes

L‘ɓ>€`§ạ⁹÷@S

TIO

How?

As above, but summing all individual contributions found by a cross-product of comparisons.

L‘ɓ>€`§ạ⁹÷@S - Link: list of positive integers, Heights
L            - length {Heights} -> n
 ‘           - increment -> n+1
  ɓ          - start a new dyadic chain - f(Heights, n+1)
     `       - use {Heights} as both arguments of:
    €        -   for each:
   >         -     greater than? (vectorises)
      §      - sums
       ạ⁹    - absolute difference with {n+1} (vectorises)
         ÷@  - {n+1} divided by each of {those}
           S - sum
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Wouldn't group indices by ascending value amount to a sort so \$O(n \log n)\$? \$\endgroup\$ Commented 20 hours ago
  • \$\begingroup\$ Ah, yes, it needs to sort by the m keys - interpreter function. \$\endgroup\$ Commented 20 hours ago
1
\$\begingroup\$

Python 3, \$O(n^2)\$ 55 bytes

lambda a:sum(-~len(a)/-~sum(h<=v for v in a)for h in a)

An unnamed function that accepts a list of positive integers, a, and returns the expected total visible distance.

Try it online!

Python 3.8+ \$O(n \log n)\$, 104 bytes

lambda a,s=1:(c:=Counter(a))and sum(c[v]/(s:=s+c[v])for v in sorted(c)[::-1])*s
from collections import*

TIO

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

R, 43 bytes \$O(n\log n)\$

a=table(-y)
(sum(a)+1)*sum(a/(cumsum(a)+1))

Try it online!

R, 47 bytes \$O(n^2)\$

sum((length(y)+1)/(rowSums(outer(y,y,"<="))+1))

Try it online!

Improve this answer
New contributor
Henry is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
5
0
\$\begingroup\$

Charcoal, O(n²), 15 bytes

ＩΣＥθ∕⊕Ｌθ⊕ＬΦθ÷λι

Try it online! Link is to verbose version of code. Explanation: Port of @JonathanAllan's Python 3 answer, except replacing sum(h<=v for v in a) with len(v for v in a if v//h).

   θ            Input array
  Ｅ             Map over positive integers
       θ        Input array
      Ｌ         Length
     ⊕          Incremented
    ∕           Divided by
           θ    Input array
          Φ     Filtered by
             λ  Inner positive integer
            ÷   Is not less than
              ι Outer positive integer
         Ｌ      Length
        ⊕       Incremented
 Σ              Take the sum
Ｉ               Cast to string
                Implicitly print
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Julia, \$O(n^2)\$, 44 bytes

sum((length(y)+1)/(sum(i.<=y)+1) for i in y)

Attempt This Online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 56 bytes, \$O(n^2)\$

The much more clever algorithm used by Jonathan Allan.

a=>a.map(h=>t+=a.map(H=>q+=++n&&h<=H,n=q=1)&&n/q,t=0)&&t

Try it online!

JavaScript (ES6), 104 bytes, \$O(n!)\$

A naive implementation that processes all permutations of the input array and computes the rays for each of them.

f=(a,q=t=n=0,p=[f])=>a.map((v,i)=>f(a.filter(_=>i--),p.findIndex(V=>V<v^1)-~q,[v,...p]))+a?t/n:t+=++n&&q

Try it online!

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.