The Casino Chips Problem Solved With Python

The challenge

You are given three piles of casino chips: white, green and black chips:

• the first pile contains only white chips
• the second pile contains only green chips
• the third pile contains only black chips

Each day you take exactly two chips of different colors and head to the casino. You can chose any color, but you are not allowed to take two chips of the same color in a day.

You will be given an array representing the number of chips of each color and your task is to return the maximum number of days you can pick the chips. Each day you need to take exactly two chips.

solve([1,1,1]) = 1, 
because after you pick on day one, there will be only one chip left

solve([1,2,1] = 2, 
you can pick twice; you pick two chips on day one then on day two

solve([4,1,1]) = 2

N.B Brute force is not the way to go here. Look for a simplifying mathematical approach.

Test cases

@test.describe('Fixed Tests')
def fixed_tests():
    @test.it('Basic Test Cases')
    def basic_tests():        
        test.assert_equals(solve([1,1,1]), 1)
        test.assert_equals(solve([1,2,1]), 2)
        test.assert_equals(solve([4,1,1]), 2)
        test.assert_equals(solve([8,2,8]), 9)
        test.assert_equals(solve([8,1,4]), 5)
        test.assert_equals(solve([7,4,10]), 10) 
        test.assert_equals(solve([12,12,12]), 18) 
        test.assert_equals(solve([1,23,2]), 3)

A brute force solution in Python

def solve(arr):
    # start by creating a new list,
    # that is sorted in reverse (big to small)
    sorted_chips = sorted(arr, reverse=True)
    
    # we will return this after incrementing it
    days = 0
    
    # create a copy to work on
    chips = sorted_chips[:]
    
    # loop until we kill
    while True:
        # move through the chips
        for i in range(len(chips)):
            # if the first and next have chips
            if chips[0]>0 and chips[1]>0:
                # increment days
                days += 1
                # decrement chips
                chips[0] -= 1
                chips[1] -= 1
                # re-sort the chips list
                chips = sorted(chips, reverse=True)
            else:
                # return if we've hit a limit
                return days
    
    # fail-safe return
    return days

While this works, it is quite slow when we have larger test cases, such as the following:

test.assert_equals(solve([5000000,5000000,10000000]), 10000000)

Revised test cases

@test.describe('Fixed Tests')
def fixed_tests():
    @test.it('Basic Test Cases')
    def basic_tests():        
        test.assert_equals(solve([1,1,1]), 1)
        test.assert_equals(solve([1,2,1]), 2)
        test.assert_equals(solve([4,1,1]), 2)
        test.assert_equals(solve([8,2,8]), 9)
        test.assert_equals(solve([8,1,4]), 5)
        test.assert_equals(solve([7,4,10]), 10) 
        test.assert_equals(solve([12,12,12]), 18) 
        test.assert_equals(solve([1,23,2]), 3)
        test.assert_equals(solve([5000000,5000000,10000000]), 10000000)

An optimal solution in Python

def solve(arr):
    # create easiest variables to use below
    a, b, c = arr[0], arr[1], arr[2]
    
    # import `math` package so we can use `floor`
    import math
    
    # return the floor of the minimum values
    return math.floor(min( a+b, b+c, c+a, math.floor(a+b+c)/2 ))