CS Unplugged activity
Treasure Island
Your goal is to find Treasure Island. Pirate ships sail fixed routes between islands, and every island has two ships leaving it, ship A and ship B. At each island you choose one ship, and it carries you straight to the next island on your route.
Here’s a route already worked out for you, starting at Pirates’ Island: B, B, B, A, B, A, B.
| Ship | You land on… |
|---|---|
| Start | Pirates' Island |
| B | Musket Hill |
| B | Mutineers' Island |
| B | Dead Man's Island |
| A | Musket Hill |
| B | Mutineers' Island |
| A | Smugglers' Cove |
| B | Treasure Island! |
Now you try it:
- Always start at Pirates’ Island.
- Follow the letters below one at a time, moving to the next island each time.
- Write down the name of the island where you land.
- For the last two questions, trace routes with your finger before you write.
Route A, A: where do you land?
Route B, B, A: where do you land?
Route A, A, A: where do you land?
Find your own route from Pirates’ Island to Treasure Island. Write the letters you used:
Now find the shortest route you can. How many letters long is it?
Look at Musket Hill on the map. Once you land there, follow ship B, then ship A, then ship B. Where do you end up?
Make your own map
Can you hide your buried treasure well? How hard can you make it to find the treasure? It’s time to make your own map!
Draw your own basic plan like this, so you can clearly see the routes your pirate ships will travel. Draw at least five islands, and give every island (except your Treasure Island) two ships leaving it: A and B. What is the most efficient sequence of routes to reach your Treasure Island?
Shortest route to my Treasure Island:
How well can a friend follow your map? Give them a sequence of As and Bs, and see if they land on the correct island. You can make up a variety of games and puzzles based on this idea of finite-state automata.
What’s it all about?
Finite-state automata are used in computer science to help a computer process a sequence of characters or events.
A simple example is when you dial up a telephone number and you get a message that says “Press 1 for this… Press 2 for that… Press 3 to talk to a human operator.” Your key presses are inputs for a finite-state automaton at the other end of the phone. The dialogue can be quite simple, or very complex. Sometimes you are taken round in circles because there is a peculiar loop in the finite-state automaton. If this occurs, it is an error in the design of the system—and it can be extremely frustrating for the caller!
Although computers are not really very good at understanding natural language, they can readily process artificial languages. One important type of artificial language is the programming language. Computers use finite-state automata to read in programs and translate them into the form of elementary computer instructions, which can then be “executed” directly by the computer.
Learn more: finite-state machines.
Answer key
-
Route A, A ends at Musket Hill.
-
Route B, B, A ends at Smugglers’ Cove.
-
Route A, A, A ends at Pirates’ Island (a loop back to the start).
Shortest route. B, B, A, B: just 4 letters. Any route to Treasure Island has to pass through Musket Hill, then Mutineers’ Island, then Smugglers’ Cove, so nothing shorter is possible.
Musket Hill. B, then A, then B from Musket Hill always finishes at Treasure Island (Musket Hill → Mutineers’ Island → Smugglers’ Cove → Treasure Island). That’s the last three letters of the shortest route above. The first letter just gets you from Pirates’ Island to Musket Hill.
Challenge. One route that visits Dead Man’s Island twice: A, B, B, B, A, B, A, B (Pirates’ Island → Shipwreck Bay → Dead Man’s Island → Shipwreck Bay → Dead Man’s Island → Musket Hill → Mutineers’ Island → Smugglers’ Cove → Treasure Island). There are other routes that work too.
Your own map. There’s no single answer here. Trade maps with a partner and check each other’s shortest route by tracing it together.
Version history
- Loading commit history…