# Algorithm for simple board game

• July 26th, 2015, 03:56 AM
aakashjsr
Algorithm for simple board game
We have N coins of type-1 and M coins of type-2. A game-board has N squares of type-1 and M squares of type-2. In this game we must place one coin into each square. After placing all coins we will get a score based on our coin placement strategy .

If type-1 square contains a type-1 coin then we will get A points, if type-2 square contains a type-2 coin then we will get B points and in all other cases, we will get C points.Our total game score will be sum of scores of all squares.

Inputs Available are ( N,M,A,B,C )

How can we maximize our score ?
• July 27th, 2015, 07:20 AM
tiliavirga
Re: Algorithm for simple board game
Quote:

Originally Posted by aakashjsr
How can we maximize our score ?

We can start by putting all N type-1 coins on the N type-1 squares and all M type-2 coins on the M type-2 squares. The score becomes,

Score = N*A + M*B + 0*C

Can we improve on this? Yes we can swap one type-1 coin with one type-2 coin. The score becomes,

Score = (N-1)*A + (M-1)*B + 2*C

Did it pay off? Well we lost A+B but gained 2*C so if

2*C > A+B

we gained more than we lost. And if we gained something by this one-coin swap we can gain even more by swapping as many coins as possible.

So first we must find out whether swapping pays off at all (otherwise we already have the maximum score). If it pays off indeed we must figure out what is the biggest swap we can make and calculate the score for that.
• July 27th, 2015, 07:26 AM
OReubens
Re: Algorithm for simple board game
this is a simple math problem.

all coins into the 'right' squares gives a total score of N*A+M*B

as many coins as possible into the 'wrong' squares is 2*min(N,M)*C + (N-min(N,M))*A + (M-min(N,M))*B

follow whichever of the above 2 possibilities gives the highest value