The buses that went by
- O(n²) · Very hard
- Full plan
- Python
- JavaScript
- lists
- comparisons
- conditionals
Problem
Don Efraín sells newspapers on the corner and, so he does not get bored, he writes down the number of every bus that goes by, in the order they go by. His granddaughter Lupita helped him for a while on her own sheet, and now they want to know whether the two sheets tell the same story or one of them is a piece of the other.
Write a function that takes one and other, two lists of whole numbers: the bus numbers on each sheet, in order. They may be empty and neither one goes past 20 numbers. Return one of these four strings: "equal" if both sheets have the same numbers in the same order; "inside" if the first one shows up whole, back to back and in the same order somewhere in the second one; "contains" if it is the second one that shows up that way inside the first; and "different" if none of the three happens.
Back to back means with no gaps: [6, 20, 9] is inside [6, 20, 9, 14, 3], and inside [3, 6, 20, 9] too, but [6, 9] is not inside [6, 20, 9], because another bus went by between the 6 and the 9. The numbers are compared one by one and whole: every bus is a number, not the digits it is written with. A 6 followed by a 20 is two buses, and they do not match a single bus 620.
An empty sheet counts as showing up inside any other one: if the first one is empty and the second one is not, you return "inside"; if it is the second one that is empty, "contains"; and if both are empty, "equal".
Examples
Both sheets are the same
[41, 7, 13], [41, 7, 13] → "equal"
The first one starts the second one
[6, 20, 9], [6, 20, 9, 14, 3] → "inside"
The first one sits in the middle of the second
[20, 9], [6, 20, 9, 14] → "inside"
The second one sits in the middle of the first
[6, 20, 9, 14], [20, 9] → "contains"
The same buses in another order
[6, 20, 9], [9, 20, 6] → "different"
A bus is missing in the middle
[6, 9], [6, 20, 9] → "different"
Besides these, the challenge has hidden tests that are revealed when you submit your solution.
You start with this
Python
def compare_notes(one, other):
passJavaScript
function compareNotes(one, other) {
}It opens in your browser, with the editor and the tests. This challenge is part of the full plan; the O(1) and O(log n) ones are free.