bridge.c

/* https://www.youtube.com/watch?v=7yDmGnA8Hw0 */
#include <stdio.h>
#define	LEN 4

int slowest (int *p) {
	return (p[0] > p[1]) ? p[0] : p[1];
}

int try (int *side1, int *side2, int index, int time) {
	// using current and other for readability purposes
	int *current, *other;

	int i,min,ctime,j,k,d,ret;
	int p[2],v[2];

	if (time >= 17) {
		for(i=0;i<LEN;i++) {
			if (side1[i]) {
				return 0;
			}
		}
		return (time == 17);
	}

	if (!(index % 2)) {
		// saving people
		current = side1;
		other = side2;

		// all possible groups of 2 elements
		// (technically, also sending 1 person at a time should 
		// be allowed but because of (1) and (2), there is
		// no point in studying those cases
		/*
		((1) and (2) assume that all people should be moved
		from side 1 to side 2)

		(1) Assuming a on side 1, b on side 2
		At least t_b has passed for b to be on side 2
		Sending a to side 2 requires t_a, and sending
		b back requires t_b: eventually, at least
		2*t_b + t_a has elapsed, for an operation that
		could be done in t_a: not efficient!

		(2) Because of (1), there is no point in sending a 
		single person forward when 2+ people can proceed. 
		Moreover, there is no useful scenario where a single
		person is left on side 1 to cross: since the person
		would need to have the lantern, it means that said
		person would have had to cross the bridge back alone
		for no purpose: this is not a useful case and should
		not be considered.

		*/
		for (i=0;i<LEN;i++) {
			for (j=0;j<LEN;j++) {
				if (current[i] && current[j] && i != j) {
					p[0] = current[i];
					p[1] = current[j];
					current[i] = 0;
					current[j] = 0;
					for (k=0,d=0;k<LEN;k++) {
						if (!other[k]) {
							other[k] = p[d];
							v[d++] = k;
							if (d == 2) break;
						}
					}
					if (try (side1, side2, index+1, time + slowest(p))) {
						printf ("Sending forward %d %d\n",p[0],p[1]);
						return 1;
					}
					current[i] = p[0];
					current[j] = p[1];
					other[v[0]] = 0;
					other[v[1]] = 0;
				}

			}
		}
	}
	else {
		// bringing people back
		current = side2;
		other = side1;

		// always send the fastest one back!
		min = 0;
		for (i=1;i<LEN;i++) {
			if (current[i] < current[min] && current[i]) {
				min = i;
			}
		}
		for (i=0;i<LEN;i++) {
			if (!other[i]) {
				other[i] = current[min];
				break;
			}
		}
		ctime = current[min];
		current[min] = 0;
		if (try (side1, side2, index+1, time + ctime)) {
			printf ("Sending back %d\n",ctime);
			return 1;
		}
		// since this is the only option allowed when
		// going back, il simply returns 0 at this point
	}
	return 0;
}

int main () {
	int side1[] = {1,2,5,10};
	int side2[] = {0,0,0,0};

	try (side1, side2, 0, 0);
}