Board Game Problem using Python Assignment Solution

June 22, 2024
Dr. Andrew
Python
Dr. Andrew Taylor, a renowned figure in the realm of Computer Science, earned his PhD from McGill University in Montreal, Canada. With 7 years of experience, he has tackled over 500 Python assignments, leveraging his extensive knowledge and skills to deliver outstanding results.
Key Topics
• Optimal Path for high score
Tip of the day
News

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:

Index[0][1][2][3][4][5][6][7][8][9]
Value35182459230510
Weight5101359149727

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() ```

Similar Samples

Explore our diverse array of programming homework samples at ProgrammingHomeworkHelp.com. From introductory exercises to advanced projects in languages like Java, Python, and more, our solutions exemplify clarity, precision, and expertise. These samples demonstrate our commitment to delivering high-quality, tailored assistance for your programming needs. See how we can elevate your academic success today