kartikkukreja

#include <iostream>
#include <bitset>
using namespace std;

// used char for illustration, use int in practice
typedef unsigned char uint;
const unsigned int SIZE = sizeof(uint) * 8;

void printBitRepresentation(uint x) {
	cout << bitset<SIZE>(x) << endl; 

kartikkukreja

MAX_DEPTH = 5 # the fixed maximum depth for game tree expansion
MAX_PROBES = 10 # the fixed maximum number of MCS probes for a non-terminal state
import random

def value(game, state, role, depth):
  """
  returns the estimated value of the given state for the given role by
  expanding the search tree until MAX_DEPTH has been reached and then
  using MCS for non-terminal states' value estimation.
  This method can be used to select the best action for the given role by

kartikkukreja

class LinearCombinationHeuristic:
  def __init__(self, game, role, weights, MAX_POSSIBLE_ACTIONS, MAX_POSSIBLE_STATES):
    self.game = game
    self.role = role
    self.weights = weights
    self.MAX_POSSIBLE_ACTIONS = MAX_POSSIBLE_ACTIONS
    self.MAX_POSSIBLE_STATES = MAX_POSSIBLE_STATES
    self.heuristics = [actionMobility, stateMobility, actionFocus, stateFocus, goalValue]
    assert(len(self.heuristics) == len(self.weights))
  

kartikkukreja

class Game:
  def getStartState(self):
    # return the start state
    pass
  
  def getNextState(self, currentState, jointMove):
    # return the state achieved by playing jointMove in currentState
    pass
  
  def getRoles(self):

kartikkukreja

def twoSum(bst, k):
    if bst is None: return None
    bstStart = inorderFromStart(bst)
    bstEnd = inorderFromEnd(bst)
    start, end = bstStart.next(), bstEnd.next()
    while start != end:
        if start.data + end.data == k: return (start.data, end.data)
        elif start.data + end.data > k: end = bstEnd.next()
        else: start = bstStart.next()
    return None

kartikkukreja

def inorderFromEnd(bst):
    stack = [bst]
    while bst.right is not None:
        bst = bst.right
        stack.append(bst)
    while stack:
        top = stack.pop()
        if top.left is not None:
            bst = top.left
            stack.append(bst)

kartikkukreja

def inorderFromStart(bst):
    stack = [bst]
    while bst.left is not None:
        bst = bst.left
        stack.append(bst)
    while stack:
        top = stack.pop()
        if top.right is not None:
            bst = top.right
            stack.append(bst)

kartikkukreja

class BST:
    def __init__(self, data, left, right):
        self.data = data
        self.left = left
        self.right = right

kartikkukreja

def twoSumSortedArray(A, k):
    """
    Given a sorted integer array A, return two elements from it which sum to k
    """
    start, end = 0, len(A) - 1
    while start != end:
        if A[start] + A[end] == k: return (A[start], A[end])
        elif A[start] + A[end] > k: end -= 1
        else: start += 1
    return None

kartikkukreja

def value(problem, state):
  if problem.isTerminalState(state): return problem.getTerminalUtility(state)
  if state is a MAX node: return maxValue(problem, state)
  if state is a MIN node: return minValue(problem, state)
  if state is an EXP node: return expValue(problem, state)
  
def expValue(problem, state):
  v = 0
  for successor in problem.getSuccessors(state):
    v += problem.getProbability(state, successor) * value(problem, successor)