Robert Eisele
Engineer, Systems Architect and DBA

Skillvalue: Decrypt the enigma

Given a text, you must jump to every Nth letter of the text repeatedly until you pick all the characters. Combine all the letters together and this will be your message.

The jump positions will be represented by prime numbers: N = {2, 3, 5, 7, 11 ...}. Always jump through the initial text.

Character selection ends when you have collectedall the letters in the text, including duplicates. The output will consist of the collected letters arranged in the order they have been selected.
Input: String
Output: String

Examples:
For the following text: “ERA”, the output will be “RREREREREA”

For the following text: “HELLO” The output will be “EOOELHLEOL”.

Solution

The problem is not that hard. Given a reasonable large prime table P, we successively add the primes to calculate the current position p and limit the pointer circular by the length of the actual string using modulo its length. Since the position is now zero-indexed, we need to reduce the pointer to read from by one.

The tricky part is to check when we arrive at the end. Since the string is never longer than 32 chars, we can use an integer bitmap and add bits at the position we have finished. Duplicates don't change anything and the final bit vector must be a number of binary all 1 for the same length as the original string. Using a set is not efficient enough to finish this task with 100%. However, when implemented in C++ the code can look like this:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

int P[] = {2, 3, 5, 7, 11, ...};

int main(int argc, char **argv){

  char temp[256], word[256];
  char result[256];
  char const* const file_name = argv[1];
  FILE *fp = fopen(file_name, "r");

  fgets(temp, 256, fp); 
  sscanf(temp, "%s", &word);		
  int len = strlen(word);

  int p = 0;
  int fin = (1 << len) - 1;
  int done = 0;
  for (int i = 0; done != fin; i++) {
    p+= P[i];
    p%= len;
    done|= 1 << p;
    putchar(word[(p - 1 + len) % len]);
  }
  putchar("\n");
  fclose(fp);
  return 0;
}

« Back to problem overview

All images are copyright to Skillvalue