--- /dev/null
+<!DOCTYPE html>
+<html>
+ <head>
+ <title>Programming strategy</title>
+ <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
+ <style type="text/css">
+ /* Slideshow styles */
+ body {
+ font-size: 20px;
+ }
+ h1, h2, h3 {
+ font-weight: 400;
+ margin-bottom: 0;
+ }
+ h1 { font-size: 3em; }
+ h2 { font-size: 2em; }
+ h3 { font-size: 1.6em; }
+ a, a > code {
+ text-decoration: none;
+ }
+ code {
+ -moz-border-radius: 5px;
+ -web-border-radius: 5px;
+ background: #e7e8e2;
+ border-radius: 5px;
+ font-size: 16px;
+ }
+ .plaintext {
+ background: #272822;
+ color: #80ff80;
+ text-shadow: 0 0 20px #333;
+ padding: 2px 5px;
+ }
+ .ciphertext {
+ background: #272822;
+ color: #ff6666;
+ text-shadow: 0 0 20px #333;
+ padding: 2px 5px;
+ }
+ .indexlink {
+ position: absolute;
+ bottom: 1em;
+ left: 1em;
+ }
+ .float-right {
+ float: right;
+ }
+ </style>
+ </head>
+ <body>
+ <textarea id="source">
+
+# Programming strategy
+
+## Moving up a level
+
+Data structures
+
+Algorithms
+
+Seeing alternatives
+
+---
+
+layout: true
+
+.indexlink[[Index](index.html)]
+
+---
+
+# Data structures before algorithms
+
+* What data do you need?
+* What operations must you perform on it?
+
+These go a long way to defining the algorithms you must use.
+
+## Python built-in types
+
+* Numbers (float and integer)
+* Strings
+* Tuples
+* Lists
+* Dictionaries (a.k.a. hashes or maps)
+
+Many tasks will fit into these
+
+More in the `collections` standard library, such as `namedtuple` and `Counter`
+
+---
+
+# String
+
+* Immutable in Python
+* Single or double quotes (beware apostrophies)
+* Triple-quoted contain newlines
+
+```python
+'This is a string'
+```
+```python
+"This isn't a problem"
+```
+```python
+"""This is
+a multiline
+string"""
+```
+
+---
+# Tuple
+
+* Immutable in Python
+* Fixed-size collection
+* Indexed by position
+
+```python
+neil = ('Neil', 'Smith', 44)
+first_name = neil[0]
+surname = neil[1]
+```
+
+* Unpacking with assignment
+
+```python
+first_name, surname, age = neil
+```
+
+```python
+for _, surname, age in people:
+ ....
+```
+
+---
+
+# List
+
+* Ordered collection
+* Mutable
+* Index by position and slices
+
+```python
+members = ['Freddie', 'Brian', 'Roger', 'John']
+print(members[1])
+print(members[1:2])
+print(members[1:3])
+print(members[1:1])
+print(members[-1])
+print(members[2:])
+print(members[:2])
+```
+
+---
+# Lists: beware copy depth!
+
+```python
+members = ['Freddie', 'Brian', 'Roger', 'John']
+tour_lineup = members
+tour_lineup[0] = 'Paul'
+print(tour_lineup)
+print(members)
+```
+
+---
+
+# Copying a list
+
+```python
+tour_lineup = members[:]
+```
+
+```python
+tour_lineup = list(members)
+```
+
+```python
+import copy
+tour_lineup = copy.copy(members)
+tour_lineup = copy.deepcopy(members)
+```
+
+`==` tests value equality; `is` tests object identity
+
+```python
+members = ['Freddie', 'Brian', 'Roger', 'John']
+tour_lineup = members[:]
+tour_lineup == members
+tour_lineup is members
+```
+
+## Value vs Reference
+
+Must be part of your mental model
+
+---
+
+# Dicts
+
+* A set of key-value pairs
+* Mutable
+* Items in arbirary order
+* In Python, can use any immutable type as the key
+* Use any type as the value
+
+```python
+neil = {'first_name': Neil', 'surname': Smith', 'age': 44}
+neil['surname']
+```
+
+---
+# Euler 11
+
+```python
+GRID_STRING = """08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
+49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
+81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
+52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
+22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
+24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
+32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
+67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
+24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
+21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
+78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
+16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
+86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
+19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
+04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
+88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
+04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
+20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
+20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
+01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"""
+```
+
+How many data structures can you think of for this puzzle?
+
+---
+
+# Euler 11 structures
+
+* List of lists: either a list of rows or a list of columns
+* One large list, find a number by row × 20 + column
+* Tuple of tuples, one large tuple, list of tuples, tuple of lists...
+* Dict with keys as (row, column)
+* Keep it as a string: `int(row * 20 + column) * 3)`
+ * (Beware when joining rows)
+* List of strings, tuple of strings, dict of strings...
+
+---
+
+# Comprehensions
+
+Do something to each element of an iterable, returning a sequence of the results
+
+* Iterable: anything you can use as `for item in iterable`
+* Sequence: `tuple`, `list`, `dict`
+
+Examples:
+
+* List of numbers: `[i for i in range(10)]`
+* List of squares: `[i ** 2 for i in range(10)]`
+* List of numbers from a string: `[int(n) for n in str.split()]`
+* Numbers and their squares: `{i: i ** 2 for i in range(10)}`
+* Even numbers and their squares: `{i: i ** 2 for i in range(10) if i % 2 == 0}`
+
+---
+# Comprehensions with multiple sequences
+
+All the numbers in the Euler 11 grid:
+```python
+[n for row in grid for n in row]
+```
+
+Pythagorean triples:
+<table>
+<tr valign="top">
+ <td>
+ ```python
+[(a, b, c)
+ for a in range(1, 21)
+ for b in range(1, 21)
+ for c in range(1, 21)
+ if a <= b
+ if b <= c
+ if a**2 + b**2 == c**2]
+```
+</td>
+<td>
+```python
+[(a, b, c)
+ for a in range(1, 21)
+ for b in range(a, 21)
+ for c in range(b, 21)
+ if a**2 + b**2 == c**2]
+```
+</td>
+<td>
+```python
+[(a, b, int((a**2 + b**2)**0.5))
+ for a in range(1, 21)
+ for b in range(a, 21)
+ if int((a**2 + b**2)**0.5) == (a**2 + b**2)**0.5]
+ ```
+ </td>
+</tr></table>
+
+---
+
+# Task
+
+Turn the Euler 11 grid into:
+
+* A list of lists, as a list of rows
+* A dict with keys of (x, y)
+
+Do both with explicit iteration, then using only comprehensions.
+
+---
+
+# Solutions with explicit loops
+```python
+grid_nums = [int(n) for n in GRID_STRING.split()]
+```
+
+```python
+g1 = []
+for rowstart in range(0, ROWS * COLUMNS, COLUMNS):
+ g1.append(grid_nums[rowstart:rowstart+COLUMNS])
+
+# g1[row][column]
+```
+
+```python
+g2 = {}
+for x in range(COLUMNS):
+ for y in range(ROWS):
+ g2[(x, y)] = grid_nums[x + y * COLUMNS]
+
+# g2[(x, y)]
+```
+
+Note the need for the creation of the empty container
+
+---
+
+# Solutions with comprehensions
+
+```python
+g3 = [grid_nums[row * COLUMNS:(row+1) * COLUMNS]
+ for row in range(ROWS)]
+
+# g3[row][column]
+```
+
+```python
+g4 = {(x, y): grid_nums[x + y * COLUMNS]
+ for x in range(COLUMNS)
+ for y in range(ROWS)}
+
+# g4[(x, y)]
+```
+
+```python
+g4s = {(x, y): int(GRID_STRING[(x + y * COLUMNS) * 3:(x + y * COLUMNS) * 3 + 2])
+ for x in range(COLUMNS)
+ for y in range(ROWS)}
+
+# g4s[(x, y)]
+```
+
+---
+
+# Other Python data structures
+
+## Set
+Unordered, mutable, no duplicates
+
+* Useful for removing duplicates from sequences: `list(set(items))`
+
+---
+# collections.defaultdict
+Like a dict, but doesn't throw an error if you ask for missing key
+
+```python
+>>> d = {}
+>>> d[99]
+Traceback (most recent call last):
+ File "<stdin>", line 1, in <module>
+KeyError: 99
+>>> import collections
+>>> d = collections.defaultdict(int)
+>>> d[99]
+0
+```
+
+---
+
+# collections.Counter
+Counts items in a sequence:
+
+```python
+collections.Counter(l for l in open('sherlock-holmes.txt').read()
+ if l in string.ascii_letters)
+```
+
+---
+
+# collections.namedtuple
+Dumb `object` for just storing data in named fields
+
+```python
+Point = collections.namedtuple('Point', ['x', 'y'])
+p = Point(11, y=22)
+p[0] + p[1]
+x, y = p
+p.x + p.y
+```
+
+---
+
+# Algorithms: trading space for time
+
+ </textarea>
+ <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
+ </script>
+
+ <script type="text/javascript"
+ src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
+
+ <script type="text/javascript">
+ var slideshow = remark.create({ ratio: "16:9" });
+
+ // Setup MathJax
+ MathJax.Hub.Config({
+ tex2jax: {
+ skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
+ }
+ });
+ MathJax.Hub.Queue(function() {
+ $(MathJax.Hub.getAllJax()).map(function(index, elem) {
+ return(elem.SourceElement());
+ }).parent().addClass('has-jax');
+ });
+ MathJax.Hub.Configured();
+ </script>
+ </body>
+</html>
projects / cas-master-teacher-training.git / blobdiff