CareerCup

If ball can be of different mass, it is possible that one ball is much heavier than others can slow down a lot and even stop. Given this problem, it is highly possible this is not the case.

If all ball of the same mass, and suppose two ball hits, they just change direction and speed remains the same.

Find the most left ball whose direction is right. Suppose it travels to the right edge of the table without collision requires time t1.

Find the most right ball whose direction is left. Suppose it travels to the left edge of the table without collision requires time t2.

The time that all ball fall off is max(t2,t1)

/*
 I assume the question is, find the first moment in time when all balls
 have fallen from the table (like max time).
 --
 First this is more of a physics than a C/S question, because we have
 to understand what happens at collision very well. If the balls were
 of volume lim->0 and it's an elastic collision as described and if we
 couldn't distinguish balls we would just observe the balls moving "through"
 each other. But if the balls get bigger, they would travel "through"
 each other in "no time" or "bounce of" each other.
 From the point of view of the ball, every time you hit a ball that
 runs in opposite direction you travel "light speed" for the distance
 of a balls diameter.

 So, it's about choosing units we can easily calculate here. I would
 suggest to use:
 - ball diameter: d
 - speed: 1d / time unit
 - position: in d: 0, d, 2d, etc...

 illustration (zero: zero volume case; even,odd: volume case with even
                                                 and odd distance)
 case    | zero  | even  | odd
 ---------------------------------
 position| 12345 | 12345 | 12345
 ---------------------------------
 |  1    |_.___._|_O___O_|_O__O__
 t  1.5  |       |       |
 i  2    |__._.__|__O_O__|__OO___
 m  2.5  |       |  -*-  |
 e  3    |___.___|__O_O__|_O__O__
 |  3.5  |       |       |
 v  4    |__._.__|_O___O_|O____O_

 having this definitions in place the table may look like this
 (< left moving, >right moving)
           12 15         26  30  34
           |  |          |   |   |
 ____<__<__>__>___<___<__>___>___>_____
 |   |  |         |   |               |
 5   9  11        19  23              40

 table: 5..40
 left moving: 9, 11, 19, 23
 right moving: 12, 15, 26, 30, 34

 t = time for a ball to reach table edge = distance to edge - #balls encountered
 which ball takes the longest? either the most right left-running,
 or the most left right-running (the ball 23 or 12 in the example)

 O(n + m) solution (n number of left running, m number of right running)
 1. traverse the two arrays to find the most left right-running and the most
    right left-running
 2. traverse the arrays again to find how many balls those will encounter
 3. calculate, build the max, done
 */
public class TableOfBalls {
    public static int lastBallFalling(int tableStart, int tableEnd,
                                      List<Integer> leftRunningBallPos,
                                      List<Integer> rightRunningBallPos) {
        // TODO, verify corner cases for null, empty arrays, start > end,
        // balls not in range etc.
        int rightRunning = tableEnd - Collections.min(rightRunningBallPos) + 1;
        int leftRunning = Collections.max(leftRunningBallPos) - tableStart + 1;
        for(int rr : leftRunningBallPos) {
            if(rr < leftRunning) leftRunning--;
        }
        for(int ll : rightRunningBallPos) {
            if(ll > rightRunning) rightRunning--;
        }
        return Math.max(leftRunning, rightRunning);
    }

    public static void main(String[] args) {
        System.out.println(lastBallFalling(5, 40,
                Arrays.asList(9, 11, 19, 23),
                Arrays.asList(12, 15, 26, 30, 34)));
        
        // output 27: = max(40 - 12 + 1 - 2, 23 - 5 - 2) 
    }
}

Yeah, well, nothing to do with physics :-)
The algorithm would be :
1. start at time t0
1. find time interval ( dt ) to the first collision of 2 balls or a ball with an edge
2. recalculate positions of tall balls at time t0 + dt. Change the velocities of the collided balls (if any)
3. repeat from step 1 until no more balls left on the table.

Recursive code in python

class Table(object):
    def __init__(self, l, r):
        self.l = l
        self.r = r


class Ball(object):
    def __init__(self, p, v):
        self.p = p
        self.v = v


table = Table(0, 100)
v = 1
balls = [Ball(1, v), Ball(3, -v), Ball(15, v), Ball(20, -v), Ball(45, -v), Ball(60, v), Ball(70, v), Ball(80, -v), Ball(90, v), Ball(98, -v)]
#balls = [Ball(1, v), Ball(3, -v)]


def time_to_event():
    t = (table.r - table.l)/v
    collided_balls = []
    for i in range(0, len(balls)+1):
        if i == 0:
            if balls[i].v < 0:
                t = min(t, (table.l - balls[i].p)/balls[i].v)
        elif i == len(balls):
            if balls[i-1].v > 0:
                t = min(t, (table.r - balls[i-1].p)/balls[i-1].v)
        else:
            if balls[i-1].v > 0 and balls[i].v < 0:
                t = min(t, (balls[i].p - balls[i - 1].p) / (-balls[i].v + balls[i-1].v))
                collided_balls.append(balls[i])
                collided_balls.append(balls[i-1])

    for ball in list(balls):
        ball.p += t*ball.v
        if ball.p <= table.l or ball.p >= table.r:
            balls.remove(ball)

    for ball in collided_balls:
        ball.v *= -1

    return t


def find_time():
    if len(balls) == 0:
        return 0
    if len(balls) == 1:
        return (table.r - balls[0].p)/balls[0].v if balls[0].v > 0 else (table.l - balls[0].p)/balls[0].v

    tevent = time_to_event()
    return tevent + find_time()

time = find_time()
print(time)

test

Yeah, well, nothing to do with physics :-)
The algorithm would be :
1. start at time t0
1. find time interval ( dt ) to the first collision of 2 balls or of a ball with a table edge
2. recalculate positions of all balls at time t0 + dt. Change the velocities of the collided balls (if any), and remove the ball(s) that hit a table edge
3. repeat from step 1 until no more balls left on the table.

Recursive code in python

class Table(object):
    def __init__(self, l, r):
        self.l = l
        self.r = r


class Ball(object):
    def __init__(self, p, v):
        self.p = p
        self.v = v


table = Table(0, 100)
v = 1
balls = [Ball(1, v), Ball(3, -v), Ball(15, v), Ball(20, -v), Ball(45, -v), Ball(60, v), Ball(70, v), Ball(80, -v), Ball(90, v), Ball(98, -v)]
#balls = [Ball(1, v), Ball(3, -v)]


def time_to_event():
    t = (table.r - table.l)/v
    collided_balls = []
    for i in range(0, len(balls)+1):
        if i == 0:
            if balls[i].v < 0:
                t = min(t, (table.l - balls[i].p)/balls[i].v)
        elif i == len(balls):
            if balls[i-1].v > 0:
                t = min(t, (table.r - balls[i-1].p)/balls[i-1].v)
        else:
            if balls[i-1].v > 0 and balls[i].v < 0:
                t = min(t, (balls[i].p - balls[i - 1].p) / (-balls[i].v + balls[i-1].v))
                collided_balls.append(balls[i])
                collided_balls.append(balls[i-1])

    for ball in list(balls):
        ball.p += t*ball.v
        if ball.p <= table.l or ball.p >= table.r:
            balls.remove(ball)

    for ball in collided_balls:
        ball.v *= -1

    return t


def find_time():
    if len(balls) == 0:
        return 0
    if len(balls) == 1:
        return (table.r - balls[0].p)/balls[0].v if balls[0].v > 0 else (table.l - balls[0].p)/balls[0].v

    tevent = time_to_event()
    return tevent + find_time()

time = find_time()
print(time)