The begining is an example, and the assignment is written below. Please incorporate notes in the program. Like what is happening and why you did some of the things you did. Output should show the numbers that the function is on and which direction it moved. Continuously until it hits the number on the far right. Language is any version of Python 3.6 and algorithm used should be in Depth First Search!

When using Depth First Search Please Model you code after this coding structure:

The General Idea Write a program to read in and solve path-finding puzzles. Each puzzle consists of a sequence of integers, like this The orange color on the first square indicates your current position. At each step in the puzzle, you may move exactly the number of squares indicated by the integer in the square you are in. You may move either left or right along the row but may not move past either end. For example, the only legal first move is to move three squares to the right because there is no room to move three spaces to the left. The goal of the puzzle is to move the marker to the end of the row. In this configuration, you can solve the puzzle by making the following set of moves Starting position3 6 4 13 4 2 5 30 Step 1: Move right Step 2 3 64 13 4 2 5 3 0 Move left Step 3: Move right Step Move right Step 5: 3 6 4 3 42 5 3 0 3 6 4 13 4 2 5 3 0 3 6 4 3 4 2 5 3 0 Move left 3 6 4 13 4 2 5 3 0 Move right Even though this example is solvable-and indeed has more than one solution-some puzzles of this form may be impossible, such as the following one 3 1 2 3 0 In this example, you can bounce between the two 3's, but you cannot reach any other squares. Assignment: Write a function called solve which takes a list of integers (the problem) representing the elements of the puzzle, and tries to find a path from the first location to the last location. Implement your solution to this problem as one of: A* search; beam search; breadth-first search; depth-first search; or iterative deepening Details No location in the puzzle may be entered more than once. Your solver should take a list, and return a string containing a list of moves, with a move to the left represented by the capital letter L' and a move to the right represented by the capital letter 'R'. The first character is the first move. (For the example worked through above, the return value would be "RLRRLR".) You may assume: The list length is between 1 and 1000 There are no negative numbers in the list. You may not assume: The last location in the list contains a zero. (If you can get there, it's irrelevant what number it contains.) There are no zeros elsewhere in the list. (There might be, and if you go there you are stuck.) There is a legal move from every location in the list. (A short puzzle might contain a 20, for example.) There are no loops(For example, the list might be 3 1 2 3 0 .) You may not change the numbers in the list. * The General Idea Write a program to read in and solve path-finding puzzles. Each puzzle consists of a sequence of integers, like this The orange color on the first square indicates your current position. At each step in the puzzle, you may move exactly the number of squares indicated by the integer in the square you are in. You may move either left or right along the row but may not move past either end. For example, the only legal first move is to move three squares to the right because there is no room to move three spaces to the left. The goal of the puzzle is to move the marker to the end of the row. In this configuration, you can solve the puzzle by making the following set of moves Starting position3 6 4 13 4 2 5 30 Step 1: Move right Step 2 3 64 13 4 2 5 3 0 Move left Step 3: Move right Step Move right Step 5: 3 6 4 3 42 5 3 0 3 6 4 13 4 2 5 3 0 3 6 4 3 4 2 5 3 0 Move left 3 6 4 13 4 2 5 3 0 Move right Even though this example is solvable-and indeed has more than one solution-some puzzles of this form may be impossible, such as the following one 3 1 2 3 0 In this example, you can bounce between the two 3's, but you cannot reach any other squares. Assignment: Write a function called solve which takes a list of integers (the problem) representing the elements of the puzzle, and tries to find a path from the first location to the last location. Implement your solution to this problem as one of: A* search; beam search; breadth-first search; depth-first search; or iterative deepening Details No location in the puzzle may be entered more than once. Your solver should take a list, and return a string containing a list of moves, with a move to the left represented by the capital letter L' and a move to the right represented by the capital letter 'R'. The first character is the first move. (For the example worked through above, the return value would be "RLRRLR".) You may assume: The list length is between 1 and 1000 There are no negative numbers in the list. You may not assume: The last location in the list contains a zero. (If you can get there, it's irrelevant what number it contains.) There are no zeros elsewhere in the list. (There might be, and if you go there you are stuck.) There is a legal move from every location in the list. (A short puzzle might contain a 20, for example.) There are no loops(For example, the list might be 3 1 2 3 0 .) You may not change the numbers in the list. *