+1 (315) 557-6473 

C++ Program to Implement 2D Array Assignment Solution.


Instructions

Objective
Write a c++ assignment program to implement 2D array.

Requirements and Specifications

Assignment 2: Block World
  • In this assignment, you’ll implement an agent that can solve Block World problems for an arbitrary initial arrangement of blocks. You will be given an initial arrangement of blocks and a goal arrangement of blocks, and return a list of moves that will transform the initial state into the goal state. You will submit the code for solving the problem into the autograder. You will also submit a report describing your agent.
About the Project
  • In a Block World problem, you are given an original arrangement of blocks and a target arrangement of blocks like this:
  • For us, blocks will be identified as single letters from A to Z.
  • Blocks may be moved one at a time. A block may not be moved if there is another block on top of it. Blocks may be placed either on the table or on top of another block. Your goal is to generate a list of moves that will turn the initial state into the goal state. In the example above, that could be: Move D to the table, move B to A, move C to D, move B to C, and move A to B.
  • There may be more than one sequence of moves that can accomplish the goal. If so, your goal is to generate the smallest number of moves that will turn the initial state into the goal state.
 Your Agent
  • To write your agent, download the starter code below. Complete the solve() method, then upload it to test it against the autograder.
  • The starter code contains two files: BlockWorldAgent.py and main.py. You will write your agent in BlockWorldAgent.py. You may test your agent by running main.py. You will only submit BlockWorldAgent.py; you may modify main.py to test your agent with different inputs.
  • In BlockWorldAgent.py, your solve() method will have two parameters: the initial configuration of blocks, and the goal configuration of blocks. Configurations will be represented by lists of lists of characters, where each character represents a different block (e.g. “A” would be Block A). Within each list, each subsequent block is on top of the previous block in the list; the first block in the list is on the table. For example, this list would represent the configuration shown above: two stacks, one with D on B and B on C, and the other with just A:
  • [["C", "B", "D"], ["A"]]
  • There may be up to 26 blocks in a puzzle. You may assume that the goal configuration contains all the blocks and only the blocks present in the initial configuration.
Source Code
import copy
class BlockWorldAgent:
    def __init__(self):
        #If you want to do any initial processing, add it here.
        self.state = None
        self.goal = None
        self.discovered = []
        self.moves = []
    def evaluateState11(self, state):
        """
        This function returns the Heuristic value of the state
        :param state: current state
        :return: numeric value for the cost of the state
        """
        cost = 0
        for stacki in state:
            for i, block in enumerate(stacki):
                for stackj in self.goal:
                    if block in stackj:
                        idx = stackj.index(block)
                        if i == idx:
                            cost += i
                        else:
                            cost -= i
        return cost
    def evaluateState3(self, state):
        # Evaluate the goal state
        cost = 0
        for stacki in state:
            for i, block in enumerate(stacki):
                for stackj in self.goal:
                    if block in stackj:
                        idx = stackj.index(block)
                        if i == idx:
                            cost += i
                            # Now, check if block is not in table
                            if i > 0: # block is above another block
                                # Check block under
                                block_pre_i = stacki[i-1]
                                block_pre_j = stackj[i-1]
                                if block_pre_i == block_pre_j: # block is above a block that is als in the correct pos
                                    cost += 2*i # we add the double amount
                                else:
                                    cost -= i
                            # Now check block above
                            if len(stacki) > i+2:
                                block_above_i = stacki[i+1]
                                if len(stackj)> i+2:
                                    block_above_j = stackj[i+2]
                                    if block_above_i == block_above_j:
                                        cost += 2*i
                                    else:
                                        cost -= i
                                else:
                                    cost -= i
                        else:
                            cost -= i
        return cost
    def evaluateState(self, state):
        """
        Count + 1 onyl for blocks that are resting where they should be resting
        :param state:
        :return:
        """
        # Evaluate the goal state
        cost = 0
        for stacki in state:
            for i, blocki in enumerate(stacki):
                for stackj in self.goal:
                    for j, blockj in enumerate(stackj):
                        if blocki == blockj:
                            if i == 0:
                                i_resting_on = "table"
                            else:
                                i_resting_on = stacki[i - 1]
                            if j == 0:
                                j_resting_on = "table"
                            else:
                                j_resting_on = stackj[j-1]
                            if i_resting_on == j_resting_on:
                                cost += i
                            else:
                                cost -= i
                            # Now check block above
                            if len(stacki) > i + 2:
                                block_above_i = stacki[i + 1]
                                if len(stackj) > i + 2:
                                    block_above_j = stackj[i + 2]
                                    if block_above_i == block_above_j:
                                        cost += i
                            # Now check if the block is in its correct index
                            if i != j:
                                cost -= i
                            break
        return cost
    def evaluateState2222(self, state):
        """
        Count + 1 onyl for blocks that are resting where they should be resting
        :param state:
        :return:
        """
        # Evaluate the goal state
        cost = 0
        for stacki in state:
            for i, blocki in enumerate(stacki):
                for stackj in self.goal:
                    for j, blockj in enumerate(stackj):
                        if blocki == blockj:
                            if i == 0:
                                i_resting_on = "table"
                            else:
                                i_resting_on = stacki[i - 1]
                            if j == 0:
                                j_resting_on = "table"
                            else:
                                j_resting_on = stackj[j-1]
                            if i_resting_on == j_resting_on:
                                cost += 2*i
                            else:
                                cost -= i
                            # Now check if the block is in its correct index
                            if i != j:
                                cost -= i
                            break
        return cost
    def search2(self, in_state):
        """
        This function will recursively evaluate different states and follow the state with the maximum cost
        :param state:
        :return:
        """
        # Check if state is equal to the goal
        # Remove empty states
        # Delete empty lists
        in_state = [x for x in in_state if x!= []]
        #print("\nIN STATE:", in_state)
        if in_state == self.goal: # current state is equal to the goal, so the solution has been found
            print(f"\tSolution: Found in {len(self.moves)} moves!")
            #print(in_state)
            #print(self.moves)
            return True
        if not [] in in_state: # add an empty list that represents the table
            #in_state.append([])
            in_state.insert(0, [])
        # For this state, evaluate all possible movements and pick the one with the highest value
        bestStateValue = -1E10
        bestState = None
        for i in range(len(in_state)):
            for j in range(len(in_state)):
                if i != j and len(in_state[i]) > 0:
                    # Move last element from stack i to stack j
                    if len(in_state[i]) == 1 and len(in_state[j]) == 0: # trying to move from table to table
                        continue
                    # Move block
                    state = copy.deepcopy(in_state)
                    before = copy.deepcopy(state) # store state before movement
                    block = state[i].pop()
                    state[j].append(block)
                    after = copy.deepcopy(state) # store state after movement
                    """
                        States saved in 'before' and 'after' variables are used only for debugging purposes
                    """
                    # Check that this new state has not been tested before
                    discovered = False
                    state_check = [x for x in state if x != []] # remove empty lists
                    for lst in self.discovered:
                        if lst == state_check:
                            discovered = True
                            break
                    if not discovered:
                        #print(i,j)
                        #print("Before: ", before, " -> ", self.evaluateState(before))
                        #print("Possible State:", after, " -> ", self.evaluateState(after))
                        self.discovered.append(state_check)
                        # Now, get value of state
                        value = self.evaluateState(state_check)
                        if value > bestStateValue:
                            bestStateValue = value
                            bestState = copy.deepcopy(state_check)
                            moveTo = ""
                            if len(state[j]) == 1: # it was empty before the movement
                                moveTo = "Table"
                            else:
                                moveTo = state[j][-2]
                            move = (block, moveTo)
        if bestState:
            #print("Best state selected")
            #print(bestState)
            self.moves.append(move)
            # Now, repeat with this new state
            return self.search(bestState)
        # If not, then a solution was not found
        print("\tSolution: Not found.")
        return False
    def search(self, in_state):
        """
        This function will recursively evaluate different states and follow the state with the maximum cost
        :param state:
        :return:
        """
        # Check if state is equal to the goal
        # Remove empty states
        # Delete empty lists
        #state = [x for x in in_state if x != []]
        state = copy.deepcopy(in_state)
        if [] in state:
            state.remove([])
        #print("\nIN STATE:", in_state)
        state.sort(key = lambda x: x[0])
        if state == self.goal: # current state is equal to the goal, so the solution has been found
            #print(f"\tSolution: Found in {len(self.moves)} moves!")
            #print(in_state)
            #print(self.moves)
            return True
        if not [] in state: # add an empty list that represents the table
            #in_state.append([])
            state.insert(0, [])
        possible_states = list()
        # Get all possible states
        for i in range(len(state)):
            for j in range(len(state)):
                if i != j and len(state[i]) > 0:
                    # Move last element from stack i to stack j
                    if len(state[i]) == 1 and len(state[j]) == 0: # trying to move from table to table
                        continue
                    # Move block
                    new_state = copy.deepcopy(state)
                    block = new_state[i].pop()
                    new_state[j].append(block)
                    # Check that this new state has not been tested before
                    discovered = False
                    state_check = [x for x in new_state if x != []] # remove empty lists
                    state_check.sort(key = lambda x: x[0])
                    for lst in self.discovered:
                        lst_i = copy.deepcopy(lst)
                        #lst_i.sort(key = lambda x: x[0])
                        #state_check.sort(key = lambda x: x[0])
                        if lst_i == state_check:
                            discovered = True
                            break
                    if not discovered:
                        state_check = [x for x in new_state if x != []]
                        new_state_value = self.evaluateState(state_check)
                        self.discovered.append(state_check)
                        moveTo = ""
                        if len(new_state[j]) == 1: # it was empty before the movement
                            moveTo = "Table"
                        else:
                            moveTo = new_state[j][-2]
                        move = (block, moveTo)
                        possible_states.append((new_state_value, state_check, move))
        if len(possible_states) > 0:
            # Now, pick the statr with the highest value
            possible_states.sort(key = lambda x: x[0], reverse=True)
            best_state = possible_states[0]
            move = best_state[2]
            best_state_raw = best_state[1]
            self.moves.append(move)
            # Now, repeat with this new state
            return self.search(best_state_raw)
        else:
            # If not, then a solution was not found
            #print("\tSolution: Not found.")
            return False
    def solve(self, initial_arrangement, goal_arrangement):
        goal_arrangement.sort(key = lambda x: x[0])
        self.state = initial_arrangement
        self.goal = goal_arrangement
        self.goalValue = self.evaluateState(self.goal)
        self.discovered.clear()
        self.discovered.append(initial_arrangement)
        self.moves.clear()
        #print("Solving for the following parameters:")
        #print("\tInitial State:", initial_arrangement)
        #print("\tGoal State:", goal_arrangement)
        ret = self.search(self.state)
        #print()
        if ret:
            return self.moves
        else:
            return []