You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: README.md
+2Lines changed: 2 additions & 0 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -1,5 +1,7 @@
1
1
# Introduction
2
2
3
+
> "Codes are a puzzle. A game, just like any other game." - Alan Turing
4
+
3
5
> "The only way to learn a new programming language is by writing programs in it." - Dennis Ritchie
4
6
5
7
I believe you can learn serious things through silly games. I also think you will learn best by *doing*. This is a book of programming exercises. Each chapter includes a description of a program you should write with examples of how the program should work. Most importantly, each program includes tests so that you know if your program is working well enough.
Copy file name to clipboardExpand all lines: gibberish/discussion.md
+3-1Lines changed: 3 additions & 1 deletion
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -139,4 +139,6 @@ If you didn't realize it, you just implemented a basic machine learning algorith
139
139
140
140
## What next
141
141
142
-
Now you can talk the "Markov Chain" problem that moves to the level of words and generates novel texts!
142
+
* Use the two rhyming programs (`rhymer` and `soundex_rhymer`) to create a list of words that sound similar that you use for the input to `gibberish.py` to create novel words that (might) sound like the inputs, then use those to create Suess-ish texts.
143
+
* Tackel the "Markov Chain" problem where you work at the level of words to generates novel texts.
Copy file name to clipboardExpand all lines: set/README.md
+49-33Lines changed: 49 additions & 33 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -2,10 +2,10 @@
2
2
3
3
We programmed "Blackjack," a card game using a standard deck of 52 playing cards which differed in two attributes: the suites (e.g., "Hearts"), and the card value (e.g., "10" or "Jack"). Now we're going to look at another card game that uses 81 cards which differ in 4 attributes each of which can have 3 values:
4
4
5
-
1.Color (red, green, purple)
6
-
2.Shape (oval, squiggle, diamond)
7
-
3.Number (1, 2, 3)
8
-
4.Shading (solid, striped, outlined)
5
+
1.Number (1, 2, 3)
6
+
2.Color (Red, Green, Purple)
7
+
3.Shading (Solid, Striped, Putlined)
8
+
4.Shape (Oval, Squiggle, Diamond)
9
9
10
10
Look up the game online to see examples of the cards. Even better, get a deck and play with your friends!
11
11
@@ -28,55 +28,71 @@ Otherwise, your program will need to create a deck of 81 cards by crossing all 4
28
28
````
29
29
$ ./set.py -s 1
30
30
Set 1
31
-
2: 1 Green Outlined Diamond
32
-
6: 3 Purple Outlined Squiggle
33
-
8: 2 Red Outlined Oval
31
+
1 Green Outlined Diamond
32
+
2 Red Outlined Oval
33
+
3 Purple Outlined Squiggle
34
34
Set 2
35
-
4: 2 Red Outlined Squiggle
36
-
6: 3 Purple Outlined Squiggle
37
-
9: 1 Green Outlined Squiggle
35
+
1 Green Outlined Squiggle
36
+
2 Red Outlined Squiggle
37
+
3 Purple Outlined Squiggle
38
38
````
39
39
40
40
## Creating and sorting the deck
41
41
42
-
There are dozens of ways you could chose to solve this, and it's unlikely you would stumble upon my particular solution. In order to pass the test suite, we will have to do a couple of things the same way. For one this, we both need to use the same method to sort and shuffle our decks and then select the 12 cards.
42
+
There are dozens of ways you could chose to solve this, but, in order to pass the test suite, we will have to do a couple of things the same way. For one, we both need to use the same method to sort and shuffle our decks and then select the 12 cards.
43
43
44
-
To create the deck, you could manually enter all 81 cards, but that way lies madness. I suggest you use `itertools.product` to cross four lists, one for each of the numbered attributes above and each containing their the three values. The problem comes in sorting the deck, and so let's just agree to sort the cards by the string representation which, as shown above, will be `number color shading shape`, e.g., "3 Purple Outlined Squiggle."
44
+
To create the deck, you could manually enter all 81 cards, but that way lies madness. I suggest you use `itertools.product` to cross four lists, one for each of the numbered attributes above and each containing their the three values. This returns a `list` of `tuple` values, which seems like a perfect way to model the cards:
45
45
46
-
There are many ways you could represent the idea of a "card" in your program. You could use a `tuple` of four strings which would sort properly and allow you to access each individual field for purposes of comparing cards. You'll have to remember the location of each field which is not too onerous, but still you might rather choose to use a `dict` with named fields and a full string of the values for sorting. I happened to choose a `class` with the `@dataclass` decorator that has a special `__str__` method to stringify the `Card` class.
46
+
````
47
+
>>> from itertools import product
48
+
>>> list(product('AB', '12'))
49
+
[('A', '1'), ('A', '2'), ('B', '1'), ('B', '2')]
50
+
````
47
51
48
-
Consider making a function called `make_deck` that will create the deck (however you represent it) and return it sorted properly. Then add this function to run with `pytest`:
52
+
However you chose to represent each card, the `list` of cards should be sorted for number color, shading, and shape. Consider making a function called `make_deck` that will create the deck and return it sorted properly. Then add something like this function to run with `pytest`. That is, I chose to use tuples for each card, so I'm checking that the first and last values in the `deck` are my expected tuples:
Once you have a sorted deck, use `random.shuffle` to sort it, then use `random.sample` to select 12 cards. With that, we should both have identical cards for the tests.
61
65
62
66
## Finding a set
63
67
64
-
If you run `solution.py -d`, you can see a sample hand of 12 cards:
68
+
Think about how you might decide if any three of cards forms a set. I would suggest thinking backwards from this test function which I suggest you include in your program:
65
69
66
70
````
67
-
DEBUG:root:hand =
68
-
1 Red Outlined Oval
69
-
1 Red Outlined Squiggle
70
-
1 Green Outlined Diamond
71
-
3 Red Striped Diamond
72
-
2 Red Outlined Squiggle
73
-
3 Green Outlined Oval
74
-
3 Purple Outlined Squiggle
75
-
1 Purple Solid Oval
76
-
2 Red Outlined Oval
77
-
1 Green Outlined Squiggle
78
-
1 Purple Solid Squiggle
79
-
2 Green Solid Diamond
80
-
````
81
-
82
-
Your job is to look at all possible combinations of 3 cards, and I suggest you use `itertools.combinations` for this. Any 3 cards form a set if each attribute is exactly the same or entirely different. This particular has 2 sets. Can you find them manually? How will you write code to determine if cards are a set? How will you represent each attribute?
assert not is_set([tuple('ABCD'), tuple('ABCD'), tuple('ABCE')])
77
+
assert is_set([
78
+
('1', 'Green', 'Outlined', 'Diamond', '1'),
79
+
('Green', 'Outlined', 'Squiggle'),
80
+
('1', 'Green', 'Outlined', 'Oval')
81
+
])
82
+
assert is_set([
83
+
('1', 'Green', 'Outlined', 'Diamond'),
84
+
('2', 'Red', 'Striped', 'Squiggle'),
85
+
('3', 'Purple', 'Solid', 'Oval')
86
+
])
87
+
assert not is_set([
88
+
('1', 'Green', 'Outlined', 'Diamond'),
89
+
('2', 'Red', 'Striped', 'Squiggle'),
90
+
('3', 'Green', 'Solid', 'Oval')
91
+
])
92
+
````
93
+
94
+
If you represent your cards as strings, dictionaries, sets, or some other object, you should modify the test to reflect your design decisisons. Still, the ideas are the same. The first test assumes that I pass in 3 identical structures have the same 4 elements, `A`, `B`, `C`, and `D`. That should be a set. In the second test, all 3 structures are entirely different, so that's a set. In the third, the fourth element of the last structure is composed of the values `D`, `D`, and `E`, so that's not a set. Can you write the function `is_set` that will return a `bool` that indicates whether or not the list is a set?
95
+
96
+
Once you have that function job, you need to examine all possible combinations of 3 cards. I suggest you use `itertools.combinations` for this. Then you can `filter` the combinations for those where `is_set` is `True`.
97
+
98
+
Print out each set of cards with "Set N" and then the three cards in the set each on a new line. The test suite doesn't card what order the sets are printed, but the cards need to be `sorted`.
There's very little to see in `get_args`, just defining the `-s|--seed` and `-d|--debug` options, the former of which gets passed to `random.seed`. As in many other programs, I set up `logging.basicConfig` to log to a `filename='.log'` (so it will normally be hidden from view) using `filemode='w'` (so it will overwrite each time it runs), and setting the `level` either to `logging.DEBUG` or `logging.CRITICAL` depending on the presence of the `--debug` flag.
1
+
There's very little to see in `get_args`, just defining the `-s|--seed` and `-d|--debug` options, the former of which gets passed to `random.seed`. As in many other programs, I set up `logging.basicConfig` to log to a `filename='.log'` (so it will normally be hidden from view) using `filemode='w'` (so it will be overwritten each time it runs), and setting the `level` either to `logging.DEBUG` or `logging.CRITICAL` depending on the presence of the `--debug` flag.
2
2
3
-
As stated in the introduction, I chose to use a `class` to represent the idea of a "card" in my program. I'm not actually a huge fan of object-oriented programming (OOP). I wrote object-oriented software for many years, and I find it can be rather bloated and confusing after a time. I prefer function-oriented programming these days and tend to be more influenced in my style by languages like Haskell, Elm, and Rust. The `@dataclass` decorator for a `class` makes it very easy to write an object in Python as it creates
3
+
As stated in the introduction, I chose to use the list of tuples returned from `itertools.product`. I also have chosen to include some type annotations by bringing in the `typing` module. This allows me to use the `mypy` tool to check for common errors. It also helps me think about the inputs and return values for my functions. The function `make_deck` has no inputs and returns a list of tuples:
As expected, I get 81 cards from the function. I can use the `test_make_deck` function to do a little more probing.
20
+
21
+
The next function I tackled was `is_set` that takes 3 cards and looks at the 4 attributes. The order of the attributes is actually not important for this function. That is, we don't care that "number" is first, we only care that all the first elements are exactly the same or entirely different. The data structure that comes to my mind is, not surprisingly, a `set`. If all the elements of the `set` are the same, then the length of the set will be `1`; if they are entirely different, then the length will be `3`.
22
+
23
+
I can use the `zip` function to group all the first elements together, then all the second elements, and so forth.
With those functions in place, we can make a deck of cards, shuffle them, randomly sample 12 cards, and then select only those where `is_set` is `True`:
65
+
66
+
````
67
+
>>> import random
68
+
>>> from itertools import combinations
69
+
>>> random.seed(1)
70
+
>>> deck = make_deck()
71
+
>>> random.shuffle(deck)
72
+
>>> hand = random.sample(deck, k=12)
73
+
>>> sets = filter(is_set, combinations(hand, 3))
74
+
````
75
+
76
+
If you copy and paste this code, keep in mind that the `filter` function returns a `filter`*object* which is *lazy*, so if you use, for example, `list` to force the REPL to evaluate and print the filtered sets, you will have exhausted the generation of the results. You can assign `sets` to `list(filter(...))` to get something you can `print` and get the `len` and iterate repeatedly.
77
+
78
+
Keep in mind that `sets` is a `list` of the 3-tuples of cards that form sets. We still need to iterate over the `sets` and print them out with the cards `sorted`:
I will confess that my first solution was considerably more complicated involving a custom `class` to represent a `Card` and using one-hot encoding and bit-wise addition to find sets. After writing that version and then sleeping on it, I was moved to create a far simpler solution, in part because of these ideas:
96
+
97
+
> Sometimes, the elegant implementation is just a function. Not a method. Not a class. Not a framework. Just a function. -- John Carmack
98
+
99
+
> Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away. -- Antoine de Saint-Exupery
100
+
101
+
A big leap was in thinking of sets as `ABCD` rather than `3 Purple Outlined Squiggle` and then realizing that the `list(tuple)` structure returned by `itertools.product` was the simplest data structure that solved 90% of my design. My first implementation was about 1/3 longer than this final version which I think reads considerably better.
0 commit comments