Programming for the Puzzled

Index

abs method, 45, 46, 69
Absolute minimum cardinality, 85, 93
Accessor methods, 241
Adjacency constraint, 208
Adjacent Towers of Hanoi puzzle, 126–130
Algorithmic optimization, 9
Algorithmic puzzles, vii
anagram grouping, 181–192
best time to party, 13–21
cap conformity, 1–12
coin row game, 193–201
counting change, 161–167
course scheduling, 169–179
crystal ball drop, 51–58
disorganized handyman, 135–145
eight-queens problem, 37–50
fake coin problem, 57–66
guessing numbers in least tries, 231–249
mind reading trick, 23–36
N-queens problem, 97–107
party guest list, 77–87, 205–217
six degrees of separation, 219–230
square roots, 67–75
Sudoku, 147–160
talent show contestant selection, 89–95
tiling problems, 109–122
Towers of Brahma (Towers of Hanoi), 123–133
Algorithms, 140. See also Divide-and-conquer algorithm; Greedy algorithm; Recursive divide-and-conquer algorithm
Euclidean, 98
one-pass, 9–10
two-pass, 9
all operator, 151
Anagram grouping puzzle, 181–192
Appel, Kenneth, 215
Argument defaults in procedures, 42–50
Arguments, functions as, 5, 173–176

Backtracks, 150, 154, 157
Base-r representations of numbers, 53–54
Binary search, 72–74
Binary search trees (BST), 231–233
comparing data structures, 249
for guessing game, 231–233, 243–249
object-oriented programming, 239–243
operations on, using dictionary representation, 235–239
using dictionaries, 234–235
weight of, 233, 246–247
Bipartite graphs, 208–211
coloring, 213–214
graph representation of, 212–213
Bisection search, 71–72
Breadth-first graph traversal using sets, 224–227
Breadth-first search, 221–223
using sets, 224–227
break statement, 55–56

Cap conformity puzzle, 1–12
Case analysis, 59–65
control flow for, 23–35
Chaining, 190–191
“Chains” (Karinthy), 227
Characters, 4
Checking-conflicts procedure, 43–44, 48, 49
Coin row game, 193–201
Coloring
bipartite graphs, 213–214
k-coloring, 214–215
Combinations
choosing minimum, 83–84
generating all possible, 81–82
generating and testing one at a time, 91–92
recursive generation of, 162–166
removing unfriendly, 82–83
Compression, data, 10–11
Compression utilities, 11
Conflict detection, 43–44, 48, 49
Constructor method, 240–241
continue statement, 48
Continuous domain bisection search, 71–72
Control flow (if statements and for loops), 6
Control flow for case analysis, 23–35
Counting change puzzle, 161–167
Course scheduling puzzle, 169–179
Crystal ball drop puzzle, 51–58
Cyclic Hanoi puzzle, 132–133

Data compression, 10–11
Data structures, 4. See also Binary search trees (BST); Dictionary; Lists
comparing, 249
d-digit list representation, 54–55
Decoding information, 29–31
def keyword, 5
Degrees of separation
six, 219–228
weighted, 229–230
Depth-first search, 209–211
Dictionary, 4, 186–187, 249
binary search trees using, 234–239
creation and lookup, 194–199
graph representation using, 211–214
hash tables and, 190–191
using to group anagrams, 188–190
Dijkstra, Edsger, 177
Dijkstra’s algorithm, 177. See also Greedy algorithm
Dinner party invitation list puzzle, 77–87
recursion applied to, 103–105
Divide-and-conquer algorithm, 60–61, 71
pivoting in, 136–137
recursive, 61–65, 110–118
solving Towers of Hanoi puzzle using, 124–126
Divide-and-conquer merge sort, 110–112
Doubly nested loop, 15, 19
Dynamic programming, 200–201

Earliest finish time rule, 172–176
Earliest start time rule, 171
Eight-queens problem, 37–50
elif statement, 61–62
else statement, 61–62
Empty sets, 157, 223
Encoding combinations, 81–84
Encoding information, 25–29, 33
Enumeration
exhaustive, 79–80
iterative, 49
recursive, 103
Euclidean algorithm, 98
except block, 199
Exceptions, 199–200
Exhaustive enumeration, 79–80
Exhaustive search via iteration, 49

Facebook, 228
Fake coin puzzle, 57–66
Fewest conflicts rule, 171–172, 175
Fibonacci, recursive, 99–100, 197–198
Five-color theorem for planar graphs, 215
Five-queens problem, 39
Floating-point numbers, 18, 70
dictionaries and, 186
for loop, 6, 27
in breadth-first search, 225
break statement and, 55–56
finding anagram groupings one at a time, 182–183
generating all combinations and, 81, 82
greedy algorithm and, 175
in-place recursive search and, 149
nested, 15, 18–19, 97
in recursive algorithm, 102
recursive searches with implications and, 154–155
selecting combinations, 92
Four-color conjecture for planar graphs, 215
Four-queens problem, 40–41, 103
Functions, 4
as arguments, 5, 173–176
recursive, 97
Fundamental theorem of arithmetic, 109–110, 185–186

Global variables, 150
Graph representation, using dictionaries, 211–214
Graphs
bipartite, 208–213
breadth-first graph traversal using sets, 224–227
coloring, 213–215
degrees of separation, 219–221
interval, 176–177
Gray, Frank, 130
Gray codes, 130–131
Greatest common divisor, recursive, 98–99
Greedy algorithm
binary search tree and, 243–245
course scheduling puzzle and, 169–177
defined, 169
dinner party invitation list puzzle and, 78–79, 85
interval graphs and, 176–177
for set-covering problem, 93–94
Grid, 148
Grouping, 181–192
finding groupings one at a time, 182–183
via hashing, 185–186
via sorting, 183–185
using dictionaries, 188–190
Guessing numbers in fewest tries, 231–249
binary search trees, 231–239
greedy algorithm, 243–249
OOP-style binary search trees, 239–243
Guthrie, Francis, 215

Haken, Wolfgang, 215
Hashing, anagram grouping via, 185–186
Hash tables, 190–191, 249
chained, 190–191
Heap sort, 143
Heawood, Percy John, 215

if statement, 6, 48
Incremental computation, 17
Inkala, Arto, 157–158
In-order traversal, 238–239, 243
In-place partitioning, 140–143
In-place pivoting, 141–143
In-place recursive search, 149
In-place sorting, 143
input function, 33
Input lists, 4–5
Insertion sort, 143
Integers
dictionaries and, 186
keys and, 187
Interval graphs, 176–177
Intervals, 2–3
list of, 169
represented in code, 5–6
Iterative enumeration, 49
Iterative search, 67–71

Karinthy, Frigyes, 227
Kashi Vishwanath temple, 124
k-coloring, 214–215
Kempe, Alfred, 215
Keys
in dictionaries, 186–187
hash tables and, 190
Key-value pairs, 186–187
in hash table, 191
Kochen, Manfred, 227

len function, 6, 18, 63, 83
binary search and, 73
memoized function and, 199
in merge sort, 112
traceback and, 196–197
List comprehension, 118–119
List concatenation, 81–83
List creation and modification, 7–8
List of intervals, 2–3, 13–14, 169
Lists, 4, 249
dictionaries and, 187
one-dimensional, 44–48
optimizing memory usage for, 84–85
Python’s built-in sort function for, 143
to represent two-dimensional tables, 90–93
of tuples, 14–15
tuples vs., 5, 6
two-dimensional, 41–44, 151–153
List slicing, 15, 61–62, 105, 107, 112, 188
Lucas, Édouard, 124

Magic trick
with five cards, 23–33
with four cards, 34–35
max function, 15, 83
Maximum cardinality, 80, 85, 93
Maximum independent set (MIS) problem, 85
Memoization, 100, 198–200, 201
creating optimal binary search tree and, 247
Memory usage, optimizing, 84–85
Merge sort, 110–112, 140
execution and analysis, 112–113
Milgram, Stanley, 227–228
Millennium Prize Problems, 85, 176
Mind reading trick puzzle, 23–36
Minimum cardinality solution, 166
Monotonicity property, 73
Mutator methods, 241
Mutilated chessboard tiling puzzle, 121

n-bit binary string, 81–82
Nested for loops, 15, 18–19, 97
Nested loops, selection sorting and, 140
Non-planar graph, 215
Norvig, Peter, 158
not keyword, 182–183
N-queens problem, 97–107

Object-oriented programming (OOP)-style binary search trees, 239–243
One-dimensional list/array, 44–48
One-pass algorithm, 9–10
Optimization problem, coin row game, 193–201

Partition, finding, 207–209
Partitioning
in-place, 140–143
pivot, 138–139, 140–141, 143
Party guest list puzzles, 77–87, 205–217
Pigeonhole principle, 251n1 (Chapter 3)
Pivoting
in divide-and-conquer, 136–137
in-place, 141
Planar graphs, coloring, 214–215
Prime numbers
dictionaries and hashing, 188–190
for hash values, 185
Printing routine to produce map, 119–120
print statement, 7, 27, 33, 151
Programming, dynamic, 200–201
Pseudocode, vii
Puzzles. See Algorithmic puzzles
Python, viii
built-in sort function for lists in, 143
functions for manipulating and processing lists in, 83
list comprehension style in, 118–119
set data structure in, 157
sets in, 223–224

Quicksort, 137–138, 140

Radix representations, 54, 55–57
range keyword, 6, 15, 19, 102
Range queries, 249
Reading input from user, 23–31
Recursion
applications of, 103–105
defined, 97
exhaustive searches through, 101–105
hashing and, 188
Recursive algorithm for N-queens problem, 101–103
Recursive code, 48–49
Recursive decrease-by-one search, 124–130
Recursive depth-first graph traversal, 209–211
Recursive divide-and-conquer algorithm, 110–118
merge sort and, 110–112
quicksort and, 138, 140
solving Adjacent Towers of Hanoi puzzle using, 126–130
solving Towers of Hanoi puzzle using, 124–126
Recursive divide-and-conquer strategy, 61–65
Recursive enumeration, 103
Recursive Fibonacci, 99–100, 197–198
Recursive function, 97
Recursive generation of combinations, 162–166
Recursive greatest common divisor, 98–99
Recursive in-place sorting, 140–143
Recursive search, 101–105, 148–153
coin row game and, 193–200
decrease-by-one, 124–130
divide-and-conquer, 110–118
with implications, 153–157
in-place, 149
memoization in, 198–200
Sudoku solving and, 148–153
Reflected binary code (RBC), 130–131
Remainder method, to generate binary string, 81–82
Repetition, eliminating, 163–165
Representation, sorted, 20
return statement, 28
Rules
earliest finish time, 172–176
earliest start time, 171
fewest conflicts, 171–172, 175
shortest duration, 170, 174, 175–176
Run-length decoding, 11
Run-length encoding, 11
Runtime analysis, 120

Scoping, 8–9
Search. See also Recursive search
binary, 72–74
breadth-first, 221–223
breadth-first, using sets, 224–227
continuous domain bisection, 71–72
with d balls, 53–57
depth-first, 209–211
iterative, 67–71
systematic, 40–41
ternary, 74–75
with two balls, 52–53
Selection sort, 18–19, 29, 113, 140
Set, 4, 157, 223–224
breadth-first graph traversal using, 224–227
as dictionaries, 187
empty, 157, 223
Set-covering problem, 93–94
Set operations, 157, 223–224
Shortest duration rule, 170, 174, 175–176
Shortest path problem, 177
Six degrees of separation, 219–228
history of, 227–228
shortest path problem and, 177
Six Degrees website, 228
Slicing, list, 15, 61–62, 105, 107, 112, 188
“Small-world problem,” 227–228
Sola Pool, Ithiel de, 227
Sorted representation, 20
Sorting
anagram grouping via, 183–185
hashing and, 190
heap, 143
in-order traversal and, 239, 243
in-place, 143
insertion, 143
merge sort, 110–112, 140
quicksort algorithm, 137–138
recursive in-place, 140–143
selection sort, 18–19, 29, 113, 140
Square roots puzzle, 67–75
String, 4
for combinations, 81
dictionaries and, 186
hash of, 185, 188
keys and, 187
Sudoku, 147–157
difficulty of, 157–158
sum function, 61
Systematic search, 40–41

Tables
hash, 190–191, 249
lists representing two-dimensional, 90–93
Talent show contestant selection puzzle, 89–95
Ternary representation, 65
Ternary search, 74–75
Three-queens problem, 40
3-tuples, 157
Tiling puzzles
courtyard, 109–120
mutilated chessboard, 121
Time, algorithms for best, 14–19
Towers of Brahma (Towers of Hanoi) puzzle, 123–133
Adjacent Towers of Hanoi puzzle, 126–130
recursive solution, 124–126
relationship to Gray codes, 130–131
Traceback, 196–198
try block, 199, 200
try-except blocks, 199–200
Tuples, 4, 5–6
dictionaries and, 186
keys and, 187
lists of, 14–15
lists vs., 5, 6
Twitter, 228
Two-dimensional lists/arrays
chessboard as, 41–44
sudoku solver and, 151–153
Two-dimensional tables, lists representing, 90–93
Two-pass algorithm, 9
2-tuples, 14, 18, 19

Unique prime factorization theorem, 109–110, 185–186

Variables
global, 150
initializing, 5–6
Python keywords and, 4

Watts, Duncan, 228
Weight balance, finding counterfeit coin using, 59–66
Weighted degree of separation, 229–230
Weight of binary search tree, 233, 246–247
while loop
binary search and, 74
bisection search and, 72
breadth-first search and, 225
divide and conquer and, 63
greedy algorithm and, 174
in-place partitioning and, 141–142
iterative search and, 68–70
merge sort and, 112
Wrapper for recursive procedure, 102

xrange keyword, 252n3 (Chapter 8)