Starter: Activity 1
— How many words can be made out of the letters A, C, T?
…(or, harder: out of the letters A, E, R, T?)
— Did you find them all? How do you know?
In the first exercise, I expect you worked it out by listing out the words you could think of (or find with an online dictionary), and then counted them up. For instance:
ACT, TAC, AT, CAT, TA = 5
Finding “all” of them is quick and easy. Maybe. You might be very confident you’ve found them all. But what about with the harder set?
ART, AT, RAT, RATE, TEAR, TEA, TAR, TA = 8
That’s wrong; there’s more (I think). What’s a better way of doing this? Well, if we had a methodical approach, if we had an algorithm that guaranteed to attempt every combination, and we could check each one to see if it’s a real world, that would ensure we found all of them.
A simple algorithm is:
- Write down every combination that uses 1 letter
- For each combination, add one letter on the end, and try every possible 2nd letter
- …Repeat step 2 with a third letter, then a fourth, etc
Which works out something like this:
2. E = not a word
3. R = not a word
4. T = not a word
…and then goes:
Try this enough times, and you’ll end up with a long list of possible words:
A, E, R, T, AE, AR, AT, EA, ER, ET, RA, RE, RT, TA, TE, TR, AER, AET, ARE, ART, ATE, ATR, EAR, EAT, ERA, ERT, ETA, ETR, RAE, RAT, REA, RET, RTA, RTE, TAE, TAR, TEA, TER, TRA, TRE, AERT, AETR, ARET, ARTE, ATER, ATRE, EART, EATR, ERAT, ERTA, ETAR, ETRA, RAET, RATE, REAT, RETA, RTAE, RTEA, TAER, TARE, TEAR, TERA, TRAE, TREA = 64 possible words
From which, using a dictionary to check each one, the following are all real English words:
A, AT, ET, RE, TA, ARE, ART, ATE, EAR, EAT, ERA, RAT, TAR, TEA, RATE, TARE, TEAR = 17 real words
With this process, I’ve found more than twice as many words as my first attempt. Obviously it’s been more successful! But it hasn’t just given a “better” answer — it’s given a “perfect” answer: we tested EVERY possibility, and by doing that, we guaranteed that we couldn’t miss any.
An algorithm that checks every possibility not only gives a good answer, but it’s guaranteed to give the best answer
Colloquially, a non-technical description of this is “a methodical approach”. This loosely means: you think of something that helps you be sure you checked everything, and then you check everything. Collins dictionary defines Methodical as “do things carefully, thoroughly, and in order” — we’re using the last two parts especially: by Ordering the possible items, we can be sure we Thoroughly chose them (didn’t miss any out).
The mathematical/computer science description would probably mention “Enumeration” or “Ordering”/”Ordered Set” (you can think of each word we checked as a number, and mathematically we made sure that our process counted 1,2,3,4, without skipping any numbers. That way, we were sure we’d cover every possibility).
Why do programmers care so much about Methodical approaches?
There are huge benefits to methodical approaches — guaranteed to find every answer, easy to check — with only two big downsides: They’re exceedingly boring, and they take ages (with lots of wasted time).
If you look back at the words examples, we spent more time writing down the list of possible words than we did deciding which were real/not real. Worse — of the 64 possibles we wrote down, only one quarter of them were useful! Lots of wasted effort.
So, in the real world, humans try to avoid methodical approaches until/unless they become necessary. If you can find a shorter route, you do. If you can solve something “off the top of your head”, you do. Or if you can solve it by guessing or intuition … you do.
But computers are exceptionally good at doing repetitive tasks: they never get bored, and it’s very easy to tell them to do the same thing over and over again without making any mistakes.
This makes Methodical approaches usually the best way to solve a problem using a computer: you get all the benefits, and none of the downsides.
Starter: Activity 2
— If you have a bag with three different, numbered, marbles, how many unique pairs could you pick out?
— Are you sure? How do you know?
— If you have a bag with 100 different, numbered, marbles, how many unique groups of 50 could you pick out?
How did that go? Did you use the methodical approach, to ensure that you didn’t miss any combinations?
…I hope not.
Because I know the answers. For the first part, there are 3 possible pairs you could pick out. Methodically:
A + B
A + C
B + C
(we don’t care about order: the pair “A then B” is the same as the pair “B then A”)
But the second part, there are 1.008913 x 10²⁹ ways of picking them out. ie a number written as (approximately) “1 … then 29 zeroes”.
If you tried writing them all down it would take you longer than your lifetime to answer the question. Even if you asked a computer to do it, it would take a significant amount of time: in 2018, a brand new desktop with a 4 GHz CPU can do approximately 1 x 10⁹ calculations a second. So … to solve this methodically, even a computer would need approximately 1 x 10²⁰ seconds to solve it.
That’s three TRILLION years.
So how did I answer it? I certainly didn’t use a methodical approach. Instead, I used some outside knowledge, some deeper understanding of the problem, to think of a different algorithm that would give me the answer directly.
The mathematical term for this kind of question is “Binomial”, and mathematicans figured out shortcuts to answering the questions thousands of years ago. Here’s an online calculator that will answer any question almost instantly: https://www.hackmath.net/en/calculator/n-choose-k?n=100&k=50&order=0&repeat=0
As a programmer, you want to solve every problem using a Methodical approach — except where you don’t. On a day to day basis, this is one of the most important, recurring, decisions that a programmer makes: which kind of approach is needed here?
In reality, what happens when you guess wrong?
…not much bad.
If you pick a methodical approach for a problem too big for methodical approaches then the computer will churn through it and take ages and it won’t get bored it’ll just keep going. Eventually, YOU will get bored, and cancel the program, close the window, etc. As a programmer, you’ll say to yourself: “This is taking too long; I’d better find a different way”.
If you pick a smarter-algorithm approach for a problem that could have been done methodically, then (so long as the smart algorithm is correct) it will simply work, and fast.
If you’ve ever wondered why programmers like to find “elegant” solutions, or ask lots of questions trying to learn extra detail about a problem … this is part of the cause: they want to jump straight to the faster, simpler algorithm that shortcuts work, and avoids the risk of it being too slow (even for a computer).
But if you slightly misunderstand the problem, you’ll probably pick a slightly wrong shortcut algorithm. And you’ll get completely the wrong answer. Or — randomly — you might get some right answers, some wrong answers. That’s a nightmare: it might seem correct, but later turn out to be incorrect. So it’s very important to be SURE you understand the problem if you’re going to try and shortcut it!
There are two big things from this lesson:
1. Methodical approaches always work, if you don’t make mistakes (huamns make mistakes, computers don’t)
2. Methodical approaches can be boring (for humans) and slow (for humans AND computers)
…with the net effect that most humans — including programmers — avoid methodical approaches most of the time. But if other approaches fail, the methodical approach is ALWAYS available as a fallback option.