The Puzzle Of Misanthropic Neighbors?

Problem

The misanthropes are coming. Suppose there is a row of some number, \(N\), of houses in a new, initially empty development. Misanthropes are moving into the development one at a time and selecting a house at random from those that have nobody in them and nobody living next door. They keep on coming until no acceptable houses remain. At most, one out of two houses will be occupied; at least one out of three houses will be. But what’s the expected fraction of occupied houses as the development gets larger, that is, as \(N\) goes to infinity?

Solution

from random import sample

runs = 10000
n = 1000
total_occupancy = 0
for _ in range(runs):
    remaining_houses = set(range(n))
    chosen_houses = []
    while remaining_houses:
        chosen_house = sample(remaining_houses, 1)[0]
        chosen_houses.append(chosen_house)
        remaining_houses.discard(chosen_house)
        for adj in [-1, 1]:
            remaining_houses.discard(chosen_house + adj)
    total_occupancy += len(chosen_houses)
print(total_occupancy/(n*runs))

The fraction of the occupied houses for large \(n\) is approximately is \(0.4325773\).