Skip to the content

The lamplighter's round

Problem

Paris, 1850. At nightfall, Anatole leaves his house with a pole on his shoulder and lights the lamps along a long street, always heading for the unlit lamp closest to him. He wants to know how far he walks.

You get lamps, the position of each lamp along the street: distinct whole numbers, in any order, that may be negative and are never 0 (the list may be empty). Anatole starts at position 0. While any lamp is still unlit, he walks to the unlit one closest to where he stands, adds that distance (the difference of the two positions, without sign) and lights it. If two are equally close, he goes to the smaller position. At the end he does not walk back home.

With [5, -2, 3, 9]: from 0 to -2 he walks 2, from -2 to 3 he walks 5, from 3 to 5 he walks 2 and from 5 to 9 he walks 4. In total, 13.

Return the total distance as a whole number. With no lamps, return 0.

Examples

  • The example

    [5, -2, 3, 9] → 13

  • A tie on the first step

    [3, -3, 5] → 11

  • The closest one changes with every step

    [-4, 3, 5] → 14

  • Three close and one far away

    [1, 2, 3, -10] → 16

  • A single lamp, to the left

    [-6] → 6

  • No lamps

    [] → 0

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

Python

def walk_length(lamps):
    pass

JavaScript

function walkLength(lamps) {
}
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 →