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)
Code language: Python (python)

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
Code language: Python (python)

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)
Code language: Python (python)

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)
Code language: Python (python)

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 ))
Code language: Python (python)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments