ANEO Sponsored Puzzle discussion

Puzzles
#111

I have the same problem as you do, did you solve it?

#112

iā€™ve been able to complete this puzzle 100% but am not really happy with the solution I wrote, quite hacky and doesnā€™t look especially nice, so I was wondering if anyone could advise me on where to look for inspiration as to how i can completely remove any float or doubles from my program.

Iā€™m currently (in C++) converting all my discrete speeds (Km/h) into m/s such that I can more easily calculate whether I can get through each traffic light, but as can be expected some of those conversions end up with rounding errors.

Any advice would be very much appreciated.

#113

Hi everyone
What is the distance between 2 redlights ? I supposed it s the same distance than between first redlight and starting point ?
But itā€™s not specified

#114

yes, it is:

An integer distance representing the distance of the traffic light from the starting point (in meters).

If you have the distance from the starting point for 2 different traffic lights, then you know the distance between them. (straight road)

#116

hi everyone
I want to make a function that tell me if the speed is good to pass a light number i
with python

def vert (i,speed) :
temps_darrivee = distance[i]/speed
rapport = (temps_darrivee/duration[i])

if int(rapport)%2 == 0 
    return True
  
else :
    return False

what do you think ?
my algortihm passes first tests but not all of themā€¦ I dont understantd why.

Thanks for ur help

#117

Why doesnā€™t it pass them?
Put some debug prints, and analyze the algorithm by hand. Whatā€™s going in, whatā€™s going out - with intermediate calculations - what would you do by handā€¦

Hard to tell without the input

1 Like
#118

Canā€™t pass this without the validator saying I have hard-coded solutions - which I donā€™t.

Tried two approaches:

  • one exact, which failed on the last test because of the 88.848 issue;
  • one integral (and boring but simple) which passed all the tests.

In both cases, the validator complained. So screw you, Iā€™ve got better things to do.

#119

Can anyone explain me why 78 is a bad answer to that test?

3
300 30
1500 20
3000 10
#120

Yeah sure.
You arrive at the 1500 light after 69.23 seconds and its duration is 20 seconds, so it is green between 0 and 20, red between 20 and 40, green between 40 and 60, red between 60 and 80.

The 3000m one will be red too

#121

#$@&%*!!! Damn, iā€™m so blind. I guessed distance is from the last lights so i was summing it up. I donā€™t understand why it passed first four tests xD Pure luck. Thank you a lot. Now only 7 and 8 are left, but that mean iā€™m pretty close :smiley:

#122

So my algotrithm passed all testcases,
but when I submit, doesnt pass 6 & 7, ā€œto prevent hardcoded solutionā€

but my algorithm is not hardcoded.

Do you have any idea why ??
I put round() somewhere because sometime calculated 59.99999999 (instead of 60) and got wrong.
Do you think this is why ?

Thanks

#123

Thanks. I founded the pb, it was going out 59.999999999 at one point (instead of 60) so I put round() (im with python).

And now it passes all the test. But when I submit, says I have hard coded solutionsā€¦ no idea why ! :slight_smile:

#124

Thank you for this reminder; it helped me get through the last test and eventually scoring 100% :slight_smile:

#125

Hello,

I just did the ANEO puzzle, and I had a lot of fun doing it.
My code passes all test cases.
But finally it is rated at 90% and I wonder whyā€¦

I have read that inputs are different in test cases and validation to avoid hard coding (a good point IMHO).
Anyway the setup 8 (labelled as Rain of Traffic Lights) failed in validation mode and I would like to investigate it in depth.

I have used a mathematical approach.
It is general, no special cases, all inputs are treated the same way with a simple formulae.
I use exact fractions so it is not about float or finite precision arithmetic errors.

I would like to get the validation setup (inputs/outputs) to assess if there is a bug in my code. How can I get it?

Additionally, are you 100% confident in the result of this setup?
Is a typo possible?

Thank you further,

jlandercy

#127

seems you managed to solve it @jlandercy. Please edit your post to mention it. Also, you could specify what was blocking you. Might help others to solve it.

1 Like
#129

Reading the comments, as suggested by @TwoSteps , I add my two cents.

First of all, although it is not pure beauty: brute force works! There is an algorithm with worst case complexity of O(light_count*speed). For plausible and realizable integral speeds and a decent number of traffic lights, this solution is bearable.

Second, do avoid float (or other finite precision representations such as Decimal). Make computation with Integral Numbers only. Then there are no rounding or floating point errors.

This is not true that converting km/h to m/s solve floating point error. It only avoids units consistency error. This is simply because 3.6 cannot be exactly represented with float likewise 1/3 cannot be represented exactly in finite decimal notation since it is 0.3333.... ad infinitum.

Using the IEEE-754 standard, the closest number to 3.6 is 3.60000000000000008881784197001252 (00111110010011001100110011001101b) which is not exact.

Third, do not use round function as it may produce false positive (saying the traffic light is green instead of red).
Additionally round behavior varies among languages because there are many ways to round numbers. Cases such as round(3.5) are subject to interpretation, it is somehow ill-defined. It could round to 3 or 4, both are valid solutions, it is about convention. Use floor instead which is well defined and its result should not be implementation-dependent.

Forth, representations are useful but sometimes misleading. When I began to solve this problem I had first a classic mechanical approach. I sketched this kind of figures to make up my mind:

index

That was a good idea, but it made me stick a bit with float numbers. So, it was helpful but it also had obfuscated the fact that I was working with integers.

Fifth, design time must take place before run time. First write down the properties of the problem, derive relations, then code. Do not the converse.
For the instance, it can be shown that if a solution exists, then it is computable only by using Integral Numbers, modular arithmetic and Boolean logic. That perfectly suits for any kind of programming language, specially if you are using low level language such as C.

Finally, recall the problem statement: all inputs and output are integers.

2 Likes
#130

You can stop at your secoint point.
The problem can be solved with only integers, people just have to find out.

If the light is at distance d (m) and your speed is v (m/s), you have to solve
d (m) = t (s) * v (m/s) which is 36 * d (m) = 10 * t (s) * v (km/h)
and you have another constraint on t, because you want a green light so you want
2*p*l <= t < (2*p+1)*l with l the light duration (s)

Now code :stuck_out_tongue:

#131

Hey! I canā€™t reach 100%, I need your help!

JavaScript

/**

  • Auto-generated code below aims at helping you parse
  • the standard input according to the problem statement.
    **/

const speed = parseInt(readline());
const lightCount = parseInt(readline());
var lights = new Array(lightCount);

for (let i = 0; i < lightCount; i++) {
var inputs = readline().split(ā€™ ');
const distance = parseInt(inputs[0]);
const duration = parseInt(inputs[1]);
lights[i] = {distance:distance, duration:duration};
}

var maxSpeed = speed;

var isOk = false;

while(!isOk){
isOk = true;
var speedPerSec = maxSpeed*1000/3600;
for(var l of lights){

    var timeToReach = Math.round(l.distance/speedPerSec);
    
    if(timeToReach%(2*l.duration)>=l.duration){
        isOk = false;
        break;
    }
}

if(!isOk && maxSpeed != 1){
    maxSpeed = maxSpeed-1;
}

}

// Write an action using console.log()
// To debug: console.error(ā€˜Debug messagesā€¦ā€™);

console.log(maxSpeed)

#132

I actually am getting some rounding errors.

#133

Hello,
First and foremost, The problem is really interesting and keep on innovating.

Although, I was able to pass only 7 test cases, Iā€™m curious to know the algorithm.
So, can you please tell me the way you have constructed.

Keep Innovating

Thank you

Hereā€™s my code; I someone can help me to figure out the bug, please!

// the program below works fine 
// for all test cases except 
// Test Cases: 6,9,10
// Reason: for 6; output: 48 but answer:49
// Reason: for 9; output: 0 but answer:6
// Reason: for 10; output: 88 but answer: 74

import sys
import math

//max_speed_original km/h
max_speed_o = int(input())
light_count = int(input())

// max_speed m/s
max_speed = max_speed_o * 5/18 

dur = []  //duration
dist = [] //distance

// store the values in a list
for i in range(light_count):
    distance, duration = [int(j) for j in input().split()]
    
    dur.append(duration)
    dist.append(distance)

// min time for the closest light
t_min_i = dist[0]/max_speed

// approx int val
t = math.floor(t_min_i)

while True:
    isGreen = False
    
    #iterate through each
    for i in range(light_count):
        
        // using point slope method to find the intercept
        if int((dist[i]/dist[0]*t)//dur[i]) % 2 == 0:
            isGreen = True
        else:
            isGreen = False
            break

    if isGreen:break
    t += 1
    
if isGreen:
    
    //s = speed
    s = (dist[0]/t)
    
    // check if speed > max_speed m/s
    s = max_speed if s>max_speed else s
    
    //print('Floor km/h:',math.floor(s* (18/5)))
    
    s = math.floor(s* (18/5))
    
    // check if speed > max_speed km/h
    s = max_speed_o if s>max_speed_o else s
    
    
    print(s)    
//-----------End -----------