Facebook Problem: Gamblor
====================================================================
Evil Gambling Monster
There are 9 casinos, laid out in the following configuration, with the lines between them representing overnight travel routes:

    1 ---- 2 ---- 3
    |      |      |
    |      |      |
    4 ---- 5 ---- 6
    |      |      |
    |      |      |
    7 ---- 8 ---- 9

On an otherwise uneventful visit to one of these casinos, your dear mother has had the misfortune to be enslaved by an evil gambling monster. I call him Gamblor, and it is time to snatch her away from his neon claws.[1]

Unfortunately, Gamblor demands the payment of a great deal of money in return for releasing his hostage.

Luckily, you are a psychic computer scientist. With your powers, you can predict in advance over the next 30 days how much you would win (or lose) if you played at a particular casino on that day. This schedule of winnings is represented by the following nine 30-element arrays:

    wins1 = [ 53,-84, 50,-73, 54, 60, 74, 22,-63,-78, 75, 72,
            -46, 99,-33, 24,  6,-66, 77,-61,-60,-46,-52, 84,
              91,-21,-52,-72,-39,-41]
    wins2 = [ 77,-86,-25, 27,-59,-71,-13,-85, 50, 24,-63, 26,
              -4,-10, 25, 62,-85,-68, 96, 92,-29,-64,-54, 18,
            -79,-62, 97,-32,-35,-42]
    wins3 = [ 27,-57,-28,-98, 69, 12,-70,-43, 27, 80, 80, 64,
              6,-23,-45,-68,-60,-31,-36,-63,-39, 34,-27,  7,
            -47, -7, 44,-50, 60,-90]
    wins4 = [  7,-12,-48, 79,-11,-78, -8, 19,-21,-81, -1,-40,
              83,-95, 36,-62,-63, 76,  6,  0,-87, 67,-66,-15,
            -26,-14, 78,-81, 36, 38]
    wins5 = [-71,-56,-73,-20,-77, 15,  2, 14,-66, 81, 33, 33,
            -59, 16, 37, 77, 53, 73, 53,-40,-26, 66,-73,  7,
            -48,  1, 93,-70, 19, 30]
    wins6 = [ 68, 47, 73, 94,-72, 96, 10, 30, 11, 44, 11,-56,
            -23, 51, 60,-86, 29, 13, 87,-17, 73,-39,-51,-99,
              68,  1,  1, 62, 30,-79]
    wins7 = [ -8, -1, 68,-34, -7, 96,-37,-96, 26, 73, 47,-62,
            -83,-76, 89, 77,-62, 18, -9,-75,-99,-36,-14,-50,
            -36,-45, 50, 64,-83,-19]
    wins8 = [ 85,  9, 79, 53, 75,-28, 49,-62,-25,-24,-89,-77,
              13,-72,-54,  2,-95,-17,-80, -5,  8,-79, 59, 93,
            -30,-77,-51,-79, 87,-35]
    wins9 = [  1, 72, 74,-20, 26, 49, 52,-25, 86,-72, 50, 97,
            -50,-36,-74, -4, 65,-70, 78, 85, 25,-14,-93,-16,
            -20,-24,  7, 28, -3, -5]

Travel routes between the casinos are represented by the following adjoinment matrix:

    adj = [[1, 1, 0, 1, 0, 0, 0, 0, 0],
          [1, 1, 1, 0, 1, 0, 0, 0, 0],
          [0, 1, 1, 0, 0, 1, 0, 0, 0],
          [1, 0, 0, 1, 1, 0, 1, 0, 0],
          [0, 1, 0, 1, 1, 1, 0, 1, 0],
          [0, 0, 1, 0, 1, 1, 0, 0, 1],
          [0, 0, 0, 1, 0, 0, 1, 1, 0],
          [0, 0, 0, 0, 1, 0, 1, 1, 1],
          [0, 0, 0, 0, 0, 1, 0, 1, 1]]

You begin on the first day at the location of casino 1.

For example, if you were at casino #1 on day 1, you would win $53 if you decided to play. Later, if you were at casino #3 on day 4, you would lose $98 if you decided to play. Since you can only travel the distance of one route every night, you cannot reach all the casinos right away - e.g. you would not be able to play at casino #6 on the first day to win $68.

The casino owners don't like your special abilities, but they have agreed to let you play subject to the following conditions:

    * At the beginning of the 30 days, you may either begin playing at your current casino immediately or decide to wait until the next day.
    * Once you begin playing, you must play each consecutive day until you stop.
    * Once you stop playing, you may not play again.

Each night after playing or not playing, you may either stay at your current location or travel to an immediately adjoining casino. You may travel overnight between casinos regardless of whether or not you have played that day.

You cannot play a fraction of a day; if a particular day is one where you have chosen to play, you will earn the predicted win or loss for that day.

You wish to determine how many N >= 0 days to not play, how many subsequent M >= 0 consecutive days to play (and how many remaining K >= 0 days you also don't play), and the path to travel between casinos during this 30-day time period such that you maximize your total winnings.

====================================================================

Solution:

- Problem solved by dynamic programming

- At any given night, user is at any one of the casinos (lets call them state). i.e. At any given night, user can be in any one state (S0, S1, S2, S3, S4, S5, S6, S7, S8)

- Transistion from state is governed by adjacency table. User can stay in same casino or go to another casino as determined by adjacency table.
   Note: we assume user can start from casino (0,1,3) on day 0

- For any given day, we look for possible transition to a state from a other states

  For example:

    S0 can be reached from S0, S1, S3 (oldStates) on any given day

    We attach Gain for each day for each state:

    Gain (S0,day) =  Max {Gain (S0,days-1), (Gain (S1,days-1),  (Gain (S3,days-1)} 
                        + Winning (S0, day) // as given in table


  We compute gains for 9 states for each day.

- Possible transistion are also goverend by fact, that not all transistion are psosible in intitial days.
  For example: on day 1, S8->S7 is not possible.

- At the end of 30 days, Maximum gain got in above iteration is the result.

 
Note: 
 - very rudimentry parser written to read the winnings of the casino.
   see attach "winnings.txt" for format.
   win = [<win_day1>, <>, ...];     
   
Assumption:
 - user is in casino 1 on day 1. So he can play in casino 1, 2, 4 on day 1  
====================================================================