Four Thousand Weeks: Time and how to use it, Oliver Burkeman
Klara and the Sun, Kazuo Ishiguro
This is a book about what it means to be human. How we learn as we grow (but don’t have the vocabulary to understand or express the process). How we learn what our emotions are. How we interpret the motivations of those around us, including those that could be deliberately self-serving. What it means to have a purpose, and to follow that purpose. And at the end, how to accept our finitude with grace.
All told in painfully sparse prose.
What a wonderful start to this year!
Devotions, Mary Oliver
As I was reading this, I realized I was highlighting or bookmarking pretty much every page!
The WEIRDest People in the World: How the West Became Psychologically Peculiar and Particularly Prosperous, Joseph Henrich
This is easily my book of the year, and possibly the last ten years. Not for the writing, but for the ideas that it generated and the understanding that I have hopefully developed.
This book picks up where Jared Diamond’s Guns, Germs and Steel ends. The author focuses on the difference between Western, Educated, Industrialized, Rich, and Democratic societies and how they differ from other societies. He goes all the way back to hunter-gatherers and how they coalesce (or don’t) into groups and clans, and how different customs are adopted to survive and later thrive. These lead to kin-based societies. The big disruption in the west happened due to the church – the Catholics followed by protestants. And while this institution did what it did to benefit itself, it seeded the changes that would lead to WEIRD societies in a few centuries.
When I was much younger (and more naive) I used to think that education was the solution to all of India’s problems (this is still true for many problems that we face). However, there were numerous examples of educated people behaving like idiots, and I could not fathom why, until I read this book. Take a simple example of a village threatening an entire community for what a single person has done. There is a psychological cultural explanation for this that I had not realized before.
I have a fairly good exposure to India and the US and have interacted with quite a few Europeans. There were so many descriptions that I could immediately relate to. Consider the difference between guilt (personal) and shame (collective). Now think about the institutions that we import from the west, and which, to our surprise, don’t work here! We are not culturally aligned with the processes that created these institutions; hence their failure.
A few other ideas that struck me:
- I’m still trying to figure out the role of nations today. However, there is ample evidence of the importance of competition.
- I encourage my students to take multiple online courses on the same subject. Every teacher brings a different perspective, and this deepens our knowledge of the subject. It turns out this was exactly what was happening with guilds and apprenticeships in Europe, and exactly what does not happen in kin-based clans
- The greater the interconnectedness of the network, the more innovation and invention are observed. Ditto the greater the diversity of minds at work.
- Success is a function of the network we belong to. Sharing ideas is more useful (for everyone) than hoarding ideas. The latter helps the hoarder for a short time but leaves no lasting gains. Of course, this is obvious but good to have data that backs it up!
… exploring how our psychology shapes institutions and how institutions shape our psychology.”
I think one missed opportunity is understanding how America was unique (when it was being settled) as compared to Europe, and how this has lead to a distinct American psyche!
I will be re-reading this to better think about what needs this means in the Indian context. Secondly, can we apply the same analysis to the biggest institution that we have thus far — the internet? And the impact that it has had on the psychology of pretty much everyone?
AoC: Day 07
The Problem
Given a set of ‘rules’, figure out which bags could contain a given bag, and in part 2, how many bags could be contained in the given bag.
My Solution
In the prior year, the difficulty level ratcheted up fairly quickly, and I was beginning to get worried this year! Not to worry, this one was pretty hairy!
The rules specified very clearly describe a graph, and we need to essentially do a backward traversal for part 1 and a forward traversal (accumulating values as we go) for part 2. I’m happy to say I resisted the lure of actually creating a graph, and instead just used dictionaries instead of nodes and edges.
The format of the input was fairly intricrate, so I just parsed each line directly, rather than putting together a regular expression to do so. Different dictionaries for each part and recursion to wrap it all up!
Implementation
- There is actually a library called
parsethat makes it pretty easy to, well, parse input like this - Most solutions just split the input line into two, and then searched for contained bags. I like my approach better
- Some solutions used either dictionaries or lists but iterated over them multiple times. Very inefficient!
- A few actually used
networkxto build a graph and then process it - Most solutions were essentially unreadable (as I’m sure mine is). This is a function of the problem that we’re trying to solve, I suppose. Or maybe I’m just tired…
- There was one succint, readable solution that used set comprehensions and a pretty neat recursion within it
Things are beginning to get exciting!
Anthem, Ayn Rand
I read this with my daughter and lead to great conversations about the society that we live in and that we would want to live in. Very topical, considering what has been going on in Afghanistan. Also very depressing, since the mentality that would result in this type of dystopia is too prevalent everywhere we look.
An economics education would help. An open mind would help even more. Accepting that other people have opinions, are entitled to them, and if they do not match ours, it’s alright, would help the most.
The writing matches what I remember from Atlas Shrugged and The Fountainhead, those staples of angst-driven undergrads the world over. I still find it funny how incidental women are in these books, and what a huge pedestal the heroes need.
Finally, this should be mandatory reading as a warning of where we, as humanity, could easily end up. Also suitable for everyone with an optimistic faith in humanity.
AoC: Day 06
The Problem
We have to combine all the single-character responses from groups of people in part 1, and count only the unique responses in part 2.
My Solution
Thankfully, a bit of sanity. I recognized both these as sets so just used the union and intersection operators. Quite happy with my input parsing as well — split into groups based on \n\n
One problem that I faced was that the last group from part 2 was not being processed properly. The last line was empty, hence its intersection with the rest of the data was zero. Learnt the difference between split("\n") and split()
Implementation
- A few solutions did what I would have blindly done — manually count unique solutions. Some also combined this with
sets! - We can use a single function and pass it set.reduce and set.union. cool! This function can apply the arguments using
reduce, or, even cooler, using the*operator - Once we have the unpacking operator, a one-liner with a combination of set and list comprehensions is possible. Interesting, but ugly code, and defeats the purpose….
Overall interesting problem, but not too challenging. I learnt a few new things about python, but no new algorithmic ideas.
AoC: Day 05
The Problem
We need to convert a string that encodes the seat row and column to a seat number. In part 2, we have to find the missing seat number in the input data
My Solution
I came to AoC after a bit of a break and just wanted to get it done in time. The approach I took followed the illustration in the problem for the conversion (excuses, excuses, excuses…). So I actually walked through the string, and if the character is an ‘F’ I did this, and if it’s a ‘B’ I did that. Yes, I’m embarrassed (see below). To add to my embarrassment, I implemented two functions for recovering the row and column numbers, instead of just one. My Part 2 was the most idiotic, brute-force, unelegant solution you can imagine!
Implementation
- This is not something I would do, but highlighting out of interest. A few solutions actually created a list of 128 (or 8, in case of columns) populated with the indices, and chopped it up.
- Python
stringhas areplacefunction and amaketransfunction so it’s easy to replace, say, ‘F’ with a ‘0’ and ‘B’ with a ‘1’…. and then interpret this as an integer base 2! Why would you want to do this? see the note below. - A neat implementation uses recursion and what is essentially a binary search on the indices but keyed on the string
Algorithm
- My ‘doh!’ moment was not recognizing that the string in its entirety was a binary representation of the desired output! Including the combination of rows and columns!!
Part 2 had multiple approaches:
- Put all the values in a
setand do a set difference with the entire range - Add all the numbers up and subtract from the arithmetic sum
- Similar to the above, but use XOR on the full range
- Simulate: Choose a seat and check if it’s occupied. If yes, choose the next seat. The expected number of times to do this is the harmonic series and converges very rapidly.
I really like the last approach, and would not have thought of it. I should have recognized the binary encoding and the summing, so am kicking myself.
Oh well, I live and learn!
AoC: Day 04
The Problem
We’re given a bunch of data in key:value pairs that we have to count (part 1) and validate (part 2). If it walks like a dict and talks like a dict…
My Solution
I was consciously looking for opportunities to do a bit of comprehension, so figured out how to do just that. The first had a bit of ugly code for the checks, I implemented the checks for the second part in a big function. Didn’t take me much time and my code ran the first time around, so I was quite happy.
Unfortunately, for the input processing as well as the checks, I directly did what the problem asked, while there were better and more elegant ways of solving the problem…
Implementation
- Python has a function
allthat checks if all the entries of a list are true. Cool! - Processing the input — I broke the entries when I encountered an empty line. Much better to just split on
\n\n, then join what remains and split on spaces, which gives us all the k:v pairs. Lesson: take a step back and think about the task at hand; the obvious solution isn’t the only one! - Comprehensions: the above can be put into a list comprehension, followed by a call to
all:[[y.split(':') for y in re.split(' |\n',x)] for x in r.split('\n\n')] - The biggest learning from this problem: we can use functions as values in a dict (and therefore lambdas as well)! I had no idea this was present, but in retrospect, obvious, as everything in python is an object
AoC: Day 03
The Problem
We’re still in the relatively easy phase. In this problem, we’re given a map with trees marked in, and on a straight-line path, we have to count how many trees we encounter. The only thing to account for is that the map repeats horizontally, we have to replicate it as many times as needed till we reach the bottom. We do the same in part 2, for different lines.
My Solution
I thought this was pretty straightforward; it took me about ten minutes for each part. However, when I looked at other solutions…
Algorithm
Not really an algorithm, but I was kicking myself about this. I physically (is that the right term?) replicated the map as many times as needed (even did a calculation to figure this out upfront). Turns out all I needed to do is use the mod operator!
Implementation
- The last input in part 2 required going down two rows at a time. I wrapped myself up in knots doing this, but all that was needed was a
[::2] - Lots of opportunities for (list) comprehensions, I need to start recognizing these.
- Check this out:
trees = sum(forest[i * sr][(i * sc) % cols] == '#' for i in range(rows // sr))
AoC: Day 02
The Problem
This was more of a string matching exercise followed by a bit of arithmetic on the extracted data. Part 2 involves a bit of logic.
My Solution
The first thing that came to mind was regular expressions with named fields. Its been a while, so I had to go back to the (excellent) docs, but this was pretty straightforward.
Turns out this was overkill (see below)! Also, I found out not one but two improvements in my if statements!
Other Approaches
There isn’t much to explore in terms of algorithm, since the task isn’t very complicated. So mostly looking at what I could learn from doing differently the
Implementation
- My traditional
Cbased thinking translated into python:if(num >= min_inst and num <= max_inst):A more pythonic way of doing the same:if(min_inst <= num <= max_inst): - I blindly translated the requirements of part 2 into two
ifstatements, since we needed to satisfy either of two conditions, but not both …but that’s just what an xor does! - Another approach that I liked for part 2 was along the lines of
if(condition_1 != condition_2):
AoC: Day 01
The Problem
An extremely simple problem to kick things off, and one that shows up on many beginners programming tests: find two numbers from a list that add up to a specified number. Part 2 asks for three numbers that add up to the specified number. The list is not sorted.
My Solution
My solution was pretty obvious: sort the list, and do a binary search. However, turns out that NumPy has a pretty nice function called searchsorted. We give it the sorted list and a list of keys to search for, and it returns a list of indices, each corresponding to where the key would be inserted while maintaining the order. So pretty cool, I learnt about a new function. And my overall runtime is $O(n\lg{n})$
For Part 2, the natural approach is to repeat part 1 for every element of the list, while suitably modifying the desired sum.
Other Approaches
Now the fun part! Let’s order these into three groups
Algorithm
- The straightforward – a doubly nested loop, $O(n^2)$
- Many binary searches; see the next section for variations in the implementation
- The one I liked best, and one that I’m kicking myself for not thinking about. Set a
loandhiindex and add the corresponding values. If the sum is greater than the desired value, decrementhi, if less, incrementlo, if equal, we’re done. The proof of why this is correct is left to the reader. Note that this only speeds up the search time to linear from $O(n\lg{n})$, the sorting time is not changed. The asymptotic time for both approaches is the same, but this is more elegant! - Generating functions (see below)
Implementation
- The straightforward approach can be expressed as a list comprehension
- Use recursion to make it generic: if we want $n$ numbers that add up to the desired value, express this in terms of $n-1$. And of course, don’t forget to terminate the recursion
- Read the list of numbers into a
set. Offload the search for the second number to the set. This can be done using alistas well, but the search time will be linear instead of logarithmic. Another approach used twodicts, for each input number and its complement. I think this was overkill, though I liked the approach itertools.combinationsI need to get a better handle on theitertoolslibrary. Turns out we can simply create all 2-combinations and a loop over these is all that is required. I haven’t looked up the time complexity, but this is likely $O(n^2)$, so there is that…itertools.productalso can be used for generating the cartesian products of the input
Yowza!!
Express the input list as a polynomial. The values of the list are coefficients and the powers of the variable. Then in the square of this polynomial, the coefficient of the target numbered term is the product that we’re looking for since powers are added and coefficients are multiplied. Knuth would approve!! And of course, we can do the polynomial multiplication using FFTs.
The Joy of x, Steven Strogatz
What a wonderful little book, and how effortlessly the author describes the intuition behind some pretty deep maths concepts!