algorithm - Calculating slot machine payout -

a slot machine has 5 reels , displays 3 symbols per reel (no spaces or "empty" symbols).

payout can occur in number of ways. examples...

• a special diamond symbol appears
• 3 lucky 7's appear
• all 5 symbols in payline identical
• all 5 symbols same number, different color
• etc.

there multiple paylines need checked payout.

what efficient way calculate winnings each spin? or, there more efficient way brute force apply each payout scenario each payline?

every payout besides paylines seem trivial. 3 lucky 7s, iterate on visible squares , count 7s. same checking diamond. if let h number of rows , w number of columns, operation o(hw*), practically sized slot machines pretty low.

the paylines, though, more interesting. theoretically number of paylines (m here on out) much, larger *h ** w*; before throwing out illegal paylines jump m = h^w larger *h ** w. more importantly, appear share lot of similarity. example, line 2 , line 6 in example both require matching top left , top middle-left squares. if these 2 don't match, can't win on either line 2 or line 6.

to represent paylines, i'm going use length w arrays of integers in range [1, h], such payline[i] = index in column (1 indexed) of row in solution. example, payline 1 [1, 1, 1, 1, 1], , payline 17 [3, 3, 2, 1, 2].

to end, suffix tree seems applicable data structure can vastly improve running time of checking of paylines against given board state. consider following algorithm construct suffix tree encapsulates paylines.

initialize:      create root node @ column 0 (off-screen, non-column part of solutions)     root node.length = 0     root node.terminal = false     add paylines (in form of length w arrays of integers ranging 1 h) root nodes' "todistribute set"     create towork queue, add root node  iterate: while towork not empty:     let node n = towork.pop()     if n.length < w         create children of n length n.length + 1 , terminal = (n.length + 1 == w).     payline p in n.todistribute         remove p n.todistribute         if(p.length > 1)             add p.subarray(1, end) child of n applicable.     add children of n towork 

running construction algorithm on example lines 1-11 gives tree looks this:

the computation of tree intensive; involves creation of sum = 1 w of h ^ i nodes. size of tree depends on size of board (height , width), not number of paylines, main advantage of approach. advantage it's pre-processing; can have tree built long before player ever sits down pull lever.

once tree built, can give each node field each match criteria (same symbol, same color, etc). then, when evaluating board state, can dfs tree, , @ every new node, ask (for each critera) if matches parent node. if so, mark criteria true , continue. else, mark false , do not search children criteria. example, if you're looking identical tokens on sub array [1, 1, ...] , find column 1's row 1 , column 2's row 1 don't match, payline includes [1, 1, ...] (2, 6, 16, 20) can't won, , don't have dfs part of tree.

it's hard have thorough algorithmic analysis of how more efficient dfs approach individually checking each payline, because such analysis require knowing how left-side overlap (on average) there between paylines. it's no worse, , @ least example deal better. moreover, more paylines add board, greater overlap, , greater time savings checking paylines using method.