Week 1

Overview

Objectives

By the end of this week, you should be able to:

Readings & Resources

Activities & Assignments

  1. Introduce Yourself
  2. Discussion - Design your own Algorithm
  3. Maze Solving
  4. Thought Problem: “How high can you count on five fingers?”
  5. Install PyCharm

Lesson

Algorithms

Algorithm for a Maze

Maze Solution #1 - The Random Approach

Random Walk Algorithm

  1. Move forward until there is either a left or right turn or a dead end
  2. If there is a left or right rurn, choose a random direction
  3. If you are at a dead end turn around

Problem: Can take a very long time

Maze Solution #2 - Follow the right wall

Follow Right Wall Algorithm

  1. Go in a straight line until you encounter a junction or a dead-end
  2. At a junction, always go to rightmost option from where you are currently facing
  3. At a dead-end, turn around 180 degrees

Problem: May get stuck in some mazes, or Islands - correctness

Maze Solution #3 - Tremauz’s Algorithm

Tremaux’s Algorithm

  1. As you walk down the maze, draw a line on the path
  2. At a dead end, turn around and walk back the way you came
  3. At a junction you’ve not seen before, take any new path
  4. At junction you have been to before:
    1. If you are on a new path, turn back the way you came
    2. If you are on a path you’ve marked before, take a new path if you can
  5. Never go down a path already marked with two lines
  6. When your path reaches a junction, you choose an exit

Homework

Maze Solving Game

  1. Solved solution: Link
moveForward();
moveForward();
  1. Solved solution: Link
moveForward();
turnLeft();
moveForward();
turnRight();
moveForward();
  1. Solved solution: Link
while (notDone()) {
  moveForward();
}
  1. Solved solution: Link
while (notDone()) {
  moveForward();
  turnLeft();
  moveForward();
  turnRight();
}
  1. Solved solution: Link
moveForward();
moveForward();
turnLeft();
while (notDone()) {
  moveForward();
}
  1. Solved solution: Link
while (notDone()) {
  if (isPathLeft()) {
    turnLeft();
  }
  moveForward();
}
  1. Solved solution: Link
while (notDone()) {
  if (isPathForward()) {
    moveForward();
  }
  if (isPathRight()) {
    turnRight();
  }
}
  1. Solved solution: Link
while (notDone()) {
  if (isPathLeft()) {
    turnLeft();
  }
  if (isPathRight()) {
    turnRight();
  }
  moveForward();
}
  1. Solved solution: Link
while (notDone()) {
  if (isPathForward()) {
    moveForward();
  } else {
    if (isPathLeft()) {
      turnLeft();
    } else {
      turnRight();
    }
  }
}
  1. Solved solution: Link
while (notDone()) {
  if (isPathForward()) {
    if (isPathRight()) {
      turnRight();
    } else {
      if (isPathLeft()) {
        turnLeft();
      }
    }
  } else {
    if (isPathLeft()) {
      turnLeft();
    } else {
      turnRight();
    }
  }
  moveForward();
}