Solution to "Party Time!"


The shortest distance from marker 1 to marker 2452 is 56 miles, making you arrive at the party 4 minutes early at 2:56pm. You get there fastest using the following directions (L for Left, S for Straight, and R for Right):

2-S, 2-R, L, S, 50-R

for a mile marker progression of 1, 2, 5, 6, 7, 49, 2402, 2403, 2404, 2405, ..., 2450, 2451, 2452.

In general, given a marker n, we want to work backwards and take the biggest jumps possible. That is, from n to \sqrt{n} if n is a square, or decrement to the first square plus one then inverse of square plus one if n is not a square. For example, if we are at marker 51, first we would have to travel one mile to marker 50, then one more to 7 (since from 7 you can square plus one to get to 50), for a total of 2 miles. So if n is not a perfect square, then the distance from n to the greatest perfect square less than or equal to n is

n-\lfloor\sqrt{n}\rfloor^2,

which is the same as the number of miles from n to after its first big "jump." For example,

51-\lfloor\sqrt{51}\rfloor ^2 =51-49=2.

If, on the other hand, n is a perfect square, then the biggest jump it can make is by taking the inverse of the square path for one mile to \sqrt{n} which can be expressed similarly to the previous formula,

\underbrace{n-\lfloor\sqrt{n}\rfloor^2}_{\text{=0 if n is perfect square}}+1.

This can be incorporated into a recursive algorithm to write into a programming language. I formulated one equation which covered both conditions above. To do so then I needed something that would equal 1 if n is perfect square, or 0 otherwise. So total distance f(n) to natural number mile marker n I found could be expressed recursively by:

f(n)=n-\lfloor\sqrt{n}\rfloor ^2 +\underbrace{\lfloor\sqrt{n+1/2}\rfloor-\lfloor\sqrt{n-1/2}\rfloor}_{\text{=1 if }n\text{ is perfect square; 0 otherwise}} + f(\lfloor\sqrt{n}\rfloor) \text{, for }n\ge 2,

and a stopping value of

f(1)=0.

Below you will find my program in C++. Please note this was one of the first programs I wrote outside of my first class in C++, so it is not very elegant!

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int main()
{
  double n=0, distance=0, temp=0, temp2=0;
  vector<char> turns;
  cout<<"\nPlease enter mile marker number for the party: ";
  cin>>n;
  while(n<=0) //just a check for valid input
  {
    cout<<"\n**Negative mile marker invalid, please check again: ";
    cin>>n;
  }

  cout<<"Distance to mile marker "<<n<<" is: ";

  while(n>=2)
  {
    temp=floor(sqrt(n+0.5))-floor(sqrt(n-0.5));
    temp2=n-floor(sqrt(n))*floor(sqrt(n));
    distance=distance+temp2+temp;
    if(temp==0) //if not a perfect square
    {
      for(unsigned int i=1;i<temp2;i++)
        turns.push_back('R');
      turns.push_back('S');
    }
    else if(temp==1)
      turns.push_back('L');

    n=floor(sqrt(n)); //recursion (more or less)
  }

  cout<<distance<<" miles.\n";
  if(distance!=0)
  {
    cout<<"Take this route: ";

    int turns_size=turns.size(), count=1;

    for(int j=turns_size; j>=1; j--) //print directions
    {
      if(turns[j-2]!=turns[j-1]) //if different turns than next, print turn
      {
        if (count==1)
          cout<<turns[j-1];
        else
          cout<<count<<"-"<<turns[j-1]; //coefficient number of turns
        if(j>=2)
          cout<<", ";
        else
          cout<<endl<<endl;
        count=1;
      }
      else
        count++;
    }
  }
  else
    cout<<endl;

  return 0;
}