JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 99
Problem: BrokenSlotMachines

Problem Statement

    

In a casino, a popular game is played on a device called a slot machine. In the game, 3 wheels have symbols around them. The wheels spin, and each randomly stops on a symbol. When the three symbols on which each wheel lands match, the player wins. It costs one coin for each play of the game. The number of coins the player wins when landing on a winning combination is determined by a payout chart shown below.

Although they do not affect the outcome of the game, the player can typically see which symbol is immediately above and below the symbol on which each wheel stopped. The frequency of different symbols appearing on each different wheel, and indeed, on each different machine, may vary. An example of what is visible after playing is shown below:

   B - C - E
-- D - D - D --
   F - A - C

Each column is the three symbols shown on a given wheel. The middle row is the "pay line", that is to say, the symbols that must match to win a prize. Indeed the result of the spin shown above is a winner. The output of the spin could be described as "BCEDDDFAC", where B-D-F are consecutive symbols on the first wheel, C-D-A are consecutive symbols on the second wheel, and E-D-C are consecutive symbols on the third wheel.

Some friends have informed you that at a particular casino, some of the slot machines may be "broken" in a sense that the frequency of symbols on the wheels is such that the player may tend to win more coins than they will lose. You have only a limited amount of time to mess around, as of course you have important meetings to attend, however, you figure it might be worth a look into the situation.

Playing a slot machine without paying much attention to the specific outcome (beyond how many coins you may have won) takes a single unit of time, whereas playing in such a way that you make an effort to note down the symbols that show up takes much longer. You will initially be given startingCoins, maxTime, noteTime, and numMachines.

The payout table looks the same for all of the slot machines:

  A A A : 1,000
  B B B :   200
  C C C :   100
  D D D :    50
  E E E :    20
  F F F :    10
  G G G :     5

Your code may call one of two library methods:

  • PlaySlots.quickPlay(machineNumber, times): returns the total number of coins you won by playing times times on machineNumber.
  • PlaySlots.notePlay(machineNumber, times): returns a String[] where the first element is the number of coins you won (converted to a String), and each additional element is the nine symbols shown on a given play

In either case, you the number of times you play cannot be more than the number of coins you currently hold, as you cannot depend upon unknown winnings to keep playing.

Test case generation is done as follows (all selections are uniformly at random):

  • coins is chosen between 100 and 10000
  • maxTime is chosen between 100 and 10000
  • noteTime is chosen between 2 and 10
  • numMachines is chosen between 3 and 10
  • The wheel size is chosen (separately for each machine) between 10 and 30
  • Each symbol on each wheel is chosen from the distribution "AABBBBCCCCCDDDDDDEEEEEEFFFFFFFGGGGGGGG"

The time limit per test case is 30s, and the memory limit is 1GB. Any calls with invalid parameters, any exceptions thrown by competitor code, and so on, will result in failing that test case (and getting no points towards the final score).

You may play as few or as many times as you like, so long as you don't run out of coins or time. Your raw score for a test case will be the total number of coins you have at the end of all your playing. Your relative score for a given test case will be YOURS / MAX, where MAX is the highest score anyone achieved for a test case. Your total combined score will be 1,000,000 * SUM(REL_SCORE).

You can download the test harness code that is used internally, for reference, to understand test case generation, or for general clarity on how the processing works. [available here]

For reference, we are also providing a skeletal solution in Java, C++, C# and Python. [available here]

 

Definition

    
Class:BrokenSlotMachines
Method:playSlots
Parameters:int, int, int, int
Returns:int
Method signature:int playSlots(int coins, int maxTime, int noteTime, int numMachines)
(be sure your method is public)
 

Available Libraries

    
Class:PlaySlots
Method:quickPlay
Parameters:int, int
Returns:int
Sample Call:val = PlaySlots.quickPlay(machineNumber, times);
Method:notePlay
Parameters:int, int
Returns:String[]
Sample Call:val = PlaySlots.notePlay(machineNumber, times);
    
 

Examples

0)
    
Seed = 1

Coins: 2961
Max Time: 2096
Note Time: 3
Num Machines: 6

Machine 0...
Wheel 0: DFECFDBGFCDDEFBDBBAAGFCD
Wheel 1: CGGFFFADCFAGGCECBBFGGGGC
Wheel 2: DDGGFEBCDCCEFGDBGCGCGDFE
Expected payout rate: 0.9801793981481483

Machine 1...
Wheel 0: ECFFDGDGGDGFCDGCGFB
Wheel 1: GDGEBGGDEFGFFCGFDFB
Wheel 2: DCGACACBCFADGCBCDDC
Expected payout rate: 0.854351946347864

Machine 2...
Wheel 0: EEGGFFFGGFEEEDCBFB
Wheel 1: GGABCCGGBAFCDGBBDE
Wheel 2: DEDBDDCCADEEBFGEGB
Expected payout rate: 1.123113854595336

Machine 3...
Wheel 0: GCBGEGFCGGFBCFC
Wheel 1: GBGGCBCFEGEBBCF
Wheel 2: DGECAGDBDECEAAE
Expected payout rate: 1.2918518518518518

Machine 4...
Wheel 0: CDGBBEBGEGCBCFGCGDBGF
Wheel 1: FGGEDBGDDEDDGCGFDFFFE
Wheel 2: BEAADECFDEFBFDFGABGFG
Expected payout rate: 0.7029478458049886

Machine 5...
Wheel 0: CCDEEFGDGCBEBBEFDFEF
Wheel 1: AACEEECAGGAEBFCBDCGG
Wheel 2: GGGCFBBGDFEDFCDAFEEG
Expected payout rate: 0.8512500000000001

1)
    
Seed = 2

Coins: 5826
Max Time: 1040
Note Time: 4
Num Machines: 3

Machine 0...
Wheel 0: CACEGCCAAC
Wheel 1: FCGCGEGCCG
Wheel 2: CAFBCDEGGB
Expected payout rate: 4.06

Machine 1...
Wheel 0: BGBGFCGDCBECEBECCGCBCGDF
Wheel 1: AGGFGDDEFFEDBFDEDGFEGCDG
Wheel 2: BFEGCFCBABEFFBEGGFFGEDCF
Expected payout rate: 0.6481481481481481

Machine 2...
Wheel 0: CCBGGCCFECDBFFGE
Wheel 1: EBEGCEDAGAEDGGFB
Wheel 2: FGGGFAEFEBCCFEBC
Expected payout rate: 0.947265625

2)
    
Seed = 3

Coins: 1571
Max Time: 176
Note Time: 8
Num Machines: 9

Machine 0...
Wheel 0: EEFFCBFEBCFFGDEDFADFDD
Wheel 1: FFCGADAGCDFDFEFFCFDCGF
Wheel 2: GAEGBBBCGGGEGGGEFGFFGF
Expected payout rate: 0.509954921111946

Machine 1...
Wheel 0: CAGDDAGDEGBCBDGEFG
Wheel 1: CBGEGGEGCBCCFDGCDG
Wheel 2: ECBEGCDGECGCCGGDEC
Expected payout rate: 1.486625514403292

Machine 2...
Wheel 0: AFDFAECGDGGBFBDCEFGDDAC
Wheel 1: GCCEBFDBBCFGEDBDDBGCGDG
Wheel 2: GFCBCEBCCGFFCDFCDDDABBG
Expected payout rate: 1.7177611572285691

Machine 3...
Wheel 0: FCEAFGEBDBAFEFECEFDACFCEDED
Wheel 1: CEDCCCGEFGFBDFDEFFCDGGFGGFA
Wheel 2: DACEFGFFGDDDDFGDCGECEFEDBCC
Expected payout rate: 1.1634405324391608

Machine 4...
Wheel 0: GDFFDGFCGGFDFB
Wheel 1: EGGBBFCDCBGCGF
Wheel 2: FGFACEFCEBFAGG
Expected payout rate: 0.6705539358600584

Machine 5...
Wheel 0: DECDDBCFGGGCD
Wheel 1: EGFFFCEGFGGDF
Wheel 2: GDGGADFEGDFCB
Expected payout rate: 0.5826126536185708

Machine 6...
Wheel 0: CEGAGBEEFEDCAGFEFG
Wheel 1: FEDDGBGFGFBFBGFFED
Wheel 2: FEFCBBCDDFGCCBFFEA
Expected payout rate: 0.5967078189300411

Machine 7...
Wheel 0: BGECEGGADBDEEGCGGGBCGDGGDC
Wheel 1: GDGDDEEFFGDGEFDFEFEGGEDFFC
Wheel 2: GGGGBDEDFCCFDEGFEGEDDCDDFD
Expected payout rate: 0.8261265361857076

Machine 8...
Wheel 0: DDBDGFBGFFGECEEBDFEGGED
Wheel 1: ADBFDDFBDCEGGDEFGGBGGCG
Wheel 2: DFFEEDDFFCGFCEDCEFDBDGF
Expected payout rate: 0.9772335004520424

3)
    
Seed = 4

Coins: 9997
Max Time: 9405
Note Time: 5
Num Machines: 9

Machine 0...
Wheel 0: GGFDCGECEFDDCAFCGFGB
Wheel 1: ABGACDGCFCDFFCBEEDBF
Wheel 2: EGDCDDFBDFDACFGFFGEC
Expected payout rate: 1.345

Machine 1...
Wheel 0: GEBFFCFCFBFF
Wheel 1: DGGDGGEEEECC
Wheel 2: DFBGGCAGCCCB
Expected payout rate: 0.9606481481481483

Machine 2...
Wheel 0: CFABGDFDBEC
Wheel 1: EGGEBFGBBDE
Wheel 2: GFGCGCCGCEE
Expected payout rate: 0.15026296018031554

Machine 3...
Wheel 0: AGDEADBEEFFDGAEGFGDCFFG
Wheel 1: CECFEDAGCFEFBGCCDDFGEBB
Wheel 2: CGGCADBCEFEGCDCFFACGFGD
Expected payout rate: 1.0861346264485903

Machine 4...
Wheel 0: FDFGDCCADGG
Wheel 1: CDECGCGDFFA
Wheel 2: EBEDGGFEEFE
Expected payout rate: 0.33057851239669417

Machine 5...
Wheel 0: GBEEFDEGCFECGGGG
Wheel 1: FDGCEGGFGGGGCDGE
Wheel 2: CBGEEFGBGAGEDFAC
Expected payout rate: 0.5908203125

Machine 6...
Wheel 0: FGAGEFDDAGGCDDBEBFDGBEEF
Wheel 1: EGCEEGGDEBBDBGFFGGADAGFF
Wheel 2: CGFGGDFDEFGEABBCGGEGBEFC
Expected payout rate: 1.0376880787037037

Machine 7...
Wheel 0: DBDEAGDEGDB
Wheel 1: CCAFGEFGGFD
Wheel 2: CDGCGFBCCBG
Expected payout rate: 0.21788129226145755

Machine 8...
Wheel 0: DDEEDGGGEGEEBDFGGEDGCFFCDDF
Wheel 1: DDDEEDGCEDGFDCFEDDFCABGEDCG
Wheel 2: DCGCEGDBBGDDBDGFCFFGFABGEGC
Expected payout rate: 1.1385459533607682

4)
    
Seed = 5

Coins: 5741
Max Time: 2288
Note Time: 10
Num Machines: 7

Machine 0...
Wheel 0: CABBEBAFBFD
Wheel 1: FDCFAFEGEBG
Wheel 2: EBCFCFFBGAB
Expected payout rate: 3.6213373403456046

Machine 1...
Wheel 0: DGAGBGGEGFBEC
Wheel 1: GCBBCGFBDEFFD
Wheel 2: DGDBGGDGEDGGF
Expected payout rate: 0.8966772872098315

Machine 2...
Wheel 0: BECGDDBFGDFGC
Wheel 1: CDFFGDFFEGEAG
Wheel 2: CCGCGGBACCGEB
Expected payout rate: 0.5553026854802002

Machine 3...
Wheel 0: DGEBFCDGFGGDEDD
Wheel 1: FCGGEECEBGGFGAB
Wheel 2: CDDGCGBEEBGGECG
Expected payout rate: 0.6696296296296296

Machine 4...
Wheel 0: EAGFCFCDAGEBEBDBCEGECGBGEFCFG
Wheel 1: FCEDCDEFGDBGDDADBFBEACDFBECGB
Wheel 2: GBECFBDDEEEFGFEEDBEDDAFACFAGE
Expected payout rate: 1.4928861371929967

Machine 5...
Wheel 0: FEBAEBDDGFGCBGEFBDBEBGCCBCFFDF
Wheel 1: GGGEBFFFFGFFGDBEFDFGFCEGCEDGEG
Wheel 2: BGDDFGCGCDFFGGDFDEGCGFGGCFDGDG
Expected payout rate: 0.585925925925926

Machine 6...
Wheel 0: EFBDCEFBDDEDEAGFFFEED
Wheel 1: BCGGFECDAEFGBGDCGBDEF
Wheel 2: BBBADDBEGDFBCAABFGGBD
Expected payout rate: 1.6666666666666667

5)
    
Seed = 6

Coins: 8607
Max Time: 1232
Note Time: 10
Num Machines: 4

Machine 0...
Wheel 0: BCGGBEBDGFDFFFB
Wheel 1: CEGBGGBCGCEGFBE
Wheel 2: FFFACDGDDEFBDCE
Expected payout rate: 0.9940740740740741

Machine 1...
Wheel 0: BFCGEACGEBC
Wheel 1: BFGCEECAEGE
Wheel 2: EBGDEFBFEEC
Expected payout rate: 1.5627347858752818

Machine 2...
Wheel 0: BDDCDCFGDDFBEGCGBFGD
Wheel 1: BGEGCDDCBFCEFBBDDEGC
Wheel 2: CDFGAEGFDFGAECFGGBEF
Expected payout rate: 0.9975

Machine 3...
Wheel 0: FFGEAGAEBD
Wheel 1: EDCGFGFGEA
Wheel 2: DGFEEAGEGB
Expected payout rate: 2.42

6)
    
Seed = 7

Coins: 4351
Max Time: 368
Note Time: 8
Num Machines: 3

Machine 0...
Wheel 0: DDCCGGEFDFDABGBGCGFCAGGECFDCC
Wheel 1: DGACDGEFDCGDABEBGGFEFBGDCGAEB
Wheel 2: FFFDBEGBEGGFGFFFFFBCFCEFGCFFG
Expected payout rate: 0.6502931649514124

Machine 1...
Wheel 0: ABEFEEFGGCCAFEGGEFEFABCDCFGB
Wheel 1: BBEDBGADGEFBEDGAFECDFGCGGFGC
Wheel 2: FAGBGAFEACBGEEGAFCADCFFEFCEE
Expected payout rate: 2.0417274052478134

Machine 2...
Wheel 0: DDGCGFFCABFGCAAFF
Wheel 1: GBEGFDBFEDGCECEBB
Wheel 2: EFBDDGEDGFDCDFBEF
Expected payout rate: 0.7510685935273763

7)
    
Seed = 8

Coins: 2876
Max Time: 9597
Note Time: 3
Num Machines: 3

Machine 0...
Wheel 0: FFCDEEEGGFDFGGCDEDFFFEBGBCBA
Wheel 1: GFGDECCGAACFGFEGEBGDGCDFFECC
Wheel 2: FEFDADGFEGBFFCAEEBCCFEFDFBEG
Expected payout rate: 0.8529974489795917

Machine 1...
Wheel 0: DGCDCCFEGFGFFGGBGGCCDFBGGADG
Wheel 1: EEGGCCGCEEABBDFGEFBGFGGAECBE
Wheel 2: BDDFFECEGFGABDGEEDBAGDADCCDF
Expected payout rate: 0.9456997084548104

Machine 2...
Wheel 0: FFGCFGGDEBC
Wheel 1: FDBBBFFBBFG
Wheel 2: FFBGFDGABDE
Expected payout rate: 1.8707738542449286

8)
    
Seed = 9

Coins: 8521
Max Time: 2480
Note Time: 9
Num Machines: 9

Machine 0...
Wheel 0: AGFEGEGDGFDBABGFCC
Wheel 1: DGGGFDBGEDGEEBGEDG
Wheel 2: DEBEEFCCCEDDFEFGEE
Expected payout rate: 0.5804183813443072

Machine 1...
Wheel 0: ECGADDFDGCGC
Wheel 1: DDECDDFEEGFB
Wheel 2: GCCDGEDCBGEG
Expected payout rate: 1.3194444444444444

Machine 2...
Wheel 0: GDDFACEABDEBGFGGBAGCFDDGEFD
Wheel 1: FDDCGEFEBCEFCEBGCEGAGDFEACD
Wheel 2: EGEDCFECFGDDGEDGEEDFFCGGEDF
Expected payout rate: 0.7234669511761419

Machine 3...
Wheel 0: EAGECEFEFCFDAEDFDCBADA
Wheel 1: FFCGFFDGGGGGEBFEECFGDG
Wheel 2: EADECEFEEDBECCBEGGGEGF
Expected payout rate: 0.5672426746806912

Machine 4...
Wheel 0: ECCGFFGFGCDFGEDBCFE
Wheel 1: GEDEAGADBDBCCGCEFBD
Wheel 2: FECCECCBBFADDFGCGGD
Expected payout rate: 1.3252660737716868

Machine 5...
Wheel 0: GCFDFFFBEAEDAEGDGECCDGC
Wheel 1: BDGFCEFFCFAGDCDBADBEGFA
Wheel 2: BCDDFGDGGBGFDDBEGCGFGEC
Expected payout rate: 0.8827155420399442

Machine 6...
Wheel 0: FEFDDEDGGDADGGAEDDCC
Wheel 1: GDDDGGGACFGFFDFCEGGB
Wheel 2: CFDDEGCDCEBDFGEDFDCC
Expected payout rate: 1.3875

Machine 7...
Wheel 0: GGCFBGCDCEBBGBGDDBDGGCGGGGFFDC
Wheel 1: GEEGEDDDECFEBFBDBGDEEFGBCAGGCC
Wheel 2: DAGFBEGCCFBGCGCBDBEFEDCCGGGGEF
Expected payout rate: 1.3077777777777777

Machine 8...
Wheel 0: EBEAGECDEFBFDGDGC
Wheel 1: CFCBEGGGCFDBDDEBD
Wheel 2: DDFEFGGCGGBEDDDFC
Expected payout rate: 1.2253205780582128

9)
    
Seed = 10

Coins: 1486
Max Time: 1424
Note Time: 8
Num Machines: 6

Machine 0...
Wheel 0: GBEDGGABCFDBGFCGDFEDBBE
Wheel 1: FCDCFCGCDFGDCCGGCCGFGEC
Wheel 2: FEFGCCADBDCCGCADCCEADCF
Expected payout rate: 1.444891920769294

Machine 1...
Wheel 0: CGFGGDCBEGAEGBADGDFBEAED
Wheel 1: GEGEDDGAGGCGCCCGGDGFCGFD
Wheel 2: EFFDEEEFGGEEGFBCGDFEGEGF
Expected payout rate: 0.4282407407407407

Machine 2...
Wheel 0: CDCFDBDGGDGFDG
Wheel 1: CDGEEBFFGGAFCF
Wheel 2: EGEEAFBGEFBFDG
Expected payout rate: 0.38994169096209913

Machine 3...
Wheel 0: DBGEFCCFAGBCDGBGGCGFD
Wheel 1: GGACGCDGGCDDFCDABEFBF
Wheel 2: FBCDEGCCFGFBBGFGCGEEG
Expected payout rate: 1.2871180218118992

Machine 4...
Wheel 0: EGFCDGEDDDABDB
Wheel 1: EADDDFFGGGGFFA
Wheel 2: GBGDFDCAFBGGEB
Expected payout rate: 1.3775510204081631

Machine 5...
Wheel 0: AEBDGBCDGDGFEFAACABGEAGFE
Wheel 1: BDGCDGBFEAGDACEDEGCEBBEGF
Wheel 2: CFGBDGFABDGFGECDFFGDCDFEF
Expected payout rate: 1.37248


This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.