Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

projecteuler
algorithm
python
communitycreator

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

Muhammad Muzammil

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 LL). 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)=(black+colored)!black!colored!(black+colored)C(black) = \frac{(black + colored)!}{black!colored!}

Where blackblack is the number of black tiles and coloredcolored is the number of colored tiles.

The value of blackblack can be found by using black=50(coloredL)black = 50 - (colored*L), and coloredcolored will simply be increments of 1 of the values starting from 1 to the floor of 50L\frac{50}{L}. By plugging in the value of blackblack, and the respective values for all increments of coloredcolored 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)
	return total_ways

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
RELATED COURSES

View all Courses

Keep Exploring