/*
 * chameleon.spin: mechanical proof for problem involving 54 chameleons,
 *	20 red, 18 blue, and 16 green.  When two chameleons of different
 *	colors meet, they both turn to the third color.  Can any sequence
 *	of such color changes result in all chameleons being the same
 *	color?  May 2009 CACM, page 112.
 *
 * Build and run as follows:
 *
 *	spin -a chameleon.spin
 *	cc -DSAFETY -o pan pan.c
 *	./pan
 *
 * This model detects the goal of all chameleons being the same color
 * with a set of assert() statements, so an "error free" run would indicate
 * that this goal is impossible.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 *
 * Copyright (c) 2009 Paul E. McKenney, IBM Corporation.
 */

/* Promela validation variables. */

byte r = 20;	/* Red chameleons. */
byte b = 18;	/* Blue chameleons. */
byte g = 16;	/* Green chameleons. */

/* Model the colony. */

init {
	do
	:: r > 0 && b > 0 -> /* Red and blue meet, turn green. */
		r = r - 1;
		b = b - 1;
		g = g + 2;
		assert(r > 0 || b > 0);
	:: r > 0 && g > 0 -> /* Red and green meet, turn blue. */
		r = r - 1;
		g = g - 1;
		b = b + 2;
		assert(r > 0 || g > 0);
	:: b > 0 && g > 0 -> /* Blue and green meet, turn red. */
		b = b - 1;
		g = g - 1;
		r = r + 2;
		assert(b > 0 || g > 0);
	od;
}