Related Tags

projecteuler
algorithm
python
communitycreator

# How to solve the Project Euler "red, green, or blue" problem

### Problem

A row of five black square tiles is to have a number of its tiles replaced with colored oblong tiles chosen from red (length = 2), green (length = 3), or blue (length = 4).

If red tiles are chosen, there are 7 ways this can be done.

If green tiles are chosen, there are 3 ways.

And if blue tiles are chosen, there are 2 ways.

Assuming that colors cannot be mixed, there are 7 + 3 + 2 = 12 ways to replace the black tiles in a row measuring five units in length.

How many different ways can the black tiles in a row measuring 50 units in length be replaced if colors cannot be mixed and at least one colored tile must be used?

### Solution

This problem can be solved using simple combinatorics.

The row is filling with arbitrary sequences of black and colored tiles (of length $L$). To find the number of different combinations for any sequence of black and colored tiles, you can use the following formula:

$(black+colored)C(black) = \frac{(black + colored)!}{black!colored!}$

Where $black$ is the number of black tiles and $colored$ is the number of colored tiles.

The value of $black$ can be found by using $black = 50 - (colored*L)$, and $colored$ will simply be increments of 1 of the values starting from 1 to the floor of $\frac{50}{L}$. By plugging in the value of $black$, and the respective values for all increments of $colored$ for each of the three colors in the formula above, you can determine the total possible combinations with 50 tiles.

The program below implements this algorithm in Python.

def factorial (num):
if num <= 1: return 1
else: return num*factorial(num - 1)

def nCr (n, r):
return int(factorial (n) / (factorial (r) * factorial (n - r)))

def red_green_blue (tile_capacity, min_tile_length, max_tile_length):
total_ways = 0
for len_colored_tile in range (min_tile_length, max_tile_length + 1):
current_colored_tile_capacity = int(tile_capacity/len_colored_tile)
for num_colored in range (1, 1 + current_colored_tile_capacity):
num_black_tiles = tile_capacity - num_colored*len_colored_tile
num_black_and_colored_tiles = num_black_tiles + int((tile_capacity - num_black_tiles) / len_colored_tile)
total_ways = total_ways + nCr(num_black_and_colored_tiles, num_black_tiles)

def main ():
tile_capacity = 50
min_tile_length = 2
max_tile_length = 4
print (red_green_blue(tile_capacity, min_tile_length, max_tile_length))
main ()

RELATED TAGS

projecteuler
algorithm
python
communitycreator

CONTRIBUTOR 