Snow Plow Algorithm

#!/usr/bin/env lua

-- Edit those

local house_count = 1000
local bounds = { min = -1000, max = 1000}

-- Init and helper functions ---------------------------------------

math.randomseed(os.time())

local total_time = 0
local snow_plow
local street = {}

local function house_exists(distance)
    for i, house in ipairs(street) do
        if house.x == distance then
            return house
        end
    end
end

for i=1,house_count do
    local distance
    repeat -- Makes sure no houses are at the same spot
        distance = math.random() * (bounds.max - bounds.min) + bounds.min
    until not house_exists(distance)
    if distance ~= 0 then -- House at 0 is clean by default
        local new_house = {
            clean = false,
            x = distance,
            time = 0
        }

        street[#street + 1] = new_house
    end
end

do -- Adding a dummy house at 0 to be the starting point
    local new_house = {
        index = #street + 1,
        clean = true,
        x = 0,
        dummy = true
    }
    street[#street + 1] = new_house
end

table.sort(street, function(a, b) return a.x < b.x end)

for i, house in ipairs(street) do
    if i < #street then
        house.next = street[i + 1]
    end
    if i > 1 then
        house.prev = street[i - 1]
    end
    if house.dummy then
        snow_plow = house
    else
        print(("%g"):format(house.x))
    end
end

-- Calculates the density of house per max distance to the left and right of the plow
local function get_lr_density()
    local cursor = snow_plow
    local left, right = 0, 0

    while cursor.prev do
        cursor = cursor.prev
        if not cursor.clean then -- house isn't clean and should be counted
            left = left + 1
        end
    end
    if cursor ~= snow_plow then
        left = left / math.abs(cursor.x - snow_plow.x)
    end

    cursor = snow_plow
    while cursor.next do
        cursor = cursor.next
        if not cursor.clean then -- house isn't clean and should be counted
            right = right + 1
        end
    end
    if cursor ~= snow_plow then
        right = right / math.abs(cursor.x - snow_plow.x)
    end

    return left, right
end

-- Actual algorithm ------------------------------------------

while true do
    local left, right = get_lr_density()
    if left == 0 and right == 0 then break end -- We're done

    local old_x = snow_plow.x
    if left > right then -- left has more people
        while snow_plow.prev and snow_plow.clean do -- go left until we find the next unclean house
            snow_plow = snow_plow.prev
        end
    else -- right has more people
        while snow_plow.next and snow_plow.clean do -- go right until we find the next unclean house
            snow_plow = snow_plow.next
        end
    end
    local time = math.abs(old_x - snow_plow.x) -- Time spent during this maneuver
    for i, house in ipairs(street) do
        if not house.clean then -- Add wait time to every unclean house ...
            house.time = house.time + time
        end
    end
    total_time = total_time + time -- ... and to the total timer
    snow_plow.clean = true -- Clean the house after adding the wait time
end

-- Recap stuff

local total_times = 0
local total_houses = 0

for i, house in ipairs(street) do
    if not house.dummy then
        total_times = total_times + house.time
        total_houses = total_houses + 1
    end
end

local avg = total_times / total_houses

print(([[-----------------
Done !
Cleaned %d houses on a street going from %g to %g
Spent %g (UNIT) of total time (or distance)
Average wait time is %g (UNIT)
Total time to average ratio is %g (higher is better)]]):format(total_houses, bounds.min, bounds.max, total_time, avg, total_time / avg))