 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Algorithm for simple board game

1. Junior Member Join Date
Jul 2015
Posts
1

## 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 ?  Reply With Quote

2. Banned  Join Date
Jun 2015
Posts
208

## Re: Algorithm for simple board game 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.
Last edited by tiliavirga; July 27th, 2015 at 07:50 AM.  Reply With Quote

3. Elite Member Power Poster           Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

## 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  Reply With Quote

algorithm, game, optimization #### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
• 