Longest path

longest.c

// https://x.com/matrix67/status/2012030625759576378

#include <stdio.h>

#define N 10

static int longest = 0;

static int
fit(int path[], int n, int v) {
	int i;
	for (i=0;i<n;i++) {
		if (v == path[i])
			return 0;
	}
	return 1;
}

static void
output(int path[]) {
	int i;
	int len = 0;
	for (i=2;i<=N;i++) {
		int diff = path[i] - path[i-1];
		if (diff < 0)
			diff = -diff;
		len += diff;
	}
	if (len > longest) {
		printf("(%d) : ", len);
		longest = len;
		for (i=1;i<=N;i++) {
			printf("%d ", path[i]);
		}
		printf("\n");
	}
}

static void
gen(int path[], int index) {
	int step;
	if (index & 1) {
		// bigger
		step = 1;
	} else {
		// smaller
		step = -1;
	}
	
	int last = path[index-1];
	int i;
	for (i=last + step; i>0 && i<=N; i+=step) {
		if (fit(path, index-1, i)) {
			path[index] = i;
			if (index == N) {
				output(path);
			} else {
				gen(path, index + 1);
			}
		}
	}
}

int
main() {
	int path[N+1] = { 0 };
	gen(path, 1);
	
	return 0;
}