# python
from collections import namedtuple

# pypi
from attrs import define
from expects import contain_only, equal, expect

Direction = namedtuple("Direction", ["up_left", "up", "left"],
                       defaults=["\\", "|", "-"])()

@define
class LongestCommonSubsequence:
    """Finds the longest common subsequence of two sequences

    Args:
     x: first sequence
     y: second sequence
    """
    x: list
    y: list
    _table: list=None
    _trace_table: list=None
    _length: int=None

    @property
    def table(self) -> list:
        """The memoization table"""
        if self._table is None:
            self._table = [[0] + [None] * len(self.y)
                           for row in range(len(self.x) + 1)]
            for column in range(len(self.y) + 1):
                self._table[0][column] = 0
        return self._table

    @property
    def trace_table(self) -> list:
        """Table to reconstruct longest common subsequence"""
        if self._trace_table is None:
            self._trace_table = [[None] * len(self.y)
                                 for row in range(len(self.x))]
        return self._trace_table

    @property
    def length(self) -> int:
        """Number of characters in longest common subsequence"""
        if self._length is None:
            for row in range(1, len(self.x) + 1):
                for column in range(1, len(self.y) + 1):
                    previous_row, previous_column = row - 1, column - 1
                    unpadded_row, unpadded_column = row - 1, column - 1
                    if self.x[previous_row] == self.y[previous_column]:
                        self.table[row][column] = self.table[previous_row][previous_column] + 1
                        self.trace_table[unpadded_row][unpadded_column] = Direction.up_left
                    elif self.table[previous_row][column] >= self.table[row][previous_column]:
                        self.table[row][column] = self.table[previous_row][column]
                        self.trace_table[unpadded_row][unpadded_column] = Direction.up
                    else:
                        self.table[row][column] = self.table[row][previous_column]
                        self.trace_table[unpadded_row][unpadded_column] = Direction.left
            self._length = self.table[-1][-1]
        return self._length

    def print_lcs(self, row: int, column: int) -> None:
        """Prints the elements of the longest common subsequence

        Note:
         to start row and column should match the last cell in the trace table.

        Args:
         row: row in the trace_table to start with
         column: column in the trace_table to start with
        """
        if row < 0 or column < 0:
            return

        if self.trace_table[row][column] == Direction.up_left:
            self.print_lcs(row - 1, column - 1)
            print(self.x[row])
        elif self.trace_table[row][column] == Direction.up:
            self.print_lcs(row - 1, column)
        else:
            self.print_lcs(row, column - 1)
        return

    def print_longest(self):
        self.print_lcs(len(self.trace_table) - 1, len(self.trace_table[0]) - 1)
        return

x = "A B C B D A B".split()
y = "B D C A B A".split()
lcs = LongestCommonSubsequence(x, y)

expect(len(lcs.table)).to(equal(len(x) + 1))
expect(len(lcs.table[0])).to(equal(len(y) + 1))
for row in lcs.table:
    expect(row[0]).to(equal(0))

expect(lcs.table[0]).to(contain_only(*([0] * (len(y) + 1))))
expect(len(lcs.trace_table)).to(equal(len(x)))
expect(len(lcs.trace_table[0])).to(equal(len(y)))
expect(lcs.length).to(equal(4))

gallons_per_dollar = Fraction(1, 5)
joules_per_gallon = 13 * 10**7
joules_per_dollar = joules_per_gallon * gallons_per_dollar
MEGAJOULES_PER_JOULE = Fraction(1, 10**6)
gas_megajoules_per_dollar = joules_per_dollar * megajoules_per_joule
gasoline = 1/gas_megajoules_per_dollar

print_energy(float(gas_megajoules_per_dollar), "Gasoline")
COSTS.append((gasoline, "Gasoline"))

kilowatt_hours_per_dollar = 20 # 1/0.05 = 20
megajoules = 3.6
electricity_megajoules_per_dollar = kilowatt_hours_per_dollar * megajoules
electricity = 1/electricity_megajoules_per_dollar

print_energy(electricity_megajoules_per_dollar, "Electricity")
COSTS.append((electricity, "Electricity"))

joules_per_cubic_foot = 1.1E6
cubic_feet_per_btu = 1/1030
btus_per_dollar = 5e5

joules_per_btu = joules_per_cubic_foot * cubic_feet_per_btu

joules_per_dollar = joules_per_btu * btus_per_dollar
natural_gas_megajoules_per_dollar = joules_per_dollar * MEGAJOULES_PER_JOULE
natural_gas = 1/natural_gas_megajoules_per_dollar
print_energy(natural_gas_megajoules_per_dollar, "Natural Gas")
COSTS.append((natural_gas, "Natural Gas"))

coal_megajoules_per_dollar = MEGAJOULES_PER_JOULE * 3.2e10/40
coal = 1/coal_megajoules_per_dollar
print_energy(coal_megajoules_per_dollar, "Coal")
COSTS.append((coal, "Coal"))

ounces_per_dollar = 1/0.10
kilocalories_per_ounce = 240
joules_per_calorie = 4.2
calories_per_kilocalorie = 10**3

corn_megajoules_per_dollar = (ounces_per_dollar
                              * kilocalories_per_ounce
                              * calories_per_kilocalorie
                              * joules_per_calorie
                              * MEGAJOULES_PER_JOULE)
corn = 1/corn_megajoules_per_dollar
print_energy(corn_megajoules_per_dollar, "Corn")
COSTS.append((corn, "Corn"))

# python
from collections import namedtuple
from functools import partial

import random

# pypi
from attrs import define
from expects import (be_below_or_equal, contain_exactly, equal, expect,
                     raise_error)
from joblib import Parallel, delayed

import altair
import numpy
import pandas

# other monkey stuff
from graeae.visualization.altair_helpers import output_path, save_chart
from graeae import Timer

Solution = namedtuple("Solution", "value inventory count")
TableSolution = namedtuple("TableSolution", "value inventory count table")
NEGATIVE_INFINITY = float("-inf")
TIMER = Timer()

SLUG = "the-knapsack-problem"
OUTPUT_PATH = output_path(SLUG)
save_it = partial(save_chart, output_path=OUTPUT_PATH)

def brute_knapsack(capacity: int, values: list, weights: list) -> Solution:
    """Finds the best selection of items to maximize value

    Args:
     capacity: maximum weight allowed
     values: value for each item available
     weights: how much each item weighs

    Returns:
     best-value, count of each item, count of loops
    """
    assert len(values) == len(weights)

    number_of_items = len(values)
    items = [0] * number_of_items
    best_value = 0
    count = 0

    for combination in range(2**(number_of_items)):
        value, weight, carry = 0, 0, 1
        for item in range(number_of_items):
            increment = items[item] + carry
            keep = increment % 2
            carry = increment//2
            if keep:
                value += values[item]
                weight += weights[item]
            items[item] = keep
            count += 1
        if weight <= capacity and value > best_value:
            best_value = value
            solution = items[:]

    return Solution(value=best_value, inventory=solution, count=count)

def totals(inventory: list, values: list, weights: list) -> tuple:
    """Reduce the inventory values and weights to a total value and a total weight

    Args:
     inventory: list of item counts
     values: list of values for the items
     list of weights for the items

    Returns:
     value, weight for the inventory
    """
    value = sum((value for index, value in enumerate(values) if inventory[index]))
    weight = sum((weight for index, weight in enumerate(weights) if inventory[index]))
    return value, weight

def check_solution(solution: Solution,
                   expected_inventory: list,
                   values: list, weights: list, capacity: int):
    """Check that the solution matches the expected

    Args:
     solution: namedtuple with the knapsack solution
     expected_inventory: list of 0's and 1's representing which items to keep
     expected_value: total value expected for the solution
     values: values for the items
     weights: weights for the items
     capacity: maximum weight for the knapsack

    Raises:
     AssertionError if something isn't the expected
    """
    expect(solution.inventory).to(contain_exactly(*expected_inventory))
    value, weight = totals(solution.inventory, values, weights)
    expected_value, expected_weight = totals(expected_inventory, values, weights)
    expect(weight).to(be_below_or_equal(capacity))
    expect(weight).to(equal(expected_weight))
    expect(value).to(equal(expected_value))
    return

def check_examples(solver: object) -> None:
    """Check the toy examples

    Args:
     solver: function to find the optimal knapsack load
    """
    # values and weights don't match
    # broken = lambda : solver(5, [0, 1], [2, 1, 3])
    # expect(broken).to(raise_error(AssertionError))

    capacity = 10
    values = [42, 12, 40, 25]
    weights = [7, 3, 4, 5]
    expected = [0, 0, 1, 1]

    solution = solver(capacity, values, weights)
    check_solution(solution, expected, values, weights, capacity)

    capacity = 6
    values = [3, 2, 4, 4]
    weights = [4, 3, 2, 3]

    expected = [0, 0, 1, 1]
    solution = solver(capacity, values, weights)
    check_solution(solution, expected, values, weights, capacity)

    capacity = 18
    values = [0, 3, 7, 7, 2, 5, 3, 0]
    weights = [4, 4, 6, 6, 1, 5, 2, 5]
    expected = [0, 0, 1, 1, 1, 1, 0, 0]
    solution = solver(capacity, values, weights)
    check_solution(solution, expected, values, weights, capacity)

    # this won't work for greedy algorithms
    capacity = 10
    values = [42, 20, 25, 6]
    weights = [7, 4, 5, 6]
    expected = [0, 1, 1, 0]
    return

check_examples(brute_knapsack)

values = [3, 4, 2, 4]
weights = [4, 2, 3, 3]
capacity = 6
solution = brute_knapsack(capacity=capacity, values=values, weights=weights)
print(f"Call Count: {solution.count}")
print(f"Chosen knapsack value {solution.value}")
print(f"Item inventory: {solution.inventory}")

expect(solution.count).to(equal(len(values) * 2**len(values)))
expect(solution.value).to(equal(8))
expect(solution.inventory).to(contain_exactly(0, 1, 0, 1))

def exhausted(capacity: int, values: list, weights: list, this_item: int=0) -> Solution:
    """Find the optimal knapsack using an exhaustive search

    Args:
     capacity: how much weight the knapsack can hold
     values: how much the items are worth
     weights: hom much the items weigh
     this_item: index of the current item in the values and weights
     count: number of times this function is called
    """
    assert len(values) == len(weights)

    next_item = this_item + 1

    # quit this branch if the knapsack is already out of space
    if capacity == 0:
         return Solution(0, [0] * (len(weights) - this_item), 1)

    # to save on an extra base-case call handle the last item separately here
    if next_item == len(weights):
        skip_this_item = Solution(0, [0], 1)

        if weights[this_item] > capacity:
            return skip_this_item

        use_this_item = Solution(value=values[this_item],
                                 inventory=[1], count=1)
        return max((skip_this_item, use_this_item), key=lambda x: x.value)

    # now on to the recursive cases
    descendant_solution = exhausted(this_item=next_item, capacity=capacity,
                                    values=values, weights=weights)

    skip_count = descendant_solution.count + 1
    skip_this_item = Solution(value=descendant_solution.value,
                              inventory=[0] + descendant_solution.inventory,
                              count=skip_count)

    if capacity < weights[this_item]:
        solution = skip_this_item
        count = skip_count
    else:
        capacity_after_this_item_is_added = capacity - weights[this_item]
        descendant_solution = exhausted(
            this_item=next_item,
            capacity=capacity_after_this_item_is_added,
            values=values,
            weights=weights)

        check_count = skip_count + descendant_solution.count

        include_this_item = Solution(value=values[this_item] + descendant_solution.value,
                                     inventory=[1] + descendant_solution.inventory,
                                     count=check_count)

        skip_this_item = Solution(value=skip_this_item.value,
                                  inventory=skip_this_item.inventory,
                                  count=check_count)
        solution = max((skip_this_item, include_this_item), key=lambda x: x.value)
        count = check_count
    return solution

check_examples(exhausted)

values = [3, 4, 2, 4]
weights = [4, 2, 3, 3]
capacity = 6
solution = exhausted(capacity=capacity, values=values, weights=weights)
brute_solution = brute_knapsack(capacity=capacity, values=values, weights=weights)
print(f"Call Count: {solution.count}")
print(f"Chosen knapsack value {solution.value}")
print(f"Item inventory: {solution.inventory}")

expect(solution.value).to(equal(brute_solution.value))
expect(solution.inventory).to(contain_exactly(*brute_solution.inventory))

@define
class Memorizer:
    """Dynamic Programming solution to the knapsack problem

    Args:
     capacity: total capacity (by weight) of knapsack
     values: values for items to put in knapsack
     weights: weights for items to put in knapsack
    """
    capacity: int
    values: list
    weights: list
    _items: int=None
    _table: list=None
    count: int=0
    _value: int=None
    _inventory: list=None

    @property
    def items(self) -> int:
        """The number of items available for the knapsack

        Raises:
         AssertionError: the number of values and weights don't match

        Returns:
         number of items
        """
        if self._items is None:
            assert len(self.values) == len(self.weights)
            self._items = len(self.values)
        return self._items

    @property
    def value(self) -> int:
        """The total value of the optimal knapsack"""
        if self._value is None:
            self._value = self.find_value(self.items,
                                          self.capacity)
        return self._value

    @property
    def table(self) -> list:
        """The memo table

        Returns:
        items + 1 x capacity + 1 list of lists: 0's in 0 column/row, -1 elsewhere
        """
        if self._table is None:
            first_row = [0] * (self.capacity + 1)
            row = [0] + [-1] * self.capacity
            table = [row[:] for item in range(self.items)]
            self._table = [first_row] + table
        return self._table

    def find_value(self, item: int, capacity: int) -> int:
        """Find the best total value for the knapsack

        Args:
         item: the number of the item to use (0...item)
         capacity: maximum weight allowed

        Returns:
         best-value
        """
        self.count += 1
        # the table is padded 
        # so we need to adjust the item index for weights, values
        this_item = item - 1
        if self.table[item][capacity] < 0:
            previous_item = item - 1
            previous_value = self.find_value(previous_item, capacity)

            if capacity < self.weights[this_item]:
                value = previous_value
            else:
                value = max(previous_value,
                            self.values[this_item] + self.find_value(
                                previous_item,
                                capacity - self.weights[this_item]))
            self.table[item][capacity] = value
        return self.table[item][capacity]

    @property
    def inventory(self) -> list:
        """Reconstructs the optimal knapsack load using the table

        Returns:
         inventory of items in the optimal knapsack
        """
        if self._inventory is None:
            # make sure that the problem has already been solved
            self()
            self._inventory = [0] * self.items
            remaining_capacity = self.capacity

            for table_item in range(self.items, 0, -1):
                # table_item is padded by one
                this_item = previous_table_item = table_item - 1

                if (self.weights[this_item] <= remaining_capacity and
                    self.table[previous_table_item][
                        remaining_capacity - self.weights[this_item]]
                    + self.values[this_item]
                    >= self.table[previous_table_item][remaining_capacity]):
                    self._inventory[this_item] = 1
                    remaining_capacity -= self.weights[this_item]
        return self._inventory            

    def __call__(self) -> int:
        """Finds the best solution:

        As a side effect this also sets self.value

        Returns:
         value for optimal knapsack
        """
        return self.value

sizes = list(range(2, 61))

# 0 weights break the Memorizer so make sure everything weighs at least 1
values = [random.choices(list(range(1, size)), k=size) for size in sizes]
weights = [random.choices(list(range(1, random.randint(1, size) * size)), k=size)
           for size in sizes]
capacities = [sum(random.choices(weight, k=4)) for weight in weights]

capacities_values_weights = list(zip(capacities, values, weights))

with TIMER:
    exhaustive_output = Parallel(n_jobs=-1)(
    delayed(exhausted)(capacity, values, weights)
        for capacity,values,weights in capacities_values_weights)

def memorizer_knapsack(capacity, values, weights):
    memorizer = Memorizer(capacity, values, weights)
    memorizer()
    return memorizer

with TIMER:
    memorized_output = Parallel(n_jobs=-1)(
    delayed(memorizer_knapsack)(capacity, values, weights)
        for capacity,values,weights in capacities_values_weights)

for index, output in enumerate(exhaustive_output):
    try:
        expect(output.value).to(equal(memorized_output[index].value))
        capacity, value, weight = capacities_values_weights[index]
        b_value, b_weight = totals(output.inventory,
                                   value,
                                   weight)
        m_value, m_weight = totals(memorized_output[index].inventory,
                                   value,
                                   weight)
        expect(m_value).to(equal(b_value))
        expect(m_weight).to(be_below_or_equal(capacity))
    except AssertionError as error:
        c, v, w = capacities_values_weights[index]
        print(f"Index: {index}")
        print(error)
        print(f"Brute: {brute_knapsack(c, v, w)}")
        raise

frame = pandas.DataFrame({"Items": sizes,
                          "Exhaustive": [
                              solution.count
                              for solution in exhaustive_output],
                          "Memoized": [
                              solution.count
                              for solution in memorized_output]})

melted = frame.melt(id_vars=["Items"],
                    value_vars=["Exhaustive", "Memoized"],
                    var_name="Algorithm", value_name="Calls")

chart = altair.Chart(melted).mark_line(point=True).encode(
    x="Items",
    y="Calls",
    color="Algorithm",
    tooltip=[altair.Tooltip("Items", format=","),
             altair.Tooltip("Calls", format=","),
             "Algorithm"],
).properties(
    title="Exhaustive vs Memoized Knapsack Solution",
    width=800,
    height=525
)

save_it(chart, "exhaustive-vs-memoized")

UPPER_BOUND = 47
trimmed = melted[melted.Items < UPPER_BOUND]
chart = altair.Chart(trimmed).mark_line(point=True).encode(
    x="Items",
    y="Calls",
    color="Algorithm",
    tooltip=[altair.Tooltip("Items", format=","),
             altair.Tooltip("Calls", format=","),
             "Algorithm"],
).properties(
    title=f"Exhaustive vs Memoized Knapsack Solution (< {UPPER_BOUND})",
    width=800,
    height=525
)

save_it(chart, "exhaustive-vs-memoized-trimmed")

@define
class CaptainDynamic(Memorizer):
    """Dynamic Programming solution to the knapsack problem

    Args:
     capacity: total capacity (by weight) of knapsack
     values: values for items to put in knapsack
     weights: weights for items to put in knapsack
    """
    @property
    def value(self) -> int:
        """The total value of the optimal knapsack"""
        if self._value is None:
            self._value = self.find_value()
        return self._value

    def find_value(self) -> int:
        """Finds the optimal value"""
        for item_row in range(1, self.items + 1):
            previous_item = this_item = item_row - 1
            for capacity in range(self.capacity + 1):
                skip_this_item = self.table[previous_item][capacity]
                if self.weights[this_item] > capacity:
                    self.table[item_row][capacity] = skip_this_item
                else:
                    use_this_item = (
                        self.table[previous_item][
                            capacity - self.weights[this_item]] +
                        self.values[this_item])

                    self.table[item_row][capacity] = max(
                        (skip_this_item, use_this_item)
                    )
                self.count += 1
        return self.table[self.items][self.capacity]

def dynamic_knapsack(capacity, values, weights):
    captain = CaptainDynamic(capacity, values, weights)
    captain()
    return captain

with TIMER:
    dynamic_output = Parallel(n_jobs=-1)(
    delayed(dynamic_knapsack)(capacity, values, weights)
        for capacity,values,weights in capacities_values_weights)

for index, output in enumerate(exhaustive_output):
    try:
        expect(output.value).to(equal(dynamic_output[index].value))
        capacity, value, weight = capacities_values_weights[index]
        b_value, b_weight = totals(output.inventory,
                                   value,
                                   weight)
        m_value, m_weight = totals(dynamic_output[index].inventory,
                                   value,
                                   weight)
        expect(m_value).to(equal(b_value))
        expect(m_weight).to(be_below_or_equal(capacity))
    except AssertionError as error:
        c, v, w = capacities_values_weights[index]
        print(f"Index: {index}")
        print(error)
        print(f"Brute: {brute_knapsack(c, v, w)}")
        raise

frame = pandas.DataFrame({"Items": sizes,
                          "Dynamic": [
                              solution.count
                              for solution in dynamic_output],
                          "cN": [
                              solution.capacity * solution.items
                              for solution in dynamic_output],
                          "Memoized": [
                              solution.count
                              for solution in memorized_output]})

melted = frame.melt(id_vars=["Items"],
                    value_vars=["Dynamic", "Memoized", "cN"],
                    var_name="Algorithm", value_name="Calls")

chart = altair.Chart(melted).mark_line(point=True).encode(
    x="Items",
    y="Calls",
    color="Algorithm",
    tooltip=[altair.Tooltip("Items", format=","),
             altair.Tooltip("Calls", format=","),
             "Algorithm"],
).properties(
    title="Dynamic vs Memoized Knapsack Solution",
    width=800,
    height=525
)

save_it(chart, "dynamic-vs-memoized")

# python
from collections import namedtuple
from functools import partial

# pypi
from expects import contain_exactly, expect, equal

import altair
import pandas

# my stuff
from graeae.visualization.altair_helpers import output_path, save_chart

ChangeCounts = namedtuple("ChangeCounts", ["coin_counts", "run_count"])
ChangeCountsTable = namedtuple("ChangeCounts", ["coin_counts", "run_count", "table"])

SLUG = "the-coin-changing-problem"
OUTPUT_PATH = output_path(SLUG)
save_it = partial(save_chart, output_path=OUTPUT_PATH)

PlotParameters = namedtuple("PlotParameters", ["height", "width"],
                            defaults=[525, 750])()

Denominations = namedtuple("Denominations", "US double_dime obsolete",
                           defaults=[[25, 10, 5, 1],
                                    [25, 20, 10, 5, 1],
                                    [25, 20, 10, 5, 3, 2, 1]])()

def cashier_changer(amount: int, denominations: list) -> ChangeCounts:
    """Implements the cashier's method for making change

    Args:
     amount: the value of the change needed
     denominations: values for coins (in descending order)

    Returns:
     list of coin-counts, number of loops ran
    """
    coins = [0] * len(denominations)
    remainder = amount
    loop_count = 0

    for index, denomination in enumerate(denominations):
        coin_count = 0
        while denomination <= remainder:
            coin_count += 1
            loop_count += 1
            remainder = remainder - denomination

        coins[index] = coin_count
    return ChangeCounts(coin_counts=coins, run_count=loop_count)

PLOT_AMOUNTS = list(range(1, 100))
CASHIER_COUNTS = [cashier_changer(amount, Denominations.US).run_count
                  for amount in PLOT_AMOUNTS]

PLOT_FRAME = pandas.DataFrame({"Amount to Change": PLOT_AMOUNTS,
                               "Coins": CASHIER_COUNTS})

chart = altair.Chart(PLOT_FRAME).mark_bar().encode(
    x=altair.X("Amount to Change", axis=altair.Axis(tickMinStep=1)),
    y=altair.Y("Coins", axis=altair.Axis(tickMinStep=1)),
    tooltip=["Amount to Change", "Coins"]).properties(
        title="Cashier's Change Coin Counts (Common U.S. Coins)",
        width=PlotParameters.width,
        height=PlotParameters.height,
    )

save_it(chart, "cashiers-change-us-coins")

def greedy_changer(money: int, denominations: list) -> ChangeCounts:
    """Make change using the fewest coins

    Args:
     money: the amount to change
     denominations: list of coin denominations in decreasing order

    Returns:
     Number of each denomination needed to make the change, loop-count
    """
    coins = [0] * len(denominations)
    remainder = money
    count = 0
    for location, denomination in enumerate(denominations):
        coins[location] = remainder // denomination
        remainder = remainder - denomination * coins[location]
        count += 1
    return ChangeCounts(coins, count)

greedy_counts = [greedy_changer(amount, Denominations.US).run_count
                 for amount in PLOT_AMOUNTS]
GREEDY_FRAME = PLOT_FRAME.rename(columns={"Coins": "Cashier"})
GREEDY_FRAME["Greedy"] = greedy_counts
melted = GREEDY_FRAME.melt(id_vars=["Amount to Change"],
                           value_vars=["Greedy", "Cashier"],
                           var_name="Change Method",
                           value_name="Loop Count")

chart = altair.Chart(melted).mark_line(point=True).encode(
    x="Amount to Change",
    y=altair.Y("Loop Count", axis=altair.Axis(tickMinStep=1)),
    tooltip=["Amount to Change", "Loop Count", "Change Method"],
    color="Change Method").properties(
        title="Cashier's and Greedy Change Coin Counts (Common U.S. Coins)",
        width=PlotParameters.width,
        height=PlotParameters.height,
    )

save_it(chart, "cashiers-greedy-change-us-coins")

brute_counts = [brute_changer(amount, Denominations.US).run_count
                for amount in PLOT_AMOUNTS]
GREEDY_FRAME["Brute-Force"] = brute_counts
melted = GREEDY_FRAME.melt(id_vars=["Amount to Change"],
                           value_vars=["Greedy", "Cashier", "Brute-Force"],
                           var_name="Change Method",
                           value_name="Loop Count")

chart = altair.Chart(melted).mark_line(point=True).encode(
    x="Amount to Change",
    y=altair.Y("Loop Count", axis=altair.Axis(tickMinStep=1)),
    tooltip=["Amount to Change", "Loop Count", "Change Method"],
    color="Change Method").properties(
        title="Greedy Change & Brute-Force Coin Counts (Common U.S. Coins)",
        width=PlotParameters.width,
        height=PlotParameters.height,
    )

save_it(chart, "brute-force-change-us-coins")

def check_changers(changer: object, amount: int, denominations: list):
    """Check that the changer matches the brute-force solution

    Arguments:
     changer: change-function to compare to brute-force
     amount: cents to change
     denominations: descending list of coin-denominations

    Raises:
     AssertionError: there's a discrepancy somewhere
    """
    brute_counts = brute_changer(amount, denominations)
    check_counts = changer(amount, denominations)
    check_coins(check_counts.coin_counts, denominations, brute_counts.coin_counts, amount)
    return

def check_cases(changer: object) -> None:
    """Check the pre-picked cases are okay

    Arguments:
     changer: the dynamic-programming changer to check

    Raises:
     AssertionError if something doesn't check out
    """
    for amount in range(100):
        check_changers(changer, amount, Denominations.US)
        check_changers(changer, amount, Denominations.double_dime)
        check_changers(changer, amount, Denominations.obsolete)

        money = 2
        coins = [10, 5, 1]
        check_changers(memoized_changer, money,  coins)

        money = 28
        check_changers(memoized_changer, money,  coins)

        coins = [25, 10, 5, 1]
        check_changers(memoized_changer, money,  coins)

        money = 14
        check_changers(memoized_changer, money,  coins)

        # the double-dimes
        coins = [25, 20, 10, 5, 1]
        money = 40
        check_changers(memoized_changer, money,  coins)
        return

check_cases(memoized_changer)