Partition problem

can_balance

# We have some rocks represented as numbers (weights of the rocks)

# We want to know if its possible to balance scales using all of our rocks.

# Given a list of numbers,
# return if it is possible to partition the numbers into two sets with equal sums,
# where a number has to be in either one or the other set.

# eg
# [10, 10] -> True
# [1, 2, 3] -> True
# [4, 3] -> False
# [4, 3, 1] -> True
# [] -> True
# [0] -> True
# [1] -> False

# hint 1
# First a recursive solution,
# at each rock the function considers adding that rock to the left or the right,
# if either can balance then it balances!
# the recurrence relation for the time this takes is `f(n) = 2 * f(n - 1)` this results in `O(2^n)` runtime

# hint - here is the recursive solution
def can_balance_recursive(rocks, current_rock_index=0, left_weight=0, right_weight=0):
    if current_rock_index >= len(rocks):
        return left_weight == right_weight

    return can_balance_recursive(
        rocks, current_rock_index + 1, left_weight + rocks[current_rock_index], right_weight
    ) or can_balance_recursive(
        rocks, current_rock_index + 1, left_weight, right_weight + rocks[current_rock_index]
    )


# hint
# The recursive solution solves overlapping sub-problems,
# eg sometimes it will be at the same position in the list and have obtained the same left and right weight


# hint
# There is a dynamic programming solution which stores at each point in the list,
# what kinds of differences in the scales can be seen

# solution



def can_balance_dynamic(rocks):
    '''
    The algorithm computes the possible difference in the scales at each step
    '''
    if len(rocks) == 0:
        return True
    # We don't add weights at a point i more than total_remaining_weight (the sum of the remaining rocks)
    # because they wouldn't balance if we added everything left on the other side.
    total_remaining_weight = 0
    for i in xrange(1, len(rocks)):
        total_remaining_weight += rocks[i]
    previous_differences = set([])
    # previous/current_differences stores the possible differences in scales we can see.
    if total_remaining_weight >= rocks[0]:
        previous_differences.add(rocks[0])
    for i in xrange(1, len(rocks) - 1):
        current_differences = set([])
        total_remaining_weight -= rocks[i]
        for difference in previous_differences:

            weight = abs(difference + rocks[i])
            if total_remaining_weight >= weight:
                current_differences.add(weight)

            weight = abs(difference - rocks[i])
            if total_remaining_weight >= weight:
                current_differences.add(weight)
        previous_differences = current_differences
    for difference in previous_differences:
        if difference == abs(rocks[-1]):
            return True
    return False

# the runtime is classified as "pseudo polynomial" because depending on how large the numbers are its possible to take O(2^n) time.

# there are some optimizations that are done
# one is to stop considering weight differences at any point which are larger than the sum of the remaining rocks
# another is to consider only absolute value of the difference in scales
# (it is equivalent if you swap the rocks on each scale and always consider one scale to be the heavy one)

# there are other optimisations which can be tried, one is pre-running a greedy algorithm which sorts the rocks highest to lowest
# and then iteratively places the rock in the unbalanced scale,
# this works some of the time.


# depending on the input this algorithm can still take O(2^n) time
# if there are many different weights creating twice as many possible differences in the scales at each step.
# there is no known polynomial time algorithm which solves this problem


# ######### Tests ############
import random
import unittest


class TestBalancer(unittest.TestCase):
    def test_can_balance_recursive(self):
        self.does_balance_recursive([1, 2, 3, 4, 5, 6], False)
        self.does_balance_recursive([5, 5, 5, 5], True)
        self.does_balance_recursive([5, 5, 5, 5, 5], False)
        self.does_balance_recursive([4, 4], True)
        self.does_balance_recursive([4, 3], False)
        self.does_balance_recursive([4], False)
        self.does_balance_recursive([1], False)
        self.does_balance_recursive([0], True)

    def test_can_balance(self):
        self.does_balance([1, 2, 3, 4, 5, 6], False)
        self.does_balance([5, 5, 5, 5], True)
        self.does_balance([5, 5, 5, 5, 5], False)
        self.does_balance([4, 4], True)
        self.does_balance([4, 3], False)
        self.does_balance([4], False)
        self.does_balance([1], False)
        self.does_balance([0], True)
        self.does_balance([0, 1, 1, 1], False)
        # self.does_balance([1] * 100, True)
        # self.does_balance([1] * 100 + [100], True)

        # self.does_balance([1] * 1000 + [100], True)
        # self.does_balance([9999999] + 1000 * [1], False)
        arr = [random.randint(0, 10) for i in xrange(1500)]
        can_balance_dynamic(arr)

    def does_balance(self, arr, output):
        self.assertEqual(can_balance_dynamic(arr), output)

    def does_balance_recursive(self, arr, output):
        self.assertEqual(can_balance_recursive(arr), output)


if __name__ == '__main__':
    unittest.main()