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 ))
