Mostbeers.py

Mostbeers.py

# coding: utf-8
'''
Using Depth-First Search to calculate max number of beers money can buy
'''

from collections import deque


def next_actions(rules, state):
  actions = []
  for m in range(state[0]/rules['money']+1):
    for e in range(state[1]/rules['empty bottles']+1):
      for c in range(state[2]/rules['bottle caps']+1):
        actions.append((m,e,c))
        
  return actions


def dfs_beers(rules, initial_state):
  root_node = (initial_state, [])
  frontier = deque([root_node])
  explored = set([])
  
  best_node = root_node
   
  while (frontier):
    node = frontier.pop()
    current_state = node[0]
    explored.add(current_state)
    
    possible_actions = next_actions(rules, current_state)
    
    if possible_actions == [(0,0,0)]:
      print node
      if current_state[3] > best_node[0][3]:
        best_node = node
 
    for a in possible_actions:
      new_beers = sum(a)
      if new_beers != 0:
        current_beers = current_state[3] + new_beers
        child_state = (current_state[0]-a[0]*rules['money'], current_state[1]-a[1]*rules['empty bottles'] + new_beers, current_state[2]-a[2]*rules['bottle caps'] + new_beers, current_beers)
        if child_state not in explored: 
          frontier.append((child_state, node[1] + [(current_state, a)]))
  
  print 'search complete'
  print 'best solution:', best_node
  return 

# state: (money, empty bottles, bottle caps)
dfs_beers({'empty bottles': 2, 'bottle caps': 4, 'money': 2}, (10, 0, 0, 0))
#print next_actions({'empty bottles': 2, 'bottle caps': 4, 'money': 2}, (0, 2, 8, 8))