I'd say the curve is just long, not steep. Most of the capabilities in Org-mode can in my opinion be ignored for a To-Do list.
brie
joined 2 years ago
C: gcc -O2 easy.c
In case formatting is messed up
#include
#include
void bail(char const *msg)
{
fputs(msg, stderr);
exit(EXIT_FAILURE);
}
int main(int argc, char **argv)
{
int count = 0;
char *p, c = 0;
if (argc != 2) {
bail("Improper invocation.\n");
}
for (c = *(p = argv[1]); *p; p++) {
if (c == *p) {
count++;
} else {
printf("%c%d", c, count);
c = *p;
count = 1;
}
}
if (count) {
printf("%c%d", c, count);
}
putchar('\n');
return 0;
}
C: gcc -O2 hard.c
This is very poorly written, but does seem to work.
The stack keeps track of the start of a match, and the character that would complete the match. In cases where a match just ended, the start is preserved (because two adjacent matches are effectively one), but the required matching character is changed to that of the new opening match.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>
int main(int argc, char **argv)
{
char map[256] = { 0 };
struct match {
char const *start;
char requirement;
};
char const *match_start;
ptrdiff_t length = 0;
char const *p;
struct match *stack, *top;
char opener;
if (argc != 2) {
fputs("Improper invocation\n", stderr);
exit(EXIT_FAILURE);
}
/* Initialise lookup table */
map[')'] = '(';
map[']'] = '[';
map['}'] = '{';
if (!(stack = calloc(sizeof(*stack), strlen(argv[1]) + 1))) {
fputs("Allocation failure\n", stderr);
exit(EXIT_FAILURE);
}
/* Note: stack[0].requirement must be 0. This is satisfied by calloc. */
top = stack;
match_start = argv[1];
for (p = argv[1]; *p; p++) {
/* Are we a closing brace? */
if ((opener = map[(size_t)*p])) { /* Yes */
if (top->requirement == opener) {
if (p - top->start >= length) {
length = p - top->start + 1;
match_start = top->start;
}
top[1].start = 0;
top--;
} else {
top[1].start = 0;
/* Set start to nullptr to invalidate the matches */
while (top > stack) {
top--->start = 0;
}
}
} else { /* No */
(++top)->requirement = *p;
/* If we are right outside another match, we can use their pointer instead */
if (!top->start) {
top->start = p;
}
}
}
printf("%.*s\n", (int)length, match_start);
free(stack);
}
Figured out my old solution didn't actually work past 4, so here's a new solution in C. It matches @SleveMcDichael@programming.dev's solution up to n=10.
Some stats using wc -l:
n=0 has 1 combinations
n=2 has 3 combinations
n=4 has 18 combinations
n=6 has 135 combinations
n=8 has 1134 combinations
n=10 has 10206 combinations
n=12 has 96228 combinations
n=14 has 938223 combinations
n=16 has 9382230 combinations
n=18 has 95698746 combinations
n=20 has 991787004 combinations
#include <stdio.h>
#include <stdlib.h>
char const brackets[6] = "({[)}]";
int update(int *buf, int len)
{
int width = *buf >> 2;
if (width > len - 2) {
return -1;
}
if ((++*buf & 3) < 3) {
return 0;
}
*buf &= ~3;
if (update(buf + 1, width)) {
buf[1] = 0;
if (update(buf + width + 2, len - width - 2)) {
*buf = (width += 2) << 2;
if (width > len - 2) {
return -1;
}
buf[width + 2] = 0;
}
}
return 0;
}
void display(int *buf, int len)
{
int width = *buf >> 2;
char const *bracket = brackets + (*buf & 3);
if (len <= 0) {
return;
};
putchar(bracket[0]);
display(buf + 1, width);
putchar(bracket[3]);
display(buf + width + 2, len - width - 2);
}
int main(int argc, char **argv)
{
int n;
int *buf;
if (argc < 2) {
fputs("Bad invocation", stderr);
exit(EXIT_FAILURE);
}
sscanf(argv[1], "%d", &n);
buf = calloc(n + 2, sizeof(*buf));
display(buf, n);
putchar('\n');
while (!update(buf, n)) {
display(buf, n);
putchar('\n');
}
free(buf);
return 0;
}
v1 slightly incorrect solution
#include <stdio.h>
#include <stdlib.h>
char const brackets[6] = "({[)}]";
int update(int *buf, int len)
{
int width = *buf >> 2;
if (width > len - 2) {
return -1;
}
if ((++*buf & 3) < 3) {
return 0;
}
*buf &= ~3;
if (update(buf + 1, width)) {
buf[1] = 0;
if (update(buf + width + 2, len - width - 2)) {
*buf = (width += 2) << 2;
if (width > len - 2) {
return -1;
}
buf[width + 2] = 0;
}
}
return 0;
}
void display(int *buf, int len)
{
int width = *buf >> 2;
char const *bracket = brackets + (*buf & 3);
if (len <= 0) {
return;
};
putchar(bracket[0]);
display(buf + 1, width);
putchar(bracket[3]);
display(buf + width + 2, len - width - 2);
}
int main(int argc, char **argv)
{
int n;
int *buf;
sscanf(argv[1], "%d", &n);
if (n == 0) {
return 0;
}
buf = calloc(n + 20, sizeof(*buf));
display(buf, n);
putchar('\n');
while (!update(buf, n)) {
display(buf, n);
putchar('\n');
}
free(buf);
return 0;
}
This sounds neat, but it also seems like it does not have much practical advantage over hibernation except faster wake.
If order doesn't matter, implementations can be quickly compared with a reference implementation using diff + sort:
>> for i in 2 4 6 8; do diff -qs <(./a.out $i|sort) <(./a.out $i|sort); done
Files /dev/fd/63 and /dev/fd/62 are identical
Files /dev/fd/63 and /dev/fd/62 are identical
Files /dev/fd/63 and /dev/fd/62 are identical
Files /dev/fd/63 and /dev/fd/62 are identical
>> for i in 2 4 6 8; do diff -qs <(./a.out $i|sort) <(true $i|sort); done
Files /dev/fd/63 and /dev/fd/62 differ
Files /dev/fd/63 and /dev/fd/62 differ
Files /dev/fd/63 and /dev/fd/62 differ
Files /dev/fd/63 and /dev/fd/62 differ
Probably doesn't count since the lines are out of order, but here's a first attempt at a C solution.
#include <stdio.h>
char const brackets[6] = "()[]{}";
void combo(int pairs, int seed)
{
if (pairs <= 0) {
return;
}
char const *pair = brackets + ((seed % 3) << 1);
if (pairs == 1) {
putchar(pair[0]);
putchar(pair[1]);
} else {
putchar(pair[0]);
if (seed & 1) {
combo(pairs - 1, seed / 6);
putchar(pair[1]);
} else {
putchar(pair[1]);
combo(pairs - 1, seed / 6);
}
}
}
int main(int argc, char **argv)
{
int n;
size_t combos = 1;
size_t i;
sscanf(argv[1], "%d", &n);
for (i = 0; i < n; i += 2) {
combos *= 6;
}
combos >>= 1;
int pairs = n / 2;
for (i = 0; i < combos; i++) {
combo(pairs, i);
puts("");
}
return 0;
}
GIMP opens each frame of the GIF as a layer. It's probably not a good choice for longer GIFs though.
Minetest and Mindustry are two of my favourites. It's a bit complicated to find a good combination of Minetest mods though.
This gave me the idea to do the same in C, but use the argument string itself as the stack to avoid any allocations. It could probably be further optimized.
#include <stdio.h>
int main(int argc, char **argv)
{
char map[256] = { 0 };
map[')'] = '(';
map['}'] = '{';
map[']'] = '[';
while (--argc) {
char *top, *p, c;
top = p = *++argv;
while ((c = *p++)) {
if (top != *argv && map[(size_t)c] == top[-1]) {
top--;
} else {
*top++ = c;
}
}
*top = 0;
puts(*argv);
}
}
Skew, targetting Deno/JS, and recieving input via command-line parameters.
@entry
def main {
dynamic.Deno.args.forEach(s => {
var r=dynamic.RegExp("\\(\\)|{}|\\[]","g")
while s != (s = s.replaceAll(r,"")) {}
dynamic.console.log(s)
})
}
Compile with skewc main.sk --output-file=main.js --release.
Compiled JS
(function(){function c(){Deno.args.forEach(function(a){for(var b=RegExp('\\(\\)|{}|\\[]','g');a!==(a=a.replaceAll(b,'')););console.log(a)})}c()})();
To run:
deno run main.js '[(({})({)(()}]' '(){}[]'
Karax has the appeal that it is just Nim code, so there is no new syntax.