Swift Playground Part 7: Algorithms   

In this section we look at algorithms. What is an algorithm? An algorithm is just a fancy name for a set of instructions on how to do something. For example, tying your shoe can be thought of as an algorithm.

The right hand rule

A popular algorithm when solving a maze is called the right hand rule. This is where you follow a wall while touching it.

The sample code provided gives a big clue on how to solve this puzzle. You want to make sure you that if there is a wall on your right, in other words you are blocked on your right, you continue to move forward.

Also, you need to work out what the end condition is for the code to stop. Hint, see the example code. If you still get stuck, check out the answers below or watch the video.

The right hand rule - Solution
func navigateAroundWall() {
    if isBlockedRight {
        moveForward()
    }  else {
        turnRight()
        moveForward()
    }
}
while !isOnClosedSwitch {
        navigateAroundWall()
    if isOnGem {
        collectGem()
        turnLeft()
        turnLeft()
    }
}
toggleSwitch()

Adjusting your algorithm

This puzzle is very similar to the previous one but a few adjustments need to be made. Try running the code for the right hand rule and note where it starts to go wrong.

You will have to add a condition to turn left. You could also add a condition to turn right or just turn right in the else statement at the end of the if condition. The rest of the code will be exactly the same.

Adjusting your algorithm - Solution
func navigateAroundWall() {
if isBlockedRight && isBlocked{
turnLeft()
} else if isBlockedRight{
moveForward()
} else {
turnRight()
moveForward()
}
}

while !isOnClosedSwitch {
navigateAroundWall()
if isOnGem {
collectGem()
turnLeft()
turnLeft()
}
}
toggleSwitch()

Conquering a maze

This next challenge looks tricky but when we break it down, it is not too bad at all. The first thing to do is to find your end condition which is the gem at the very end. We want to say, keep walking through the maze until we are on a gem.

Now all we have to do is figure out when we should walk forward, turn left or turn right. Start with the right hand rule which means keep walking forward if you are blocked on the right. Then add in conditions for when to turn left or right. If you get stuck, check out the answers below.

Conquering a maze - Solution
while !isOnGem {
if isBlockedRight && isBlocked {
turnLeft()
} else if isBlockedRight {
moveForward()
} else {
turnRight()
moveForward()
}
}
collectGem()

Which way to turn?

To solve this puzzle, first try and figure out the code or “algorithm” get to the gem at the end. Once you have done this you can then go back and put in the code to toggle the switch.

Again it is just starting with the right hand rule and then putting in conditions to turn left or right. The new part is to put the code in to test if you are on a switch or not and that should be easy.

However, a better way to solve this though is to notice that every time you are on a switch, you want to turn either left or right. So you could keep walking forward until you reach a switch, toggle it, and then turn. How do you know whether to turn left or right?

This highlights that there can be multiple algorithms to solve a particular problem but some algorithms are better than others.

Which way to turn - Solution 1
while !isOnGem {
if isOnClosedSwitch {
toggleSwitch()
}
if isBlocked {
turnLeft()
} else if isBlockedRight {
moveForward()
} else {
turnRight()
moveForward()
}
}
collectGem()
Which way to turn - Better solution
while !isOnGem {
    moveForward()
    if isOnClosedSwitch {
        toggleSwitch()
        if isBlocked {
            turnLeft()
        } else {
            turnRight()
        }
    }
}
collectGem()

Roll right, roll left

The last challenge in this section needs a bit of thinking and planning. There are several patterns you should be able to see here but remember to first identify what the end condition is, try to navigate there first. Notice how you should move forward whenever you are blocked on the right OR on the left? Notice how the gems and switches are all in a similar position?

Have a go and if you get stuck, check out the solutions or the video below. Good luck!

Roll right, roll left - Solution
moveForward()
turnRight()

while !isOnOpenSwitch {
    if isOnGem {
        collectGem()
    }
    if isBlocked && isBlockedLeft {
        turnRight()
    } else if isBlocked {
        turnLeft()
    } else if isBlockedRight || isBlockedLeft {
        moveForward()
    } 
    
    if isOnClosedSwitch {
        toggleSwitch()
        turnLeft()
        moveForward()
        toggleSwitch()
        moveForward()
    }
}

See all solutions in the video below

Leave a Reply

Your email address will not be published. Required fields are marked *