The Counterfeit Coin Puzzle - Revision history

John: /* select_coins( +Part, +Coins, ?Sample, ?Residue, ?N ) */

2018-01-13T20:36:44Z

select_coins( +Part, +Coins, ?Sample, ?Residue, ?N )

← Older revision	Revision as of 20:36, 13 January 2018
(No difference)

John: partition/4 used to aid readability.

2017-11-23T22:52:54Z

partition/4 used to aid readability.

← Older revision		Revision as of 22:52, 23 November 2017
Line 147:		Line 147:
	<pre class="prolog">		<pre class="prolog">
	assay( Counterfeit, Coins0, Step, Branch, Coins ) :-		assay( Counterfeit, Coins0, Step, Branch, Coins ) :-
	~~WeighingDatum = weighing_data(InfoContent, Left, Right, Table),~~		step( Step, Left, Right, Table, Branches ),
	step( Step, Left, Right, Table, Branches ),		partition( Coins0, Left, Right, Table ),
	~~findall(~~		balance( Left, Right, Counterfeit, Result ),
	~~WeighingDatum,~~		draw_inferences( Result, Left, Right, Table, Coins ),
	~~valid_partition~~( Coins0~~, InfoContent~~, Left, Right, Table ),		branch( Result, Branches, Branch ).
	~~WeighingData~~
	),
	~~sort( WeighingData, OrderedWeighingData ),~~
	~~member( WeighingDatum, OrderedWeighingData ),~~
	balance( Left, Right, Counterfeit, Result ),
	draw_inferences( Result, Left, Right, Table, Coins ),
	branch( Result, Branches, Branch ).
	</pre>		</pre>

John: partition/4 defined to aid readability.

2017-11-23T22:48:53Z

partition/4 defined to aid readability.

← Older revision		Revision as of 22:48, 23 November 2017
Line 184:		Line 184:

	===Choosing which coins to weigh===		===Choosing which coins to weigh===

			====partition( +Coins, ?Left, ?Right, ?Table )====
			holds when <var>Coins</var> is partitioned into three collections:
			<var>Left</var> side, <var>Right</var> side and <var>Table</var>.

			Operationally, alternative valid partitions are selected in order of reducing
			information content.

			<pre class="prolog">
			partition( Coins, Left, Right, Table ) :-
			Partition = ptn(Info,Left,Right,Table),
			findall(
			Partition,
			valid_partition(Coins, Info, Left, Right, Table),
			Partitions
			),
			sort( Partitions, OrderedPartitions ),
			member( Partition, OrderedPartitions ).
			</pre>

	====valid_partition( +Coins, ?Content, ?Left, ?Right, ?Table )====		====valid_partition( +Coins, ?Content, ?Left, ?Right, ?Table )====

John: /* Definite Clause Grammar */

2017-02-21T14:58:26Z

Definite Clause Grammar

← Older revision		Revision as of 14:58, 21 February 2017
Line 333:		Line 333:
	==Definite Clause Grammar==		==Definite Clause Grammar==

	The following DCG ~~represents~~ the method for finding the counterfeit coin as a structured procedure.		The following DCG presents the method for finding the counterfeit coin as a structured procedure.

	<pre class="prolog">		<pre class="prolog">

John: /* solve_coins( +Counterfeit, ?Procedure ) */

2017-02-21T14:56:50Z

solve_coins( +Counterfeit, ?Procedure )

← Older revision		Revision as of 14:56, 21 February 2017
Line 102:		Line 102:

	====solve_coins( +Counterfeit, ?Procedure )====		====solve_coins( +Counterfeit, ?Procedure )====
	holds when <var>Procedure</var> can correctly identify the <var>Counterfeit</var> coin. Beginning with a ~~‘~~start~~’~~ collection, in which all the coins are untested, the <var>Procedure</var> comprises three ~~‘~~steps~~’. For each step, a weighing is made and a ‘branch’ is made in the <var>Procedure</var>, depending on the result of the weighing~~.		holds when <var>Procedure</var> can correctly identify the <var>Counterfeit</var> coin. Beginning with a ''start'' collection, in which all the coins are untested, the <var>Procedure</var> comprises three steps.

	~~After three steps~~, the <var>Procedure</var> ~~must have reached~~ the ~~‘end’ condition~~.		For each step, a weighing is made and a ''branch'' is made in the <var>Procedure</var>, depending on the result of the weighing.

	Finally, an assertion (redundant test) ensures that the <var>Procedure</var> has found the correct end condition.		After three steps, the <var>Procedure</var> must have reached the ''end'' condition.

			Finally, an assertion (redundant test) ensures that the <var>Procedure</var> has found the correct ''end'' condition.

	<pre class="prolog">		<pre class="prolog">

John: /* coins_puzzle( ?Procedure ) */

2017-02-20T14:03:54Z

coins_puzzle( ?Procedure )

← Older revision		Revision as of 14:03, 20 February 2017
Line 56:		Line 56:
	</pre>		</pre>

	A procedure is either ~~‘~~done~~’~~, identifying a particular coin and whether		A procedure is either ''done'', identifying a particular coin and whether
	it is heavy or light; or it is a ~~‘~~step~~’~~.		it is heavy or light, or it is a ''step''.

	A step defines the coins to be placed on the <var>Left</var> and		A ''step'' defines the coins to be placed on the <var>Left</var> and
	<var>Right</var> pans, with the residue remaining on the		<var>Right</var> pans, with the residue remaining on the
	<var>Table</var>, and three <var>Branches</var>, one of which will		<var>Table</var>, and three <var>Branches</var>, one of which will
Line 90:		Line 90:
	</pre>		</pre>

	A ~~‘~~coin collection~~’~~ comprises four ~~‘parts’~~ (subsets): the <code>known_true</code>, <code>not_heavy</code>, <code>not_light</code> and <code>untested</code> sets of coins.		A ''coin collection'' comprises four <code>part</code>s (subsets): the <code>known_true</code>, <code>not_heavy</code>, <code>not_light</code> and <code>untested</code> sets of coins.

	<pre class="prolog">		<pre class="prolog">

John: /* valid_partition( +Coins, ?Content, ?Left, ?Right, ?Table ) */

2017-01-24T16:10:51Z

valid_partition( +Coins, ?Content, ?Left, ?Right, ?Table )

← Older revision		Revision as of 16:10, 24 January 2017
Line 193:		Line 193:
	* <var>Left</var> and <var>Right</var> must have the same number of coins (at least one);		* <var>Left</var> and <var>Right</var> must have the same number of coins (at least one);
	* <var>Left</var> cannot contain any known_true coins, because adding true coins to both sides creates redundant comparisons;		* <var>Left</var> cannot contain any known_true coins, because adding true coins to both sides creates redundant comparisons;
	* Comparisons between mixtures of coins where only the choice of pans is different are equivalent; so a partial order (≥) on mixtures of coins is used to eliminate some redundant comparisons.		* Comparisons between mixtures of coins where only the choice of pans is different are equivalent, so a partial order (≥) on mixtures of coins is used to eliminate some redundant comparisons.

	<pre class="prolog">		<pre class="prolog">

John: /* assay( +Counterfeit, +Coins0, ?Step, ?Branch, ?Coins1 ) */

2017-01-24T16:08:01Z

assay( +Counterfeit, +Coins0, ?Step, ?Branch, ?Coins1 )

← Older revision		Revision as of 16:08, 24 January 2017
Line 137:		Line 137:

	====assay( +Counterfeit, +Coins0, ?Step, ?Branch, ?Coins1 )====		====assay( +Counterfeit, +Coins0, ?Step, ?Branch, ?Coins1 )====
	holds when the appropriate <var>Branch</var> from <var>Step</var> is chosen by comparing the weights of two coin collections taken from the full set of coins: <var>Coins0</var>. <var>Coins1</var> is the full set of coins, updated with the inferences drawn from the weighing. <var>Counterfeit</var> is used to determine the result of the weighing.		holds when the appropriate <var>Branch</var> from <var>Step</var> is chosen by comparing the weights of two coin collections taken from the full set of coins: <var>Coins0</var>. <var>Coins1</var> is the full set of coins updated with the inferences drawn from the weighing, where <var>Counterfeit</var> is used to determine the result of the weighing.

	This predicate applies the critical insight into the solution of this puzzle: we have 24 (12 × 2) possible inputs to the procedure, with only 27 (3 × 3 × 3) possible outcomes from the weighings.		This predicate applies the critical insight into the solution of this puzzle: we have 24 (12 × 2) possible inputs to the procedure, with only 27 (3 × 3 × 3) possible outcomes from the weighings.

John: /* select_coins( +Part, +Coins, ?Sample, ?Residue, ?N ) */

2017-01-05T20:52:02Z

select_coins( +Part, +Coins, ?Sample, ?Residue, ?N )

← Older revision		Revision as of 20:52, 5 January 2017
Line 499:		Line 499:

	<pre class="prolog">		<pre class="prolog">

	:- ensure_loaded( misc ).		:- ensure_loaded( misc ).

	</pre>		</pre>

Line 507:		Line 505:

	<pre class="prolog">		<pre class="prolog">

	:- use_module( library(ordsets), [ord_union/2,ord_union/3] ).		:- use_module( library(ordsets), [ord_union/2,ord_union/3] ).

	</pre>		</pre>

John: Remove broken syntax highlighting

2017-01-05T20:50:24Z

Remove broken syntax highlighting

Show changes