Udacity CS212 Design of Computer Programs

Code for Udacity CS212 Design of Computer Programs

Unit 1

• poker.py

• poker_refactored.py
  one to one correspondence between hand of cards and interger paritition

• shuffle.py
  need explaination form probabilistic perspective; discussions12

• seven_card_stud.py
  choose the best hand(5 cards) from more than 5 cards

• jokers_wild.py
itertools.produce to build the whole problem space
  [constant] * [wildcard possiblilities ..] ...

Unit 2

• time_calls.py simple profile tool for function calls;
  zebra_puzzle inside

• solving_cryptarithmetic.py

  • example for using eval
  • profile (python -m cPython solving_cryptarithmetic.py) shows eval consumes a large percentage of time. eval parses formulae in every call, compile that into functions is a better approach

• fast_solver.py

  • optimized version of solving_cryptarithmetic.py
  • use eval to compile frequently computed formulas to functions in python
  • when assembling strings to a legal function to feed eval, I feel missing Scheme. S-expr rocks!

• floor_puzzie.py

• subpalindrome.py

Unit 3

Regex Recognizer and Generator

• regex_simple.py
  a simple regex interpreter, patterns have no structure, no grouping.

• regex_interpreter.py
  a regex interpreter, regex patterns have inner structure.

• regex_compiler.py
  a regex compiler, compile regex patterns(looks like function calls) to python functions.

• regex_generator.py
  a regex generator, generate instances of a regex pattern of some certain length

Useful python decorators

• memoization.py
  • n_ary: decorator that makes a binary function n ary.
  • memo : decorator that caches the return value for each call to f(args). look cache[args] up before actually call the function.
• trace_tool.py
  • trace:trace function call stack inplemented with a decorator, pretty print the result with indentation(trace.level)
  • countcalls: decorator that makes the function count calls to it, store in callcount[f]

Parser

• grammar.py
  a simple top-down deterministic PEG parser generator
• grammar_memo.py
  • almost the same as grammar.py, the only difference is subroutine parse_atom is memoized(with @memo defined in memoization.py)
  • reduce total function calls (parse_atom and parse_atoms) from 180 to 66
• verify.py
  help function for checking user defined grammars
• Json_parser.py
  a Json parser generated by grammar and parser in grammar_memo.py

Inverse function

• inverse_f.py
  • return the inverse function of a monotonically increasing non-negative(both x and y) function
  • has a binary_search function in it

Unit 4

Bridge Problem

• bridge.py
  best first search to solve bridge problem. cost is contained in state, which makes it easier to handle but less efficient.
• bridge_refactored.py
  refactored version, move cost out of state, adjust several data structures, move complex steps to independent functions.

General Search Algorithms

• shortest_path_search.py:
  width first search`
• lowest_cost_search.py:
  best first search
  TODO: use heap to represent frontier instead of list

profile: bridge problem with here = range(10)

lowest_cost_search_heap.py
real 0m27.711s
user 0m26.742s
sys 0m0.116s
lowest_cost_search.py
real 0m0.305s
user 0m0.284s
sys 0m0.008s
lowest_cost_search_unopt.py
real 0m0.321s
user 0m0.289s
sys 0m0.004s

some thhing is wrong with lowest_cost_search_heap.py

Examples

• pour_problem.py:
  example for using shortest_path_search
• subway_planning.py
  • example for using shortest_path_search
  • collections collections.defaultdict