#!/usr/local/pypy3-5.10.0/bin/pypy3

"""
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.Union[None, typing.List[float]] = None, 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()