Pages

CodeEval magic numbers

We have to detect all the numbers in a given interval that are "magic".

You could find the full description of the problem, and input your solution, on CodeEval.
The most interesting part is the description of the numbers we consider as magic:

* No digits repeat.
* Beginning with the leftmost digit, take the value of the digit and move that number of digits to the right. Repeat the process again using the value of the current digit to move right again. Wrap back to the leftmost digit as necessary. A magic number will visit every digit exactly once and end at the leftmost digit.

6231 is magic because there is no duplicate digit and:
* in position 0 there is a 6, move to position 2 -> (0 + 6) % 4 = 2
* in position 2 there is a 3, move to position 1 -> (2 + 3) % 4 = 1
* in position 1 there is a 2, move to position 3 -> (1 + 2) % 4 = 3
* in position 3 there is a 1, move to position 0 -> (3 + 1) % 4 = 0

Stripping down all the less interesting code, here is how implemented this algorithm in C++.

Firstly ensure there is no duplicated digit in the number:
for(auto it = number.begin(); it != number.end(); ++it)
{
  if(std::find(it + 1, number.end(), *it) != number.end())
    return false;
}
Then loop on the digits until we land on a digit that we have already visited:
std::vector visited(number.size(), false);
int pos = 0;
while(!visited[pos])
{
  visited[pos].flip();
  int cur = number[pos] - '0';
  pos = (pos + cur) % number.size();
}

Finally return success if we ended at the beginning of the string and all the digits have been visited:
return pos == 0 && std::find(visited.begin(), visited.end(), false) == visited.end();

No comments:

Post a Comment