1-3. A Simple Recursive Procedure4 fragments
Fragment 1 of 4
def ask_yes_or_no(question):
answer = input(question + ' ').strip().lower()
if len(answer) > 0:
if answer[0] == 'y':
return True
if answer[0] == 'n':
return False
print('Please answer with yes or no.')
# Now what?Fragment 2 of 4
private static boolean askYesOrNo(String question) {
char answer = ' ';
System.out.print(question + " ");
String line = scanner.nextLine();
if (line.length() > 0) {
answer = line.toLowerCase().charAt(0);
if (answer == 'y') return true;
if (answer == 'n') return false;
}
System.out.println("Please answer with yes or no.");
// Now what?
}Fragment 3 of 4
def ask_yes_or_no(question):
answer = input(question + ' ').strip().lower()
if len(answer) > 0:
if answer[0] == 'y':
return True
if answer[0] == 'n':
return False
print('Please answer with yes or no.')
return ask_yes_or_no(question)Fragment 4 of 4
private static boolean askYesOrNo(String question) {
char answer = ' ';
System.out.print(question + " ");
String line = scanner.nextLine();
if (line.length() > 0) {
answer = line.toLowerCase().charAt(0);
if (answer == 'y') return true;
if (answer == 'n') return false;
}
System.out.println("Please answer with yes or no.");
return askYesOrNo(question);
}1-4. Factorial3 fragments
Fragment 1 of 3
1! == 1
2! == 1 * 2 == 2
3! == 1 * 2 * 3 == 6
4! == 1 * 2 * 3 * 4 == 24Fragment 2 of 3
def factorial(n):
"Computes the factorial of its argument."
if n == 0:
return 1
else:
return factorial(n - 1) * nFragment 3 of 3
public static int factorial(int n) {
if (n == 0) return 1;
else return n * factorial(n - 1);
}1-5. The Principle of Information Hiding3 fragments
Fragment 1 of 3
def minimum1(numbers):
"""Return the smallest number in a list."""
numbers.sort()
return numbers[0]
def minimum2(numbers):
"""Return the smallest number in a list."""
global i
min = numbers[0]
for i in range(1, len(numbers)):
if numbers[i] < min:
min = numbers[i]
return min
def maximum(numbers):
"""Return the largest number in a list."""
max = 0
for i in range(0, len(numbers)):
if numbers[i] > max:
max = numbers[i]
return max
Fragment 2 of 3
def main():
setup()
player = choose_who_goes_first()
game_over = False
while not game_over:
if player == 'human':
move = ask_human_for_move()
(game_over, result) = make_move(player, move)
player = 'computer'
else: # player == 'computer'
move = decide_move()
(game_over, result) = make_move(player, move)
player = 'human'
print("Game over!")
print(result)
def ask_human_for_move():
move = input('Enter your move: ')
if legal_move(move):
return move
else:
print("That's not legal. Try again.")
return ask_human_for_move()Fragment 3 of 3
def main():
global k
setup()
choose_who_goes_first()
while not game_over:
if player == 'human':
ask_human_for_move()
check_if_move_is_legal()
k = k - 1
make_move()
else: # player == 'computer'
decide_move()
k = k + 1
make_move()
print("Game over!")
print(result)1-8-2. Rule 2. Recur Only With a Simpler Case2 fragments
Fragment 1 of 2
def bad_factorial(n):
if n == 0:
return 1
else:
return n * (n - 1) * bad_factorial(n - 2)Fragment 2 of 2
public static int badFactorial(int n) {
if (n == 0) return 1;
else return n * (n - 1) * factorial(n - 2);
}1-8-2-1. An Aside: The Collatz Conjecture1 fragment
Fragment 1 of 1
def collatz(n):
if n == 1:
return 1
elif n % 2 == 0:
return collatz(n // 2) # integer division
else:
return collatz(3 * n + 1)1-8-3-1. Deep Copies4 fragments
Fragment 1 of 4
a = [1, [2, 3], 4]Fragment 2 of 4
b = a
b[0] = 10
b[1][0] = 20
print(a) # prints [10, [20, 3], 4]Fragment 3 of 4
b = a.copy()
b[0] = 10
b[1][0] = 20
print(a) # prints [1, [20, 3], 4]Fragment 4 of 4
import copy
a = [1, [2, 3], 4]
b = copy.deepcopy(a)
b[0] = 10
b[1][0] = 20
print(a) # prints [1, [2, 3], 4]1-9. What the Computer Does1 fragment
Fragment 1 of 1
def factorial(n):
if n == 0:
return 1
else:
return factorial(n - 1) * n1-10. Removing Recursion2 fragments
Fragment 1 of 2
def r_factorial(n):
"""Compute the factorial of its argument."""
if n == 0:
return 1
else:
return r_factorial(n - 1) * nFragment 2 of 2
def factorial(n):
"""Compute the factorial of its argument."""
stack = []
while n != 0:
stack.append(n) # "push"
n = n - 1
fac = 1
while stack != []:
n = stack.pop()
fac = fac * n
return fac1-11. Tail Recursion3 fragments
Fragment 1 of 3
def factorial(n):
"""Compute the factorial of its argument."""
if n == 0:
return 1
else:
return factorial(n - 1) * nFragment 2 of 3
def factorial(n):
return fac(n, 1)
def fac(n, acc):
if n == 0:
return acc
else:
return fac(n - 1, n * acc)Fragment 3 of 3
def factorial(n):
acc = 1
while n != 0:
acc = n * acc
n = n - 1
return acc1-12. Recursive Drawings2 fragments
Fragment 1 of 2
size(400, 400)
background(255)
rectMode(CENTER)
noFill()
def squares(x, y, size):
if size < 12:
return
square(x, y, size)
half = size / 2
squares(x - half, y - half, half)
squares(x + half, y - half, half)
squares(x - half, y + half, half)
squares(x + half, y + half, half)
squares(200, 200, 175)Fragment 2 of 2
public void settings() {
size(400, 400);
}
void squares(int x, int y, int size) {
if (size < 12) return;
square(x, y, size);
int half = size / 2;
squares(x - half, y - half, half);
squares(x + half, y - half, half);
squares(x - half, y + half, half);
squares(x + half, y + half, half);
}
void draw() {
background(255);
rectMode(CENTER);
noFill();
squares(200, 200, 175);
}2-1-1. Array Maximum2 fragments
Fragment 1 of 2
def maximum(numbers):
"""Find the maximum value in list 'numbers'."""
if len(numbers) == 1:
return numbers[0]
mid = len(numbers) // 2 # integer division
leftmax = maximum(numbers[0:mid])
rightmax = maximum(numbers[mid:len(numbers)])
if leftmax > rightmax:
return leftmax
else:
return rightmaxFragment 2 of 2
public static int maximum(int[] numbers) {
return maxHelper(numbers, 0, numbers.length - 1);
}
private static int maxHelper(int[] numbers,
int lo, int hi) {
if (lo == hi) return numbers[lo];
int mid = (lo + hi) / 2;
int leftmax = maxHelper(numbers, lo, mid);
int rightmax = maxHelper(numbers, mid + 1, hi);
if (leftmax > rightmax) return leftmax;
else return rightmax;
}2-1-2. Quicksort4 fragments
Fragment 1 of 4
def quicksort(array, left, right):
if left < right:
p = partition(array, left, right)
quicksort(array, left, p - 1)
quicksort(array, p + 1, right)Fragment 2 of 4
public static void quicksort(int[] array,
int left,
int right) {
if (left < right) {
int p = partition(array, left, right);
quicksort(array, left, p - 1);
quicksort(array, p + 1, right);
}
}Fragment 3 of 4
quicksort(array, 0, len(array) - 1)Fragment 4 of 4
Quicksort.quicksort(array, 0, array.length - 1);2-2-1. Lists in Java5 fragments
Fragment 1 of 5
public class List {
public Object head;
public List tail;
public List(Object head, List tail) {
this.head = head;
this.tail = tail;
}
}Fragment 2 of 5
@Override
public boolean equals(Object obj) {
if (! (obj instanceof List)) return false;
List that = (List) obj;
return eq(this.head, that.head) &&
eq(this.tail, that.tail);
}Fragment 3 of 5
private static boolean eq(Object obj1, Object obj2) {
if (obj1 == null) return obj2 == null;
return obj1.equals(obj2);
}Fragment 4 of 5
public static boolean member(Object obj, List lst) {
if (lst == null) return false;
if (eq(obj, lst.head)) return true;
return member(obj, lst.tail);
}Fragment 5 of 5
public static boolean deepMember(Object obj, List lst) {
if (lst == null) return false;
if (eq(obj, lst.head)) return true;
if (lst.head instanceof List &&
deepMember(obj, (List) lst.head)) return true;
return deepMember(obj, lst.tail);
}2-2-2. Lists in Python3 fragments
Fragment 1 of 3
class List:
def __init__(self, head, tail=None):
"""Construct a List."""
self.head = head
self.tail = tailFragment 2 of 3
def length(lst):
"""Count the top-level elements in a list."""
if lst == None:
return 0
return 1 + length(lst.tail)Fragment 3 of 3
def __str__(self):
"""Return a string representation
of this List."""
return '[' + self.contents() + ']'
def contents(self):
"""Return a string representation of
the contents of this List."""
s = str(self.head)
if self.tail != None:
s += ', ' + self.tail.contents()
return s2-2-3. Accumulators3 fragments
Fragment 1 of 3
def list_copy(lst):
if lst == None:
return None
return List(lst.head, list_copy(lst.tail))Fragment 2 of 3
def reverse(self):
return self.rev(self, None)
def rev(self, lst, acc=None):
if lst == None:
return acc
return lst.rev(lst.tail,
List(lst.head, acc))Fragment 3 of 3
public List reverse() {
return reverse(this, null);
}
private List reverse(List lst, List acc) {
if (lst == null) return acc;
return reverse(lst.tail,
new List(lst.head, acc));
}2-3. Binary Trees4 fragments
Fragment 1 of 4
public class BinaryTree {
public Object value;
BinaryTree left = null;
BinaryTree right = null;
BinaryTree(Object value,
BinaryTree left,
BinaryTree right) {
this.value = value;
this.left = left;
this.right = right;
}
BinaryTree(Object value) {
// shortcut for making a leaf
this(value, null, null);
}
}Fragment 2 of 4
class BinaryTree(object):
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = rightFragment 3 of 4
static BinaryTree makeTree() {
BinaryTree root, a, b, c, d, e, f, g, h, i, j;
g = new BinaryTree("G");
h = new BinaryTree("H");
i = new BinaryTree("I");
j = new BinaryTree("J");
c = new BinaryTree("C");
d = new BinaryTree("D", g, null);
e = new BinaryTree("E", h, i);
f = new BinaryTree("F", null, j);
a = new BinaryTree("A", c, d);
b = new BinaryTree("B", e, f);
return new BinaryTree("Root", a, b);
}Fragment 4 of 4
def make_tree():
g = BinaryTree('G')
h = BinaryTree('H')
i = BinaryTree('I')
j = BinaryTree('J')
c = BinaryTree('C')
d = BinaryTree('D', g, None)
e = BinaryTree('E', h, i)
f = BinaryTree('F', None, j)
a = BinaryTree('A', c, d)
b = BinaryTree('B', e, f)
return BinaryTree('Root', a, b)2-3-1. Printing Binary Trees4 fragments
Fragment 1 of 4
Root(A(C, D(G, null)), B(E(H, I), F(null, J)))Fragment 2 of 4
Root(A(C, D(G, None)), B(E(H, I), F(None, J)))Fragment 3 of 4
@Override
public String toString() {
if (left == null && right == null) {
return value.toString();
}
return value + "(" + left + ", " + right + ")";
}Fragment 4 of 4
def __str__(self):
if (self.left == None and
self.right == None):
return str(self.value)
return (str(self.value) + "(" +
str(self.left) + ", " +
str(self.right) + ")")2-3-2. Counting Nodes3 fragments
Fragment 1 of 3
def count_nodes(bt):
return (1
+ count_nodes(bt.left)
+ count_nodes(bt.right)Fragment 2 of 3
def count_nodes(bt):
if bt == None:
return 0
return (1
+ count_nodes(bt.left)
+ count_nodes(bt.right))Fragment 3 of 3
static int countNodes(BinaryTree bt) {
if (bt == null) return 0;
return (1
+ countNodes(bt.left)
+ countNodes(bt.right));
}2-4. Trees4 fragments
Fragment 1 of 4
public class BinaryTree {
public Object value;
BinaryTree leftChild = null;
BinaryTree rightChild = null;
…
}Fragment 2 of 4
public class Tree {
public Object value;
private ArrayList children;Fragment 3 of 4
public class Tree<V> {
public V value;
private ArrayList<Tree<V>> children;Fragment 4 of 4
class Tree:
def __init__(self, value):
self.value = value
self.children = []2-4-1. Parse Trees2 fragments
Fragment 1 of 2
if a > b:
temp = a
a = b
b = tempFragment 2 of 2
function interpret(node):
if node type is "if":
if (interpret first child):
interpret second child
else:
interpret third child (if present)
else if node type is [something else]
[do something else]2-4-2. Indirect Recursion1 fragment
Fragment 1 of 1
def __str__(self):
s = str(self.value)
if self.children != None:
s += str(self.children)
return s3-1. The Backtracking Algorithm3 fragments
Fragment 1 of 3
function solvable(n):
if n is a leaf node:
if n is a goal node, return true
else return false
else:
for each child c of n:
if solvable(c), return true
return falseFragment 2 of 3
for each child c of n:
if solvable(c), return true
return falseFragment 3 of 3
if n is a leaf node:
if n is a goal node, return true
else return false3-2. Non-Recursive Backtracking2 fragments
Fragment 1 of 2
boolean solve(Node n):
put node n on the stack
while the stack is not empty:
topnode = the node at the top of the stack
if topnode is a leaf:
if it is a goal node, return true
else pop it off the stack
else:
if topnode has untried children:
push the next untried child onto the stack
else pop the node off the stack
return falseFragment 2 of 2
boolean solve(Node n) {
if n is a leaf node {
if the leaf is a goal node {
print n
return true
}
else return false
} else {
for each child c of n {
if solve(c) succeeds {
print n
return true
}
}
return false
}
}3-4. Pruning and Four Coloring3 fragments
Fragment 1 of 3
void createMap() {
map = new int[13][];
map[0] = new int[] { 1, 2, 3, 9, 12 };
map[1] = new int[] { 0, 2, 5 };
map[2] = new int[] { 0, 1, 3, 4, 5 };
map[3] = new int[] { 0, 2, 4, 6, 8, 9 };
map[4] = new int[] { 2, 3, 5, 6, 7, 8 };
map[5] = new int[] { 1, 2, 4, 8, 11 };
map[6] = new int[] { 3, 4, 7, 8 };
map[7] = new int[] { 4, 6, 8 };
map[8] = new int[] { 3, 4, 5, 6, 7, 9, 10, 11 };
map[9] = new int[] { 0, 3, 8, 10, 12 };
map[10] = new int[] { 8, 9, 11, 12 };
map[11] = new int[] { 5, 8, 10, 12};
map[12] = new int[] { 0, 9, 10, 11 };
}Fragment 2 of 3
boolean explore1(int country, Color color) {
if (country >= map.length)
return goodColoring();
mapColors[country] = color;
for (Color c : Color.values()) {
if (explore1(country + 1, c)) {
return true;
}
}
mapColors[country] = Color.NONE;
return false;
}Fragment 3 of 3
boolean explore2(int country, Color color) {
if (country >= map.length)
return true;
if (okToColor(country, color)) {
mapColors[country] = color;
for (Color i : Color.values()) {
if (explore2(country + 1, i))
return true;
}
}
return false;
}3-5. Binary Tree Search I7 fragments
Fragment 1 of 7
public class BinaryTree {
String name;
BinaryTree leftChild = null;
BinaryTree rightChild = null;
boolean isGoalNode = false;
BinaryTree(String name,
BinaryTree left,
BinaryTree right,
boolean isGoalNode) {
this.name = name;
leftChild = left;
rightChild = right;
this.isGoalNode = isGoalNode;
}
}Fragment 2 of 7
class BinaryTree(object):
def __init__(self, name, left_child,
right_child, is_goal_node):
self.name = name
self.left_child = left_child
self.right_child = right_child
self.is_goal_node = is_goal_nodeFragment 3 of 7
static BinaryTree makeTree() {
BinaryTree root, a, b, c, d, e, f;
c = new BinaryTree("C", null, null, false);
d = new BinaryTree("D", null, null, false);
e = new BinaryTree("E", null, null, true);
f = new BinaryTree("F", null, null, false);
a = new BinaryTree("A", c, d, false);
b = new BinaryTree("B", e, f, false);
root = new BinaryTree("Root", a, b, false);
return root;
}Fragment 4 of 7
def make_tree():
c = BinaryTree('C', None, None, False)
d = BinaryTree('D', None, None, False)
e = BinaryTree('E', None, None, True)
f = BinaryTree('F', None, None, False)
a = BinaryTree('A', c, d, False)
b = BinaryTree('B', e, f, False)
root = BinaryTree('Root', a, b, False)
return rootFragment 5 of 7
public static void main(String args[]) {
BinaryTree tree = makeTree();
System.out.println(solvable(tree));
}Fragment 6 of 7
def main():
tree = make_tree()
print(solvable(tree))Fragment 7 of 7
function solvable(binaryTree):
1. if node is null/None, return false
2. if node is a goal node return true
3. if solvable(node.leftChild), return true
4. if solvable(node.rightChild), return true
5. return false
}3-6. Binary Tree Search II4 fragments
Fragment 1 of 4
/**
* Find goal node and report path.
*/
static List solve(BinaryTree node) {
List temp;
if (node == null) {
return null;
}
if (node.isGoalNode) {
return new List(node.name, null);
}
temp = solve(node.leftChild);
if (temp != null) {
return new List(node.name, temp);
}
temp = solve(node.rightChild);
if (temp != null) {
return new List(node.name, temp);
}
return null;
}Fragment 2 of 4
def solve(node):
"""Find goal node and report path."""
if node == None:
return None
if node.is_goal_node:
return [node.name]
temp = solve(node.left_child)
if temp != None:
return [node.name] + temp
temp = solve(node.right_child)
if temp != None:
return [node.name] + temp
return NoneFragment 3 of 4
function toString(list):
if the tail is null, return the head
else return head + toString(the tail)Fragment 4 of 4
@Override
public String toString() {
String s = ("[ ");
s += contents(this);
return s + ("]");
}
private String contents(List list) {
if (list.tail == null) {
return list.head + " ";
} else {
return list.head + " " + contents(list.tail);
}
}3-7. Tree and Graph Searches3 fragments
Fragment 1 of 3
To search from a node:
if the node doesn't exist, return false.
if the node is a goal node, return success.
if searching from the left child succeeds,
return success.
if searching from the right child succeeds,
return success.
return failure.Fragment 2 of 3
To search from a node:
if the node is a goal node,
return success.
for each child of the node:
if searching from that child succeeds,
return success.
return failure.Fragment 3 of 3
To search from a node:
if the node is a goal node,
return success.
if we've been at this node before,
return failure.
for each neighbor of the node:
if searching from that neighbor succeeds,
return success.
return failure.3-8. Debugging Techniques8 fragments
Fragment 1 of 8
static String indent = "";
static String name(BinaryTree node) {
if (node == null) return null;
else return node.name;
}
static void enter(BinaryTree node) {
System.out.println(indent + "Entering solvable(" +
name(node) + ")");
indent = indent + "| ";
}
static boolean yes(BinaryTree node) {
indent = indent.substring(3);
System.out.println(indent + "solvable(" +
name(node) + ") returns true");
return true;
}
static boolean no(BinaryTree node) {
indent = indent.substring(3);
System.out.println(indent + "solvable(" +
name(node) + ") returns false");
return false;
}Fragment 2 of 8
static boolean solvable(BinaryTree node) {
if (node == null) return false;
if (node.isGoalNode) return true;
if (solvable(node.leftChild)) return true;
if (solvable(node.rightChild)) return true;
return false;
}Fragment 3 of 8
static boolean solvable(BinaryTree node) {
enter(node);
if (node == null) return no(node);
if (node.isGoalNode) return yes(node);
if (solvable(node.leftChild)) return yes(node);
if (solvable(node.rightChild)) return yes(node);
return no(node);
}Fragment 4 of 8
Entering solvable(Root)
| Entering solvable(A)
| | Entering solvable(C)
| | | Entering solvable(null)
| | | solvable(null) returns false
| | | Entering solvable(null)
| | | solvable(null) returns false
| | solvable(C) returns false
| | Entering solvable(D)
| | | Entering solvable(null)
| | | solvable(null) returns false
| | | Entering solvable(null)
| | | solvable(null) returns false
| | solvable(D) returns false
| solvable(A) returns false
| Entering solvable(B)
| | Entering solvable(E)
| | solvable(E) returns true
| solvable(B) returns true
solvable(Root) returns trueFragment 5 of 8
static final boolean debugging = false;
static void enter(BinaryTree node) {
if (debugging) {
System.out.println(indent +
"Entering solvable(" +
name(node) +
")");
indent = indent + "| ";
}
}
static boolean yes(BinaryTree node) {
if (debugging) {
indent = indent.substring(3);
System.out.println(indent +
"solvable(" +
name(node) +
") returns true");
}
return true;
}
static boolean no(BinaryTree node) {
if (debugging) {
indent = indent.substring(3);
System.out.println(indent +
"solvable(" +
name(node) +
") returns false");
}
return false;
}Fragment 6 of 8
new Exception("Alpha").printStackTrace(System.out);Fragment 7 of 8
java.lang.Exception: Alpha
at TreeSearch.solvable(TreeSearch.java:53)
at TreeSearch.solvable(TreeSearch.java:57)
at TreeSearch.main(TreeSearch.java:72)
etc.Fragment 8 of 8
import traceback
traceback.print_stack()3-9. The Frog Puzzle3 fragments
Fragment 1 of 3
def solve_and_print(board):
"""Recursively solve the puzzle and print
the reversed sequence of boards."""
if puzzle_solved(board):
return True
for i in range(0, len(board)):
if can_move(board, i):
new_board = make_move(board, i)
if solve_and_print(new_board):
print_board(board)
return True
return FalseFragment 2 of 3
/**
* Recursively solve the puzzle and print
* the reversed sequence of boards.
*/
boolean solveAndPrint(String[] board) {
if (puzzleSolved(board)) {
return true;
}
for (int position = 0;
position < BOARD_SIZE;
position++) {
if (canMove(board, position)) {
String[] newBoard =
makeMove(board, position);
if (solveAndPrint(newBoard)) {
printBoard(newBoard);
return true;
}
}
}
return false;
}Fragment 3 of 3
Toad Toad Toad [ ] Frog Frog Frog
Toad Toad Toad Frog [ ] Frog Frog
Toad Toad [ ] Frog Toad Frog Frog
Toad [ ] Toad Frog Toad Frog Frog
Toad Frog Toad [ ] Toad Frog Frog
Toad Frog Toad Frog Toad [ ] Frog
Toad Frog Toad Frog Toad Frog [ ]
Toad Frog Toad Frog [ ] Frog Toad
Toad Frog [ ] Frog Toad Frog Toad
[ ] Frog Toad Frog Toad Frog Toad
Frog [ ] Toad Frog Toad Frog Toad
Frog Frog Toad [ ] Toad Frog Toad
Frog Frog Toad Frog Toad [ ] Toad
Frog Frog Toad Frog [ ] Toad Toad
Frog Frog [ ] Frog Toad Toad Toad
Frog Frog Frog [ ] Toad Toad Toad3-10. Frogs Accumulator3 fragments
Fragment 1 of 3
List solve(String[] board) {
return new List(board, solve(board, null));
}
private List solve(String[] board, List acc) {
if (puzzleSolved(board)) {
return new List(board, acc);
}
for (int position = 0;
position < BOARD_SIZE;
position++) {
if (canMove(board, position)) {
String[] newBoard =
makeMove(board, position);
List result = solve(newBoard, acc);
if (result != null) {
return new List(newBoard, result);
}
}
}
return null;
}Fragment 2 of 3
def solve(board):
"""Façade method."""
return [board] + solve2(board, [])
def solve2(board, acc):
"""Recursively solve the frog puzzle."""
if puzzle_solved(board):
return [board] + acc
for i in range(0, len(board)):
if can_move(board, i):
new_board = make_move(board, i)
result = solve2(new_board, acc)
if result != []:
return [new_board] + result
return []Fragment 3 of 3
def solve2(board, acc):
"""Recursively solve the frog puzzle."""
for i in range(0, len(board)):
if can_move(board, i):
new_board = make_move(board, i)
if puzzle_solved(new_board):
return [new_board] + acc
result = solve2(new_board, acc)
if result != []:
return [new_board] + result
return []Appendix A. Quicksort in Java1 fragment
Fragment 1 of 1
public static void quicksort(int[] array,
int left,
int right) {
if (left < right) {
int p = partition(array, left, right);
quicksort(array, left, p - 1);
quicksort(array, p + 1, right);
}
}
static int partition(int[] arr, int lo, int hi) {
int pivot = arr[hi];
int i = lo - 1;
for (int j = lo; j < hi; j++) {
if (arr[j] < pivot) {
i += 1;
swap(arr, i, j);
}
}
swap(arr, i + 1, hi);
return i + 1;
}
static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}Appendix B. Quicksort in Python1 fragment
Fragment 1 of 1
def quicksort(array, left, right):
if left < right:
p = partition(array, left, right)
quicksort(array, left, p - 1)
quicksort(array, p + 1, right)
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
return i + 1Appendix C. Binary Tree Search in Java1 fragment
Fragment 1 of 1
public class BinaryTree {
String name;
BinaryTree leftChild = null;
BinaryTree rightChild = null;
boolean isGoalNode = false;
BinaryTree(String name,
BinaryTree left,
BinaryTree right,
boolean isGoalNode) {
this.name = name;
leftChild = left;
rightChild = right;
this.isGoalNode = isGoalNode;
}
}
public class List {
public String head;
public List tail;
public List(String head, List tail) {
this.head = head;
this.tail = tail;
}
@Override
public String toString() {
String s = ("[ ");
s += contents(this);
return s + ("]");
}
private String contents(List list) {
if (list.tail == null) {
return list.head + " ";
} else {
return list.head + " " + contents(list.tail);
}
}
}
public class TreeSearch {
static BinaryTree makeTree() {
BinaryTree root, a, b, c, d, e, f;
c = new BinaryTree("C", null, null, false);
d = new BinaryTree("D", null, null, false);
e = new BinaryTree("E", null, null, true);
f = new BinaryTree("F", null, null, false);
a = new BinaryTree("A", c, d, false);
b = new BinaryTree("B", e, f, false);
root = new BinaryTree("Root", a, b, false);
return root;
}
static boolean solvable(BinaryTree node) {
if (node == null) return false;
if (node.isGoalNode) return true;
if (solvable(node.leftChild)) return true;
if (solvable(node.rightChild)) return true;
return false;
}
static List solve(BinaryTree node) {
List temp;
if (node == null) {
return null;
}
if (node.isGoalNode) {
return new List(node.name, null);
}
temp = solve(node.leftChild);
if (temp != null) {
return new List(node.name, temp);
}
temp = solve(node.rightChild);
if (temp != null) {
return new List(node.name, temp);
}
return null;
}
public static void main(String args[]) {
BinaryTree tree = makeTree();
System.out.println(solvable(tree));
System.out.println(solve(tree));
}
}Appendix D. Binary Tree Search in Python1 fragment
Fragment 1 of 1
class BinaryTree(object):
def __init__(self, name, left_child,
right_child, is_goal_node):
self.name = name
self.left_child = left_child
self.right_child = right_child
self.is_goal_node = is_goal_node
def make_tree():
c = BinaryTree('C', None, None, False)
d = BinaryTree('D', None, None, False)
e = BinaryTree('E', None, None, True)
f = BinaryTree('F', None, None, False)
a = BinaryTree('A', c, d, False)
b = BinaryTree('B', e, f, False)
root = BinaryTree('Root', a, b, False)
return root
def solvable(node):
if node == None: return False
if node.is_goal_node: return True
if solvable(node.left_child): return True
if solvable(node.right_child): return True
return False
def solve(node):
if node == None:
return None
if node.is_goal_node:
return [node.name]
temp = solve(node.left_child)
if temp != None:
return [node.name] + temp
temp = solve(node.right_child)
if temp != None:
return [node.name] + temp
return None
def main():
tree = make_tree()
print(solvable(tree))
print(solve(tree))
main()Appendix E. Java Debugging3 fragments
Fragment 1 of 3
static String indent = "";
static boolean debugging = false;
static void enter(String method, Object ...args) {
if (! debugging) return;
String[] strs = new String[args.length];
for (int i = 0; i < args.length; i++) {
strs[i] = "" + args[i];
}
String s = indent + method + "(";
s += String.join(", ", strs) + ")";
System.out.println(s);
indent = indent + "| ";
}
static boolean yes() {
if (! debugging) return true;
indent = indent.substring(3);
System.out.println(indent + "true");
return true;
}
static boolean no() {
if (! debugging) return false;
indent = indent.substring(3);
System.out.println(indent + "false");
return false;
}Fragment 2 of 3
static Object result(Object obj) {
if (! debugging) return obj;
indent = indent.substring(3);
System.out.println(indent + obj);
return obj;
}Fragment 3 of 3
static BinaryTree result(BinaryTree obj) {
if (! debugging) return obj;
indent = indent.substring(3);
System.out.println(indent + obj);
return obj;
}
static String result(String obj) {
if (! debugging) return obj;
indent = indent.substring(3);
System.out.println(indent + obj);
return obj;
}Appendix F. Python Debugging3 fragments
Fragment 1 of 3
def solve(node):
"""Find goal node and report path."""
if node == None:
return None
if node.is_goal_node:
return [node.name]
temp = solve(node.left_child)
if temp != None:
return [node.name] + temp
temp = solve(node.right_child)
if temp != None:
return [node.name] + temp
return NoneFragment 2 of 3
def solve(node):
"""Find goal node and report path."""
enter(node)
if node == None:
return nothing()
if node.is_goal_node:
return result([node.name])
temp = solve(node.left_child)
if temp != None:
return result([node.name] + temp)
temp = solve(node.right_child)
if temp != None:
return result([node.name] + temp)
return nothing()Fragment 3 of 3
indent = ""
debugging = True
def enter(*args):
if not debugging: return
import inspect
global indent
fargs = [str(x) for x in args]
print(indent + inspect.stack()[1].function + str(fargs))
indent += "| "
def yes():
if not debugging: return True
global indent
indent = indent[3:]
print(indent + "True")
return True
def no():
if not debugging: return False
global indent
indent = indent[3:]
print(indent + "False")
return False
def result(value):
if not debugging: return value
global indent
indent = indent[3:]
print(indent + str(value))
return value
def nothing():
if not debugging: return None
global indent
indent = indent[3:]
print(indent + "None") # can be omitted
return NoneAppendix G. Frog Puzzle in Java1 fragment
Fragment 1 of 1
import java.util.Arrays;
public class FrogPuzzle {
static final int BOARD_SIZE = 7;
static String frog = "Frog";
static String toad = "Toad";
static String empty = "[ ]";
public static void main(String[] args) {
FrogPuzzle bt = new FrogPuzzle();
String[] board = new String[BOARD_SIZE];
setup(board);
bt.solveAndPrint(board);
bt.printBoard(board);
}
/**
* Create initial board.
*/
private static void setup(String[] board) {
int length = board.length;
int half = length / 2;
for (int i = 0; i < half; i++) {
board[i] = frog;
board[length - 1 - i] = toad;
}
board[half] = empty;
}
/**
* Initial solution method: Recursively solve
* the puzzle and print the reversed sequence
* of boards.
*/
boolean solveAndPrint(String[] board) {
if (puzzleSolved(board)) {
return true;
}
for (int position = 0;
position < BOARD_SIZE;
position++) {
if (canMove(board, position)) {
String[] newBoard =
makeMove(board, position);
if (solveAndPrint(newBoard)) {
printBoard(newBoard);
return true;
}
}
}
return false;
}
/**
* Façade method for revised solution.
*/
List solve(String[] board) {
return new List(board, solve(board, null));
}
/**
* Improved solution method: Recursively solve
* the frog puzzle and return the solution.
*/
private List solve(String[] board, List acc) {
for (int position = 0;
position < BOARD_SIZE;
position++) {
if (canMove(board, position)) {
String[] newBoard =
makeMove(board, position);
if (puzzleSolved(newBoard)) {
return new List(newBoard, acc);
}
List result = solve(newBoard, acc);
if (result != null) {
return new List(newBoard, result);
}
}
}
return null;
}
/**
* Print the frog puzzle board.
*/
private void printBoard(String[] board) {
for (String a : board) {
System.out.print(a + " ");
}
System.out.println();
}
/**
* Move the frog or toad at board[index],
* returning a new board, not the original.
*/
private String[] makeMove(String[] board,
int index) {
int next = -1;
if (board[index] == frog) {
if (isEmpty(board, index + 1)) {
next = index + 1;
}
else next = index + 2;
}
else {
if (isEmpty(board, index - 1)) {
next = index - 1;
}
else next = index - 2;
}
String[] nextBoard =
Arrays.copyOf(board, board.length);
nextBoard[next] = board[index];
nextBoard[index] = empty;
return nextBoard;
}
/**
* Is move possible from board[index]?
*/
private boolean canMove(String[] board,
int index) {
if (board[index] == frog) {
return isEmpty(board, index + 1) ||
isEmpty(board, index + 2);
}
if (board[index] == toad) {
return isEmpty(board, index - 1) ||
isEmpty(board, index - 2);
}
return false;
}
/**
* Is board[index] a legal location and empty?
*/
private boolean isEmpty(String[] board,
int index) {
return index >= 0 &&
index < board.length &&
board[index] == empty;
}
/**
* Test if the goal has been reached.
*/
private boolean puzzleSolved(String[] board) {
int half = board.length / 2;
for (int i = 0; i < half; i++) {
if (board[i] != toad) return false;
}
if (board[half] == empty) {
// printBoard(board);
return true;
}
return false;
}
}Appendix H. Frog Puzzle in Python1 fragment
Fragment 1 of 1
frog = 'frog'
toad = 'toad'
empty = ' '
def setup(size):
"""Create initial puzzle state."""
board = [empty] * size
for i in range(0, size // 2):
board[i] = frog
board[-i - 1] = toad
return board
def can_move(board, index):
"""Is move possible from board[index]?"""
if board[index] == frog:
return (is_empty(board, index + 1) or
is_empty(board, index + 2))
if board[index] == toad:
return (is_empty(board, index - 1) or
is_empty(board, index -+ 2))
return False
def is_empty(board, index):
"""Is board[index] a legal location and empty?"""
return (index >= 0 and
index < len(board) and
board[index] == empty)
def make_move(board, index):
"""Move the frog or toad at board[index],
returning a new board, not the original."""
next_board = board[:]
if board[index] == frog:
if board[index + 1] == empty:
next = index + 1
else:
next = index + 2
else: # toad
if board[index - 1] == empty:
next = index - 1
else:
next = index - 2
next_board[next] = board[index]
next_board[index] = empty
return next_board
def solve_and_print(board):
"""Initial solution method: Recursively
solve the puzzle and print the reversed
sequence of boards."""
if puzzle_solved(board):
return True
for i in range(0, len(board)):
if can_move(board, i):
new_board = make_move(board, i)
if solve_and_print(new_board):
print_board(board)
return True
return False
def solve(board):
"""Façade method for revised solution."""
return [board] + solve2(board, [])
def solve2(board, acc):
"""Improved solution method: Recursively
solve the frog puzzle."""
for i in range(0, len(board)):
if can_move(board, i):
new_board = make_move(board, i)
if puzzle_solved(new_board):
return [new_board] + acc
result = solve2(new_board, acc)
if result != []:
return [new_board] + result
return []
def print_board(board):
"""Print the frog puzzle board."""
print('-' * (7 * len(board) + 1))
print('|', ' | '.join(board), '|')
print('-' * (7 * len(board) + 1))
def puzzle_solved(board):
"""Test if the goal has been reached."""
half = len(board) // 2
for i in range(0, half):
if board[i] != toad:
return False
if board[half] == empty:
print_board(board)
return True
return False
def main():
board = setup(7)
print_board(board)
solve_and_print(board)
main()Appendix I. Map Coloring in Java1 fragment
Fragment 1 of 1
public class ColoredMap {
public enum Color {
RED, YELLOW, GREEN, BLUE, NONE
}
Color[] mapColors = new Color[] {
Color.NONE, Color.NONE,
Color.NONE, Color.NONE,
Color.NONE, Color.NONE,
Color.NONE, Color.NONE,
Color.NONE, Color.NONE,
Color.NONE, Color.NONE,
Color.NONE
};
int map[][];
Debugging db = new Debugging();
void createMap() {
map = new int[13][];
map[0] = new int[] { 1, 2, 3, 9, 12 };
map[1] = new int[] { 0, 2, 5 };
map[2] = new int[] { 0, 1, 3, 4, 5 };
map[3] = new int[] { 0, 2, 4, 6, 8, 9 };
map[4] = new int[] { 2, 3, 5, 6, 7, 8 };
map[5] = new int[] { 1, 2, 4, 8, 11 };
map[6] = new int[] { 3, 4, 7, 8 };
map[7] = new int[] { 4, 6, 8 };
map[8] = new int[] { 3, 4, 5, 6, 7, 9, 10, 11 };
map[9] = new int[] { 0, 3, 8, 10, 12 };
map[10] = new int[] { 8, 9, 11, 12 };
map[11] = new int[] { 5, 8, 10, 12};
map[12] = new int[] { 0, 9, 10, 11 };
}
/**
* Tries all possible map colorings
* until getting a four-colored map.
*/
boolean explore1(int country, Color color) {
if (country >= map.length)
return goodColoring();
mapColors[country] = color;
for (Color c : Color.values()) {
if (explore1(country + 1, c)) {
return true;
}
}
mapColors[country] = Color.NONE;
return false;
}
/**
* Uses pruning to find a four-colored map.
*/
boolean explore2(int country, Color color) {
// Backtracking with pruning
if (country >= map.length)
return true;
if (okToColor(country, color)) {
mapColors[country] = color;
for (Color i : Color.values()) {
if (explore2(country + 1, i))
return true;
}
}
return false;
}
/**
* Returns true if no country adjacent to this
* one has already been given this color.
*/
boolean okToColor(int country, Color color) {
if (color == Color.NONE) return false;
for (int i = 0; i < map[country].length; i++) {
int ithAdjCountry = map[country][i];
if (mapColors[ithAdjCountry] == color) {
return false;
}
}
return true;
}
/**
* Return true if the map is properly colored.
*/
boolean goodColoring() {
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
if (mapColors[i] == mapColors[map[i][j]]) {
return false;
}
}
}
return true;
}
void printMap() {
for (int i = 0; i < mapColors.length; i++) {
System.out.println("map[" + i + "] is " +
mapColors[i]);
}
}
public static void main(String args[]) {
ColoredMap m;
long ns;
m = new ColoredMap();
m.createMap();
ns = System.nanoTime();
m.explore1(0, Color.RED);
ns = System.nanoTime() - ns;
m.printMap();
System.out.println(ns + " ns.\n");
m = new ColoredMap();
m.createMap();
ns = System.nanoTime();
m.explore2(0, Color.RED);
ns = System.nanoTime() - ns;
m.printMap();
System.out.println(ns + " ns.\n");
}
}Appendix J. Map Coloring in Python1 fragment
Fragment 1 of 1
import time
colors = ['RED', 'YELLOW', 'GREEN', 'BLUE', 'NONE']
def create_map():
global map, map_colors
map_colors = [None] * 13
map = [None] * 13
map[0] = [ 1, 2, 3, 9, 12 ]
map[1] = [ 0, 2, 5 ]
map[2] = [ 0, 1, 3, 4, 5 ]
map[3] = [ 0, 2, 4, 6, 8, 9 ]
map[4] = [ 2, 3, 5, 6, 7, 8 ]
map[5] = [ 1, 2, 4, 8, 11 ]
map[6] = [ 3, 4, 7, 8 ]
map[7] = [ 4, 6, 8 ]
map[8] = [ 3, 4, 5, 6, 7, 9, 10, 11 ]
map[9] = [ 0, 3, 8, 10, 12 ]
map[10] = [ 8, 9, 11, 12 ]
map[11] = [ 5, 8, 10, 12]
map[12] = [ 0, 9, 10, 11 ]
def explore1(country, color):
"""Tries all possible map colorings
until finding one that works."""
if country >= len(map):
return good_coloring();
map_colors[country] = color
for c in colors:
if explore1(country + 1, c):
return True;
return False
def explore2(country, color):
"""Uses pruning to ignore map
colorings that cannot work."""
if country >= len(map):
return True
if ok_to_color(country, color):
map_colors[country] = color
for c in colors:
if explore2(country + 1, c):
return True
return False
def ok_to_color(country, color):
"""Returns true if this color is not
in use by any adjacent country."""
if color == 'NONE':
return False
for i in range(0, len(map[country])):
ith_adj_country = map[country][i]
if (map_colors[ith_adj_country] == color):
return False
return True
def good_coloring():
"""Returns true if a four-coloring
has been found."""
for i in range(0, len(map)):
for j in range(0, len(map[i])):
if map_colors[i] == map_colors[map[i][j]]:
return False
return True
def main():
global map_colors
m = create_map()
start = time.time()
explore2(0, 'RED')
print(map_colors)
end = time.time()
print("time: ", end - start)
m = create_map()
start = time.time()
explore1(0, 'RED')
print(map_colors)
end = time.time()
print("time: ", end - start)
main()Appendix K. Lists in Python2 fragments
Fragment 1 of 2
class List:
def __init__(self, head, tail=None):
"""Construct a List."""
self.head = head
self.tail = tail
def __str__(self):
"""Return a string representation
of this List."""
return '[' + self.contents() + ']'
def contents(self):
"""Return a string representation of
the contents of this List."""
s = str(self.head)
if self.tail != None:
s += ' ' + self.tail.contents()
return s
def __eq__(self, other):
"""Test if this List equals other."""
if type(other) != List:
return False
if self == []:
return other == [];
if other == []:
return False
return (self.head == other.head and
self.tail == other.tail)Fragment 2 of 2
def to_List(lst):
"""Convert Python list to List."""
if lst == []:
return None
if type(lst[0]) == list:
head = to_List(lst[0])
else:
head = lst[0]
return List(head, to_List(lst[1:]))
def member(x, lst):
"""Test if x is a top-level element
of List lst."""
if lst == None: # out of elements
return False
if lst.head == x:
return True
else:
return member(x, lst.tail)
def deep_member(x, lst):
"""Test if x is a member, at any level,
of List lst."""
if lst == None:
return False
if lst.head == x:
return True
if type(lst.head) == List:
if deep_member(x, lst.head):
return True
return deep_member(x, lst.tail)
def length(lst):
"""Return the number of top-level
elements in List lst."""
if lst == None:
return 0
return 1 + length(lst.tail)Appendix L. Trees in Java1 fragment
Fragment 1 of 1
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;
/**
* General tree class.
*/
public class Tree<V> {
public V value;
private ArrayList<Tree<V>> children;
/**
* Constructs a single Tree node with the given value.
*/
public Tree(V value) {
this.value = value;
children = new ArrayList<Tree<V>>();
}
/**
* Tests whether the given Object is a Tree
* that is equal to this Tree.
*/
@Override
public boolean equals(Object o) {
if (!(o instanceof Tree)) {
return false;
}
Tree<?> that = (Tree) o;
if (! eq(this.value, that.value)) {
return false;
}
return this.children.equals(that.children);
}
/**
* Tests whether two possibly null values are equal.
*/
private static boolean eq(Object o1, Object o2) {
if (o1 == null) {
return o2 == null;
}
return o1.equals(o2);
}
/**
* Returns a list of the children of this node.
* If the node has no children, an empty list
* is returned.
*/
public List<Tree<V>> children() {
return children;
}
/**
* Returns the i-th child of this node.
*/
public Tree<V> getChild(int i) {
return children.get(i);
}
/**
* Adds a node as the new last child of this tree.
*/
public Tree<V> addChild(Tree<V> newChild)
throws IllegalArgumentException {
if (newChild.contains(this)) {
String message = this + " is already in " + newChild;
throw new IllegalArgumentException(message);
}
children.add(newChild);
return this;
}
/**
* Creates a new node with the given value and
* adds it as the last child of this Tree node.
*/
public Tree<V> addChild(V val) {
children.add(new Tree<V>(val));
return this;
}
/**
* Returns a string representing this tree.
* The string does not contain newlines.
* The general form of the output is:
* value(child child ... child)<.
*/
@Override
public String toString() {
if (children.size() == 0) {
return value.toString();
}
String result = value + "(";
boolean first = true;
for (Tree<V> child : children) {
if (!first)
result += " ";
first = false;
result += child.toString();
}
return result + ")";
}
/**
* Prints this tree as an indented structure.
*/
public void print() {
print(this, "");
}
/**
* Prints the tree as an indented structure,
* with the root indented by the given amount.
*/
private void print(Tree<V> node, String indent) {
if (node == null) {
return;
}
System.out.println(indent + node.value);
for (Iterator<Tree<V>> iter = node.children.iterator();
iter.hasNext();) {
print(iter.next(), indent + " ");
}
}
/**
* Returns a string that, if printed, will show
* the given node as an indented tree structure.
*/
public String toMultilineString() {
return toMultilineString(this, "");
}
/**
* Returns a string that, if printed, will show the
* given node as an indented tree structure, with
* the initial line prefixed by the indent string.
*/
private String toMultilineString(Tree<V> node, String indent) {
if (node == null) {
return "";
}
String result = indent + node.value + "\n";
if ("block".equals(node.value .toString())) {
indent += "|";
}
for (Iterator<Tree<V>> iter = node.children.iterator();
iter.hasNext();) {
Tree<V> next = iter.next();
result += toMultilineString(next, indent + " ");
}
return result;
}
/**
* Parses a string of the general form
* value(child, child, ..., child) and returns the
* corresponding tree. Children may be separated
* by commas and/or spaces.
* Node values are all Strings.
*/
public static Tree<String> parse(String s)
throws IllegalArgumentException {
StringTokenizer tokenizer =
new StringTokenizer(s, " (),", true);
List<String> tokens = new LinkedList<String>();
while (tokenizer.hasMoreTokens()) {
String token = tokenizer.nextToken();
if (token.trim().length() == 0) continue;
if (token.equals(",")) continue;
tokens.add(token);
}
Tree<String> result = parse(tokens);
if (tokens.size() > 0) {
throw new IllegalArgumentException("Leftover tokens: " + tokens);
}
return result;
}
/**
* Parses and returns one tree, consisting of
* a value and possible children (enclosed in
* parentheses), starting at the first element
* of tokens. Returns null if this token is a
* close parenthesis, or if there are no
* more tokens.
*/
private static Tree<String> parse(List<String> tokens)
throws IllegalArgumentException {
// No tokens -- return null
if (tokens.size() == 0) {
return null;
}
// Get the next token and remove it from the list
String token = tokens.remove(0);
// If the token is an open parenthesis
if (token.equals("(")) {
throw new IllegalArgumentException(
"Unexpected open parenthesis before " + tokens);
}
// If the token is a close parenthesis, we are
// at the end of a list of children
if (token.equals(")")) {
return null;
}
// Make a tree with this token as its value
Tree<String> tree = new Tree<String>(token);
// Check for children
if (tokens.size() > 0 && tokens.get(0).equals("(")) {
tokens.remove(0);
Tree<String> child;
while ((child = parse(tokens)) != null) {
tree.addChild(child);
}
}
return tree;
}
/**
* Tests whether this tree contains the node
* passed in as a parameter.
*/
public boolean contains(Tree<V> node) {
if (this == node)
return true;
for (Tree<V> child : children) {
if (child.contains(node))
return true;
}
return false;
}
}