(The seed obviously should not be revealed during the game.)
Here is an example of its usage:
Code: Select all
$ ./shuffle -s 0xf83b75def2458563 shuffle.c
* a copy of this software and associated documentation files (the
static void version(const char *program) {
* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
"\n"
return list;
}
}
case 'h':
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
shuffle(list, listlen, seed);
if (len >= capacity) {
/* http://vigna.di.unimi.it/ftp/papers/xorshift.pdf */
capacity += ALLOCATION_UNIT;
* List shuffler. Tested on Linux only.
fprintf(stderr, "%s: invalid seed: %s\n", argv[0], optarg);
uint64_t seed = 0;
if (seed == 0) {
}
/* initialize seed if zero */
}
"With no FILE, or when FILE is -, read standard input.\n"
free(list);
printf(helptext, program);
list[len++] = line;
#include <inttypes.h>
*outlist = list;
return 0;
if (!urandom) {
}
* Copyright (c) 2023 McEndu.
* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
char **list;
#define ALLOCATION_UNIT 32
return 1;
}
}
{NULL, 0, NULL, 0},
int main(int argc, char **argv) {
" -h, --help displays this help\n"
for (size_t i = size; i > 1; --i) {
version(argv[0]);
}
help(argv[0]);
while (seed == 0) {
fprintf(stderr, "%s: failed to open %s: %s\n", argv[0], argv[optind],
#include <stddef.h>
uint64_t result = *state * UINT64_C(0x2545f4914f6cdd1d);
free(list[i]);
if (f == NULL) {
* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
return 0;
while ((arg = getopt_long(argc, argv, "s:hv", options, NULL)) != -1) {
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* without limitation the rights to use, copy, modify, merge, publish,
static void version(const char *program);
argv[0]);
*state ^= *state >> 27;
free(line);
puts("Yet another list shuffler\n");
static size_t readList(FILE *f, char ***outlist);
return 1;
list = realloc(list, capacity * sizeof(char *));
void *x = list[i - 1];
char *line = NULL;
}
"%s: cannot open /dev/urandom; am I running on the wrong OS?\n",
size_t listlen = readList(f, &list);
* "Software"), to deal in the Software without restriction, including
"Usage: %s [-hv] [-s seed] [FILE]\n"
};
static void help(const char *program) {
char **list = malloc(ALLOCATION_UNIT * sizeof(char *));
size_t n; /* required by getline(3) */
++optind;
* Permission is hereby granted, free of charge, to any person obtaining
}
static const struct option options[] = {
#include <stdlib.h>
*
if (*strend != '\0') {
* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
#include <getopt.h>
#include <string.h>
{"help", no_argument, NULL, 'h'},
}
return 0;
}
while ((linelen = getline(&line, &n, f)) != -1) {
* permit persons to whom the Software is furnished to do so, subject to
" -v, --version displays version information\n";
return 1;
/*
#include <errno.h>
static void help(const char *program);
*state ^= *state << 25;
break;
line = NULL; /* make space for another line */
if (line[linelen - 1] == '\n')
static uint64_t xorshift64star(uint64_t *state) {
char *strend;
{"seed", required_argument, NULL, 's'},
return len;
fprintf(stderr,
}
line[linelen - 1] = '\0';
f = fopen(argv[optind], "r");
fclose(urandom);
/* replace newline */
* the following conditions:
" -s, --seed Generate using a specific seed\n"
int arg;
seed = strtoull(optarg, &strend, 0);
uint64_t rngstate = seed;
#include <stdio.h>
"\n"
}
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
{"version", no_argument, NULL, 'v'},
}
#include <stdint.h>
*state ^= *state >> 12;
case 'v':
*/
"A list shuffler.\n"
if (optind < argc && strcmp(argv[optind], "-") != 0) {
ssize_t linelen;
size_t n = xorshift64star(&rngstate) % i;
}
}
fprintf(stderr, "%s: using generated seed 0x%" PRIx64 "\n", argv[0], seed);
for (size_t i = 0; i < listlen; ++i) {
return result >> 24;
* The above copyright notice and this permission notice shall be
FILE *urandom = fopen("/dev/urandom", "rb");
static const char helptext[] =
* included in all copies or substantial portions of the Software.
int count = fread(&seed, 1, sizeof(uint64_t), urandom);
list[i - 1] = list[n];
static char **shuffle(char **list, size_t size, uint64_t seed) {
fputs(list[i], stdout);
* distribute, sublicense, and/or sell copies of the Software, and to
if (count < sizeof(uint64_t)) {
*
putc('\n', stdout);
static size_t readList(FILE *f, char ***outlist) {
switch (arg) {
}
size_t len = 0;
case 's':
size_t capacity = ALLOCATION_UNIT;
*
return 1;
list[n] = x;
FILE *f = stdin;
strerror(errno));
}
fprintf(stderr, "%s: /dev/urandom is not sane\n", argv[0]);
The tool is written in C. The core code is simple. It takes a list of strings and a seed. The list is split into two parts, one part consisting of unshuffled items and one part consisting of shuffled items. For each item on the list, a backing pseudorandom number generator (here xorshift64*) is used to select an item in the unshuffled part. The item is then swapped with the last item of the unshuffled part, and gets moved into the shuffled part.
Code: Select all
/* http://vigna.di.unimi.it/ftp/papers/xorshift.pdf */
static uint64_t xorshift64star(uint64_t *state) {
*state ^= *state >> 12;
*state ^= *state << 25;
*state ^= *state >> 27;
uint64_t result = *state * UINT64_C(0x2545f4914f6cdd1d);
return result >> 24;
}
char **shuffle(char **list, size_t size, uint64_t seed) {
uint64_t rngstate = seed;
for (size_t i = size; i > 1; --i) {
size_t n = xorshift64star(&rngstate) % i;
void *x = list[i - 1];
list[i - 1] = list[n];
list[n] = x;
}
return list;
}
The full source code of the tool follows. C code cannot be run directly; you should use a C99 compiler with GNU extensions, preferably GCC or Clang, to convert it to a real program. I have only tested this program under Linux x86-64, though it is expected to also compile and run on macOS. It does not work correctly on Windows (due to assuming that /dev/urandom is an RNG), and I have no interest in a proper Windows port. If you really want to run it on Windows, you can give Windows Subsystem for Linux (WSL) a try, though.
Code: Select all
/*
* List shuffler. Tested on Linux only.
* Copyright (c) 2023 McEndu.
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/
#include <errno.h>
#include <getopt.h>
#include <inttypes.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* http://vigna.di.unimi.it/ftp/papers/xorshift.pdf */
static uint64_t xorshift64star(uint64_t *state) {
*state ^= *state >> 12;
*state ^= *state << 25;
*state ^= *state >> 27;
uint64_t result = *state * UINT64_C(0x2545f4914f6cdd1d);
return result >> 24;
}
static char **shuffle(char **list, size_t size, uint64_t seed) {
uint64_t rngstate = seed;
for (size_t i = size; i > 1; --i) {
size_t n = xorshift64star(&rngstate) % i;
void *x = list[i - 1];
list[i - 1] = list[n];
list[n] = x;
}
return list;
}
static const struct option options[] = {
{"seed", required_argument, NULL, 's'},
{"help", no_argument, NULL, 'h'},
{"version", no_argument, NULL, 'v'},
{NULL, 0, NULL, 0},
};
static void help(const char *program);
static void version(const char *program);
static size_t readList(FILE *f, char ***outlist);
int main(int argc, char **argv) {
FILE *f = stdin;
uint64_t seed = 0;
int arg;
while ((arg = getopt_long(argc, argv, "s:hv", options, NULL)) != -1) {
char *strend;
switch (arg) {
case 'h':
help(argv[0]);
return 0;
case 'v':
version(argv[0]);
return 0;
case 's':
seed = strtoull(optarg, &strend, 0);
if (*strend != '\0') {
fprintf(stderr, "%s: invalid seed: %s\n", argv[0], optarg);
return 1;
}
break;
}
}
if (optind < argc && strcmp(argv[optind], "-") != 0) {
f = fopen(argv[optind], "r");
if (f == NULL) {
fprintf(stderr, "%s: failed to open %s: %s\n", argv[0], argv[optind],
strerror(errno));
return 1;
}
++optind;
}
/* initialize seed if zero */
if (seed == 0) {
FILE *urandom = fopen("/dev/urandom", "rb");
if (!urandom) {
fprintf(stderr,
"%s: cannot open /dev/urandom; am I running on the wrong OS?\n",
argv[0]);
return 1;
}
while (seed == 0) {
int count = fread(&seed, 1, sizeof(uint64_t), urandom);
if (count < sizeof(uint64_t)) {
fprintf(stderr, "%s: /dev/urandom is not sane\n", argv[0]);
return 1;
}
}
fclose(urandom);
fprintf(stderr, "%s: using generated seed 0x%" PRIx64 "\n", argv[0], seed);
}
char **list;
size_t listlen = readList(f, &list);
shuffle(list, listlen, seed);
for (size_t i = 0; i < listlen; ++i) {
fputs(list[i], stdout);
putc('\n', stdout);
free(list[i]);
}
free(list);
return 0;
}
static void help(const char *program) {
static const char helptext[] =
"Usage: %s [-hv] [-s seed] [FILE]\n"
"A list shuffler.\n"
"\n"
"With no FILE, or when FILE is -, read standard input.\n"
"\n"
" -s, --seed Generate using a specific seed\n"
" -h, --help displays this help\n"
" -v, --version displays version information\n";
printf(helptext, program);
}
static void version(const char *program) {
puts("Yet another list shuffler\n");
}
#define ALLOCATION_UNIT 32
static size_t readList(FILE *f, char ***outlist) {
char **list = malloc(ALLOCATION_UNIT * sizeof(char *));
size_t len = 0;
size_t capacity = ALLOCATION_UNIT;
ssize_t linelen;
size_t n; /* required by getline(3) */
char *line = NULL;
while ((linelen = getline(&line, &n, f)) != -1) {
/* replace newline */
if (line[linelen - 1] == '\n')
line[linelen - 1] = '\0';
if (len >= capacity) {
capacity += ALLOCATION_UNIT;
list = realloc(list, capacity * sizeof(char *));
}
list[len++] = line;
line = NULL; /* make space for another line */
}
free(line);
*outlist = list;
return len;
}