The warriors of Cadmus
- O(n²) · Very hard
- Full plan
- Python
- JavaScript
- lists
- loops
- comparisons
Problem
Cadmus sowed the dragon's teeth in the earth, and a row of armed warriors sprang up. Not knowing who the enemy was, they fought one another. The city's chronicler wants to know how many dawns the fight lasted.
You get strength: each warrior's strength, from left to right (positive whole numbers, repeats allowed; it may be empty). Every dawn, looking at the row as it stood when the day began, every warrior weaker than the one right next to them on the left falls. They all fall at once, and the row closes up. The first warrior never falls, and neither does anyone tied with the warrior on their left.
Return how many dawns saw at least one warrior fall. With no warriors, or if nobody falls, it is 0.
With [4, 7, 3, 5, 2, 6]: on the first day the 3 and the 2 fall, leaving [4, 7, 5, 6]; on the second the 5 falls, now with the 7 on its left, leaving [4, 7, 6]; on the third the 6 falls, leaving [4, 7]. On the fourth nobody falls: you return 3.
Examples
The example
[4, 7, 3, 5, 2, 6] → 3
They all fall on the same day
[5, 4, 3, 2, 1] → 1
Equals fall one per day
[7, 3, 3, 3] → 3
Each one stronger than the last
[1, 2, 3, 4] → 0
All equally strong
[5, 5, 5] → 0
A single warrior
[9] → 0
Besides these, the challenge has hidden tests that are revealed when you submit your solution.
You start with this
Python
def fight_days(strength):
passJavaScript
function fightDays(strength) {
}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.