Skip to the content

The warriors of Cadmus

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):
    pass

JavaScript

function fightDays(strength) {
}
Solve this challenge

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.

More O(n²) challenges

See all challenges →