Skip to content

Find all collision courses given a N X M matrix representing a road filled with self driving cars

Notifications You must be signed in to change notification settings

Nikhil22/self-driving-car-collision-courses

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

27 Commits
 
 
 
 
 
 
 
 

Repository files navigation

Self Driving Car: Find all collision courses given a N X M grid/array representing a road full of self driving cars

Problem

Among the many things a self-driving car must consider when driving, the car has to ensure it doesn’t collide with any other cars.

We can represent a road as an N X M grid. How can we tell whether 2 cars are on a collision course with each other?

Take a look at these short animations and see if you notice something.

Collision

demo

Safe

demo

Diagonal

The key? Cars that are on a collision course are on the same diagonal. We know this because they are moving at the exact same speed. See the 'Assumptions' section below for more details about this.

demo

Input

A 2D array, with 1s and 0s

  • 1 signifies there is a car at the coordinate
  • 0 signifies the coordinate is empty
  [0, 1, 1, 1, 0, 0, 1, 1, 0, 0]
  [1, 1, 1, 1, 1, 0, 0, 1, 1, 1]
  [0, 1, 0, 0, 0, 0, 1, 0, 1, 1]
  [0, 1, 0, 1, 1, 0, 0, 1, 0, 0]
  [1, 1, 0, 0, 0, 1, 1, 0, 1, 1]
  [1, 0, 0, 1, 0, 0, 1, 0, 0, 1]
  [1, 1, 0, 1, 1, 1, 0, 1, 0, 1]
  [1, 0, 0, 0, 0, 0, 0, 0, 1, 0]
  [1, 0, 1, 1, 1, 1, 1, 0, 0, 0]
  [1, 0, 0, 0, 1, 1, 1, 1, 0, 1]

Output

An Object, with key as stringed coordinates, and value as an an array of coordinates which are collision courses

Example: The collision courses of (0,0) are coordinates (1,1), (3,3) & (9,9) because (1,1), (3,3) & (9,9) are diagonals and have cars in them

  {
    0,0: [[1, 1], [3, 3], [9, 9]],
    0,1: [[1, 2], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [1, 0]],
    0,2: [[1, 3], [4, 6], [1, 1]],
    0,3: [[1, 4], [6, 9], [1, 2], [2, 1]],
    .....
  }

Assumptions

All cars in the same road are moving at the exact same speed. We make this assumption for 2 reasons

  1. They are on the same road space (same speed limits)
  2. They are autonomous (can control the exact speed they go)

In data structure terms

Given a 2D array, find all diagonals of all coordinates.

Inspiration

The Simple Solution To Traffic

Author

Nikhil Bhaskar

About

Find all collision courses given a N X M matrix representing a road filled with self driving cars

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published