6
\$\begingroup\$

Introduction

In this challenge, I asked you to implement swap encoding.

Swap encoding is an encoding method where you iterate through the string, reversing substrings between identical characters. The basic algorithm is:

For each character in the string:

Check: Does the string contain the character again, after the instance you found?

If so, then modify the string by reversing the section between the character and the next instance, inclusive.

Otherwise do nothing.

Example

Start with the string 'eat potatoes'.

e is found again, so reverse that section: eotatop taes
o is found again, so reverse that section (doing nothing as it is palindromic)
t is found again, so reverse that section (doing nothing as it is palindromic)
a is found again, so reverse that section: eotat potaes
t is found again, so reverse that section: eotatop taes
None of 'op taes' are found again, so eotatop taes is our final string!

Anyway, in this chat, @okie and I discussed what would happen if you repeatedly ran the swap algorithm on something until it returned to the original string. We managed to prove that it will always return.

Okay, that's a lot of preamble. Here's your challenge:

Write a program or function that takes a string as input, and returns the number of times it has to be swapped before it will return to itself.

Scoring

Answers will be timed on their combined score on all the scored testcases, so please append a snippet to your program that runs all the testcases one after another.

I will time all answers on all on my computer (2018 Macbook Air), although please link to a downloadable interpreter/compiler for less mainstream languages.

Here is my reference implementation.

Testcases

Simple testcases (Just to check it works):

1231 => 2
1234512345 => 6
123142523
Sandbox for Proposed Challenges => 1090
Collatz, Sort, Repeat => 51
Rob the King: Hexagonal Mazes => 144
Decompress a Sparse Matrix => 8610
14126453467324231 => 1412
12435114151241 - 288
Closest Binary Fraction => 242
Quote a rational number => 282
Solve the Alien Probe puzzle => 5598

Scored testcases (The ones I'm timing you on)

124351141512412435325 => 244129
Write a fast-growing assembly function => 1395376
And I'm now heading to the elevator => 207478
I'm in the now infamous elevator => 348112
1549827632458914598012734 => 1025264
i was always mediocre at golfing => 1232480
tho, i like some code challenges => 2759404
I am once again in an elevator => 1606256
A person with mannerism of cat => 867594

IMPORTANT

To make it fair, I have to time all programs under the same load on my computer. So if one person requests a retime, I have to retime them all. This means your time may fluctate.

\$\endgroup\$
6
  • \$\begingroup\$ My elevator journey shall forever be known now \$\endgroup\$ – lyxal May 4 at 6:49
  • \$\begingroup\$ @Lyxal I can even link to the transcript if you really want me to. \$\endgroup\$ – A username May 4 at 6:53
  • \$\begingroup\$ You don't have to - the references are enough \$\endgroup\$ – lyxal May 4 at 6:55
  • 1
    \$\begingroup\$ It would be better to have your first link point to the main site rather than the sandbox. \$\endgroup\$ – Arnauld May 4 at 12:44
  • \$\begingroup\$ I guess you could submit the sequence of maximum cycle length for a given string size on OEIS: 1,1,1,2,3,4,6,12,38,117,234,650,... \$\endgroup\$ – Arnauld May 4 at 13:50
3
\$\begingroup\$

C++ (gcc), 3.809 seconds

Compile with g++ -O3 -std=c++14.

As requested by the OP, the testcases were included in the source.

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

constexpr int TESTCASES_NUM = 9;
constexpr char *TESTCASES[TESTCASES_NUM] = {"124351141512412435325", "Write a fast-growing assembly function", "And I'm now heading to the elevator", "I'm in the now infamous elevator", "1549827632458914598012734", "i was always mediocre at golfing", "tho, i like some code challenges", "I am once again in an elevator", "A person with mannerism of cat"};

int solve(char *s, int n) {
    int ans = 0;
    int i, j;
    char *p, *q, b;
    char s0[n];
    memcpy(s0, s, n);
    do {
        for(i = 0; i < n; ++i) {
            for(j = i + 1; j < n; ++j) {
                if(s[i] == s[j]) {
                    for(p = s + i + 1, q = s + j - 1; p < q; ++p, --q) {
                        b = *p;
                        *p = *q;
                        *q = b;
                    }
                    break;
                }
            }
        }
        ++ans;
    } while (memcmp(s0, s, n));
    return ans;
}

int main(int argc, char **argv) {
    for(int t = 0; t < TESTCASES_NUM; ++t) {
        char* s = TESTCASES[t];
        int  n = strlen(s);
        
        int count[300];
        memset(count, 0, sizeof(count));
        for(int i = 0; i < n; ++i) {
            ++count[s[i]];
        }
        char z[n];
        int m = 0;
        for(int i = 0; i < n; ++i) {
            if(count[s[i]] == 1) {
                if(i > 1 and count[s[i - 1]] == 1 and count[s[i - 2]] == 1) {
                    continue;
                }
            }
            if(i > 1 and s[i] == s[i - 2] and count[s[i - 1]] == 1) {
                --m;
                continue;
            }
            if(m == 0 and count[s[i]] == 0) {
                continue;
            }
            z[m++] = s[i];
        }
        while(m > 1 and count[z[m - 1]] == 1) {
            --m;
        }
        
        printf("%d\n", solve(z, m));
    }
}

Try it online!

The naive implementation, with a couple of preprocessing optimizations.

Say that a character is unique if it occurs exactly once in the input string.

  • If there are more than 2 consecutive unique characters, we can remove some of them until there are exactly 2 consecutive ones.
  • We can remove every prefix or suffix consisting entirely of unique characters.
  • We can make substitutions aba -> a whenever b is unique (thanks to kops for the suggestion!).
\$\endgroup\$
11
  • \$\begingroup\$ Nice! Will time! \$\endgroup\$ – A username May 4 at 9:58
  • 1
    \$\begingroup\$ "If there is a unique character without any unique neighbors, we can delete it from the string." <- This is false in general. Consider abcab (period 2) vs abab (period 1). I believe your second observation is correct, though. \$\endgroup\$ – kops May 4 at 15:30
  • 1
    \$\begingroup\$ On the other hand, another (admittedly small) optimization you can do is reduce repeated letters like aa->a. \$\endgroup\$ – kops May 4 at 15:38
  • 1
    \$\begingroup\$ For the 7th test case, removing one of the doubled letters (ll in challenges) results in half as many iterations as the reference implementation. I'm unsure why. Both programs give the same result for, say, the 2nd test case (which has ss in assembly). \$\endgroup\$ – Dingus May 5 at 3:43
  • 1
    \$\begingroup\$ @Dingus Yes, sorry. It should be fixed now (and I also added the other optimizations suggested by kops above). \$\endgroup\$ – Delfad0r 2 days ago
2
\$\begingroup\$

C, 1.972 seconds

In 2021 we don't have faster CPUs, we just have more cores. Let's use them! Naive implementation using POSIX threads to parallelize. A simple but fast hash is used to save some string compares.

Update: unrolled loop for short distances to shave off 9% percent.

Update 2: flag unique characters to prevent unnecessary searching for duplicate character (saves additional 12%, now saved 19% over original code).

// To compile:
//    $ gcc -Wall -O3 JasonSmith.c -lpthread -o JasonSmith
//
#include <assert.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define UNIQUE_MASK  (0x80)

/**
 * Test Vectors with expected answers.
 */
typedef struct {
   const char *text;
   int         expected;
} test_vector_t;
 
test_vector_t test_vectors[] = {
   {  "124351141512412435325",                  244129   },
   {  "Write a fast-growing assembly function", 1395376  },
   {  "And I'm now heading to the elevator",    207478   },
   {  "I'm in the now infamous elevator",       348112   },
   {  "1549827632458914598012734",              1025264  },
   {  "i was always mediocre at golfing",       1232480  },
   {  "tho, i like some code challenges",       2759404  },
   {  "I am once again in an elevator",         1606256  },
   {  "A person with mannerism of cat",         867594   },
};
int nr_test_vectors = sizeof(test_vectors)/sizeof(test_vectors[0]);

/**
 * Worker thread
 * @param test vector to process
 */
void process(test_vector_t *test_vector) {
   
   // swap encoding is destructive, so first make copy
   // of challenge text in separate buffer
   char text[strlen(test_vector->text) + 1 + 5];
   memset(text, 0, sizeof(text));
   strcpy(text, test_vector->text);

   // flag unique characters by setting high bit
   for (char *p = text; *p; p++) {
      assert((*p & UNIQUE_MASK) == 0);  // assume no "weird" UTF-8 chars
      int is_unique = 1;
      for (char *q = text; *q; q++) {
          if (p == q) continue;
          if (*p == *q) {
            is_unique = 0;
            break;
          }
      }
      if (is_unique) *p |= UNIQUE_MASK;
   }

   // flagged text no longer matches original text, so we must
   // save flagged text as the new "original" for comparison later.
   char orig[strlen(text) + 1];
   strcpy(orig, text);

   // calculcate hash of original text
   unsigned long original_hash = 0;
   for (char *p = text; *p; p++) {
      original_hash = original_hash*31 + *p;
   }

   // repeatedly swap encode until original text is back
   unsigned long hash;
   unsigned int count = 0;
   do {
      hash = 0;
      for (char *p = text; *p; p++) {
         hash = hash*31 + *p;
         
         // no need to search for duplicate of unique character
         if ((*p & UNIQUE_MASK) != 0) continue;
         
         // unrolled loop for short distances
         if (p[0] == p[1]) continue;
         if (p[0] == p[2]) continue;
         if (p[0] == p[3]) {
            char temp = p[1];
            p[1] = p[2];
            p[2] = temp;
            continue;
         }
         if (p[0] == p[4]) {
            char temp = p[1];
            p[1] = p[3];
            p[3] = temp;
            continue;
         }
         if (p[0] == p[5]) {
            char temp = p[1];
            p[1] = p[4];
            p[4] = temp;
            
            temp = p[2];
            p[2] = p[3];
            p[3] = temp;
            continue;
         }
         
         // scan for larger distances
         char *last = p+6;
         while (*last && *last != *p) last++;
         if (*last) {
            char *start = p;
            while (++start < --last) {
               char temp = *start;
               *start = *last;
               *last = temp;
            }
         }
      }
      count++;
   } while (hash != original_hash || strcmp(orig, text));

   // show result to user
   printf("%-40s -> %8d (%s)\n", test_vector->text, count, 
      (count == test_vector->expected ? "Ok" : "FAIL"));
}

/**
 * Main
 */
int main() {
   pthread_t threads[nr_test_vectors];
   for (int i = 0; i < nr_test_vectors; i++) {
      pthread_create(&threads[i], NULL, (void (*))process, test_vectors+i);
   }
   for (int i = 0; i < nr_test_vectors; i++) {
      pthread_join(threads[i], NULL);
   }
   return 0;
}

\$\endgroup\$
5
  • \$\begingroup\$ We'll see how this goes! \$\endgroup\$ – A username yesterday
  • \$\begingroup\$ Nice, much faster! You might want to optimise it a bit more. \$\endgroup\$ – A username yesterday
  • \$\begingroup\$ Bit more optimization: unrolled loop for short distances. Considered "borrowing" DelfadOr and kops length reduction rules, but that would be lame ;-) \$\endgroup\$ – Jason Smith 10 hours ago
  • \$\begingroup\$ Also: flag unique characters to prevent unnecessary searching for duplicate character. Optimizations saved 19% over original code \$\endgroup\$ – Jason Smith 10 hours ago
  • \$\begingroup\$ Nice! I think this has improved more than the score suggests, because the other two took longer than they did before.. (I retime every program just to be fair, because the load on my computer varies) \$\endgroup\$ – A username 2 hours ago
2
\$\begingroup\$

C (clang), 5.383 seconds

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

unsigned int f(char* str)
{
    unsigned int count = 0;

    char original[strlen(str) + 1];
    strcpy(original, str);

    do {
        for (char* current = str; *current; ++current)
        {
            for (
                    char* last = index(current + 1, *current),
                    *start = current;
                    last > start;
                )
            {
                char temp = *start;
                *start++ = *last;
                *last-- = temp;
            }
        }
        ++count;
    } while (strcmp(original, str));

    return count;
}

int main(int argc, char** argv)
{
#ifdef SIMPLE
    char* tests[] = {"1231", "1234512345", "123142523", "Sandbox for Proposed Challenges", "Collatz, Sort, Repeat", "Rob the King: Hexagonal Mazes", "Decompress a Sparse Matrix", "14126453467324231", "12435114151241", "Closest Binary Fraction", "Quote a rational number", "Solve the Alien Probe puzzle"};
    int expected[] = {2, 6, 4, 1090, 51, 144, 8610, 1412, 288, 242, 282, 5598};
#else
    char* tests[] = {"124351141512412435325", "Write a fast-growing assembly function", "And I'm now heading to the elevator", "I'm in the now infamous elevator", "1549827632458914598012734", "i was always mediocre at golfing", "tho, i like some code challenges", "I am once again in an elevator", "A person with mannerism of cat"};
    int expected[] = {244129, 1395376, 207478, 348112, 1025264, 1232480, 2759404, 1606256, 867594};
#endif

    char* checker[]   = {"\xE2\x9C\x95", "\xE2\x9C\x93"};
    for (int index = 0; index < sizeof(expected)/sizeof(*expected); ++index) {
        char* t = tests[index];
        char buff[strlen(t) + 1];
        strcpy(buff, t);
        int s = f(buff);
        int e = expected[index];
        printf("\"%s\" -> %d %s\n", t, s, checker[e==s]);
    }
}

Try it online!

Compile with -O3.

\$\endgroup\$
13
  • \$\begingroup\$ Yes. Will time. \$\endgroup\$ – A username May 4 at 10:58
  • \$\begingroup\$ 48 milliseconds ????!?!?!?!??!?!?!?!? \$\endgroup\$ – A username May 4 at 11:01
  • \$\begingroup\$ Did you define SCORE to run the right tests? \$\endgroup\$ – Noodle9 May 4 at 11:02
  • \$\begingroup\$ Oops no. Will do. \$\endgroup\$ – A username May 4 at 11:03
  • \$\begingroup\$ Changed it to run score tests by default \$\endgroup\$ – Noodle9 May 4 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.