Write a function that takes a 2-dimensional array of booleans representing a maze. There will be no wall in the upper-left or lower-right corner.
The procedure should print out the maze, indicating the shortest path from the upper-left corner to the lower-right corner. For example, the output might look like this:
..###### #.# # #.# # # #...# # ## ....# ######..
If no such path exists, print the maze without any path.
As suggested in the lecture notes, write a function that can parse an arithmetic expression in postfix notation and return an expression tree.
Extend the infix expression parser from the lecture so that an expression can contain variables, where every variable name is a lowercase letter. For example, here is one possible expression:
((2 + x) * (y – 7))
Also extend the eval() function so that it can evaluate an expression with variables, given a dictionary that maps each variable name to its value.
Extending the previous exercise, write a function simplify() that takes an expression tree and simplifies it by making the following replacements:
E + 0 => E
0 + E => E
E * 0 => 0
0 * E => 0
E * 1 => E
1 * E => E
For example, simplifying the expression '((x * 1) – (y * 0))' will yield the expression 'x'.
Write a function solve(start, goal, f) that can search any state space. solve() should take three arguments: a start state, a goal state, and a function f that computes the neighbors of any state. solve() should find the shortest possible path from the start state to the goal state, and should print out the sequence of states along this path, with one state per line. If no solution is possible, it should print 'no path'.
We have three jugs with capacity 8, 5, and 3 liters. Initially the first jug is full of water, and the others are empty.
We can pour water between the jugs, but they have no markings of any sort, so we can pour between two jars only until one of them becomes full or empty.
What sequence of moves can we make so that the jugs will hold 4, 4, and 0 liters of water, respectively?
Write a program that can find the shortest possible sequence.
Three missionaries and three cannibals are on the west bank of a river. They have a canoe that can hold two people, and they all must cross to the east bank of the river. There may never be more cannibals than missionaries on either side of the river, or the cannibals will eat the missionaries. Further, the canoe must have at least one person on board to cross the river. Write a program to find and print a sequence of crossings that will take the party safely across.