Network Cabling puzzle discussion

I am so ashamed…

I worked really hard on figuring this out, tried all sorts of “clever” algorithms, put way too much time into it. I was overthinking the problem in a big way. When I took a step back and saw how simple it was, I erased all my code and completed the puzzle in 5 minutes.

Some hints for you:

  1. This is one of those “When you see it…” situations.

  2. If you have written more than 50 lines of code, erase everything and go back to the drawing board. I had written far more than that before I smacked myself hard and erased everything.

  3. If you took highschool math, you have more than enough knowledge to pull this off. Go back to the basics. Some of the most basic stuff you can think of. Even before high school.

Good luck!!! :smiley:

  1. Finish the puzzle

  2. Be proud

  3. Try this test case

     # in
     9
     0 0
     0 2
     0 3
     1 0
     1 2
     1 3
     2 2
     2 3
     4 0  
    
     # out
     19
    
  4. Realize that your code is crap

  5. Go back and rewrite everything

:slightly_smiling:

the correct answer is 13

1 Like

Every building needs a separate cable. You need count multiple times when vertical cables overlaps.

For each building, a dedicated cable will connect from the building to the main cable by a minimal path

1 Like

There is no overlapping cables when main cable goes through y = 2.

Hmm…

6 . Post something on puzzle’s forum

7 . Get fast reply

8 . Realize that you’re horribly wrong

9 . Go back and rewrite everything

:joy:

For everyone explaining that solution is O(n.log n) … You can do better :wink:
There’s no need to sort to find the median.
Median can be found in O(n).

Thanks! This solution is awesome! :clap:

Not every language has a built-in function suitable for finding median.
Using a built-in sort function instead is okay as long as it is fast enough for the task at hand.

None of what you’ve said changes the facts of my previous comment. I.e.
Anyone explaining that “the solution is O(n.log n)” can do better.

Note that I didn’t say you couldn’t use sort to find the median - just that it wasn’t optimal.
You also don’t need a built-in function to find the median using an O(n) algorithm.

1 Like

Yes one can do better. But the question is, should he? Only if (n log n) is not good enough.

You don’t need a built’in function to sort an array either. But if a built-in exists, why not use it?

I have no idea why someone wouldn’t want to use a built-in function. You tell me.
You’re the one who’s saying people should try to use the slowest possible algorithm.
Personally, if a tool provides provides a useful built in function, I’d use it.
If the tool doesn’t provide something I need, I write my own function (or take a different approach).

And you’re still missing the fundamental point. I never said anyone’s O(n.log n) solutions wouldn’t “work”.
I was simply pointing out that claims that the data had to be sorted (resulting in a best case solution O(of n.log n)) are wrong and claims that the best solution is O(n.log n) are wrong. (Though I had originally attempted to avoid being so blunt about it.)
The claims are wrong because the problem is solvable without sorting; and a solution can be found in O(n) by anyone interested in digging a little deeper.

Really, the logic semantics behind my statements are quite trivial. I have no idea how I can explain it any more clearly to you.
I’d prefer it if this discussion doesn’t get derailed by tangential rhetoric.
I was merely pointing out something that might motivate some people to dig a little deeper into the functions their language provides and the algorithms that can determine what values go where without needing to fully sort a list.
This is after all a learning site. :wink:

I agree that those claims are wrong. But “slowest possible”, really? O(n log n) is best to second-best for most typical problems. Saying drivel like that just makes your point weaker

Hi.
It looks like Example 5 is wrong.
We have the positions (-3,-3), (2,2) and (-4,-4).
So if we place the main cable at y = -3,
then the dedicated cables will have lengths 0, 5 and 1.
And the main cable is 6, so in total we need 12 units of cable.
However, the expected solution is 18.

Is this a bug?

Regards, Lau

seems like you read the y value twice (or override the variable instead of storing x before reading y)…
The provided input for example 5 is:

3
-5 -3
-9 2
3 -4

Wow, that’s the kind of bug (in my code) that should be so obvious, but since the first couple of examples passed the test, I didn’t think that my coordinates could be wrong!
I read the coordinates correctly:
for i in range(n):
x[i], y[i] = [int(j) for j in input().split()]
But back when I started this puzzle I for some reason thought you could do:
x = y = np.zeros(n)
as a short way of assigning several variables. But then they point to the same array. So when I change y, I change x too…
Thanks for your reply =)

Are you serious??? So that’s why it wasn’t passing… Thanks a lot for this!!

i try to solve this network cabling with javascript, but i dont know why there is always problem with one of the examples.

what problem? :slight_smile:

Usort failed timeout on 99k+ elements. Used Quick Select, timed after submit. Ex.7 executed in 307.179ms and Ex8 in 139.552 . For reference, Ex. 5 ran in .075ms.