#!/usr/local/cpython-3.12/bin/python3
"""
Find a good solution to the house robber problem, using a Genetic Algorithm.
The solution found is not necessarily optimal.
The problem:
A robber wishes to maximize the value of robbing houses on a given street full of houses.
However, he/she cannot rob adjacent houses; if attempted, this will result in being
caught.
Input:
Values of robbing each house, as floats, one per line - on stdin.
Output:
1) The total value obtained by the robber.
2) List of tuples. Each tuple is the value of one house, and "rob" or "skip".
On genetic algorithms: https://en.wikipedia.org/wiki/Genetic_algorithm
"""
import sys
import copy
import random
import typing
class House:
"""Describe one house."""
def __init__(self, value_from_robbers_perspective: float) -> None:
"""Initialize."""
self.value = value_from_robbers_perspective
self.to_be_robbed = False
def plan_to_rob(self) -> None:
"""Plan to rob this house."""
self.to_be_robbed = True
def plan_to_skip(self) -> None:
"""Plan to skip this house."""
self.to_be_robbed = False
def flip_plan(self) -> None:
"""Change the plan for this house."""
self.to_be_robbed = not self.to_be_robbed
def as_tuple(self) -> typing.Tuple[float, str]:
"""Return a tuple describing this house from the robber's perspective, as part of describing the solution."""
if self.to_be_robbed:
string = 'rob'
else:
string = 'skip'
tuple_ = (self.value, string)
return tuple_
def __str__(self) -> str:
"""Convert to str."""
return str(self.as_tuple())
__repr__ = __str__
def __copy__(self):
"""Copy this house to a new house."""
new_house = House(self.value)
new_house.to_be_robbed = self.to_be_robbed
return new_house
def __eq__(self, other):
"""Return True iff self == other."""
return self.value == other.value and self.to_be_robbed == other.to_be_robbed
class OnePlan:
"""Hold a street plan for the robber."""
def __init__(self, house_values: typing.Union[typing.Iterator[float], typing.List[float]]) -> None:
"""Initialize."""
self.houses = [House(value) for value in house_values]
def __eq__(self, other):
"""Return True iff our houses are the same as other's."""
return self.houses == other.houses
def one_mutation(self) -> None:
"""Change the plan for one random house - rob to skip, or skip to rob."""
while True:
house = random.choice(self.houses)
house.flip_plan()
if self.is_valid():
return
# Change it back before trying again
house.flip_plan()
def is_valid(self) -> bool:
"""Return True iff no adjacent houses are both to be robbed."""
for left_house, right_house in zip(self.houses, self.houses[1:]):
if left_house.to_be_robbed and right_house.to_be_robbed:
return False
return True
def __str__(self) -> str:
"""Convert to string."""
return '{}: '.format(self.value_of_plan()) + ', '.join(str(house) for house in self.houses)
__repr__ = __str__
def __copy__(self):
"""Copy this plan to a new plan."""
new_plan = OnePlan(house.value for house in self.houses)
for index, new_house in enumerate(new_plan.houses):
if self.houses[index].to_be_robbed:
new_house.plan_to_rob()
return new_plan
def __len__(self):
"""Return the number of houses on the street."""
return len(self.houses)
def value_of_plan(self) -> float:
"""Return the total value of the plan for the robber."""
assert self.is_valid()
return sum(house.value for house in self.houses if house.to_be_robbed)
def initial_population(floats: typing.Iterable[float], start_simple: bool) -> typing.List[OnePlan]:
"""
Generate an initial population.
One generation will be a street that isn't robbed.
Several generations will be just one house being robbed on the entire street.
Two more generations will be all of the evens, and all of the odds.
"""
generations = []
float_list = list(floats)
all_skipped = OnePlan(float_list)
generations.append(all_skipped)
if start_simple:
# We do just one of these, so we can crossover, but we can also see things progressing...
just_one_robbed = OnePlan(float_list)
just_one_robbed.houses[0].plan_to_rob()
generations.append(just_one_robbed)
else:
# We generate some reasonable guesses for speed...
for index in range(len(all_skipped)):
each_just_one_robbed = OnePlan(float_list)
each_just_one_robbed.houses[index].plan_to_rob()
generations.append(each_just_one_robbed)
evens = OnePlan(float_list)
for index in range(0, len(all_skipped), 2):
evens.houses[index].plan_to_rob()
generations.append(evens)
odds = OnePlan(float_list)
for index in range(1, len(all_skipped), 2):
odds.houses[index].plan_to_rob()
generations.append(odds)
return generations
class Population:
"""
Hold a "population" of street plans.
These are some of the reasonably-good guesses found so far.
Each element of self.street_plans is a single plan for getting the most from the street.
"""
def __init__(
self,
floats: typing.Iterable[float],
do_initial_guesses=True,
start_simple=False,
) -> None:
"""Initialize."""
if do_initial_guesses:
self.street_plans = initial_population(floats, start_simple=start_simple)
else:
self.street_plans = []
def __eq__(self, other):
"""Return True iff self.street_plans == other.street_plans."""
return self.street_plans == other.street_plans
def __iter__(self) -> typing.Iterator[OnePlan]:
"""Iterate over the street_plans of this population."""
yield from self.street_plans
def sort(self) -> None:
"""Sort self from best plan to worst - so far."""
list_ = []
for planno, one_plan in enumerate(self):
# The "planno" number keeps us from trying to compare one_plan's, which do not have enough comparison operators
# defined. This works because planno is always unique.
list_.append((one_plan.value_of_plan(), planno, one_plan))
list_.sort(reverse=True)
# Throw away all but the one_plan
self.street_plans = [element[2] for element in list_]
def dedup(self) -> None:
"""Deduplicate street_plans. Assumes the list is sorted."""
# Strictly speaking this is O(n^2), but it should in practice be pretty close to O(n)."""
len_street_plans = len(self.street_plans)
index = 0
# for index, street_plan in enumerate(self.street_plans):
while True:
street_plan = self.street_plans[index]
dup_candidate = index + 1
while True:
if dup_candidate >= len_street_plans:
return
if street_plan == self.street_plans[dup_candidate]:
del self.street_plans[dup_candidate]
len_street_plans -= 1
else:
# Leave the inner loop to check the next index
break
index += 1
def sort_dedup_and_truncate(self, max_elements: int) -> None:
"""Sort the list of street plans and truncate it to a number of values that is something manageable."""
self.sort()
self.dedup()
self.street_plans = self.street_plans[:max_elements]
def create_new_population(self) -> 'Population':
"""Create a new population from old_population. Hopefully it'll be better."""
self.sort()
new_population = Population([], do_initial_guesses=False)
plans = copy.copy(self.street_plans)
for left_planno, left_plan in enumerate(self):
# Random choice: 0 or 1
random_number = random.randrange(2)
if random_number == 0:
# Mutate one plan
plan = copy.copy(left_plan)
plan.one_mutation()
plans.append(plan)
elif random_number == 1:
# crossover two plans: left and right
plan = do_one_crossover(self, left_plan, left_planno)
else:
raise AssertionError('random_number not 0 or 1: {}'.format((random_number, )))
plans.append(plan)
new_population.street_plans = plans
return new_population
def __str__(self) -> str:
"""Convert to a str."""
list_ = [str(street_plan) for street_plan in self.street_plans]
return '\n'.join(list_)
__repr__ = __str__
def are_all_lengths_equal(plans: typing.List[OnePlan]) -> bool:
"""Return True iff all plan lengths are the same."""
# This is for debugging
lengths = [len(plan) for plan in plans]
first_length = lengths[0]
return all(first_length == other_length for other_length in lengths)
def do_one_crossover(population: Population, left_plan: OnePlan, left_planno: int):
"""Do a crossover between two plans."""
plan = copy.copy(left_plan)
assert are_all_lengths_equal(population.street_plans)
num_houses = len(population.street_plans[0].houses)
num_plans = len(population.street_plans)
while True:
# Pick a right_planno that isn't equal to left_planno
while True:
right_planno = random.randrange(num_plans)
if right_planno != left_planno:
# Break out of this inner loop
break
right_plan = population.street_plans[right_planno]
# BTW, it doesn't make sense to do a null crossover, so we do these 1's
dividing_point = random.randrange(1, num_houses - 1)
plan.houses = left_plan.houses[:dividing_point] + right_plan.houses[dividing_point:]
if plan.is_valid():
# Return, effectively terminating the outer loop
return plan
# Otherwise, go back up for another iteration
def make_used(var: object) -> None:
"""Convince pylint and pyflakes that var is used."""
assert True or var
def usage(retval: int) -> None:
"""Output a usage message."""
if retval:
write = sys.stderr.write
else:
write = sys.stdout.write
write('Usage: {} --verbose --generations 10 --max-population-size 100 --help\n'.format(sys.argv[0]))
sys.exit(retval)
def main() -> None:
"""Generate a good solution."""
verbose = False
# This is often not enough, but it's quick :)
generations = 10
max_population_size = 100
start_simple = False
while sys.argv[1:]:
if sys.argv[1] in ('-v', '--verbose'):
verbose = True
elif sys.argv[1] == '--start-simple':
start_simple = True
elif sys.argv[1] == '--generations':
generations = int(sys.argv[2])
del sys.argv[1]
elif sys.argv[1] == '--max-population-size':
max_population_size = int(sys.argv[2])
del sys.argv[1]
elif sys.argv[1] in ('-h', '--help'):
usage(0)
else:
sys.stderr.write('{}: unrecognized option: {}\n'.format(sys.argv[0], sys.argv[1]))
usage(1)
del sys.argv[1]
population = Population([float(line) for line in sys.stdin.readlines()], do_initial_guesses=True, start_simple=start_simple)
for generationno in range(generations):
make_used(generationno)
population = population.create_new_population()
population.sort_dedup_and_truncate(max_population_size)
if verbose:
# The street plans are sorted in reverse order of value to the thief.
print(population.street_plans[0])
if not verbose:
# If verbose, this was already printed once, so we don't bother to do it again.
# The street plans are sorted in reverse order of value to the thief.
print(population.street_plans[0])
main()