Project Euler Problem 84
モノポリーで、どの升目に止まりやすいかという問題。
まじめに計算できそうな感じだけど、せっかくなのでサンプリングしてみる。
ただひたすら面倒なだけ。
import random # monopoly simulator cells = [ 'GO', 'A', 'CC', 'A', 'T', 'R', 'B', 'CH', 'B', 'B', 'JAIL', 'C', 'U', 'C', 'C', 'R', 'D', 'CC', 'D', 'D', 'FP', 'E', 'CH', 'E', 'E', 'R', 'F', 'F', 'U', 'F', 'G2J', 'G', 'G', 'CC', 'G', 'R', 'CH', 'H', 'T', 'H' ] cccards = ['DC', 'DC', 'DC', 'DC', 'DC', 'DC', 'DC', 'DC', 'DC', 'DC', 'DC', 'DC', 'DC', 'DC', '0', '10'] ccards = ['DC', 'DC', 'DC', 'DC', 'DC', 'DC', '0', '10', '11', '24', '39', '5', 'G2NR', 'G2NR', 'G2NU', 'GB3'] def pe84(): ntrial = 500000 shuffle_cards() visited = sampling( ntrial ) print visited print get_solution( visited ) def get_solution( visited ): first = get_max_index( visited ) visited[first] = 0 second = get_max_index( visited ) visited[second] = 0 third = get_max_index( visited ) return "".join( [encode_squareface( first ), encode_squareface( second ), encode_squareface( third ) ] ) def get_max_index( lis ): idx = 0 max = 0 for i in range( 0, len( lis ) ): if lis[i] >= max: idx = i max = lis[i] return idx def sampling( ntrial ): visited = [ 0 for i in range(0, len(cells))] pos = 0 tried = 0 # should I count first GO as visited ? while tried < ntrial: nextpos = nextcell( pos) #print len( visited ), " ", nextpos visited[nextpos]+= 1 pos = nextpos tried +=1 return visited def nextcell( current_position): global prev_doubles score1 = random.randint( 1, 4 ) score2 = random.randint( 1, 4 ) if score1 == score2: if prev_doubles == 2: prev_doubles = 0 return 10 else: prev_doubles += 1 else: prev_doubles = 0 next_position = advance( score1+score2, current_position ) #print score, next_position if cells[next_position] == 'CC': return ccjump( next_position ) elif cells[next_position] == 'CH': return cjump( next_position ) elif cells[next_position] == 'G2J': return 10 else: return next_position def ccjump( current_position ): card = drawcc() if card == 'DC': return current_position else: return int( card ) def cjump( current_position ): card = drawc() if card == 'DC': return current_position elif card == 'G2NR': return g2nr( current_position ) elif card == 'G2NU': return g2nu( current_position ) elif card == 'GB3': return back( 3, current_position ) else: return int( card ) def g2nr( current_position ): while( True ): current_position = advance( 1, current_position) if cells[current_position] == 'R': return current_position def g2nu( current_position ): while( True ): current_position = advance( 1, current_position ) if cells[current_position] == 'U': return current_position def advance( nsteps, current_position ): while nsteps > 0: current_position+=1 if current_position > len( cells ) - 1: current_position = 0 nsteps-=1 return current_position def back( nsteps, current_position ): while nsteps > 0: current_position -= 1 if current_position < 0: current_position = len( cells ) - 1 nsteps -=1 return current_position def shuffle_cards(): global ccards global cccards random.shuffle( ccards ) random.shuffle( cccards ) def drawc(): global ccards drawed = ccards.pop( 0 ) ccards.append( drawed ) return drawed def drawcc(): global cccards drawed = cccards.pop( 0 ) cccards.append( drawed ) return drawed def encode_squareface( num ): print "n : ", num if num < 10: return '0'+str(num ) else: return str( num ) prev_doubles = 0 pe84()
なんだかとてもまじめに書いた。