theseus.html

<script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');

  ga('create', 'UA-101485962-1', 'auto');
  ga('send', 'pageview');

</script>
  
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0-alpha.6/css/bootstrap.min.css" integrity="sha384-rwoIResjU2yc3z8GV/NPeZWAv56rSmLldC3R/AZzGRnGxQQKnKkoFVhFQhNUwEyJ" crossorigin="anonymous">
<link rel="stylesheet" href="blog-style.css">

<h1>Theseus and The Minotaur</h1>

<div id="date">JANUARY 14, 2013</div>

<p>The point of the game is for you, the red circle (Theseus) to escape from the maze before the black circle (the Minotaur) "eats" you. The caveat is that the Minotaur moves twice, for every one move of yours. On the up side, the Minotaur is very predictable: he only moves towards you and he prefers moving horizontally to vertically. The trick is to get the minotaur partially stuck. Try a hand at it; the first few are pretty easy, but I would be surprised if you could get all of the last three.</p>

<p>For my final project in The Art of Recursion last semester, I wrote a solution to this puzzle in Haskell. You can find the full code here: github.come/stevekrouse/theseus</p>

<p>With some input from Mitchell Stern, I settled on a two-dimensional array to represent each maze and a pair of (x,y) coordinates ((x1,y1),(x2,y2)) to represent Theseus's and the Minotaur's positions, respectively. Next, I represented each square in each maze as a list of cardinal directions, one for each direction that a player in said square cannot move to. For example, if the square (1,1) has walls to the North and East, it would be represented in the 2-d array by [N,E]. Thus a Maze type is represented by a 2-d array of arrays. </p>

<p>Next, I spend a big portion of my code on displaying these mazes properly so I can make sure I inputted them correctly. As you can see in maze6, for example, it is all to easy to make a typo.</p>

<p>The only interesting part about how I displayed the data is to note that in order to only draw each wall once, it was necessary to remove two non-colinear directions. For illustration, imagine starting from the top, left point (0,0) and drawing out maze6. It's [N,W,S] so you draw a line on top, a line to the left, and a line to the bottom. Now move down a row to point (0,1) which is [N,W], so draw a line to left and a line to the top. Wait! We had already drawn a line to the bottom of the square above this one, so this line to the top is unnecessary. In fact, almost all North and South pairs and East and West pairs are redundant. (The ones that aren't redundant are the ones on the outside edges, i.e. all of the Norths on the top row.) Thus I needed to define a function called northWestRemove (northEastRemove, southEastRemove, and southWestRemove would have all worked too) to remove these redundancies. Why are the redundancies needed in the first place if we are building this function to remove them? That's because we aren't actually removing them permanently; we are just removing them momentarily for display purposes. We need them there so when Theseus and the Minotaur call the function "movesAndDelay" it will correctly read in the maze and the respective character's location and inform that character where he is allowed to move next (based on the complement of the list of directions he is not allowed to move in). </p>

<p>Next, on to the real fun stuff: how I solved the mazes. I decided to perform a breadth first search on each maze. In effect, this is as if I, as Theseus, decided every turn to take one step in every direction, creating up to 4 distinct "possibilities" every turn I take. Then the Minotaur, in each of the respective possibilities, takes his two, deterministic moves. The possibilities in which the Minotaur eats Theseus are discarded and then Theseus, in each of the respective possibilities that remain, again takes one step in every direction allow to him. You can look at it as if Theseus is guessing all possible moves at the same time. And, as those who are familiar with non-deterministic Turing Machines know, when you guess all of the possibilities, you always guess correctly.</p>

<p>However, I soon ran into a problem with mazes 6 and up: the code never stopped running. After much code-proofing and running tests on my code (with a Haskeller's best friend, Debug.Trace), I finally realized that 1) there weren't any bugs or typos in my code and, more frustratingly, 2) my code wasn't in an infinite loop, which lead me to discovery 3) that my program was examining so many different possibilities at the same time that my processor couldn't handle it. After running a few more tests, my girlfriend, Diana, came up with the theory that a large number of possibilities (maybe 10 or so) would converge to the same (Thesues, Minotaur)-coordinate-pairs in places where it is critical to trap the Minotaur. But then, once the minotaur is partially trapped, Theseus is usually able to move in a lot of different ways. So each of these 10 or so possibilities could quickly become 30 then 100 then 400 in just 3 subsequent turns. I had run into a problem in which I would need to delete "duplicate" possibilities; I couldn't return all possible solutions as I had hoped. It was just too much for my computer to handle. </p>

<p>So in order to cut down the number of possibilities, I had two options. The more obvious 1) keeping a running list of (Theseus, Minotaur) coordinates that I pass around to all appropriate functions and delete duplicates accordingly. However, this option seemed quite cumbersome as my functions were already taking 2, 3 or 4 inputs as it was. So I came up an alternative solution 2) that in effect "chops off the top" of all possible solutions, which I named "rebuild", because the way it works technically is by rebuilding the solution set without the duplicates (as opposed to removing the unnecessary ones). However it is easier to imagine the function doing the following: after each one of the Minotaur's turns, it goes through each possible solutions and deletes each one that has the same current (Theseus, Minotaur) coordinate pair as one of the possibilities listed before it. In effect, this makes it so that there is only one way to trap the minotaur. So in the previous example, 1 would have exploded to 3, then 12, then 48, which are all within the computing range of my macbook.</p>