Best shuffle: Difference between revisions

Line 126:

#define DEBUG

void best_shuffle(const ~~unsigned~~ char* txt, ~~unsigned~~ char* result) {

void best_shuffle(const char* txt, char* result) {

const ~~int~~ len = ~~(int)~~strlen(~~(char*)~~txt);

const size_t len = strlen(txt);

if (len == 0)

return;

Line 133:

#ifdef DEBUG

// txt and result must have the same length

assert(len == ~~(int)~~strlen(~~(char*)~~result));

assert(len == strlen(result));

#endif

// how many of each character?

~~int~~ counts[UCHAR_MAX];

size_t counts[UCHAR_MAX];

memset(counts, '\0', UCHAR_MAX * sizeof(int));

~~int~~ fmax = 0;

size_t fmax = 0;

for (~~int~~ i = 0; i < len; i++) {

for (size_t i = 0; i < len; i++) {

counts[txt[i]]++;

counts[(unsigned char)txt[i]]++;

const ~~int~~ fnew = counts[txt[i]];

const size_t fnew = counts[(unsigned char)txt[i]];

if (fmax < fnew)

fmax = fnew;

}

assert(fmax > 0 && fmax <= len);

⚫

// how long can our cyclic groups be?

⚫

const ~~int~~ grp = 1 + (len - 1) / fmax;

⚫

// how many of them are full length?

⚫

const ~~int~~ lng = 1 + (len - 1) % fmax;

// all character positions, grouped by character

~~int~~ *ndx1 = malloc(~~(unsigned int)~~len * sizeof(~~int~~));

size_t *ndx1 = malloc(len * sizeof(size_t));

if (ndx1 == NULL)

exit(EXIT_FAILURE);

for (~~int~~ ch = 0, i = 0; ch < UCHAR_MAX; ch++)

for (size_t ch = 0, i = 0; ch < UCHAR_MAX; ch++)

if (counts[ch])

for (~~int~~ j = 0; j < len; j++)

for (size_t j = 0; j < len; j++)

if (ch == txt[j]) {

if (ch == (unsigned char)txt[j]) {

ndx1[i] = j;

i++;

Line 167:

Line 161:

// regroup them for cycles

~~int~~ *ndx2 = malloc(~~(unsigned int)~~len * sizeof(~~int~~));

size_t *ndx2 = malloc(len * sizeof(size_t));

if (ndx2 == NULL)

exit(EXIT_FAILURE);

for (~~int~~ i = 0, n = 0, m = 0; i < len; i++) {

for (size_t i = 0, n = 0, m = 0; i < len; i++) {

ndx2[i] = ndx1[n];

n += fmax;

Line 178:

Line 172:

}

⚫

// how long can our cyclic groups be?

⚫

const size_t grp = 1 + (len - 1) / fmax;

assert(grp > 0 && grp <= len);

⚫

// how many of them are full length?

⚫

const size_t lng = 1 + (len - 1) % fmax;

assert(lng > 0 && lng <= len);

// rotate each group

for (~~int~~ i = 0, j = 0; i < fmax; i++) {

for (size_t i = 0, j = 0; i < fmax; i++) {

~~int~~ first = ndx2[j];

const size_t first = ndx2[j];

~~int~~ glen = grp - (i < lng ? 0 : 1);

const size_t glen = grp - (i < lng ? 0 : 1);

for (~~int~~ k = 1; k < glen; k++)

for (size_t k = 1; k < glen; k++)

ndx1[j + k - 1] = ndx2[j + k];

ndx1[j + glen - 1] = first;

Line 191:

Line 193:

// result is original permuted according to our cyclic groups

result[len] = '\0';

for (~~int~~ i = 0; i < len; i++)

for (size_t i = 0; i < len; i++)

result[ndx2[i]] = txt[ndx1[i]];

Line 198:

Line 200:

}

void display(char* txt1, char* txt2) {

void display(const char* txt1, const char* txt2) {

~~int~~ len = ~~(int)~~strlen(txt1);

const size_t len = strlen(txt1);

assert(len == ~~(int)~~strlen(txt2));

assert(len == strlen(txt2));

int score = 0;

for (~~int~~ i = 0; i < len; i++)

for (size_t i = 0; i < len; i++)

if (txt1[i] == txt2[i])

score++;

(void)printf("%s, %s, (%d)\n", txt1, txt2, score);

(void)printf("%s, %s, (%u)\n", txt1, txt2, score);

}

Line 211:

Line 213:

char* data[] = {"abracadabra", "seesaw", "elk", "grrrrrr",

"up", "a", "aabbbbaa", "", "xxxxx"};

const ~~int~~ data_len = sizeof(data) / sizeof(data[0]);

const size_t data_len = sizeof(data) / sizeof(data[0]);

for (~~int~~ i = 0; i < data_len; i++) {

for (size_t i = 0; i < data_len; i++) {

const ~~unsigned int~~ shuf_len = strlen(data[i]) + 1;

const size_t shuf_len = strlen(data[i]) + 1;

~~unsigned~~ char shuf[shuf_len];

char shuf[shuf_len];

#ifdef DEBUG

memset(shuf, 0xFF, shuf_len * sizeof(~~unsigned~~ char));

memset(shuf, 0xFF, shuf_len * sizeof(char));

shuf[shuf_len - 1] = '\0';

#endif

best_shuffle(~~(unsigned char*)~~data[i], shuf);

best_shuffle(data[i], shuf);

display(data[i], ~~(char*)~~shuf);

display(data[i], shuf);

}