In January 2025 computer scientist Simon Peyton Jones gave an inspiring lecture at Darwin College Cambridge on “Bits with Soul” about the joy, beauty, and creativity of computer science … from simple ideas of data representation comes all of virtual reality.
Our universe is built from elementary particles: quarks, electrons and the like. Out of quarks come protons and neutrons. Put those together with electrons in different ways to get different atoms. From atoms are built molecules, and from there on come ever more complexity including the amazing reality of planets and suns, humans, trees, mushrooms and more. From small things ever more complex things are built and ultimately all of creation.
The virtual world of our creation is made of bits combined using binary, but what are bits, and what is binary? Here is a puzzle that Simon Peyton Jones was set by his teacher as a child to solve, to help him think about it. Once you have worked it out then think about how things might be built from bits: numbers, letters, words, novels, sounds, music, images, videos, banking systems, game worlds … and now artificial intelligences?
A bank cashier has a difficult customer. They always arrive in a rush wanting some amount of money, always up to £1000 in whole pounds, but a different amount from day to day. They want it instantly and are always angry at the wait while it is counted out. The cashier hatches a plan. She will have ready each day a set of envelopes that will each contain a different amount of money. By giving the customer the right set of envelope(s) she will be able to hand over the amount asked for immediately. Her first thought had been to have one envelope with £1 in, one envelope with £2 in, one with £3 and so on up to an envelope with £1000 in. However, that takes 1000 envelopes. That’s no good. With a little thought though she realised she could do it with only 10 envelopes if she puts the right amount of money in each. How much does she put in each of the 10 envelopes that allows her to give the customer whatever amount they ask for just by handing over a set of those envelopes?
The computing world is a wild west, with bugs in software the norm, and malicious people and hostile countries making use of them to attack people, companies and other nations. We can do better. Just as in the original wild west, advances have happened faster than law and order can keep up. Rather than catch cyber criminals we need to remove the possibility. In software the complexity of our computers and the programs they run has increased faster than ways have been developed and put in place to ensure they can be trusted. It is important that we can answer precisely questions such as “What does this code do?” and “Does it actually do what is intended?”, but can also assure ourselves of what code definitely does NOT do: it doesn’t include trapdoors for criminals to subvert, for example. Philippa Gardner has dedicated her working life to rectifying this by providing ways to verify software, so mathematically prove such trust-based properties hold of it.
Programs are incredibly complicated. Traditionally, software has been checked using testing. You run it on lots of input scenarios and check it does the right thing in those cases. If it does you assume it works in all the cases you didn’t have time to check. That is not good enough if you want code to really be trustworthy. It is impossible to check all possibilities, so testing alone is just not good enough. The only way to do it properly is to also use engineering methods based on mathematics. This is the case, not just for application programs, but also for the software systems they run within, and that includes programming languages themselves. If you can’t trust the programming language then you can’t trust any programs written in that language. Building on decades of work by both her own team and others, Philippa has helped provide tools and techniques that mean complex industrial software and the programming languages they are written in can now be verified mathematically to be correct. Helping secure the web is one area she is making a massive contribution via the W3C WebAssembly (Wasm) initiative. She is helping ensure that programs of the future that run over the web are trustworthy.
Programs written in programming languages are compiled (translated) into low level code (ie binary 1s and 0s) that can actually be run on a computer. Each kind of computer has its own binary instructions. Rather than write a compiler for every different machine, compilers often now use common intermediary languages. The idea is you have what is called a virtual machine – an imaginary one that does not really exist in hardware. You compile your code to run on the imaginary machine. A compiler is written for each language to compile it into the common low level language for that virtual machine. Then a separate, much simpler, translator can be written to convert that code into code for a particular real machine. That two step process is much easier than writing compilers for all combinations of languages and machines. It is also a good approach to make programs more trustworthy, as you can separately verify the separate, simpler parts. If programs compile to the virtual machine, then to be sure they cannot do harm (like overwrite areas of memory they shouldn’t be able to write to) you also only have to be sure that programs running on the virtual machine programs cannot , in general, do such harm.
The aim of Wasm is to make this all a reality for web programming, where visiting a web page may run a program you can’t trust. Wasm is a language with linked virtual machine that programming language compilers can be compiled into that itself will be trustworthy even when run over the web. It is based on a published formal specification of how the programming language and the virtual machine should behave.
As Philippa has pointed out, while some companies have good processes for ensuring their software is good enough, these are often kept secret. But given we all rely on such software we need much better assurances. Processes and tools need to be inspectable by anyone. That has been one of the areas she has focussed on. Working on Wasm is a way she has been doing that. Much of her work over 30 years or so has been around the development and use of logics that can be used to mathematically verify that concurrent programs are correct. Bringing that experience to Wasm has allowed her to work on the formal specification conducting proofs of properties of Wasm that show it is trustworthy in various way, correcting definitions in the specification when problems are found. Her approach is now being adopted as the way to do such checking.
Her work with Wasm continues but she has already made massive steps to helping ensure that the programs we use are safe and can be trusted. As a result, she was recently awarded the BCS Lovelace medal for her efforts.
Computer Scientists talk about “Syntactic Sugar” when talking about programming languages. But in what way might a program be made sweet? It is all about how necessary a feature of a language is, and the idea and phrase was invented by Computer Scientist and gay activist, Peter Landin. He realised it made it easier to define the meaning of languages in logic and made the definitions more elegant.
Peter Landin was involved in the development of several early and influential programming languages but also a pioneer of the use of logic to define exactly what each construct of a programming language did: the language’s “semantics”. He realised there was a fundamental difference between different parts of a language. Some were absolutely fundamental to the language. If you removed them then programs would have to be written in a different way, if at all, as a result. Remove the assignment construct that allows a program to change the value of variables, for example, and there are things your programs can no longer do, or at least it would need to do it in very different way. Remove the feature that allows someone to write i++ instead of i = i + 1, on the other hand, and nothing much changes about how you write code. They were just abbreviations for common uses of the more core things.
As another example, suppose you didn’t like using curly brackets to start and end blocks of code (perhaps having learnt to program using Pascal) then if programming in C or Java you could add a layer of syntactic sugar by replacing { by BEGIN and } by END. Your programs might look different and make you feel happier, but were not really any different.
Peter called these kinds of abbreviations “syntactic sugar”. They were superficial, just there to make the syntax (the way things were written at the level of spelling and punctuation) a little bit nicer for the programmers: sometimes more readable, sometimes just needing less typing.
It is now recognised, of course, that writing readable code is a critically important part of programming. Code has to be maintainable: easily understood and modified by others long after it was written. Well thought out syntactic sugar can help with this as well as making it easier to avoid mistakes when writing code in the first place. For example, syntactic sugar is used in many languages to give special syntax to core datatypes, where they are called sugared types. Common example include using quotes to represent a String value like “abc” or square brackets like [1,2,3] to stand for an array value, rather than writing out the underpinning function calls of the core language to construct a value.
People now sometimes deride the idea of syntactic sugar, but it had a clear use for Peter beyond just readability. He was interested in logically defining languages: saying in logic exactly what each construct meant. The syntactic sugar distinction made his life doing that easier. The fundamental things were the things that he had to define directly in logic. He had to work out exactly what the semantics of each was and how to say what they meant mathematically. Syntactic sugar could be defined just by adding rewrite rules that convert the syntactic sugar to the core syntax. i++, for example does not need to be defined logically, just converted to i = i + 1 to give its meaning. If assignment was defined in terms of logic then the abbreviation is ultimately too as a result.
Peter discussed this in relation to treating a kind of logic called the lambda calculus as the basis for a language. Lambda Calculus is a logic based on functions. Everything consists of lambda expressions, though he was looking at a version which included arithmetic too. For example, in this logic, the expression:
(λn.2+n)
defines a function that takes a value n and returns the value resulting from adding 2 to that value. Then the expression:
(λn.2+n) [5]
applies that function to the value 5, meaning 5 is substituted for the n that comes after the lambda, so it simplifies to 2+5 or further to 7. Lambda expressions, therefore, have a direct equivalence to function call in a programming language. The lambda calculus has a very simple and precise mathematical meaning too, in that any expression is just simplified by substituting values for variables as we did to get the answer 7 above. It could be used as a programming language in itself. Logicians (and theoretical computer scientists) are perfectly happy reading lambda calculus statements with λ’s, but Peter realised that as a programming language it would be unreadable to non-logicians. However with a simple change, adding syntactic sugaring, it could be made much more readable. This just involved replacing the Greek letter λ by the word “where” and altering the order and throwing in an = sign..
Now instead of writing
(λn.2+n) [5]
in his programming language you would write
2 + n where n = 5
Similarly,
(λn.3n+2) [a+1]
became
3n+2 where n = a + 1
This made the language much more readable but did not complicate the task of defining the semantics. It is still just directly equivalent to the lambda calculus so the lambda calculus can still be used to define its semantics in a simple way (just apply those transformations backwards). Overall this work showed that the group of languages called functional programming languages could be defined in terms of lambda calculus in a very elegant way.
Syntactic sugar is at one level a fairly trivial idea. However, in introducing it in the context of defining the semantics of languages it is very powerful. Take the idea to its extreme and you define a very small and elegant core to your language in logic. Then everything else is treated as syntactic sugar with minimal work to define it as rewrite rules. That makes a big difference in the ease of defining a programming language as well as encouraging simplicity in the design. It was just one of the ways that Peter Landin added elegance to Computer Science.
Thousands of programming languages have been invented in the many decades since the first. But what makes a good language? A key idea behind language design is that they should make it easy to write complex algorithms in simple and elegant ways. It turns out that logic is key to that. Through his work on programming language design, Peter Landin as much as anyone, promoted both elegance and the linked importance of logic in programming.
Peter was an eminent Computer Scientist who made major contributions to the theory of programming languages and especially their link to logic. However, he also made his mark in his stand against war, and support of the nascent LGBTQ+ community in the 1970s as a member of the Gay Liberation Front. He helped reinvigorate the annual Gay Pride marches as a result of turning his house into a gay commune where plans were made. It’s as a result of his activism as much as his computer science that an archive of his papers has been created in the Oxford Bodleian Library.
However, his impact on computer science was massive. He was part of a group of computing pioneers aiming to make programming computers easier, and in particular to move away from each manufacturer having a special programming language to program their machines. That approach meant that programs had to be rewritten to work on each different machine, which was a ridiculous waste of effort! Peter’s original contribution to programming languages was as part of the team who developed the programming language, ALGOL which most modern programming languages owe a debt to.
ALGOL included the idea of recursion, allowing a programmer to write procedures and functions that call themselves. This is a very mathematically elegant way to code repetition in an algorithm (the code of the function is executed each time it calls itself). You can get an idea of what recursion is about by standing between two mirrors. You see repeated versions of your reflection, each one smaller than the last. Recursion does that with problem solving. To solve a problem convert it to a similar but smaller version of the same problem (the first reflection). How do you solve that smaller problem? In the same way, as a smaller version of the same problem (the second reflection)… You keep solving those similar but smaller problems in the same way until eventually the problem is small enough to be trivial and so solved. For example, you can program a factorial method (multiplying all numbers from 1 to n together),in this way. You write that to compute factorial of a number, n, it just calls itself and computes the factorial of (n-1). It just multiply that result by n to get the answer. In addition you just need a trivial case eg that factorial of 1 is just 1.
Peter was an enthusiastic and inspirational teacher and taught ALGOL to others. This included teaching one of the other, then young but soon to be great, pioneers of Programming Theory, Tony Hoare. Learning about recursion led Hoare to work out a way, using recursion, to finally explain the idea that made his name in a simple and elegant way: the fast sorting algorithm he invented called Quicksort. The ideas included in ALGOL had started to prove their worth.
The idea of including recursion in a programming language was part of the foundation for the idea of functional programming languages. They are mathematically pure languages that use recursion as the way to repeat instructions. The mathematical purity makes them much easier to understand and so write correct programs in. Peter ran with the idea of programming in this way. He showed the power that could be derived from the fact that it was closely linked to a kind of logic called the Lambda Calculus, invented by Alonso Church. The Lambda Calculus is a logic built around mathematical functions. One way to think about it is that it is a very simple and pure way to describe in logic what it means to be a mathematical function – as something that takes arguments and does computation on them to give results. This Church showed was a way to define all possible computation just as Turing’s Turing machine is. It provides a simple way to express anything that can be computed.
Peter showed that the Lambda Calculus could be used as a way to define programming languages: to define their “semantics” (and so make the meaning of any program precise).
Having such a precise definition or “semantics” meant that once a program was written it would be sure to behave the same way whatever actual computer it ran on. This was a massive step forward. To make a new programming language useful you had to write compilers for it: translators that convert a program written in the language to a low level one that runs on a specific machine. Programming languages were generally defined by the compiler up till then and it was the compiler that determined what a program did. If you were writing a compiler for a new machine you had to make sure it matched what the original compiler did in all situations … which is very hard to do.
So having a formal semantics, a mathematical description of what a compiler should do, really makes a difference. It means anyone developing a new compiler for a different machines can ensure the compiler matches that semantics. Ultimately, all compilers behave the same way and so one program running on two different manufacturer’s machines are guaranteed to behave the same way in all situations too.
Peter went on to invent the programming language ISWIM to illustrate some of his ideas about the way to design and define a programming language. ISWIM stands for “If you See What I Mean”. A key contribution of ISWIM was that the meaning of the language was precisely defined in logic following his theoretical work. The joke of the name meant it was logic that showed what he meant, very precisely! ISWIM allowed for recursive functions, but also allowed recursion in the definition of data structures. For example, a List is built from a List with a new node on the end. A Tree is built from two trees forming the left and right branches of a new node. They are defined in terms of themselves so are recursive.
Building on his ideas around functional programming, Peter also invented something he called the SECD machine (named after its components: a Stack, Environment, Control and Dump). It effectively implements the Lambda calculus itself as though it is a programming language.ISWIM provided a very simple but useful general-purpose low level language. It opened up a much easier way to write compilers for functional programming languages for different machines. Just one program needed to be written that compiled the language into SECD. Then you had a much simpler job of writing a compiler to convert from the low level SECD language to the low level assembly language of each actual computer. Even better, once written, that low level SECD compiler could be used for different functional programming languages on a single machine. In SECD, Peter also solved a flaw in ALGOL that prevented functions being fully treated as data. Functions as Data is a powerful feature of the best modern programming languages. It was the SECD design that first provided a solution. It provided a mechanism that allowed languages to pass functions as arguments and return them as results just as you could do with any other kind of data without problem.
In the later part of his life Peter focussed much more on his work supporting the LGBTQ+ community having decided that Computer Science was not doing the good for humanity he once hoped. Instead, he thought it was just supporting companies making profit, ahead of the welfare of people. He decided that he could do more good as part of the LGBTQ+ community. Since his death there has been an acceleration in the massing of wealth by technology companies, whereas support for diversity has made a massive difference for good, so in that he was prescient. His contributions have certainly, though, provided a foundation for better software, that has changed the way we live in many ways for the better. Because of his work they are less likely to cause harm because of programming mistakes, for example, so in that at least he has done a great deal of good.
Magic tricks are just algorithms – they involve a magician following the steps of the trick precisely. But how can a magician be sure a trick will definitely work when they do it in front of an audience? Just like computer scientists who can prove their algorithms always work, a magician can use logic and deduction to be sure their tricks always work too.
Image from Pixabay
Try the following trick on your own first, before reading about how it works or trying it with a volunteer. Take the role of both the magician and volunteer. I will do my best to remote-control the magic via my own mind-meld with you as you read my words, to try and make sure it works for you!
The magical effect
Take a full pack of playing cards and give them a good shuffle. Fan the cards face down. Now ask a volunteer to think of the colour RED and point to a card. Cut the pack at that point and count the top eight cards into a pile face down. Now ask them to think BLACK and touch another card. Cut the pack there and count out 7 cards onto the pile. Repeat this with 6 cards and then 5 cards having them think RED and then BLACK. Have the volunteer shuffle the selected cards then turn the pile face up.
Image by Paul Curzon
You take the cards that are left and shuffle them, keeping them face down. Have the volunteer now run through their cards taking out groups of cards that are together and of the same colour. They should put them either in a “RED” pile in front of them if they are a group of red cards, or in a “BLACK” pile if they are black, telling you how many cards they have placed in that pile. As they take each group of cards, you, focussing hard on your cards, but without looking at what they are, pick out the same number of cards from points through the pack as the volunteer put down, and put them in your own corresponding “RED” or “BLACK” pile in front of you, Place your cards face down. In this way, they end up with a pile of red cards and a pile of black cards, both face up in front of them. You end up with two corresponding face down piles in front of you. They have seen their cards but yours contain cards that you have not seen. Once they have run out of cards and you have placed your matching cards, stop and think for a moment, then go through your two piles and swap two cards without looking at them, saying you believe you made a couple of mistakes and those two ended up in the wrong piles.
Now, looking happy, tell the volunteer that through a mind-meld between you, them and the red and black cards you have, you believe, succeeded in your aim. Remind them that the piles were shuffled, they were responsible for the way the cards were split which was at random, and you haven’t seen any of your cards. One card out at any point and the trick would not have worked. Despite this, announce that you have managed to place the same number of red cards in your red pile as you have placed black cards in your black pile. Pass them the two piles in turn and ask them to check by first counting the red cards in your face down “RED” pile onto the table, and then do the same with the black cards that are in your “BLACK” pile.
Amazingly you have succeeded, the number of red cards in the red pile is the same as the number of black cards in the black pile.
Proving it always works
Did I mind meld with you to make it work? Or is something else going on? We can actually use logic and deduction (with some algebra) to show it works.
First we need to make a mathematical model of the situation – essentially describe the situation, or at least the parts of it that matter, in maths. That sounds a bit scary but it isn’t really. Its just giving names to some piles of cards! Let’s go through it…
In the trick, we end up with four piles of cards. A RED pile and a BLACK pile, both face up, in front of the volunteer and a RED pile and a BLACK pile, both face down, in front of the magician (see the picture above). We do not know how many cards are in each pile and it will be different each time we do the trick anyway because of all the shuffling. Luckily the actual numbers don’t matter. In the trick we care about the numbers of red cards and the numbers of black cards, Let us therefore use mathematical variables to represent these different numbers (that just means give them names!). Mathematicians often use names like x and y for variables, but to help us remember what they stand for we will use variations on R and B to mean numbers of red and black cards respectively.
So, we will use R to stand for the number of red cards in the volunteer’s face up “RED” pile (which are all red) and B to mean the number of black cards in the volunteers face up “BLACK” pile (which are all black).
Now for the magician’s face down piles. They have both red and black cards in each pile so we will write R1 to mean the number of red cards in the magician’s face down “RED” pile and B1 to mean the number of black cards in the magician’s face down “RED” pile. Similarly, we will write R2 to mean the number of red cards in the magician’s face down “BLACK” pile and B2 to mean the number of black cards in the magician’s face down “BLACK” pile. We have the situation as shown below in the picture..
Image by Paul Curzon
In doing this we are doing a form of abstraction – hiding of detail – we have hidden the actual numbers of red and black cards in each pile within our description, describing them with variables as the precise numbers do not matter (and are different every time we do the trick anyway).
So far so good. Now, we want to try and prove that the trick always works. But how to start? First, just think of any facts you know about the situation (and especially anything you know about red and black cards). It may not be obvious how it can help, but write it down anyway!
Well the first thing we know is that a full pack of cards was used, and there are 52 cards in a pack, half (26) red and half (26) black. All these cards ended up on the table in one pile or another. So that means if we add up all the red cards in the four piles it will equal 26. How can we write this in terms of our variables? It is just:
R + R1 + R2 = 26
We add the three variables that stand for numbers of red cards and it equals 26. There are only three things to add for the four piles as one pile is all black. We can say a similar thing about the black cards:
B + B1 + B2 = 26
Now we have two different sums that equal the same thing (26) so we can put them together as equalling each other to get a combined equation which we will call EQUATION 1.
R + R1 + R2 = B + B1 + B2 (EQUATION 1)
That doesn’t seem to tell us much useful, but don’t worry, we are just gathering facts for now. What else do we know about how the trick worked? Well, every time the volunteer put some number of cards in their “RED” pile, the magician puts the same number of cards in their “RED” pile (though those cards may be red or black). That means that, throughout the two “RED” piles hold the same number of cards. The number of cards in one “RED” pile is R and the number of cards in the other “RED” pile is R1 + B1 (the reds plus the blacks in that pile). We can write this out as an equation:
R = R1 + B1
Now, this tells us that R is exactly the same as R1 + B1 so anywhere we see R we can replace it with R1 + B1. In particular, we can make this switch in EQUATION 1 to give:
(R1 + B1) + R1 + R2 = B + B1 + B2 (EQUATION 2)
With the same logical reasoning, we can deduce an equation for the “BLACK” piles too. The number of cards in one “BLACK” pile is B and the number of cards in the other “BLACK” pile is R2 + B2 (the reds plus the blacks in that pile). We can write this out as an equation:
B = R2 + B2
Substituting R2 + B2 for B into EQUATION 2 we get EQUATION 3
Now, this seems to have just made things more complicated and not got us anywhere much, but we can now simplify it. Notice that there are two R1s on one side and two B2s on the other, each added, so we can group them together to get:
2R1 + B1 + R2 = R2 + 2B2 + B1
Also, on each side there is a B1 and that pair can cancel out (just subtract B1 from both sides and the equality holds but it is simpler), and on each side there is an R2 which can cancel in the same way. This leaves us with:
2R1 = 2B2
Of course the multiplication by 2 on both sides cancels too (just divide both sides by 2 and they will still be equal). We get:
R1 = B2
That is a very simple equation. It basically tells us that if you follow the steps of this trick that, whatever numbers of reds and blacks end up in each pile, R1 is guaranteed at the end to be the same number as B2. So what does that mean back in the real world? R1 just stands for the number of red cards in the magician’s “RED” pile. B2 just stands for the number of black cards in the magician’s “BLACK” pile. The equation we are left with just tells us that as long as we follow the steps (actually as long as we make the number of cards in each pair of piles match) then at the end the number of red cards in the magician’s “RED” pile will be the same as the number of black cards in the magician’s “BLACK” pile…and that is the “magical” result we predicted!
The trick will always work if you follow the steps!
Proving software and hardware always works
A magic trick involves the magician following steps precisely – following an algorithm. That is all computer hardware and software do – they follow algorithms to achieve some desired result (a magical effect). Just as we proved the trick always works, we can prove that other algorithms (whether implemented as a program or hardware) work using logical deduction too. That is one of the reasons why logic and deduction are so important to computer scientists. You do not want a trick to go wrong in front of an audience, so it is worth proving it always works. How much more important is it that all that software we now rely on for everyday life is error free. And what about a medical device keeping someone alive, or the software flying a plane. We want to be sure they always work. If they contain mistakes, people die. Logic and proof can therefore save lives, not just magic shows.
By Przemysław Wałęga, Queen Mary University of London
Logical reasoning and proof, whether done using math notation or informally in your head, is an important tool of computer scientists. The idea of proving, however, is often daunting for beginners and it takes a lot of practice to master this skill. Here we look at a simple puzzle to get you started.
Computer Scientists use logical reasoning and proofs a lot. They can be used to ensure correctness of algorithms. Researchers doing theoretical computer science use proofs all the time, working out theories about computation.
Proving mathematical statements can be very challenging, though. Coming up with a proof often requires making observations about a problem and exploiting a variety of different proof methods. Making sure that the proof is correct, concise, and easy to follow matters too, but that in itself needs skill and a lot of practice. As a result, proving can be seen as a real art of mathematics.
Let’s think about a simple puzzle to show how logical thinking can be used when solving a problem. The puzzle can be solved without knowing any specific maths, so anyone can attempt it, but it will probably look very hard to start with.
Before you start working on it though, let me recommend that first you try to solve it entirely in your mind, that is, with no pen and paper (and definitely no computer!).
The Puzzle
Here is the puzzle, which I heard at a New Year’s party from a friend Marcin:
Mrs. and Mr. Taylor hosted a party and invited four other couples. After the party, everyone gathered in the hallway to say their goodbyes with handshakes. No one shook hands with themselves (of course!) or their partner, and no one shook hands with the same person more than once. Each person kept track of how many people they had shaken hands with. At one point, Mr. Taylor shouted “STOP” and asked everyone to say how many people they had shaken hands with. He received nine different answers.
How many people did Mrs Taylor shake hands with?
I will give you some hints to help solving the puzzle, but first try to solve it on you own, and see how far you get. Maybe you will be solve the puzzle on your own?
Why did I recommend solving the puzzle without pen and paper? Because, our goal is to use logical and critical thinking instead of finding a solution in a “brute force” manner, that is, blindly listing all the possibilities and checking each of them to find a solution to the puzzle. As an example of a brute force way of solving a problem, take a crossword puzzle where you have all but one of the letters of a word. You have no idea what the clue is about, so instead you just try the 26 possible letters for the missing one and see which make a word and then check which that do fit the clue!
Notice that the setting of our puzzle is finite: there are 10 people shaking hands, so the number of ways they shake hands is also finite if bigger than say checking 26 different letters of the crossword problem. That means you could potentially list all the possible ways people might shake hands to solve the puzzle. This is, however, not what we are aiming for. We would like to solve the puzzle by analysing the structure of the problem instead of performing brute force computation.
Also, it is important to realise that often mathematicians solve puzzles (or prove theorems) about situations in which the number of possibilities is infinite so the brute force approach of listing them all is not possible at all. There are also many situations where the brute force approach is applicable in theory, but in practice it would require considering too many cases: so many that even the most powerful computers would not be able to provide us with an answer in our lifetimes.
For our puzzle, you may be tempted to list all possible handshake situations between 10 people. Before you do start listing them, let’s check how much time you would need for that. You have to consider every pair that can be formed from 10 people. A mathematician refers to that as “10 choose 2”, the answer to which is that there are 45 possible pairs among 10 people (the first person pairs with 9 others, the next has 8 others to pair with having been paired with the first already, and so on and 9+8+….+1 = 45). However, 45 is not the number that we are looking for. Each of these pairs can either shake hands or not, and we need to consider all those different possibilities. There are 245 such handshake combinations. How big is this number? The number 210 is 1024, so it is approximately 1000. Hence 240=(210)4 (which is clearly smaller than our 245) is approximately 10004 = 1,000,000,000,000 that is, a trillion. Listing a trillion combinations should sound scary to you. Indeed, if you can be quick enough to write each of the trillion combinations in one second, you will spend 31 688 years. Let’s not try this!
Of course, we can look more closely at the description of the puzzle to decrease the number of combinations. For example, we know that nobody shakes hands with their partner, which will already massively reduce the number. However, let’s try to solve the puzzle without using any external memory aids or computational power. Only our minds.
Can you solve it? A key trick that mathematicians and computer scientists use is to break down problems into simpler problems first (decomposition). You may not be able to solve this puzzle straight away, so instead think about what facts you can deduce about the situation instead.
If you need help, start by considering Hint 1 below. If you are still stuck, maybe Hint 2 will help? Answer these questions and you will be a long way to solving the puzzle.
Hints
Mr. Taylor received nine different answers. What are these answers?
Knowing the numbers above, can you work out who is a partner of whom?
No luck in solving the puzzle? Try to spend some more time before giving up! Then read on. If you managed to solve it you can compare your way of thinking with the full solution below.
Solution
First we will answer Hint 1. We can show that the answers received by Mr. Taylor are 0, 1, 2, 3, 4, 5, 6, 7, and 8. There are 5 couples, meaning that there are 10 people at the party (Mr. and Mrs. Taylor + 4 other couples). Each person can shake hands with at least 0 people and at most 8 other people (since there are 10 people, and they cannot shake hands with themselves or their partner). Since Mr. Taylor received nine different answers from the other 9 people, they need to be 0, 1, 2, 3, 4, 5, 6, 7, and 8. This is an important observation which we will use in the second part of the solution.
Next, we will answer Hint 2. Let’s call P0 the person who answered 0, P1 the person who answered 1, …, P8 the person who answered 8. The person with the highest (or the lowest) number of handshakes is a good one to look at first.
Who is the partner of P8? P8 did not shake hands with themselves and with P0 (as P0 did not shake hands with anybody). So P8 had to shake hands with all the other 8 people. Since no one shakes hands with their partner, it follows that P0 is the partner of P8!
Who is the partner of P7? They did not shake hands with themselves, with P0 and with P1, because we already know that P1 shook hands with P8, and they shook hands with only one person. So the partner of P7 can be either P8, P0, or P1. Since P8 and P0 are partners, P7 needs to be the partner of P1.
Following through with this analysis for P6 and P5, we can show that the following are partners: P8 and P0, P7 and P1, P6 and P2, P5 and P3. The only person among P0, … , P8 who is left without a partner is P4. So P4 needs to be Mrs. Taylor, the partner of Mr. Taylor, the one person left who didn’t give a number.
Consequently, we have also showed that Mr Taylor shook hands with 4 people.
Observe that the analysis above does not only provide us an answer to the puzzle, but it also allows us to uniquely determine the handshake setting as presented in the picture below (called a graph by Computer Scientists). Here, people are nodes (circles) and handshakes are represented as edges (lines) in the graph. Red edges correspond to handshakes with P8, blue edges are handshakes with P7, green with P6 and yellow with P5. Partners are located next to each other, for example, Mr. Taylor is a partner with P4.
Image computer generated by Przemysław Wałęga
Large Language Models
Although this article is about logical thinking, and not about tools to solve logic puzzles, it is interesting to see if current AI models are capable of solving the puzzle. As puzzles go it is relatively easy and occurs on the Internet in different settings and languages, so large language models (LLMs) trained on the Internet should be good at solving it. Let’s test them!
I asked ChatGPT-4o and Gemini 1.5 Flash to solve the puzzle. To my surprise, both of them did struggle. They had problems with understanding some parts of the problem formulation and made mathematical mistakes.
ChatGPT seems to wrongly assume that Mr. Taylor answered his own question about the number of handshakes, and so, that each of 10 people announced a different number of handshakes. As follows from our solution of the puzzle, there exists exactly one graph representing the handshake situation. In this graph, the number of handshakes of Mr. and Mrs. Taylor is the same, namely 4. Hence, the additional assumption made by ChatGPT (that each of 10 people had a different number of handshakes) makes the situation described in the puzzle impossible. Interestingly, ChatGPT was able to solve such an impossible puzzle providing a correct answer… Does it mean that ChatGPT has solved the puzzle?
Gemini, in contrast, states that the puzzle cannot be solved without more information such as the order of arrivals. This is clearly wrong. We know how to solve the puzzle and the order of arrivals is actually completely irrelevant to the puzzle!
This small experiment uses basic LLMs and does not aim to draw any conclusions about their capabilities. I am quite certain that one can find an LLM that can solve this simple puzzle without mistakes. However, this experiment aims to emphasise the need for checking AI solutions yourself. To do that you need to gain the skills of doing proof yourself!
In what follows I provide answers obtained from AI models and highlight as bold parts which are wrong assumptions or reasoning.
Solution by ChatGPT:
Key Observations:
There are 10 people in total at the party (5 couples: Mr. and Mrs. Taylor and 4 other couples).
No one shakes hands with their own partner.
No one shakes hands with themselves or the same person more than once.
The handshake answers must be unique and range from 0 to 9 (since there are 10 people, including Mr. and Mrs. Taylor).
Solution:
Since there are 10 people total, the number of handshakes any one person could have ranges from 0 to 9.
If everyone gives a unique answer, it means:
One person shook hands with 0 people.
Another shook hands with 1 person.
Another with 2, and so on, up to 9.
Steps:
The person who shook hands with 9 people: This person shook hands with everyone else, meaning their partner (who doesn’t shake hands with them) must have shaken hands with 0 people.
The person who shook hands with 8 people: This person shook hands with everyone except their partner and the person who shook hands with 0.
By continuing this pattern, we see that for every unique count of handshakes k, the person with k handshakes corresponds to a partner with 9−k handshakes.
Mrs. Taylor’s Handshakes:
Mr. Taylor shouted “STOP” after collecting answers from all 10 people. Since there are 9 different handshake counts, one of those counts must belong to Mrs. Taylor.
Let’s assume Mr. Taylor is among the group and is the one with the maximum or minimum handshakes.
The pairing pattern ensures Mrs. Taylor’s number of handshakes must fall within the range, but based on symmetry of couples logic !
The key is to match couples symmetrically:
If Mr. Taylor gets answers (0, 1, 2,…
Let’s refine the solution:
The possible handshake counts are 0,1,2,…,9, ensuring each number is unique.
The pairing works such that if one person shakes k hands, their partner shakes 9-k hands.
This logic means:
The person who shook 9 hands paired with the person who shook 0.
The person who shook 8 hands paired with the person who shook 1, and so on.
Mrs. Taylor’s Count:
If there are nine unique handshake counts (from 0 to 9), Mrs. Taylor must have shaken 4 hands because her partner, Mr. Taylor, who controls the setup, must fall at the midpoint to allow symmetrical pairing logic.
Solution by Gemini:
Certainly, let’s solve the handshake puzzle!
Understanding the Problem:
We have 10 people at the party (Mr. and Mrs. Taylor, plus 4 other couples).
No one shakes hands with themselves or their partner.
No one shakes hands with the same person more than once.
Each person keeps track of how many handshakes they’ve done.
Mr. Taylor asks everyone how many handshakes they’ve done, and gets 9 different answers.
We need to figure out how many handshakes Mrs. Taylor did.
Let’s Analyze:
The key to solving this is to consider the possible range of handshakes each person could have.
Lowest Possible Handshakes: If someone is the first to arrive and doesn’t shake hands with anyone else, they’ll have 0 handshakes.
Highest Possible Handshakes: The maximum number of handshakes depends on the order of arrivals and who shakes hands with whom. In the most efficient scenario, everyone could shake hands with everyone else except their partner. This would lead to a maximum of 8 handshakes for each person.
Now, let’s consider the 9 different answers:
Since there are 9 different answers, and the minimum is 0, the maximum number of handshakes someone could have is 8.
Let’s think about Mrs. Taylor:
She can’t have 0 handshakes because she would have to shake hands with someone eventually.
She can’t have 8 handshakes because Mr. Taylor would have to have the same number (since they are the only couple).
Therefore, Mrs. Taylor must have shaken hands with a number between 1 and 7.
Unfortunately, without more information about the order of arrivals and who shook hands with whom, we can’t pinpoint the exact number of handshakes Mrs. Taylor did.
Let me know if you’d like to explore a specific scenario with a particular order of arrivals and handshakes to determine Mrs. Taylor’s exact number!
Victorian, William Stanley Jevons was born in Liverpool in 1835. He was famous in his day as an economist and his smashhit book ‘The Coal Question’ drew the nation’s attention to the reduction in Britain’s coal supplies. He was the first economist to raise the issue of the ecological impact of economics.Jevons had other strings to his bow though and one of the strangest for the time if also incredibly forward thinking was his 1869 “logic piano”: a device that looked a little like a piano but that “played” logic.
Jevons was fascinated with logic and reasoning. He believed you could start with one thing (a premise) and from this work through a chain of reasoning to the conclusion. He thought that this could be done for everything. This was based on a principle he espoused of “the substitution of similars”: essentially reasoning based on the idea that “Whatever is true of a thing is true of its like”, For example, If Pharaohs are gods and Rameses is a Pharaoh (so is one of the things “like” a Pharaoh) then you can conclude Rameses is a god. He built on, and combined the ideas of, the Ancient Greeks with the then new ideas of George Boole, that we now call Boolean logic.
Boolean logic is based on a system of algebra using only the values of true and false (or 1 and 0), with operations corresponding to logical operations such as AND and OR that turn true/false values into new true/false values. This is the logic upon which computers are founded. A key idea was that you can abstract away from actual statements about truth in the real world and just replace them with variables that can stand for anything. Boole had laboriously shown using his logic how new abstract facts could be deduced from existing ones. Jevons realised that when reasoning was thought of like this, it became a mechanical process…and that meant a machine could do it.
His contemporary, Charles Babbage had been working on the idea of building mechanical “computers” but Babbage’s fundamental idea was that machines could do calculation. Jevon’s idea was slightly different and more fundamental: that machines could do logical reasoning, deducing new facts from existing ones. This was an idea that eventually came to fruition in the 20th century with the development of theorem provers where computers were programmed to do complex logical reasoning, even working on building up the whole of mathematics by proving ever more theorems from a few starting facts.
So, (with the help of an unknown craftsperson), Jevons set about designing and building his wooden Logic Piano. The idea was that you could put in the premises, the basic facts, by playing the keys of the “piano”. It would then mechanically apply his reasoning rules to discover all conclusions that could be deduced, altering its conclusion with each new fact added, The keys moved rods and levers that made logical facts appear on (or disappear from) the “display” of the machine – essentially facts on the rods appeared in slots cut into the back of the piano.
The kind of logical problem his machine worked with are Syllogisms (see Superhero Syllogisms). They were invented by the Ancient Greeks who were very good at logic. A syllogism is just a common pattern that combines facts where you figure out a conclusion only using the facts supplied, slotted into a template. For example, if we know facts 1 and 2 in the following template (where you can swap in anything for A, B and C) then we can create a new fact as shown.
Image by Paul Curzon
So let’s replace A with the word superheroes, B with fight crime and C with my favourite superhero, Ghost Girl. If we put them in to the template above we get a new “fact” deduced from two existing ones:
Image by Paul Curzon
Image by Paul Curzon
In the piano, a set of rods acted as truth tables, each one giving a true or false values for each variable. So imagine a piano that could deal with two variables A and B. Each of A and B can have two different values true and false, so there are four possibilities (so four rods):
(A, B);
(A, NOT B);
(NOT A, B);
(NOT A, NOT B)
where we write A to mean the assertion A is true and NOT A (or ~A in the picture) to mean A is false. Each rod represents a possible state of the world.
Let’s look at a simple example. Suppose A stands for the statement “Paul is a programmer” and B stands for “Safia is a programmer”, then the possibilities (if we know no specific facts) are
(Paul is a programmer, Safia is a programmer) : (A, B)
(Paul is a programmer, Safia is NOT a programmer) : (A, NOT B)
(Paul is NOT a programmer, Safia is a programmer) : (NOT A, B)
(Paul is NOT a programmer, Safia is NOT a programmer) : (NOT A, NOT B)
Image by Paul Curzon
Each rod in Jevon’s piano had one of the possibilities on, so each rod represented a possible state of the world being reasoned about. At the start all the rods were visible, showing that nothing specific was yet known.
The point is that these represent all possible states of the world about Paul and Safia and whether they are programmers or not. If we know nothing more then all we can say is that all the pairs of facts are a possibility: all are possible states of the world.
The piano worked by essentially leaving displayed or hiding each rod’s state as new facts were keyed in. (See the video at the end which includes a detailed explanation by expert David E Dunning on the detail of how it did this step by step). Initially all the possibilities are displayed as above. If we add a new fact that we have discovered or wish to assume, say that “Safia IS a programmer” (in terms of the piano, press the B key corresponding to the fact B is true), then doing so removes all states of the world where Safia is NOT a programmer. The piano, therefore, hides all the rods that include the assertion representing “Safia is NOT a programmer” (all those with (NOT B) on them) . We are left with two alternatives:
Image by Paul Curzon
(Paul is a programmer, Safia is a programmer) : (A, B)
(Paul is NOT a programmer, Safia is a programmer) : (NOT A, B)
The mechanics of the machine meant that those facts would remain a possibilities (reading down the rods) but pushing the keys for that assertion would have moved the other rods, so hide their state. In doing so, the piano has deduced from the fact B that the possible conclusions are A AND B is true or NOT A AND B is true.
With three variables instead of two the machine would be able to deal with more complex situations – there are then 8 possibilities so 8 rods representing the 8 different states. .
Image by Paul Curzon
Let A represent superheroes, (so NOT A represents those people who are not superheroes), B represents those people who fight crime and C with a person being Ghost Girl. Suppose we are considering some, at the moment, random person we know nothing about. The possibilities about them are:
(Is a superhero, does fight crime, is Ghost Girl) : (A, B, C)
(Is a superhero, does fight crime, is NOT Ghost Girl) : (A, B, NOT C)
(Is a superhero, does NOT fights crime, is Ghost Girl) : (A, NOT B, C)
(Is a superhero, does NOT fight crime, is NOT Ghost Girl) : (A, NOT B, NOT C)
(Is NOT a superhero, does fight crime, is Ghost Girl) : (NOT A, B, C)
(Is NOT a superhero, does fight crime, is NOT Ghost Girl) : (NOT A, B, NOT C)
(Is NOT a superhero, does NOT fights crime, is Ghost Girl) : (NOT A, NOT B, C)
(Is NOT a superhero, does NOT fight crime, is NOT Ghost Girl) : (NOT A, NOT B, NOT C)
If we put the fact about them into the piano that ALL superheroes fight crime (ALL A are B) then we remove all rods where A is true but B is different so false (a superhero who doesn’t fight crime) as in this world, that is impossible.
Image by Paul Curzon
(Is a superhero, does fight crime, is Ghost Girl) : (A, B, C)
(Is a superhero, does fight crime, is NOT Ghost Girl) : (A, B, NOT C)
(Is NOT a superhero, does fight crime, is Ghost Girl) : (NOT A, B, C)
(Is NOT a superhero, does fight crime, is NOT Ghost Girl) : (NOT A, B, NOT C)
(Is NOT a superhero, does NOT fights crime, is Ghost Girl) : (NOT A, NOT B, C)
(Is NOT a superhero, does NOT fight crime, is NOT Ghost Girl) : (NOT A, NOT B, NOT C)
Then we add the fact that Ghost Girl is a superhero (C is a A) so remove all those rods where Ghost Girl is not a superhero (ie NOT A, C):
Image by Paul Curzon
(Is a superhero, does fight crime, is Ghost Girl) : (A, B, C)
(Is a superhero, does fight crime, is NOT Ghost Girl) : (A, B, NOT C)
(Is NOT a superhero, does fight crime, is NOT Ghost Girl) : (NOT A, B, NOT C)
(Is NOT a superhero, does NOT fight crime, is NOT Ghost Girl) : (NOT A, NOT B, NOT C)
We have deduced (the first possible state) that if the person we are interested in is Ghost girl then she is a superhero. We are also left with other possibilities too. If the person we are considering is not actually Ghost Girl then they may or may not fight crime and may or may not be a superhero!
If we add in an additional fact that the person we are thinking of IS actually Ghost Girl then we remove those extra rods so possibilities and get
Image by Paul Curzon
(Is a superhero, does fight crime, is Ghost Girl) : (A, B, C)
Ghost Girl is a superhero who does fight crime! We knew she was Ghost Girl and was a superhero but using the piano we have now deduced that she does fight crime. The machine has deduced the syllogism we gave at the start.
IF ALL superheroes fight crime AND
Ghost girl is a superhero
THEN
Ghost girl fights crime.
The actual piano dealt with 4 variables (A, B, C, D) so had 16 rods representing the 16 different combinations. It also included keys to indicate the end of a conjecture, a key for IS A, and more to allow specific assertions to be input. The mechanism then hid rods automatically based on the facts entered. To use it, you did as we did: create a table of what A, B, C and D stand for (this is done outside the machine), enter the facts you want to reason about, and it then displayed all the possible states that remained in terms of A, B, C and D. Then, by seeing what each of the variables stood for in the table, you could convert that answer back into a deduced fact about the real world that you were interested in.
Amazingly, (after a first failed attempt) it did work. It is similar in idea to modern day theorem provers which are used to verify properties of safety-critical computer designs that must npot have bugs. Of course, being small and woody, the logic piano couldn’t solve every thing but then it turns out that was always an impossible dream. Even modern computers (and human mathematicians) have fundamental limits in what they can do (which is another story). The logic piano was a rather amazing, if woody, start to the area of automated theorem proving, though.
– Paul Curzon, Queen Mary University of London
Make a paper logic piano
Here is a kit to make a paper or card logic piano of your own (actually more like Jonons’ logic abacus the piano was a mechanised version of):
A Talk by David E Dunning at the Imagining AI conference about William Stanley Jevons and the logic piano including at the end a more detailed explanation of how pressing keys actually caused rods to by hidden in a series of steps. See also his article about it for the Computer History Museum.
Superheroes don’t just have physical powers. Often theycome out on top because of their mental abilities. Sherlockis a good example, catching villains through logicalthinking. Anyone can get better at thinking! Just practice.
It is important for everyone to be able to think clearly. It is especially true for programmers, detectives and lawyers as well as superheroes. You need to be able to work things out from the facts you know. The Ancient Greeks were very good at logic. They invented the idea of a ‘syllogism’. These are common patterns that combine facts where you figure out a conclusion only using the facts.
For example, if we know facts 1 and 2 below (where you can swap in anything for X, Y and Z) then we can create a new fact as shown.
Image by Paul Curzon
So let’s replace X with the word superheroes, Y with fight crime and Z with my favourite superhero, Ghost Girl. If we put them in to the picture above we get the new picture:
Image by Paul Curzon
In this case we can deduce the new fact that Ghost Girl fights crime. Notice how you use the plurals in Fact 1 and singular words in the other facts to make the English work.
Puzzles
Can you solve these Superhero Syllogism puzzles? Work out which conclusion is the one that follows from the given facts. Use our coloured template above to help.
Superhero syllogism puzzle 1
FACT 1: ALL superheroes do good. FACT 2: The Invisible Woman is a superhero.
Which statement below (a, b, c or d) can we say from these facts alone? Don’t use anything extra, just use fact 1 and fact 2. (ANSWERS at the bottom of the page).
a) The Invisible Woman has superpowers. b) The Invisible Woman does good. c) The Invisible Man does good. d) The Invisible Woman does not do good
Superhero syllogism puzzle 2
FACT 1: ALL superheroes sometimes accidentally do harm. FACT 2: Jamila is a superhero.
What can we say from these facts alone?
a) Jamila sometimes accidentally does harm. b) Jamila is not a superhero c) Those with superpowers only do good. d) Jamie is a superhero
Superhero syllogism puzzle 3
FACT 1: ALL supervillains laugh in an evil way. FACT 2: The Spider is a supervillain.
What can we say from these facts alone?
a) The Spider sometimes accidentally does harm. b) The Spider does not laugh in an evil way. c) Supervillains are evil. d) The Spider laughs in an evil way.
As long as the facts are true the conclusion follows, though if the facts are not true then nothing is really known.
Superhero syllogism puzzle 4
The following logic is good but something has gone wrong because the conclusion is not true. The superhero called the Angel does not actually have any superpowers! The Angel just wears a flying suit! Can you work out what has gone wrong with our logic?
1. ALL superheroes have superpowers. 2. The Angel is a superhero.
Therefore we can conclude from these facts alone that
3.The Angel has superpowers.
Answers are at the bottom of the page.
Fun to do
Take the pattern of the above syllogisms and invent your own. Just substitute your own words, but keep the pattern.See how silly the “facts” you can deduce are.
– Paul Curzon, Queen Mary University of London, first appeared in A BIT of CS4FN 2
Learn the basics of computer science through magic tricks
Subscribe to be notified whenever we publish a new post to the CS4FN blog.
This page is funded by EPSRC on research agreement EP/W033615/1.
Answers
Superhero syllogism puzzle 1
Answer: b. FACT 1: ALL superheroes … do good. FACT 2: The Invisible Woman is a superhero Therefore we can conclude from these facts alone that NEW FACT: The Invisible Woman … does good.
Superhero syllogism puzzle 2
Answer: a. FACT 1: ALL superheroes … sometimes accidentally do harm. FACT 2: Jamila is a superhero Therefore we can conclude from these facts alone that NEW FACT: Jamila … sometimes accidentally does harm.
Superhero syllogism puzzle 3
Answer: d. FACT 1: ALL supervillains … laugh in an evil way. FACT 2: The Spider is a supervillain. Therefore we can conclude from these facts alone that NEW FACT: The Spider … laughs in an evil way.
Superhero syllogism puzzle 4
Something has gone wrong. We are told that The Angel has no superpowers. They just wear a special flying suit. The new fact is therefore not true. This means that one of the original ‘facts’ was not actually true. If we start from things that are not true then the things we deduce will not be true either! In this case
Image by Samson Vlad from Pixabay modified by CS4FN
One way computers store images is as a set of points (as coordinates) that make up lines and shapes. This is the basis for the kind of computer graphics called Vector Graphics. You can explore the idea by doing coordinate conundrum puzzles. A coordinate conundrum is just a Vector Graphics Image to be drawn on paper.They are join-the-dot puzzles based on the idea. Can you recreate the original drawing?
Recreate a drawing from coordinates
Points on a grid can be represented by pairs of numbers called coordinates. The first, x coordinate, says how far to go along horizontally. The second, y coordinate, says how far to go up, vertically. The numbers along the axes (along the bottom and up the side) of the grid give the distance in that direction. Draw the point at the place you end up at! So for example the coordinate (4,5) means go right from the origin 4 and up 5 and plot the point there.
Image by CS4FN
You can join any two coordinates with lines. If a series of lines join back to the original one then it make a shape (a polygon), which can be coloured in. For example, if we plot the points (4,5), (7,7 and (8,4) drawing lines between them and back to (4,5) we make a triangle.
Image by CS4FN
From 4 points we could define a square, rectangle or more general quadrilateral shape and so on.
So from a set of instructions telling you where to plot points, you can create a picture out of all the shapes and lines that make up the picture, giving colours for the lines or shapes.
This (and so these puzzles) is the basis of how programs in the language SVG (Scalable Vector Graphics) work to store a drawing as the instructions needed to recreate it. Drawing programs often store illustrations that the artists using them draw as an SVG program.
How to solve them
Each picture is made of shapes, each given by a colour and a list of the coordinates of its vertices (corners). For each shape:
1. Plot the list of (x,y) coordinates on the grid as dots.
2. Join the dots (which start and end at the same place) to make the shape.
3. Colour the shape you have made with the colour at the start of the list.
So, for example, if the first instruction starts: red (5,24) … that means plot the point 5 along and 24 up. It starts a new shape, coloured red, that ends at the same point.
If the series of points do not join back to the start then they represent coloured lines rather than a coloured shape,
Example: Semaphore flag
Image by CS4FN
Here is a simple example to draw a red and yellow semaphore flag, given the shapes:
red (0,10) (10,10) (10,0) and back to (0,10)
yellow (0,10) (10,0) (0,0) and back to (0,10)
From this we can draw the picture.
Image by CS4FN
First we plot the points given for the red shape (a triangle), join the dots and colour it in.
red (0,10) (10,10) (10,0) and back to (0,10)
Image by CS4FN
Then we plot the points given for the yellow shape (another triangle), join the dots and colour it in.
yellow (0,10) (10,0) (0,0) and back to (0,10)
Do some puzzles yourself
Try the coordinate conundrum puzzles on our puzzle page either by printing off the puzzle sheet or drawing on squared paper. Then read on to find out a little more the advantages of vector graphics.
From straight lines to curves
In these puzzles we have only used straight lines between points, but we could also include commands to create circles and curved lines between points based on the mathematical equation for the curve. SVG, the vector graphic programming language, has instructions for a variety of more complex kinds of lines and shapes like that.
Advantages and disadvantages of Vector Graphics
Recording images in this way as points, lines and shapes has several advantages over storing images as pixels:
we generally need far less space to store the image as we do not need to store a colour for thousands or even millions of pixels;
the images are mathematically accurate – a line is represented as a perfect straight line not a pixelated (staircase-like) line;
the images are scalable, meaning you can increase the size of an image, zooming in just by multiplying all the numbers involved by a scale factor (which is just a number giving the magnification you want). The resulting image is still mathematically perfect with straight lines still straight lines, for example, just bigger. For example, suppose we want to make a semaphore flag twice the size of our original. We just multiply all points by 2, for example giving red (0,20) (20,20) (20,0) and back to (0,20); yellow (0,20) (20,0) (0,0) and back to (0,20) and it gives an identical picture, just bigger. (Try plotting it and see!)
Disadvantages are:
Vector graphics are not a good way to represent photographs – digital cameras record the light at lots of points corresponding to pixels so naturally are stored as pixels (numbers that give the colour in that small square of the image). Trying to convert a photo to a vector image would be hard (needing algorithms to recognise shapes, for example). It would be a less natural and less accurate way of doing so.
With computer memory cheap, the advantages of using less storage are less important than they once were.
SVG: a graphics programming language
The programming language SVG records drawings in this way as instructions to draw shapes and lines based on points. It has some difference to our instructions though. For example the y-axis coordinates start at the top and work down. The principles are the same though, it is only the detail that differs.
One way to use logical thinking is to deduce new facts but then turn them into IF-THEN rules. They tell us an action to do IF something is true. For example: IF both cards are the same THEN shout SNAP! Once we have IF-THEN rules we can use them as the basis of a program. We can see how this works, and how it involves various computational thinking skills with a simple logical thinking puzzle.
An Egyptian Survey puzzle
Image by CS4FN
Old records show that this area of the desert contains the tombs of 3 scribes (a large tomb covering 3 squares), 1 artisan (medium, 2 squares) and 1 merchant (small, 1 square).
A survey has gathered information of where the tombs could be. Each number tells you how many squares are part of a tomb in that row or column.
Tombs are not adjacent (horizontally, vertically or diagonally).
Can you work out where all the tombs are without further digging?
Solving Egyptian Survey puzzles
The instructions of the puzzle give us some simple facts such as that the number at the end of the row tells us the number of squares in that row holding tombs. On its own that does not tell us how to solve the puzzle. However, thinking logically about it we can draw simple logical conclusions so deduce new facts. For example, it is fairly simple to deduce the fact:
the number for a row being 0 IMPLIES there are no tombs in that row.
If we know there are no tombs in a row then we can mark each square of the row as empty. If we use X to mean nothing is in that square, then we can turn that deduced fact into an action. It means that we can do the following when trying to solve the puzzle:
IF the number on a row is 0
THEN put an X in all the squares of that row.
With that rule we can start to solve the puzzle just by following the rule. Find a row numbered 0 and put Xs there. We can create a similar rule for columns. Applying both these rules to our puzzle we get:
Image by CS4FN
Can you work out more rules before reading on?
Rules, rules, rules
What happens if the number of a row is more than 0? Knowing the number alone doesn’t help us much. We need to combine it with other information. The top row of the puzzle has the number 4, for example, but one of the squares already has a cross in it. That means the remaining 4 squares all must have tombs, which we will mark T. We can turn that into a rule:
IF the number for a row is 4 AND there are 4 empty squares in that row and an X THEN put a T in all the empty squares of that row.
We can make similar rules for each number 1 to 4. We can then create similar rules for columns. Applying them once each to our puzzle gives us:
Image by CS4FN
We could also make a more general version of this rule
IF the number for a row is <n> AND there are only <n> empty squares in that row THEN put a T in all the empty squares of that row.
This is what computer scientists call generalisation: a part of computational thinking. Instead of having lots of rules (or lines of code) for lots of similar situations, we create one simple but general one that covers all the cases. We can of course apply rules more than once, so as you probably noticed we can apply our row rule once more. In effect our rules live inside a loop and we keep trying them in sequence for as long as we find a rule that makes a difference.
Image by CS4FN
Now one of the rows has the number 1, but we have already marked a tomb in a square of that row. That gives us another rule.
IF the number for a row is 1 AND there is already 1 tomb marked in that row THEN put an X in all the empty squares of that row.
This gives us:
Image by CS4FN
Similar rules apply for other numbers so we could also make a general version of this rule too.
IF the number for a row is <n> AND there are already <n> tombs marked in that row THEN put an X in all the empty squares of that row.
Now, applying a column version of the last general rule and we can mark an X in the last square for column with 2 tomb squares.
Image by CS4FN
We need one last rule for this puzzle:
IF the number for a row is <n> AND the number of spaces + the number of 0s is <n> THEN put a T in all the empty squares of that row.
This is actually an even more general version of our second rule (it is the case where the number of Ts is 0, so could replace that rule with this new one.
Applying it finally solves the puzzle:
Image by CS4FN
If we put our rules together then they become the basis of an algorithm (so program) for solving the puzzles and in creating them from deduced facts we are doing algorithmic thinking. IF-THEN instructions along with sequencing and loops are the basis of all programs. Here we create a sequence of the rules to try in order and put them inside a loop so that we keep trying them until none apply or we have solved the puzzle. There is a style of programming where all a program is is a series of IF-THEN rules – with looping happening implicitly.
Algorithms are just rules to follow that guarantee a result (here solving the puzzle). It is only an algorithm if it guarantees to always work. To solve any (solvable) Egyptian Survey puzzle like this we would need yet more rules: we would need more more rules for it to be an algorithm for solving all puzzles. Making sure algorithms cover all possibilities is one of the harder parts of algorithmic thinking – bugs in programs are often there because the programmer didn’t manage to cover every possibility. In our case we could write a program based on our limited rules. We would just need to include an extra rule that quits (admitting defeat and saying that the program cannot solve the puzzle) if no rule applies.
Perhaps you can work out all the rules (so an algorithm) needed to solve any of these puzzles! All you need are the instructions for the game, some logical thinking to deduce new facts, some algorithmic thinking to turn them into rules, and an ability to generalise so you have a small number of rules … computational thinking skills in fact.
cs4fn 