# Quiz 3

## Problem Statement:

Raphael is back again with another problem for you. Before going to his school's administrative office to submit his fixed records, he had received an important call, and had written down a string original on the blackboard in a hurry. However, when he returned to his class, he noticed that the mischievous Gin has erased his important string original, and instead replaced it with a string scrambled.

All is not lost, though. Raphael knows Gin's obfuscation tricks like the back of his hand. He knows from prior experience that Gin does the following to any string that he fancies: he takes its first letter, writes the second letter to the left of the first, then the third to the right of the new string, and so on. For example, under Gin's wrath the string "alberio" becomes "ielabro", and "betelguese" becomes "eegeebtlus".

Help Raphael get back his original string original from the string that Gin has left on the blackboard! Write a program that takes as console input (cin) a string scrambled and prints out the original string original to the console (cout)!

### Sample Output:

``` Enter the scrambled string: cpsia The original string was: spica ```

## Solution

This problem is a bit difficult, as it asks you to reverse Gin's algorithm. I presented two slightly different solutions during the Tuesday and the Thursday discussions, so I'll go over them both here. Firstly, note that the algorithm preserves the position of the last letter if `scrambled.length()` is odd, and it sends the last letter to the beginning if it is even.

#### Solution 1

The first way of going about this is to map back the indices of scrambled into original. So, "ielabro" has 7 letters. Note the following mapping: `scrambled=original`, `scrambled=original`, `scrambled=original`, `scrambled=original`. Finally, `scrambled=original`, `scrambled=original`, `scrambled=original`. So, that means if the length of the strings are odd, then the mapping happens as `scrambled[(len-1)/2 + i]=original[2*i]` for every `0<=i<=(len-1)/2`, and `scrambled[(len-1)/2-i]=original[2*i-1]` for every `1<=i<=(len-1)/2`. If you work out the details for even length strings in a similar fashion, you'll obtain `scrambled[len/2 + i]=original[2*i]` for every `0<=i<=len/2`, and `scrambled[len/2-i]=original[2*i-1]` for `1<=i<=len/2`.

```#include <iostream>
#include <string>
using namespace std;

int main()
{
string scrambled, original;
cout<<"Please enter the scrambled string: ";
cin>>scrambled;
int len = scrambled.length();  // 'len' is the length of both the scrambled and original strings.
original = scrambled;  // Initialize original string to scrambled, instead of starting with the empty string.

if(len%2==1)  // If len is odd!
{
for(int i = 0; i<=(len-1)/2; i++)
{
original[2*i]=scrambled[(len-1)/2 + i];   // Fix the even letters in 'original'
}
for(int i = 1; i<=(len-1)/2;i++)
{
original[2*i-1]=scrambled[(len-1)/2 - i];   // Fix the odd letters in 'original'
}
}
else  // Else len%2 is 0 and len is even!
{
for(int i = 0; i<=len/2; i++)
{
original[2*i]=scrambled[len/2 + i];
}
for(int i=1; i<=len/2; i++)
{
original[2*i-1]=scrambled[len/2-i];
}
}

cout<<"The original string was: "<<original<<endl;
return 0;
}
```

#### Solution 2

The other way that I discussed on Thursday uses the `+` operation which appends strings. The way I'm presenting here is a bit different from the way I discussed in the lab. Again, let us focus on "ielabro". We can start off by having original as the empty string, and then first, note that 'a' is at `scrambled`. The next letter 'l' is at `scrambled`, then 'b' is at `scrambled`, and so on. Thus what we can do is, start at the middle of the string "ielabro", therefore first append `scrambled[(len-1)/2]` to `original`, and consecutively append `scrambled[(len-1)/2-i]` and `scrambled[(len-1)/2+i]` to `original`. When the length of the string is even, then "eegeebtlus" can be unscrambled by starting with original as the empty string, and then appending `scrambled[len/2+i]` and `scrambled[len/2-i-1]` consecutively to original.

```#include <iostream>
#include <string>
using namespace std;

int main()
{
string scrambled, original;
cout<<"Please enter the scrambled string: ";
cin>>scrambled;
int len = scrambled.length();   // 'len' is the length of both the scrambled and original strings.
original = "";   // Initialize original string to the empty string.

if(len%2==1)   // If len is odd!
{
for(int i = 1; i<=(len-1)/2; i++)
{
original+=scrambled[(len-1)/2 - i];    // Append the letters to the left from the middle position in 'scrambled'
original+=scrambled[(len-1)/2 + i];    // Append the letters to the right from the middle position in 'scrambled'
}
}
else   // Else len%2 is 0 and len is even!
{
for(int i = 0; i<len/2; i++)
{
original+=scrambled[len/2 + i];    // Moving right from the middle
original+=scrambled[len/2 - i - 1];    // Moving left from the middle
}
}

cout<<"The original string was: "<<original<<endl;
return 0;
}
```