Map to Treasure Island WIP

Meta Description


Treasure Island is within reach. With group effort and the help of FSA, the map to the island can be built and the treasure will be yours to conquer!

Learning Objectives


To learn how to read and understand maps.
To understand and be able to follow instructions.
To understand the underlying concept of Finite State Automata.

Key Terms


Map
A diagram displaying locations and links.

Link
A line on the map that connects one location to the next.

Step 1
Construct the “Main Map” on an A4 paper. This should include 7 islands, including a starting island (where the activity should start) and the finishing island, Treasure Island. Each island should have 2 outward “bridges”: A and B, each connecting to a different island. This map should not be shared with the participants.

Step 2
Prepare the “Blank Maps” on the A4 papers. The “Blank Maps” must include the 7 islands of the “Main Map”, but no bridges. The starting island and Treasure Island should be clearly labelled.

Step 3
Prepare the “Island Cards” on the A5 papers. Each card should represent one of the islands, including its 2 outward bridges: A and B as highlighted in the “Main Map”.

Step 4
Position 7 children such that they each represent one of the islands. The children should be well spaced out. Give the respective “Island Card” to each of these children. Give the “Blank Maps” to the rest of the children.

Step 5
One by one, send each child with the “Blank Map” to the starting island. Ask each child to choose bridge A or bridge B. Guide the children to mark the chosen bridge on their map and walk to the island they are indicated to depending on their choice.

Step 6
Keep guiding children with “Blank Maps” to travel to different islands, marking the routes as they travel, depending on their choices. Repeat this step until they arrive at the finishing point – Treasure Island.

The number of islands and the number of routes can be increased or decreased accordingly, depending on the difficulty the supervisor wants the challenge to be and the available time.

Help keep our environment clean by reducing waste, reusing materials, and recycling whenever possible!


Have you ever heard of Treasure Island? Yes, the very famous island where a priceless treasure is hidden. We have a map to the island, but unfortunately it is incomplete – the map does not display the bridges between the islands and therefore we do not know the route. This makes it difficult for us to travel through in a safe way.

The map shows seven islands. The good news is that there are people living on each island who may help us find the right route. We also know that there are two outbound bridges on each island, each leading to another different island – bridge A and bridge B. The natives can show us the way to one bridge at a time.

Therefore, we shall travel to the first island, ask the natives about one of the bridges on the island and go to the island it is connected to. As we go from island to island, bridge by bridge, we will complete the map with the route we take until we arrive at Treasure Island.

Let us see who manages to discover the shortest route to Treasure Island.


What do the 7 children in the middle of the field represent ?

They represent the different islands displayed on the map.


Why do we have to start from the same island ?

TSo that the activity will be fair for everyone..


Why do the children have to go one at a time ?

So that nobody gets to hear the answers given to other children.

Isn’t it obvious that the child who goes through the activity first, gets to treasure island first and wins ?
The aim is not to get to Treasure Island first but to successfully construct a route from the starting point to Treasure Island.


How is this related to computer science ?

Loads of stuff, including speech recognition!

Each time the children travel from one island to another, they are choosing between two bridges or routes: A or B. When they finally reach Treasure Island, they each would have constructed a path of As and Bs that ultimately make up a valid route.

This is the basic concept underlying Finite State Automata (FSA). FSA are a method used to recognize patterns and decide whether the pattern is a valid one or not.

FSA are made up of a number of states. One of the states is the start state, and one or more of the states are final states, also referred to as “Accept states”. The remaining states are “Reject States”. To change from one state to another a transition must occur. A transition occurs when one of the accepted symbols (referred to as the alphabet) are inputted which makes the automaton either move to the next state or stay in the same state. When the FSA is given a sequence of symbols that makes it reach a final state, then the sequence is accepted.

Compare this definition to the Treasure Island map: the 7 islands represent states of an automaton. One of the states (islands) is the starting state and Treasure Island is the final state. A transition from one state to another occurs when the children choose bridge A or bridge B. A and B are the acceptable symbols, or alphabet, within our FSA. When the children land on one of the intermediary islands, the sequence of choices they make is considered invalid, since they would have not arrived at the ultimate destination. However, when they finally land on Treasure Island (the final state), the sequence of As and Bs traversed is considered an acceptable route for the activity and therefore an acceptable sequence.
https://www.javatpoint.com/finite-automata
https://classic.csunplugged.org/finite-state-automata/

A finite state automaton is mathematically represented by the following tuple:
(Q, Σ, δ, q0, F)
where,
Q is the set of all states.
Σ is the Alphabet, i.e. all possible symbols for an input.
δ is the Transition Function, i.e. the rules which specify the next state by mapping Q and Σ.
q0 is the initial state. q0 ∈ Q
F is the set of accepting states. F ⊆ Q

The treasure island map can be represented as an FDA as follows:
Q = {q0, “island 1”, “island 2”, “island 3”, “island 4”, “island 5”, “treasure island”}
Σ = {“A”, “B”} given that each island has a Bridge A and a Bridge B.
q0 = “Starting island”
F = {“Treasure island”}

The transition function, in this case, would list each island and maps where each of its 2 outward bridges links to. For example, consider the following possible extract from the map:

The diagram shows that Bridge A from “Starting island” links to “island 1” and Bridge B links to “island 3”. The transition function for the above would informally look as follows:

The complete transition function would list all the islands and the possible transitions given A or B. Note that, diagrammatically, given that “Treasure island” is an Accepting State, it would be denoted with a double-bordered circle, like so:

As can be noted, FDA are tools which represent all the possible states of a machine or process and how such states can change until the machine is in an acceptable (complete) state.
https://xplaind.com/674699/finite-automaton
https://www.eecs.wsu.edu/~ananth/CptS317/Lectures/FiniteAutomata.pdf

Applications


Finite State Automata (FSA) are the basis of many applications including vending machines, traffic lights and spell checkers amongst others. They are also used in Natural Language Processing and Speech Recognition.
https://web.cs.ucdavis.edu/~rogaway/classes/120/spring13/eric-applications.pdf

Research

Experiments are being conducted to test the powers of the quantum version of automaton. One such experiment demonstrates an optical quantum automaton, which is used to solve the problems of determining whether the length of an input string can be divided by a prime number P with no remainder or with a remainder of R.

https://www.nature.com/articles/s41534-019-0163-x

Ask the students to try to find the slowest route.

Download as PDF

Education

Time Required

  • ~45 minutes

  • Preparation: 15 mins

  • Conducting: 15 mins

  • Clean Up: 1 min

Recommended Age

Number of People

Supervision

Location

Materials

A4 papers (Maps)
A5 papers (Island cards)
Pencils
Pens

Contributors


Sources


CS Unplugged -Finite State Automata

https://classic.csunplugged.org/finite-state-automata/

Finite Automata

https://www.javatpoint.com/finite-automata

https://xplaind.com/674699/finite-automaton

https://www.eecs.wsu.edu/~ananth/CptS317/Lectures/FiniteAutomata.pdf

Finite State Automata Application

http://web.cs.ucdavis.edu/~rogaway/classes/120/spring13/eric-applications.pdf

Experimental demonstration of quantum finite automaton

https://www.nature.com/articles/s41534-019-0163-x

Additional Content


Finite State Automata in Java (Beginner)

Cite this Experiment


de Marco, A., Vella, ., & Styles, C. (2020, April 30). Map to Treasure Island. Retrieved from http://steamexperiments.com/experiment/map-to-treasure-island/

First published: April 30, 2020
Last modified: April 30, 2020

0 0
[caldera_form id="CF59c90c0240779"]

Leave a Reply