Pouring Tanks

README

alexo@codedot:~/Documents/Projects/pour$ make
cc     pour.c   -o pour
sh solve.sh ./pour 5 8 2
Now 0   and   0.  Pouring SINK  to  LEFT.  We just got   0.
Now 5   and   0.  Pouring LEFT  to RIGHT.  We just got   5.
Now 0   and   5.  Pouring SINK  to  LEFT.  We just got   5.
Now 5   and   5.  Pouring LEFT  to RIGHT.  We just got   2.
sh solve.sh ./pour 3 4 2
Now 0   and   0.  Pouring SINK  to  LEFT.  We just got   0.
Now 3   and   0.  Pouring LEFT  to RIGHT.  We just got   3.
Now 0   and   3.  Pouring SINK  to  LEFT.  We just got   3.
Now 3   and   3.  Pouring LEFT  to RIGHT.  We just got   2.
sh solve.sh ./pour 6 10 3
Failed to solve.
alexo@codedot:~/Documents/Projects/pour$ 

Makefile

all: pour solve.sh
	sh solve.sh ./pour 5 8 2
	sh solve.sh ./pour 3 4 2
	sh solve.sh ./pour 6 10 3

clean:
	-rm -f pour *.tmp

pour.c

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

enum {
	LEFT, RIGHT, SINK
};

static tank[SINK], max[SINK], target;

static const char *name(tank)
{
	if (LEFT == tank)
		return "LEFT";
	else if (RIGHT == tank)
		return "RIGHT";
	else
		return "SINK";
}

static void pour(src, dst)
{
	static loop;
	int res;

	printf("Now %-3d and %3d.  ", tank[LEFT], tank[RIGHT]);

	printf("Pouring %-5s to %5s.  ", name(src), name(dst));
	if (SINK == src) {
		assert(dst < SINK);
		tank[dst] = max[dst];
		res = tank[!dst];
	} else if (SINK == dst) {
		assert(src < SINK);
		tank[src] = 0;
		res = tank[!src];
	} else {
		int avail;

		assert(src < SINK);
		assert(dst < SINK);
		avail = max[dst] - tank[dst];
		if (tank[src] > avail) {
			tank[dst] = max[dst];
			tank[src] -= avail;
			res = tank[src];
		} else {
			tank[dst] += tank[src];
			tank[src] = 0;
			res = tank[dst];
		}
	}

	printf("We just got ");
	if (!tank[RIGHT]) {
		if (tank[LEFT] == loop) {
			printf("a loop!\n");
			exit(EXIT_FAILURE);
		}
		if (!loop)
			loop = tank[LEFT];
	}
	printf("%3d.\n", res);
	if (target == res)
		exit(EXIT_SUCCESS);
}

static void rotate(dir)
{
	int left = !dir;
	int right = !left;

	assert(target > 0);
	assert(max[LEFT] < max[RIGHT]);
	assert(target < max[RIGHT]);
	assert(target != max[LEFT]);

	while (1) {
		if (!tank[left]) {
			pour(SINK, left);
			pour(left, right);
		}
		if (tank[right] == max[right]) {
			pour(right, SINK);
			pour(left, right);
		}
	}
}

main(argc, argv)
char *argv[];
{
	assert(argc > 3);
	max[LEFT] = atoi(argv[1]);
	max[RIGHT] = atoi(argv[2]);
	target = atoi(argv[3]);
	rotate(argv[4]);
	return 0;
}

solve.sh

[ $# -eq 4 ] || exit $?

if $* - >left.tmp && $* >right.tmp; then
	left=`wc -l <left.tmp`
	right=`wc -l <right.tmp`

	if [ "$left" -gt "$right" ]; then
		cat right.tmp
	else
		cat left.tmp
	fi
else
	printf "Failed to solve.\n"
fi

rm -f *.tmp