\author{Problem Author: Nick Wu}
\newcommand{\carlsmazeheader}{Problem D: Carl's Maze Solving Algorithm}

\begin{frame}{\carlsmazeheader{}}
  \begin{block}{Problem}
    \begin{itemize}
      \item Simulate Carl the robot using a particular algorithm moving
          across a maze.
      \item Carl starts at a given square facing east.
      \item While Carl is not yet in the destination square
          \begin{itemize}
          \item If Carl can turn left by 90 degrees and face an empty square, 
            turn left $90$ degrees and then move forward by one square.
          \item Otherwise, if Carl can move forward by
                one square, move forward by one square.
          \item Else, turn right $90$ degrees (but do not move.)
          \end{itemize}
    \end{itemize}        
  \end{block}
\end{frame}
\begin{frame}{\carlsmazeheader{}}
  \begin{block}{Solution}
    \begin{itemize}
      \item Note that given algorithm will either lead to the
          destination or into a loop.
      \item Simulate the algorithm as stated, 
          while also remembering past poses of the 
          robot.  A pose is a combination of $(r, c, d_r, d_c)$
            representing the position and direction of the robot.
      \item If a previously seen pose is encountered, report $0$.
      \item If Carl reaches the destination, report $1$. 
    \end{itemize}        
  \end{block}
\end{frame}
