<commit_before>from __future__ import absolute_import
from __future__ import division
from __future__ import print_function


"""Count Coin Changes.

Count how many distinct ways you can make change that amount.
Assume that you have an infinite number of each kind of coin.
"""


def count_coin_changes_recur(amount, coins, n):
    """Count changes by recursion.

    Time complexity: O(2^n).
    Space complexity: O(1).
    """
    if amount < 0:
        return 0
    if amount == 0:
        return 1

    # When number of coins is 0 but there is still amount remaining.
    if n < 0 and amount >= 1:
        return 0

    # Compute ways with coin n included plus that with coin excluded.
    count_in = count_coin_changes_recur(amount - coins[n], coins, n)
    count_out = count_coin_changes_recur(amount, coins, n - 1)
    return count_in + count_out


def _count_coin_changes_memo(amount, coins, T, n):
    """Helper function for count_changes_memo()."""
    if amount == 0:
        return 1
    if amount < 0:
        return 0

    if n < 0 and amount >= 1:
        return 0

    if T[n][amount]:
        return T[n][amount]

    count_in = _count_coin_changes_memo(amount - coins[n - 1], coins, T, n)
    count_out = _count_coin_changes_memo(amount, coins, T, n - 1)
    T[n][amount] = count_in + count_out

    return T[n][amount]


def count_coin_changes_memo(amount, coins):
    """Count changes by top-bottom dynamic programming: 
    recursion + memoization.

    Time complexity: O(a * c), where a is amount, and c is number of coins.
    Space complexity: O(a * c).
    """
    n = len(coins) - 1
    T = [[0] * (amount + 1) for c in range(n + 1)]

    for c in range(n + 1):
        T[c][0] = 1

    return _count_coin_changes_memo(amount, coins, T, n)


def count_coin_changes_dp(amount, coins):
    """Count changes by bottom-up dynamic programming.

    Time complexity: O(a * c), where a is amount, and c is number of coins.
    Space complexity: O(a * c).
    """
    n = len(coins) - 1
    T = [[0] * (amount + 1) for c in range(n + 1)]

    for c in range(n):
        T[c][0] = 1

    for c in range(n + 1):
        for a in range(1, amount + 1):
            if a >= coins[c]:
                count_in = T[c][a - coins[c]]
            else:
                count_in = 0

            if c >= 1:
                count_out = T[c - 1][a]
            else:
                count_out = 0

            T[c][a] = count_in + count_out

    return T[-1][-1]


def main():
    import time

    amount = 5
    coins = [1, 2, 3]    # Ans = 5.
    n = len(coins) - 1

    start_time = time.time()
    print('Make change by recursion: {}'
          .format(count_coin_changes_recur(amount, coins, n)))
    print('Time: {}'.format(time.time() - start_time))

    start_time = time.time()<commit_msg>Revise DP, revise var to n_changes<commit_after>from __future__ import absolute_import
from __future__ import division
from __future__ import print_function


"""Count Coin Changes.

Count how many distinct ways you can make change that amount.
Assume that you have an infinite number of each kind of coin.
"""


def count_coin_changes_recur(amount, coins, n):
    """Count changes by recursion.

    Time complexity: O(2^n).
    Space complexity: O(1).
    """
    if amount < 0:
        return 0
    if amount == 0:
        return 1

    # When number of coins is 0 but there is still amount remaining.
    if n < 0 and amount >= 1:
        return 0

    # Compute ways with coin n included plus that with coin excluded.
    n_changes_in = count_coin_changes_recur(amount - coins[n], coins, n)
    n_changes_out = count_coin_changes_recur(amount, coins, n - 1)
    n_changes = n_changes_in + n_changes_out
    return n_changes


def _count_coin_changes_memo(amount, coins, T, n):
    """Helper function for count_changes_memo()."""
    if amount == 0:
        return 1
    if amount < 0:
        return 0

    if n < 0 and amount >= 1:
        return 0

    if T[n][amount]:
        return T[n][amount]

    n_changes_in = _count_coin_changes_memo(amount - coins[n - 1], coins, T, n)
    n_changes_out = _count_coin_changes_memo(amount, coins, T, n - 1)
    T[n][amount] = n_changes_in + n_changes_out

    return T[n][amount]


def count_coin_changes_memo(amount, coins):
    """Count changes by top-bottom dynamic programming: 
    recursion + memoization.

    Time complexity: O(a * c), where a is amount, and c is number of coins.
    Space complexity: O(a * c).
    """
    n = len(coins) - 1
    T = [[0] * (amount + 1) for c in range(n + 1)]

    for c in range(n + 1):
        T[c][0] = 1

    return _count_coin_changes_memo(amount, coins, T, n)


def count_coin_changes_dp(amount, coins):
    """Count changes by bottom-up dynamic programming.

    Time complexity: O(a * c), where a is amount, and c is number of coins.
    Space complexity: O(a * c).
    """
    n = len(coins) - 1
    T = [[0] * (amount + 1) for c in range(n + 1)]

    for c in range(n):
        T[c][0] = 1

    for c in range(n + 1):
        for a in range(1, amount + 1):
            if a < coins[c]:
                T[c][a] = T[c - 1][a]
            else:
                T[c][a] = T[c - 1][a] + T[c][a - coins[c]]

    return T[-1][-1]


def main():
    import time

    amount = 5
    coins = [1, 2, 3]    # Ans = 5.
    n = len(coins) - 1

    start_time = time.time()
    print('Make change by recursion: {}'
          .format(count_coin_changes_recur(amount, coins, n)))
    print('Time: {}'.format(time.time() - start_time))

    start_time = time.time()
{'fraction_non_alphanumeric': 0.11725504322766571, 'fraction_numerical': 0.016930835734870316, 'mean_word_length': 2.37363304981774, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1747706', 'n_tokens_mistral': 1971, 'n_tokens_neox': 1820, 'n_words': 629}