Problem Solving with Python

Contents
Welcome
1 Read a Children’s Book
Problem Solving, in General
Problem Solving, in Detail
Our First Computational Problem
Imagine a Specific Instance
Sketch Using Computational Thinking
Capturing This Thinking
An Environment for Coding
Our Generic IDE
Our First Pseudocode
Comments
Commands and Input Parameters
Scripts versus Execution
Our First Error
The Interactive Interpreter
Code and Transcript Blocks
Interacting with the Interpreter
The Interpreter as a Calculator
Python Help
Revisiting Our First Error
Undefined Names
Talking through Your Confusion
Naming a Computation’s Result
Debugging
Showtime
Printing to the Console Pane
Statements, Objects, Attributes, and Types
Namespaces
Strings and String Literals
Variables
Valid Names in Python
Terminology Illustrated
Aliasing
Reading Two Lines
Carriage Returns
Reading an Entire Story
Creating a Loop
End of File (EOF)
Three Major Tasks
Testing a Condition
Exiting the Loop
Indentation
Loop Until
Any Book
This Problem, in General
Historical References to Computational Thinking
2 Grab the Dialogue
What Is the Current Task?
A New Problem
Splitting the Problem Into Small Pieces
Reuse
Switching between Goals
Finite State Machines
Error Handling in FSMs
Encoding the state information
This or That
Work on a State
Strings as a Sequence of Characters
Membership Test
Coding a Transition
Indexing and Slicing
For-Loops
String Find
Design Patterns for Error Handling
Never Go Too Long without Testing
Concatenation, Overloading, and Shorthands
Off-by-One and Other Potential Errors
Testing
Beware of Hidden Assumptions
Function Composition
Abstraction as Information Hiding
There Is No Character
3 Replace Text with Emoji
Internationalization
Encoding
Standards
Unicode
A New Problem
Decomposition to Reduce the Problem’s Complexity
Strings as Immutable Sequences
Encode an Emoji in Unicode
Multiple Different Replacements
Feeling Overwhelmed?
Functions
Function Definitions
The Actual Function Definition and Its Invocation
Function Execution
Abstraction, Decomposition, and Algorithms
Definition Before Use
Python’s Special Variables
Docstrings
Getting a Feel for Abstraction
Another Kind of Abstraction
Lists Are Sequence Objects
Abstraction Barriers
Methods
Modules
Revisiting ‘_main_’
Pure Functions
4 Query a Web Resource
Packages and Libraries
APIs
A New Problem
Searching Wikipedia
The Client-Server Programming Model
Resources, Transactions, and Protocols
The URL
The Programmable Web
Python Dictionaries
An HTTP Response
The Response Header
JSON and the Response Body
Enumerating Answers for HOLLIS
Beyond Printing
Blocking and Non-blocking Function Calls
5 Play Guess-a-Number
Guessing a Number
The Player’s Guess
Type Conversion
Try and Recover
The Game Loop
Testing Our Proposed Solution
A Networked Architecture
Its Sequence Diagram
When to Use a New Library
Sockets in Action
Specifying the Other Party
Sending and Receiving Messages
Size Matters
Encoding Again!
A Simplified Networking Interface
The Server
A Connection
Picking Up a Call
The Conversation
Programmer Beware
Run It!
6 Do You See My Dog?
Numbers and Knowledge
Do You See My Dog?
No Interpretation, Please
Reading a Hexdump
Hexadecimal Explained
Converting between Number Systems
Does the Computer See My Dog?
Painting a Picture
Bits
One Finger, No Thumb
The Digital Abstraction
Bits, Bytes, and Nibbles
Setting a Pixel’s Color
Saturation
Overflow and Underflow
Finding Edges
7 Many but Not Any Number
Floating-Point Numbers and numerical Computing
Computers Struggle with Arithmetic?
The Range of a FP Number
Precision
Illustrating This Issue for Precision
Getting Started
One Bit at a Time
Searching for the Smallest Difference
FP Errors Accumulate
8 What Is My Problem?
Data Science
Images as Data about the World
Yes, You Must Clean Up
Understanding What Might Go Wrong
Noise and Its Removal
The Power to Create New Realities
A Process for Eliminating Photobombing
This Data Is Wrong, but...
Zero Out the Unnecessary Details
No Visible Difference
Image Steganography
Where Is That Pixel?
And How Did We Get There?
Visualizing a Traversal
Inverting a Pixel’s Color
Naming the Traversal
Specifying the Range You Want
Storing a 2D Array in Memory
End of Act I
9 Find a Phrase
A Complex Problem-to-Be-Solved
Some Basic Facts
Which Algorithm?
Algorithms, Formally
A Well-Studied Specification for String Matching
Is a Specification an Algorithm?
A Brute-Force Algorithm
A BF-String-Matching Program
One Algorithm, Multiple Implementations
Evaluation
Evaluation in Context
Measuring Performance
How Do We Do Better?
Loops Are Where the Action Is
Computational Complexity
Computational Complexity in Action
Problem Unsolved
10 Build an Index
Strings to Numbers
A Simple Hash Function
Updating a Hash with O(1) Work
Allow Collisions
Other Applications of Hashing
Indices for Fast Data Retrieval
Hash Tables
The Speed of Array-Index Operations
With High Probability
Collision Resolution
Specification for Creating a Book Index
Building Top-Down
Updating the Index
Sort and Strip
11 Discover Driving Directions
A New Approach to Programming
Driving Directions, a Formal Specification
Parallels with Finite State Machines
Solutions with Specific Characteristics
Let’s Walk Before We Drive
A Random Walk
Will It Work?
A Short Walk, Please
No Loops
Only Visit New Spots
A Dog Walk
Simulation
To Maps through OO Programming
Classes
Building an Instance
Self and Instance Attributes
Methods
Representation Invariant
Magic Methods
Building on Others
General Maps
Keeping Track
Remembering How We Got There
The Solution
Depth-First Search (DFS)
Breadth-First Search (BFS)
Informed Searches
12 Divide and Conquer
A Specification for Sorting
Sorting in Python
Sorting in Descending Order
Sorting with Your Own Comparison Function
Sorting Playing Cards
Time Complexity of Brute-Force Sorting
Binary Search
Divide and Conquer
From Split to Merge
Iterative Merge Sort
Recursion
Iterative Factorial
Recursive Merge Sort
Beckett’s Challenge
Its Base Case
The Play with a Single Actor
Looking for the Pattern
A Polished, Full Solution
13 Rewrite the Error Message
The Mistakes We Make in Problem Solving
Our Problem-to-Be-Solved
From the GUI to the Shell
Understanding Paths
From Paths to Programs
Redirecting Inputs and Outputs
Which Output?
Pattern Matching
Wildcards in the Shell
Regular Expressions
Finding Simple Words
Matching Metacharacters
Using Res
Finding Filenames
Python RE Extensions
Putting It All Together
Shell Pipes
Scripting What the Shell Did
Concurrency
Making python32 Look Like python3
14 The Dream of Bug Fixing
Finding All Bugs
Decision Problems
Uncomputable Problems
An Analysis That Finds a Bug
Running Our Simple Analysis
A Tool for Running Analyses
Grabbing a Function with a Syntax Error
Analyzing Other Functions
Using s
A Non-trivial Decision Problem
An Indecisive Decision Function
Insight from Indecision
Specifications without Implementations
15 Embrace Runtime Debugging
The Duality of Code and Data
Breakpoints and Runtime State
Inserting a Breakpoint
Inserting a New Statement
Indenting That Statement
Launching a Script from Another
Instrumenting a Script
REPL
16 Catch Them Early
Divide-by-Zero Bugs
A Silly Coding Error
What’s Hidden
Why Compile?
Finding Type Errors
To Squiggle or Not
Dynamic Typing
Why Types Are Interesting
Types versus Values
Dynamic Type Checking
Static Type Checking
Type Hints
No Free Lunch
17 Build Prediction Models
Predicting Home Prices
Your Sister’s Data
Solving This Problem Ourselves
Machine Learning
Labeled Training Data
ML Workflow
Getting a Feel for the Data
Set the Prediction Target
Pick Some Features
Fit the Model to Our Data
Predicting Unseen Data
Model Validation
Making the Fit Just Right
Bias in ML
Classifying Comments as Toxic
More Art Than Science
18 Use Generative AI
Navigating the Jagged Frontier
My Use of GAI
Large Language Models (LLMs)
The Operation of LLMs
Complexity for Simplicity
Training a Neural Network
Two Pieces to Problem Solving with GAI
An Easy Request?
Write the Script Ourselves
Ask ChatGPT
Is This Task within the Frontier?
The Expanding Frontier
How to Problem Solve with an LLM
Writing Good Prompts
Final Thoughts
Acknowledgments
Index