Count cars passing in opposite directions

The problem comes from codility, whose coding problems I'm starting to enjoy as their evaluation criteria really looks at runtime.

A non-empty zero-indexed array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road.

Array A contains only 0s and/or 1s:

• 0 represents a car traveling east,
• 1 represents a car traveling west.

The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west.

For example, consider array A such that:

  A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1


We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).

Write a function:

def solution(a)


that, given a non-empty zero-indexed array A of N integers, returns the number of passing cars.

The function should return −1 if the number of passing cars exceeds 1,000,000,000.

For example, given:

  A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1


the function should return 5, as explained above.

Assume that:

• N is an integer within the range [1..100,000];
• each element of array A is an integer that can have one of the following values: 0, 1.

Complexity:

• expected worst-case time complexity is $O(N)$;
• expected worst-case space complexity is $O(1)$, beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Solution

I've tried my hand at 2 different solutions, one where I delete elements from the array but that was slower than my first pass like this:

def solution(a)
results = 0
a.each_with_index do |el, i|
if el == 0
j = i
while j <= a.size-1
results += 1 if a[j] != 0
j += 1
end
end
return -1 if results > 1000000000
end
results
end


I understand why this is $O(n^2)$, but I'm unsure how to make this faster.

• The question is interesting, but would be better without the ugly and irritating requirement that -1 is to be returned if the number of passes exceeds one billion. – Cary Swoveland Dec 24 '14 at 15:23
• For anyone not aware, Ruby automatically upgrades the class of an int from Fixnum to Bignum after a certain machine-dependent threshold, and Bignums can hold arbitrarily large numbers (limited by machine memory). – Devon Parsons Mar 9 '15 at 12:24
• Use underscores in large numbers to improve readability – Devon Parsons Mar 9 '15 at 12:26

def solution(a)
results = 0
east_count = 0
a.each do |el|
if el == 0
east_count += 1
else
results += east_count
end
return -1 if results > 1000000000
end
results
end


Note that you don't have to compare each car to every other car. You just have to track how many are traveling east and each time you find someone going west, increment your results by the eastbound count. I find this easier to understand than tracking the westbound cars backwards.

r | c
--+--
0 | 0
0 | 1
1 | 1 (0,1)
1 | 2
3 | 2 (0,3), (2,3)
5 | 2 (0,4), (2,4)


In the table, r stands for results and c stands for east_count. The pairs found at any point are to the right.

This will not find the pairs that pass, but it does count them. It maintains the required $P < Q$ by order of iteration.

I don't know much about Ruby, so I won't try to make syntactic comments. Apologies if my own syntax is weak.

This iterates through the array once, so it's $O(n)$ in time. It defines a constant number of scalar variables, so it's $O(1)$ memory beyond the input array.

Edit: Brythan's solution is better, as it requires only a single iteration of the input rather than two iterations. The explanation is still relevant, so I'll leave the answer up.

You're counting the number of cars traveling westwards using a loop, but that's unnecessary. It's more efficient to loop trough the input once and count the number of westwards traveling cars (total_west).

Then in your main loop - When you encounter an eastward traveling car, subtract 1 from the total number of eastward traveling cars (total_west). All westwards traveling cars that could pass this car have already passed. - When you encounter an eastward traveling car, you add the total number of westward traveling cars to your total (total).

def solution(input)
total_west = input.count(1)
total      = 0

input.each do |direction|
if direction == 1
total_west -= 1
else
total += total_west
end

if total > 10e8
return -1
end
end

end


Time complexity is O(n), space complexity is O(1).

I wouldn't take an imperative approach for this kind of problems (no each, while, +=, inline conditionals nor early returns). A functional solution using a hash as state variable would look like this:

def solution(cars)
passing = cars.reduce(going_east: 0, passing: 0) do |state, car|
if car == 0 # car going to the east
state.merge(going_east: state[:going_east] + 1)
else
state.merge(passing: state[:passing] + state[:going_east])
end
end[:passing]
passing > 1e9 ? -1 : passing
end

• I'm curious, how long did it take you to write this solution? – Mohamad Dec 21 '14 at 20:22
• I don't know, a couple of minutes? does it look complicated? it's pretty standard stuff (a simple Finite-State-Maching), in FP style you do a folding (reduce/inject) with the initial state over the collection to process. – tokland Dec 21 '14 at 21:05
• I don't think it looks complicated. It does look different, though. Usually, I find functional code a bit harder to read. That's a psychological barrier, I think. I asked how long it took you because I want to compare: It takes me a lot longer, maybe 10 to 20 minutes to write a solution to this problem, and there's no guarantee it will be as succinct and well written as yours. I'm just trying to gage my ability, I suppose, and when you tell me a couple of minutes, it doesn't bode well for me :D – Mohamad Dec 21 '14 at 22:07
• I like your solution, but I think state[:going_east] += 1 and state[:passing] += state[:going_east] reads better than the somewhat forced merges. I realize you used merge to avoid the need for a pesky state at the end of the reduce block, but you can deal with that by using each_with_object rather than reduce. – Cary Swoveland Dec 24 '14 at 16:08
• @Cary: It would be a bit easier to read indeed, but a functional approach forbids in-place updates. Here it's not a big deal, but with more complex algorithms having no updates makes thing easier to follow. – tokland Dec 26 '14 at 19:07

[Edit: I'm not happy with my solution after reflecting on it. Constructing the array cum_east is wasteful, as one can just maintain a running count, as others have done.]

Here's a slightly different way of looking at it. Let i be a car position, west to east. First compute an array cum_east, such that:

• if the car in position i is westbound (a[i]=>1), cum_east[i] is the number of cars that will pass that westbound car; and
• if the car in position i is eastbound (a[i]=>0), cum_east[i] is the number of eastbound cars that are led by (and include) that eastbound car.

It is then a simple matter of summing the values of cum_east for the westbound cars.

Code

def nbr_passed(a)
cum_east = a[1..-1].reduce([1-a.first]) { |cum, c| cum << cum.last + 1-c }
n = a.zip(cum_east).reduce(0) { |t,(cum_east, direction)| t + cum_east*direction }
n > 1e9 ? -1 : n
end


Example

a = [0, 1, 0, 1, 1]
nbr_passed(a)
#=> 5


Explanation

For the example above, the following steps are performed.

cum_east = a[1..-1].reduce([1-a.first]) { |cum, c| cum << cum.last + 1-c }
#=> [1, 1, 2, 2, 2]
b = a.zip(cum_east)
#=> [[0, 1], [1, 1], [0, 2], [1, 2], [1, 2]]


The third element of b ([0, 2]) shows that the eastbound car in that position is being followed by one other eastbound car. The fourth element ([1, 2]) indicates that the westbound car in that position will pass two eastbound cars.

n = b.reduce(0) { |t,(cum_east, direction)| t + cum_east*direction }
#=> 5


This simply sums the cumulative values for the westbound cars, as direction => 1 (0) for westbound (eastbound) cars.

  n > 1e9 ? -1 : n
#=> 5