CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3
  1. #1
    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 ?

  2. #2
    Join Date
    Jun 2015
    Posts
    208

    Re: Algorithm for simple board game

    Quote Originally Posted by aakashjsr View Post
    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.

  3. #3
    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

Tags for this Thread

Posting Permissions

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





Click Here to Expand Forum to Full Width

Featured