Board Game Problem using Python Assignment Solution

Optimal Path for high score

Given a 1 dimensional board. There is an item placed on each cell. Every item has a value and weight (They are both integers). The following is an example of a board of 10 cells, with the values and weights of the item on each cell shown in the table:

Now consider moving chess on this board, subject to the following rules:

• The chess starts at the rightmost cell of the board
• Each time, the chess can move to the cell that is 2 or 3 locations to its left.
• If the chess moves out of the board, then the process is over.
• When chess reaches a cell, the player could choose to take the item on it. (The player also has the option to not take the item.)
• There is a capacity limit on the total weight of items taken in the process.

Question: How can we move the chess and which items we should take in the process so that we could maximize the total values of items taken?

In the example board shown above, assume that the capacity limit is 20, then the maximum value that could be taken is 62. Below are the steps.

Your task is to write a python assignment to solve this problem, given any board configuration and capacity limit number.

Input Format:

Your program should read from an input file named “input.txt”. The input file would have four lines. A first line is a number indicating the number of cells on the board. A second line is a number indicating the capacity limit. The third line shows the values of the items on all the cells, from the first index to the last index. The fourth line shows the weights for the items on all the cells. Sample input file showing the problem instance we show above:

Output Format:

Print a line on the screen to show the maximum value achievable.

also shows the correct process to maximize the total value.

Solution:

class Move: def __init__(self, pos, take): self.pos = pos self.take = take def __repr__(self): return str(self.pos) + " " + str(self.take) def findMaxValue(curPos, curCapacity, curValue, solution, values, weights, cache): if (curPos, curCapacity) in cache: return curValue + cache[(curPos, curCapacity)][0], solution + cache[(curPos, curCapacity)][1] if curCapacity < 0: result = (-1, solution) elif curPos < 0: result = (curValue, solution) else: possibilities = list() possibilities.append(findMaxValue(curPos - 2, curCapacity, curValue, solution + [Move(curPos, False)], values, weights, cache)) possibilities.append(findMaxValue(curPos - 2, curCapacity - weights[curPos], curValue + values[curPos], solution + [Move(curPos, True)], values, weights, cache)) possibilities.append(findMaxValue(curPos - 3, curCapacity, curValue, solution + [Move(curPos, False)], values, weights, cache)) possibilities.append(findMaxValue(curPos - 3, curCapacity - weights[curPos], curValue + values[curPos], solution + [Move(curPos, True)], values, weights, cache)) result = max(possibilities, key= lambda i : i[0]) cache[(curPos, curCapacity)] = (result[0] - curValue, result[1][len(solution):len(result[1])]) return result def toOutput(minValue, values, weights): print("The maximum value that could be taken is ", minValue[0]) bestPath = minValue[1] print("Steps:") for i in range(0, len(bestPath)): print("Now at cell index", bestPath[i].pos, end= " . ") if bestPath[i].take: print("TAKE the item here (Value: " + str(values[bestPath[i].pos]) + ". Weight :", weights[bestPath[i].pos], end=". ") if i >= len(bestPath) - 1: print("MOVE 2 cells to the left.") else: print("MOVE", bestPath[i].pos - bestPath[i+1].pos, "cells to the left.") print("Out of Board. Done.") def main(): f = open("input.txt", "r") num = int(f.readline()) capacity = int(f.readline()) values = list(map(lambda x: int(x), f.readline().strip().split(" "))) weights = list(map(lambda x: int(x), f.readline().strip().split(" "))) max = findMaxValue(num - 1, capacity, 0, list(), values, weights, {}) toOutput(max, values, weights) if __name__ == '__main__': main()