MostBeers2.py

MostBeers2.py

# coding: utf-8
'''
Using Depth-First Search to calculate max number of beers money can buy
In this version, one is allowed to borrow a beer at a time
'''

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):
        for b in range(rules['borrow limit'] + 1):
          for r in range(2):
            actions.append((m,e,c,b,r))
        
  return actions


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

# state: (money, empty bottles, bottle caps, total beers, borrowed beers)
dfs_beers({'empty bottles': 2, 'bottle caps': 4, 'money': 2, 'borrow limit': 1}, (10, 0, 0, 0, 0))
#print next_actions({'empty bottles': 2, 'bottle caps': 4, 'money': 2, 'borrow limit': 5}, (10, 0, 0, 0, 0))