BGG Wiki - Revision History - TradeMaximizer

TradeMaximizer: - give link to unofficial build 1.4 and a little info on it

2009-11-05T17:31:18-06:00

From rossum 2008-10-07 08:29:32		To JeffyJeff 2009-11-05 17:31:18


	The current version is 1.3a, released on 7 March, 2008.		The current version is 1.3a, released on 7 March, 2008.
		+
		+	There is a pending version 1.4 with changes by [username=JeffyJeff] that adds other metric's that goes with the ITERATIONS option as well as options being recognized via command line.

	==Where can I get it?==		==Where can I get it?==

	The source code and pre-compiled packages can be downloaded from [http://sourceforge.net/projects/trademax SourceForge]. The source code is written in Java.		The source code and pre-compiled packages can be downloaded from [http://sourceforge.net/projects/trademax SourceForge]. The source code is written in Java.
		+
		+	The version with [username=JeffyJeff]'s changes (v1.4) has source code checked into sourceforge but not yet the pre-compiled package, for now you can obtain if from http://isomerica.net/~jeff/tm.jar (sources are also included right in the jar).

	==How do I run it?==		==How do I run it?==

	tm wants > results.txt		tm wants > results.txt
	</pre>		</pre>
		+
		+	If you are using v1.4 you can also give options and the name of the input file right on the command line such as:
		+
		+	<pre>
		+	java -jar tm.jar optinoal-options-here filename-or-url
		+	</pre>
		+
		+	for example:
		+
		+	<pre>
		+	java -jar tm.jar --iterations=200 http://bgg.activityclub.org/olwlg/46735-officialwants.txt
		+	</pre>
		+

	==How do priorities work?==		==How do priorities work?==

TradeMaximizer: - rm unused markup

2008-10-07T08:29:32-05:00

From JeffyJeff 2008-09-30 15:04:57		To rossum 2008-10-07 08:29:32

	To run '''TradeMaximizer''', follow these steps.		To run '''TradeMaximizer''', follow these steps.

-	1. Save the want lists in a file (eg, wants.txt) in the <tt>trademax</tt> folder.	+	1. Save the want lists in a file (eg, wants.txt) in the "trademax" folder.

	2. Open a shell (Unix) or command prompt (Windows) in the same folder, and run the command		2. Open a shell (Unix) or command prompt (Windows) in the same folder, and run the command

TradeMaximizer: - 1.3a is latest release, also list show-missing and show-elapsed-time options

2008-09-30T15:04:57-05:00

From warrenac 2008-05-29 14:17:15		To JeffyJeff 2008-09-30 15:04:57

	==What is the current version?==		==What is the current version?==

-	The current version is 1.2c, released on 8 September, 2007.	+	The current version is 1.3a, released on 7 March, 2008.

	==Where can I get it?==		==Where can I get it?==

	* SORT-BY-ITEM: Sort the item summary by item, instead of by username.		* SORT-BY-ITEM: Sort the item summary by item, instead of by username.
	* CASE-SENSITIVE: Treat item names as case-sensitive instead of converting all lowercase letters to uppercase.		* CASE-SENSITIVE: Treat item names as case-sensitive instead of converting all lowercase letters to uppercase.
		+	* SHOW-MISSING: Show items with missing want lists
		+	* SHOW-ELAPSED-TIME: show elapsed time

	* NONTRADE-COST=''num'': Adjust the cost of not trading an item from its default value of 1 billion to ''num''. The net effect is to forbid trade loops whose average cost per item exceeds ''num''. Note that this means that you can end up with less than the maximum number of trades. (Warning: this option is experimental and may be removed at some point.)		* NONTRADE-COST=''num'': Adjust the cost of not trading an item from its default value of 1 billion to ''num''. The net effect is to forbid trade loops whose average cost per item exceeds ''num''. Note that this means that you can end up with less than the maximum number of trades. (Warning: this option is experimental and may be removed at some point.)

TradeMaximizer: - Put the official names format in nowiki so the italics show up properly

2008-05-29T14:17:15-05:00

From JeffyJeff 2008-02-27 16:11:31		To warrenac 2008-05-29 14:17:15


	If desired, the moderator can declare official names for all non-dummy items. Want lists for non-dummy items ''not'' on this list will be flagged as errors. This helps catch errors in which users misspell their own item names. The format is		If desired, the moderator can declare official names for all non-dummy items. Want lists for non-dummy items ''not'' on this list will be flagged as errors. This helps catch errors in which users misspell their own item names. The format is
-	<pre>	+
-	#! <i>options</i>	+	<nowiki>
-	!BEGIN-OFFICIAL-NAMES	+	<tt>
-	<i>itemname1</i> <i>optional description</i>	+	#! <i>options</i><br>
-	...	+	!BEGIN-OFFICIAL-NAMES<br>
-	<i>itemnameK</i> <i>optional description</i>	+	<i>itemname1</i> <i>optional description</i><br>
-	!END-OFFICIAL-NAMES	+	...<br>
-	<i>wantlist1</i>	+	<i>itemnameK</i> <i>optional description</i><br>
-	...	+	!END-OFFICIAL-NAMES<br>
-	<i>wantlistN</i>	+	<i>wantlist1</i><br>
-	</pre>	+	...<br>
		+	<i>wantlistN</i><br>
		+	</tt>
		+	</nowiki>
		+
	The format is designed so that the moderator can simply cut-and-paste the official item names into the wantlist file.		The format is designed so that the moderator can simply cut-and-paste the official item names into the wantlist file.

TradeMaximizer: - SEED only relevant when ITERATIONS being used

2008-02-27T16:11:31-06:00

From zefquaavius 2008-02-14 11:04:27		To JeffyJeff 2008-02-27 16:11:31


	* ITERATIONS=''num'': How many times to run the main algorithm, keeping the solution with the smallest sum-of-squares metric.		* ITERATIONS=''num'': How many times to run the main algorithm, keeping the solution with the smallest sum-of-squares metric.
-	* SEED=''num'': Seed for the random-number generator, so that the results are repeatable.	+	* SEED=''num'': Seed for the random-number generator, so that the results are repeatable. This option is only applicable when ITERATIONS is also being used.

	* REQUIRE-COLONS: Make colons mandatory for every want list.		* REQUIRE-COLONS: Make colons mandatory for every want list.

TradeMaximizer: - Fixed typo.

2008-02-14T11:04:27-06:00

From Red Dragon 2007-09-13 00:34:03		To zefquaavius 2008-02-14 11:04:27

	and '''TradeMaximizer''' would know immediately that there was an error, because the colon was in the wrong place.		and '''TradeMaximizer''' would know immediately that there was an error, because the colon was in the wrong place.

-	2. You can add your username to the beginning your want list by surrounding it with parenthese, as in	+	2. You can add your username to the beginning your want list by surrounding it with parentheses, as in
	<pre>		<pre>
	(cokasaki) 1 2 3 4 5		(cokasaki) 1 2 3 4 5

TradeMaximizer: - minor glitch fixes

2007-09-13T00:34:03-05:00

From cokasaki 2007-09-09 22:07:26		To Red Dragon 2007-09-13 00:34:03

	1 2 3 4 5		1 2 3 4 5
	</pre>		</pre>
-	This means that item 1 wants any of the items 2, 3, 4, or 5. Note that if you do not see any items that your are willing to trade for, then you should submit a blank want list for your item, as it	+	This means that item 1 wants any of the items 2, 3, 4, or 5. Note that if you do not see any items that you are willing to trade for, then you should submit a blank want list for your item, such as
	<pre>		<pre>
	1		1
	</pre>		</pre>
-	This means that item 1 does not want anything.	+	This means that you will not accept anything for item 1.

	The order of the wanted items in the want list is irrelevant, unless the trade moderator has chosen to use priorities, in which case the items should be ordered from most wanted to least wanted.		The order of the wanted items in the want list is irrelevant, unless the trade moderator has chosen to use priorities, in which case the items should be ordered from most wanted to least wanted.

TradeMaximizer: - Version is now 1.2c

2007-09-09T22:07:26-05:00

From cokasaki 2007-09-08 09:11:57		To cokasaki 2007-09-09 22:07:26

	==What is the current version?==		==What is the current version?==

-	The current version is 1.2b, released on 7 September, 2007.	+	The current version is 1.2c, released on 8 September, 2007.

	==Where can I get it?==		==Where can I get it?==

TradeMaximizer: - Updated for version 1.2b

2007-09-08T09:11:57-05:00

From rossum 2007-08-27 12:23:11		To cokasaki 2007-09-08 09:11:57


	'''TradeMaximizer''' is a program for finding trades in [[Math Trades]], developed by [username=cokasaki]. Its main features are that it always finds the maximum number of trades possible, and that it does so very quickly (in seconds).		'''TradeMaximizer''' is a program for finding trades in [[Math Trades]], developed by [username=cokasaki]. Its main features are that it always finds the maximum number of trades possible, and that it does so very quickly (in seconds).
		+
		+	==What is the current version?==
		+
		+	The current version is 1.2b, released on 7 September, 2007.

	==Where can I get it?==		==Where can I get it?==

	* In TRIANGLE-PRIORITIES, cost = 1+2+...+rank = rank*(rank+1)/2.		* In TRIANGLE-PRIORITIES, cost = 1+2+...+rank = rank*(rank+1)/2.
	* In SQUARE-PRIORITIES, cost = rank*rank.		* In SQUARE-PRIORITIES, cost = rank*rank.
		+	* In SCALED-PRIORITIES, cost = 1 + (rank-1)*2520/number of wants.

	In the simplest case, rank is equal to the position of the item in the list. In other words, the first wanted item has rank 1, the second wanted item has rank 2, and so on.		In the simplest case, rank is equal to the position of the item in the list. In other words, the first wanted item has rank 1, the second wanted item has rank 2, and so on.

	* TRIANGLE-PRIORITIES: Use the 1,3,6,10,... priority scheme.		* TRIANGLE-PRIORITIES: Use the 1,3,6,10,... priority scheme.
	* SQUARE-PRIORITIES: Use the 1,4,9,16,... priority scheme.		* SQUARE-PRIORITIES: Use the 1,4,9,16,... priority scheme.
		+	* SCALED-PRIORITIES: Normalize priorities to the range 1..2521.
	* SMALL-STEP=''num'': Adjust how priorities change between successive entries in a want list.		* SMALL-STEP=''num'': Adjust how priorities change between successive entries in a want list.
	* BIG-STEP=''num'': Adjust how priorities change for each semicolon in a want list.		* BIG-STEP=''num'': Adjust how priorities change for each semicolon in a want list.

	* ALLOW-DUMMIES: Allow users to include dummy items to protect against getting duplicates.		* ALLOW-DUMMIES: Allow users to include dummy items to protect against getting duplicates.
		+
		+	* ITERATIONS=''num'': How many times to run the main algorithm, keeping the solution with the smallest sum-of-squares metric.
		+	* SEED=''num'': Seed for the random-number generator, so that the results are repeatable.

	* REQUIRE-COLONS: Make colons mandatory for every want list.		* REQUIRE-COLONS: Make colons mandatory for every want list.

	Note that the default priority scheme is not to use priorities (ie, the 1,1,1,... scheme). Also note that dummy items are not allowed unless the moderator explicitly says so.		Note that the default priority scheme is not to use priorities (ie, the 1,1,1,... scheme). Also note that dummy items are not allowed unless the moderator explicitly says so.

-	==What do the error messages mean?==	+	==What are official names?==

-	Coming soon...	+	If desired, the moderator can declare official names for all non-dummy items. Want lists for non-dummy items ''not'' on this list will be flagged as errors. This helps catch errors in which users misspell their own item names. The format is
		+	<pre>
		+	#! <i>options</i>
		+	!BEGIN-OFFICIAL-NAMES
		+	<i>itemname1</i> <i>optional description</i>
		+	...
		+	<i>itemnameK</i> <i>optional description</i>
		+	!END-OFFICIAL-NAMES
		+	<i>wantlist1</i>
		+	...
		+	<i>wantlistN</i>
		+	</pre>
		+	The format is designed so that the moderator can simply cut-and-paste the official item names into the wantlist file.

	==How does the algorithm work?==		==How does the algorithm work?==

TradeMaximizer: - punct

2007-08-27T12:23:11-05:00

From cokasaki 2007-08-27 06:17:46		To rossum 2007-08-27 12:23:11

	==What is TradeMaximizer?==		==What is TradeMaximizer?==

-	'''TradeMaximizer''' is a program for finding trades in [[Math Trades]], developed by [username=cokasaki]. It's main features are that it always finds the maximum number of trades possible, and that it does so very quickly (in seconds).	+	'''TradeMaximizer''' is a program for finding trades in [[Math Trades]], developed by [username=cokasaki]. Its main features are that it always finds the maximum number of trades possible, and that it does so very quickly (in seconds).

	==Where can I get it?==		==Where can I get it?==

TradeMaximizer: - Added link to SourceForge page

2007-08-27T06:17:46-05:00

From cokasaki 2007-08-24 14:54:39		To cokasaki 2007-08-27 06:17:46

	==Where can I get it?==		==Where can I get it?==

-	The source code is available on the [[TradeMaximizer Source Code]] page. The source code is written in Java.	+	The source code and pre-compiled packages can be downloaded from [http://sourceforge.net/projects/trademax SourceForge]. The source code is written in Java.
-		+
-	==How do I compile it?==	+
-		+
-	For now, you need to compile '''TradeMaximizer''' yourself. You will need a recent version of Java (1.6.0 or later).	+
-		+
-	1. Cut-and-paste the Java source code from the[[TradeMaximizer Source Code]] page. Save it in a file named TradeMaximizer.java.	+
-		+
-	2. Open a shell (Unix) or command prompt (Windows) in the same folder, and run the command	+
-	<pre>	+
-	javac TradeMaximizer.java	+
-	</pre>	+

	==How do I run it?==		==How do I run it?==

	To run '''TradeMaximizer''', follow these steps.		To run '''TradeMaximizer''', follow these steps.

-	1. Save the want lists in a file (eg, wants.txt) in the same folder as TradeMaximizer.java.	+	1. Save the want lists in a file (eg, wants.txt) in the <tt>trademax</tt> folder.

	2. Open a shell (Unix) or command prompt (Windows) in the same folder, and run the command		2. Open a shell (Unix) or command prompt (Windows) in the same folder, and run the command
	<pre>		<pre>
-	java TradeMaximizer < wants.txt	+	java -jar tm.jar < wants.txt
	</pre>		</pre>
-	If you get an error that says something like "NoClassDefFoundError", try	+	If you want to save the results to a file (eg, results.txt), run the command
	<pre>		<pre>
-	java -cp . TradeMaximizer < wants.txt	+	java -jar tm.jar < wants.txt > results.txt
	</pre>		</pre>
-	If you want to save the results to a file (eg, results.txt), run the command	+	There is a simple batch file for Windows users, so you can say shorten this to
		+	<pre>
		+	tm wants
		+	</pre>
		+	or
	<pre>		<pre>
-	java TradeMaximizer < wants.txt > results.txt	+	tm wants > results.txt
	</pre>		</pre>
-	(adding the "-cp ." if necessary).

	==How do priorities work?==		==How do priorities work?==

TradeMaximizer: - Changed syntax of usernames from @user to (user)

2007-08-24T14:54:39-05:00

From cokasaki 2007-08-21 13:10:29		To cokasaki 2007-08-24 14:54:39

	==What is TradeMaximizer?==		==What is TradeMaximizer?==

-	'''TradeMaximizer''' is a program for finding trades in a [[math trade]], developed by [username=cokasaki]. It's main features are that it always finds the maximum number of trades possible, and that it does so very quickly (in seconds).	+	'''TradeMaximizer''' is a program for finding trades in [[Math Trades]], developed by [username=cokasaki]. It's main features are that it always finds the maximum number of trades possible, and that it does so very quickly (in seconds).

	==Where can I get it?==		==Where can I get it?==

	1. Add username tags to all of your want lists (if you haven't already).		1. Add username tags to all of your want lists (if you haven't already).
	<pre>		<pre>
-	@cokasaki 005-HTMF : 197-CAYL 123-VEGA 078-VEGA 150-VEGA 026-TOCO	+	(cokasaki) 005-HTMF : 197-CAYL 123-VEGA 078-VEGA 150-VEGA 026-TOCO
-	@cokasaki 006-JENG : 197-CAYL 123-VEGA 078-VEGA 150-VEGA 026-TOCO	+	(cokasaki) 006-JENG : 197-CAYL 123-VEGA 078-VEGA 150-VEGA 026-TOCO
	</pre>		</pre>
-	(Username tags have the form "@''name''" and go at the beggining of the want list.)	+	Username tags have the form "(''name'')" and go at the beginning of the want list.

	2. Create a dummy item, named "%''something''", and add the set of duplicate items to the want list of the dummy item.		2. Create a dummy item, named "%''something''", and add the set of duplicate items to the want list of the dummy item.
	<pre>		<pre>
-	@cokasaki %VEGAS : 123-VEGA 078-VEGA 150-VEGA	+	(cokasaki) %VEGAS : 123-VEGA 078-VEGA 150-VEGA
	</pre>		</pre>

	3. Now remove the duplicate items from your regular want lists, and add the dummy item instead.		3. Now remove the duplicate items from your regular want lists, and add the dummy item instead.
	<pre>		<pre>
-	@cokasaki 005-HTMF : 197-CAYL %VEGAS 026-TOCO	+	(cokasaki) 005-HTMF : 197-CAYL %VEGAS 026-TOCO
-	@cokasaki 006-JENG : 197-CAYL %VEGAS 026-TOCO	+	(cokasaki) 006-JENG : 197-CAYL %VEGAS 026-TOCO
	</pre>		</pre>


	and '''TradeMaximizer''' would know immediately that there was an error, because the colon was in the wrong place.		and '''TradeMaximizer''' would know immediately that there was an error, because the colon was in the wrong place.

-	2. You can add your username to the beginning your want list by tagging it with the @ symbol, as in	+	2. You can add your username to the beginning your want list by surrounding it with parenthese, as in
	<pre>		<pre>
-	@cokasaki 1 2 3 4 5	+	(cokasaki) 1 2 3 4 5
	</pre>		</pre>
	Adding usernames makes the output more readable by bringing the results for all of your items together, even if the items were spread out. Usernames also helps '''TradeMaximizer''' detect certain kinds of errors.		Adding usernames makes the output more readable by bringing the results for all of your items together, even if the items were spread out. Usernames also helps '''TradeMaximizer''' detect certain kinds of errors.
		+
		+	Usernames are allowed to contain spaces, as in
		+	<pre>
		+	(John Doe) 1 2 3 4 5
		+	</pre>

	Note that usernames are mandatory in any want list involving dummy items.		Note that usernames are mandatory in any want list involving dummy items.

TradeMaximizer: - Clarified explanation of NONTRADE-COST

2007-08-21T13:10:29-05:00

From cokasaki 2007-08-20 19:55:38		To cokasaki 2007-08-21 13:10:29

	* CASE-SENSITIVE: Treat item names as case-sensitive instead of converting all lowercase letters to uppercase.		* CASE-SENSITIVE: Treat item names as case-sensitive instead of converting all lowercase letters to uppercase.

-	* NONTRADE-COST=''num'': Adjust the cost of not trading an item from its default value of 1 billion to ''num''. (Warning: this option is experimental and may be removed at some point.)	+	* NONTRADE-COST=''num'': Adjust the cost of not trading an item from its default value of 1 billion to ''num''. The net effect is to forbid trade loops whose average cost per item exceeds ''num''. Note that this means that you can end up with less than the maximum number of trades. (Warning: this option is experimental and may be removed at some point.)

	Note that the default priority scheme is not to use priorities (ie, the 1,1,1,... scheme). Also note that dummy items are not allowed unless the moderator explicitly says so.		Note that the default priority scheme is not to use priorities (ie, the 1,1,1,... scheme). Also note that dummy items are not allowed unless the moderator explicitly says so.

TradeMaximizer: - Added NONTRADE-COST option

2007-08-20T19:55:38-05:00

TradeMaximizer: - Added REQUIRE-COLONS and REQUIRE-USERNAMES options.

2007-08-19T18:22:40-05:00

From cokasaki 2007-08-19 10:00:07		To cokasaki 2007-08-19 18:22:40


	* ALLOW-DUMMIES: Allow users to include dummy items to protect against getting duplicates.		* ALLOW-DUMMIES: Allow users to include dummy items to protect against getting duplicates.
		+
		+	* REQUIRE-COLONS: Make colons mandatory for every want list.
		+	* REQUIRE-USERNAMES: Make usernames mandatory for every want list.

	* HIDE-LOOPS: Do not output the trade loops.		* HIDE-LOOPS: Do not output the trade loops.

TradeMaximizer: - Added section on formatting want lists.

2007-08-19T10:00:07-05:00

From cokasaki 2007-08-19 09:40:17		To cokasaki 2007-08-19 10:00:07

	==How should a want list be formatted?==		==How should a want list be formatted?==

-	Coming soon...	+	Each want list should be on a single line, even if that line is very long. In its simplest form, a want list is simply a list of item names (taken from the item summary published by the trade moderator) separated by spaces. For example,
		+	<pre>
		+	1 2 3 4 5
		+	</pre>
		+	This means that item 1 wants any of the items 2, 3, 4, or 5. Note that if you do not see any items that your are willing to trade for, then you should submit a blank want list for your item, as it
		+	<pre>
		+	1
		+	</pre>
		+	This means that item 1 does not want anything.
		+
		+	The order of the wanted items in the want list is irrelevant, unless the trade moderator has chosen to use priorities, in which case the items should be ordered from most wanted to least wanted.
		+
		+	There are three more notations you can add to your want list, if desired.
		+
		+	1. You can add a colon right after the very first item (the wanting item), as in
		+	<pre>
		+	1 : 2 3 4 5
		+	</pre>
		+	Spaces around the colon are optional. Adding a colon makes your want list slightly more readable, and allows '''TradeMaximizer''' to detect certain errors that could be catastrophic if left undetected. In particular, using colons prevents errors in which a line break was accidentally deleted, combining two want lists
		+	<pre>
		+	1 2 3 4 5
		+	6 7 8 9
		+	</pre>
		+	into a single want list
		+	<pre>
		+	1 2 3 4 5 6 7 8 9
		+	</pre>
		+	With colons, this would become
		+	<pre>
		+	1 : 2 3 4 5 6 : 7 8 9
		+	</pre>
		+	and '''TradeMaximizer''' would know immediately that there was an error, because the colon was in the wrong place.
		+
		+	2. You can add your username to the beginning your want list by tagging it with the @ symbol, as in
		+	<pre>
		+	@cokasaki 1 2 3 4 5
		+	</pre>
		+	Adding usernames makes the output more readable by bringing the results for all of your items together, even if the items were spread out. Usernames also helps '''TradeMaximizer''' detect certain kinds of errors.
		+
		+	Note that usernames are mandatory in any want list involving dummy items.
		+
		+	3. You can mix semicolons freely with the wanted items, as in
		+	<pre>
		+	1 2 3 ; 4 5
		+	</pre>
		+	Spaces around semicolons are optional.
		+
		+	Semicolons are only useful in a trade with priorities. The semicolons indicate gaps in your preferences. In this example, you are saying that there is a big gap between your preferences for items 2 and 3 and your preferences for items 4 and 5.
		+
		+	You can use multiple semicolons in a row to indicate even bigger gaps.

	==What do the error messages mean?==		==What do the error messages mean?==

TradeMaximizer: - Added info on dummy items.

2007-08-19T09:40:17-05:00

From cokasaki 2007-08-19 06:55:20		To cokasaki 2007-08-19 09:40:17

	==How does duplicate protection (dummy items) work?==		==How does duplicate protection (dummy items) work?==

-	Coming soon...	+	Suppose you are looking for Vegas Showdown in a math trade, and other people have put up several copies of it. If you have put up a single item in the math trade, then you can safely put all the copies of Vegas Showdown in your want list, as in
		+	<pre>
		+	005-HTMF : 197-CAYL 123-VEGA 078-VEGA 150-VEGA 026-TOCO
		+	</pre>
		+	However, suppose you are creating several want lists. If you put all the copies of Vegas Showdown in all of your want lists, as in
		+	<pre>
		+	005-HTMF : 197-CAYL 123-VEGA 078-VEGA 150-VEGA 026-TOCO
		+	006-JENG : 197-CAYL 123-VEGA 078-VEGA 150-VEGA 026-TOCO
		+	</pre>
		+	then you might end up with multiple copies of Vegas Showdown. In some situations, this would be okay, but in other situations, you would vastly prefer not to get multiple copies of the same game.
		+
		+	In '''TradeMaximizer''', you can protect against getting duplicates by adding a dummy wantlist, as follows:
		+
		+	1. Add username tags to all of your want lists (if you haven't already).
		+	<pre>
		+	@cokasaki 005-HTMF : 197-CAYL 123-VEGA 078-VEGA 150-VEGA 026-TOCO
		+	@cokasaki 006-JENG : 197-CAYL 123-VEGA 078-VEGA 150-VEGA 026-TOCO
		+	</pre>
		+	(Username tags have the form "@''name''" and go at the beggining of the want list.)
		+
		+	2. Create a dummy item, named "%''something''", and add the set of duplicate items to the want list of the dummy item.
		+	<pre>
		+	@cokasaki %VEGAS : 123-VEGA 078-VEGA 150-VEGA
		+	</pre>
		+
		+	3. Now remove the duplicate items from your regular want lists, and add the dummy item instead.
		+	<pre>
		+	@cokasaki 005-HTMF : 197-CAYL %VEGAS 026-TOCO
		+	@cokasaki 006-JENG : 197-CAYL %VEGAS 026-TOCO
		+	</pre>
		+
		+	Now at most one of your regular items can "win" the dummy item, and the dummy item can win at most one of the duplicate items, so you will receive at most one of the duplicates.
		+
		+	Some things to note about dummy items:
		+
		+	* Dummy items can only be used if the trade moderator has selected the ALLOW-DUMMIES option.
		+	* You must include a username tag in any want list that involves dummy items.
		+	* You can create as many dummy items as you want.
		+	* You cannot refer to anyone else's dummy items, nor can they refer to yours.
		+	* You can refer to one of your dummy items in the want list of another dummy item.
		+	* Dummy items are not included in the trade count, so they do not artificially inflate the number of trades.
		+	* In a trade with priorities, keep in mind that priorities are ignored in the want list for a dummy item. However, the priority of the dummy item in the want list for one of your regular items is handled normally.
		+	* Dummy items are elided from the trade output. For example, if 006-JENG received %VEGAS and %VEGAS received 123-VEGA, then the output would say that 006-JENG received 123-VEGA.

	==How should a want list be formatted?==		==How should a want list be formatted?==

TradeMaximizer: - Added instructions for "-cp ."

2007-08-19T06:55:20-05:00

From cokasaki 2007-08-18 23:00:23		To cokasaki 2007-08-19 06:55:20

	java TradeMaximizer < wants.txt		java TradeMaximizer < wants.txt
	</pre>		</pre>
-	If you want to save the results to a file, run the command	+	If you get an error that says something like "NoClassDefFoundError", try
		+	<pre>
		+	java -cp . TradeMaximizer < wants.txt
		+	</pre>
		+	If you want to save the results to a file (eg, results.txt), run the command
	<pre>		<pre>
	java TradeMaximizer < wants.txt > results.txt		java TradeMaximizer < wants.txt > results.txt
	</pre>		</pre>
		+	(adding the "-cp ." if necessary).

	==How do priorities work?==		==How do priorities work?==

TradeMaximizer: - No Comment

2007-08-18T23:00:23-05:00

From cokasaki 2007-08-18 22:55:12		To cokasaki 2007-08-18 23:00:23

	</pre>		</pre>
	item B has rank 1, item C has rank 2, and item D has rank 12, assuming the small-step value is 1 and the big-step value is 9. Notice that the gap in rank between items C and D is the small-step value plus the big-step value, not just the big-step value. If the small-step and big-step values were 0 and 100, respectively, then item C would have rank 1 and item D would have rank 101.		item B has rank 1, item C has rank 2, and item D has rank 12, assuming the small-step value is 1 and the big-step value is 9. Notice that the gap in rank between items C and D is the small-step value plus the big-step value, not just the big-step value. If the small-step and big-step values were 0 and 100, respectively, then item C would have rank 1 and item D would have rank 101.
		+
		+	Multiple semicolons in a row are allowed, as are semicolons before the first wanted item.

	==How does duplicate protection (dummy items) work?==		==How does duplicate protection (dummy items) work?==
		+
		+	Coming soon...

	==How should a want list be formatted?==		==How should a want list be formatted?==
		+
		+	Coming soon...
		+
		+	==What do the error messages mean?==
		+
		+	Coming soon...

	==What options are available?==		==What options are available?==

TradeMaximizer: - Added explanation of priorities.

2007-08-18T22:55:12-05:00

From DrChek 2007-08-18 22:09:41		To cokasaki 2007-08-18 22:55:12

	==What is TradeMaximizer?==		==What is TradeMaximizer?==

-	'''TradeMaximizer''' is a program finding trades in a [[math trade]]. It's main features are that it always finds the maximum number of trades possible, and that it does so very quickly (in seconds).	+	'''TradeMaximizer''' is a program for finding trades in a [[math trade]], developed by [username=cokasaki]. It's main features are that it always finds the maximum number of trades possible, and that it does so very quickly (in seconds).

	==Where can I get it?==		==Where can I get it?==


	==How do priorities work?==		==How do priorities work?==
		+
		+	By default, '''TradeMaximizer''' does not use priorities. The moderator can choose to use priorities by specifying a priority scheme as an option (eg, LINEAR-PRIORITIES).
		+
		+	When using priorities, each wanted item in a want list is assigned a certain cost, where lower cost means higher priority. The system then uses cost as a tie-breaker among different ways of achieving the maximum number of trades. In particular, it finds the set of trades that has the minimum total cost, where total cost is the sum of the costs of all the individual items traded.
		+
		+	All priority schemes begin by finding the ''rank'' of each wanted item in a want list. The cost is then calculated as a function of rank.
		+	* In LINEAR-PRIORITIES, cost = rank.
		+	* In TRIANGLE-PRIORITIES, cost = 1+2+...+rank = rank*(rank+1)/2.
		+	* In SQUARE-PRIORITIES, cost = rank*rank.
		+
		+	In the simplest case, rank is equal to the position of the item in the list. In other words, the first wanted item has rank 1, the second wanted item has rank 2, and so on.
		+
		+	The simple case can be altered in two ways. First, the moderator can set the SMALL-STEP=''num'' option. This sets how much the rank increases when you move from one position to the next. (By default, the small-step value is 1.)
		+
		+	Second, the user can include a semicolon in a want list. A semicolon says "increase the rank of the next item by the big-step value". (The big-step value is 9 by default, but can be set by the moderator using the BIG-STEP=''num'' option.)
		+
		+	For example, in the want list
		+	<pre>
		+	A : B C ; D
		+	</pre>
		+	item B has rank 1, item C has rank 2, and item D has rank 12, assuming the small-step value is 1 and the big-step value is 9. Notice that the gap in rank between items C and D is the small-step value plus the big-step value, not just the big-step value. If the small-step and big-step values were 0 and 100, respectively, then item C would have rank 1 and item D would have rank 101.

	==How does duplicate protection (dummy items) work?==		==How does duplicate protection (dummy items) work?==

TradeMaximizer: - Removed uneeded underscores

2007-08-18T22:09:41-05:00

From cokasaki 2007-08-18 22:07:25		To DrChek 2007-08-18 22:09:41

	==Where can I get it?==		==Where can I get it?==

-	The source code is available on the [[TradeMaximizer_Source_Code]] page. The source code is written in Java.	+	The source code is available on the [[TradeMaximizer Source Code]] page. The source code is written in Java.

	==How do I compile it?==		==How do I compile it?==

	For now, you need to compile '''TradeMaximizer''' yourself. You will need a recent version of Java (1.6.0 or later).		For now, you need to compile '''TradeMaximizer''' yourself. You will need a recent version of Java (1.6.0 or later).

-	1. Cut-and-paste the Java source code from the[[TradeMaximizer_Source_Code]] page. Save it in a file named TradeMaximizer.java.	+	1. Cut-and-paste the Java source code from the[[TradeMaximizer Source Code]] page. Save it in a file named TradeMaximizer.java.

	2. Open a shell (Unix) or command prompt (Windows) in the same folder, and run the command		2. Open a shell (Unix) or command prompt (Windows) in the same folder, and run the command

TradeMaximizer: - Changing to a FAQ-like format

2007-08-18T22:07:25-05:00

From cokasaki 2007-08-18 20:55:03		To cokasaki 2007-08-18 22:07:25

	[[toc]]		[[toc]]

-	'''TradeMaximizer''' is a program for finding the maximum number of trades in a [[math trade]].	+	==What is TradeMaximizer?==

-	==Source Code==	+	'''TradeMaximizer''' is a program finding trades in a [[math trade]]. It's main features are that it always finds the maximum number of trades possible, and that it does so very quickly (in seconds).

-	The source code has been moved to the [[TradeMaximizer_Source_Code]] page.	+	==Where can I get it?==

-	==Compiling and Running TradeMaximizer==	+	The source code is available on the [[TradeMaximizer_Source_Code]] page. The source code is written in Java.

-	For now, you need to compile '''TradeMaximizer''' yourself. To do this, you'll need to have Java 1.6 (or better) installed.	+	==How do I compile it?==
		+
		+	For now, you need to compile '''TradeMaximizer''' yourself. You will need a recent version of Java (1.6.0 or later).

	1. Cut-and-paste the Java source code from the[[TradeMaximizer_Source_Code]] page. Save it in a file named TradeMaximizer.java.		1. Cut-and-paste the Java source code from the[[TradeMaximizer_Source_Code]] page. Save it in a file named TradeMaximizer.java.

	javac TradeMaximizer.java		javac TradeMaximizer.java
	</pre>		</pre>
		+
		+	==How do I run it?==

	To run '''TradeMaximizer''', follow these steps.		To run '''TradeMaximizer''', follow these steps.

	</pre>		</pre>

-	==Instructions for Moderators==	+	==How do priorities work?==
		+
		+	==How does duplicate protection (dummy items) work?==
		+
		+	==How should a want list be formatted?==
		+
		+	==What options are available?==

	As a moderator, you'll need to decide what options to use for your math trade. Include the options at the top of the want-list file, on one or more lines starting with the characters "#!". For example,		As a moderator, you'll need to decide what options to use for your math trade. Include the options at the top of the want-list file, on one or more lines starting with the characters "#!". For example,

	Note that the default priority scheme is not to use priorities (ie, the 1,1,1,... scheme). Also note that dummy items are not allowed unless the moderator explicitly says so.		Note that the default priority scheme is not to use priorities (ie, the 1,1,1,... scheme). Also note that dummy items are not allowed unless the moderator explicitly says so.

-	==Instructions for Participants==	+	==How does it work?==

-	Coming soon!	+	(Compiled from a series of posts by [username=cokasaki])

-	==How It Works==
	Ok, here's how '''TradeMaximizer''' works.		Ok, here's how '''TradeMaximizer''' works.



	That's pretty much it for how '''TradeMaximizer''' works. The only major parts that I haven't explained are Dijkstra's algorithm, which is widely known, and [http://en.wikipedia.org/wiki/Skew_heap skew heaps], which are used as a [http://en.wikipedia.org/wiki/Priority_queue priority queue] by Dijkstra's algorithm (many other kinds of priority queues could be used instead).		That's pretty much it for how '''TradeMaximizer''' works. The only major parts that I haven't explained are Dijkstra's algorithm, which is widely known, and [http://en.wikipedia.org/wiki/Skew_heap skew heaps], which are used as a [http://en.wikipedia.org/wiki/Priority_queue priority queue] by Dijkstra's algorithm (many other kinds of priority queues could be used instead).
-		+
-	--[username=cokasaki]	+

TradeMaximizer: - Added instructions for moderators.

2007-08-18T20:55:03-05:00

From cokasaki 2007-08-18 20:27:11		To cokasaki 2007-08-18 20:55:03

	The source code has been moved to the [[TradeMaximizer_Source_Code]] page.		The source code has been moved to the [[TradeMaximizer_Source_Code]] page.

-	==Instructions==	+	==Compiling and Running TradeMaximizer==

	For now, you need to compile '''TradeMaximizer''' yourself. To do this, you'll need to have Java 1.6 (or better) installed.		For now, you need to compile '''TradeMaximizer''' yourself. To do this, you'll need to have Java 1.6 (or better) installed.

	java TradeMaximizer < wants.txt > results.txt		java TradeMaximizer < wants.txt > results.txt
	</pre>		</pre>
		+
		+	==Instructions for Moderators==
		+
		+	As a moderator, you'll need to decide what options to use for your math trade. Include the options at the top of the want-list file, on one or more lines starting with the characters "#!". For example,
		+	<pre>
		+	#! LINEAR-PRIORITIES ALLOW-DUMMIES
		+	...
		+	</pre>
		+	All options must be declared before the first real want list.
		+
		+	Here are the available options:
		+
		+	* LINEAR-PRIORITIES: Use the 1,2,3,4,... priority scheme.
		+	* TRIANGLE-PRIORITIES: Use the 1,3,6,10,... priority scheme.
		+	* SQUARE-PRIORITIES: Use the 1,4,9,16,... priority scheme.
		+	* SMALL-STEP=''num'': Adjust how priorities change between successive entries in a want list.
		+	* BIG-STEP=''num'': Adjust how priorities change for each semicolon in a want list.
		+
		+	* ALLOW-DUMMIES: Allow users to include dummy items to protect against getting duplicates.
		+
		+	* HIDE-LOOPS: Do not output the trade loops.
		+	* HIDE-SUMMARY: Do not output the item summary.
		+	* HIDE-NONTRADES: Do not include items that did not trade in the item summary.
		+	* HIDE-ERRORS: Do not output error messages (except for fatal errors).
		+	* HIDE-REPEATS: Do not output error messages when a want list includes the same item more than once.
		+	* HIDE-STATS: Do not output the result statistics (other than the number of trades).
		+	* SORT-BY-ITEM: Sort the item summary by item, instead of by username.
		+	* CASE-SENSITIVE: Treat item names as case-sensitive instead of converting all lowercase letters to uppercase.
		+
		+	Note that the default priority scheme is not to use priorities (ie, the 1,1,1,... scheme). Also note that dummy items are not allowed unless the moderator explicitly says so.
		+
		+	==Instructions for Participants==
		+
		+	Coming soon!

	==How It Works==		==How It Works==

TradeMaximizer: - Added instructions

2007-08-18T20:27:11-05:00

From cokasaki 2007-08-18 20:03:31		To cokasaki 2007-08-18 20:27:11

	[[toc]]		[[toc]]

-	==Instructions==	+	'''TradeMaximizer''' is a program for finding the maximum number of trades in a [[math trade]].
-		+
-	Coming soon!	+

	==Source Code==		==Source Code==

	The source code has been moved to the [[TradeMaximizer_Source_Code]] page.		The source code has been moved to the [[TradeMaximizer_Source_Code]] page.
		+
		+	==Instructions==
		+
		+	For now, you need to compile '''TradeMaximizer''' yourself. To do this, you'll need to have Java 1.6 (or better) installed.
		+
		+	1. Cut-and-paste the Java source code from the[[TradeMaximizer_Source_Code]] page. Save it in a file named TradeMaximizer.java.
		+
		+	2. Open a shell (Unix) or command prompt (Windows) in the same folder, and run the command
		+	<pre>
		+	javac TradeMaximizer.java
		+	</pre>
		+
		+	To run '''TradeMaximizer''', follow these steps.
		+
		+	1. Save the want lists in a file (eg, wants.txt) in the same folder as TradeMaximizer.java.
		+
		+	2. Open a shell (Unix) or command prompt (Windows) in the same folder, and run the command
		+	<pre>
		+	java TradeMaximizer < wants.txt
		+	</pre>
		+	If you want to save the results to a file, run the command
		+	<pre>
		+	java TradeMaximizer < wants.txt > results.txt
		+	</pre>

	==How It Works==		==How It Works==

TradeMaximizer: - No Comment

2007-08-18T20:03:31-05:00

From DrChek 2007-08-17 03:00:59		To cokasaki 2007-08-18 20:03:31

	[[toc]]		[[toc]]

-	==Source Code==	+	==Instructions==
-	Source code for Version 1.0 of '''TradeMaximizer''':	+

-	<pre>	+	Coming soon!
-	// TradeMaximizer.java	+
-	// Created by Chris Okasaki (cokasaki)	+
-	// Version 1.0 (15 August 2007): initial release	+

-	import java.io.*;	+	==Source Code==
-	import java.util.*;	+
-		+
-	public class TradeMaximizer {	+
-	public static void main(String[] args) { new TradeMaximizer().run(); }	+
-		+
-	final String version = "Version 1.0: 15 August 2007";	+
-		+
-	void run() {	+
-	System.out.println("TradeMaximizer " + version);	+
-	System.out.println();	+
-		+
-	List< String[] > wantLists = readWantLists();	+
-	if (wantLists == null) return;	+
-		+
-	buildGraph(wantLists);	+
-	if (errors.size() > 0) {	+
-	Collections.sort(errors);	+
-	System.out.println("ERRORS:");	+
-	for (String err : errors) System.out.println(err);	+
-	System.out.println();	+
-	}	+
-		+
-	findMatches();	+
-	displayMatches();	+
-	}	+
-		+
-	//////////////////////////////////////////////////////////////////////	+
-		+
-	List< String[] > readWantLists() {	+
-	try {	+
-	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));	+
-	List< String[] > wantLists = new ArrayList< String[] >();	+
-		+
-	for (;;) {	+
-	String line = in.readLine();	+
-	if (line == null) return wantLists;	+
-	if (line.matches("\s(#.)?")) continue; // blank line or comment line	+
-	wantLists.add(line.trim().split("\s+"));	+
-	}	+
-	}	+
-	catch(Exception e) {	+
-	System.out.println("Error reading want lists: " + e.getMessage());	+
-	System.exit(1);	+
-	return null;	+
-	}	+
-	}	+
-		+
-	//////////////////////////////////////////////////////////////////////	+
-		+
-	List< String > errors = new ArrayList< String >();	+
-		+
-	final long INFINITY = 1000000000000L;	+
-	final long NOTRADE = 1000000L;	+
-	final long UNIT = 1L;	+
-		+
-	int ITEMS; // the number of items being traded	+
-	String[] names;	+
-	int[][] wants; // wants[i][j] is the jth item wanted by item i	+
-	long[][] wantCost;	+
-	long[] cheapestWantCost;	+
-		+
-	void buildGraph(List< String[] > wantLists) {	+
-		+
-	ArrayList< String > nameList = new ArrayList< String >();	+
-	HashMap< String,Integer > nameMap = new HashMap< String,Integer >();	+
-		+
-	ArrayList< ArrayList< Integer > > wants = new ArrayList< ArrayList< Integer > >();	+
-	ArrayList< ArrayList< Long > > wantCost = new ArrayList< ArrayList< Long > >();	+
-	ArrayList< Long > cheapestWantCost = new ArrayList< Long >();	+
-		+
-	// create the nodes	+
-	for (int i = 0; i < wantLists.size(); i++) {	+
-	String[] list = wantLists.get(i);	+
-	assert list.length > 0;	+
-	String name = list[0];	+
-	if (nameMap.containsKey(name)) {	+
-	errors.add("**** Item " + name + " has multiple want lists--ignoring all but first. (Sometimes the result of an accidental line break in the middle of a want list.)");	+
-	wantLists.set(i, null);	+
-	}	+
-	else {	+
-	int node = ITEMS++;	+
-	nameMap.put(name,node);	+
-	nameList.add(name);	+
-	cheapestWantCost.add(NOTRADE);	+
-	wants.add(new ArrayList< Integer >());	+
-	wantCost.add(new ArrayList< Long >());	+
-		+
-	width = Math.max(width, name.length());	+
-	}	+
-	}	+
-		+
-	// create the edges	+
-	for (String[] list : wantLists) {	+
-	if (list == null) continue; // skip the duplicate lists	+
-	String fromName = list[0];	+
-	int fromNode = nameMap.get(fromName);	+
-		+
-	// add the "no-trade" edge to itself	+
-	wants.get(fromNode).add(fromNode);	+
-	wantCost.get(fromNode).add(NOTRADE);	+
-		+
-	for (int i = 1; i < list.length; i++) {	+
-	String toName = list[i];	+
-	int toNode = nameMap.containsKey(toName) ? nameMap.get(toName) : -1;	+
-	if (toNode == -1) {	+
-	errors.add("**** Unknown item " + toName + " appears in want list for " + fromName + ". (" + toName + " might be misspelled or its want list might be missing.)");	+
-	}	+
-	else if (fromNode == toNode) {	+
-	errors.add("**** Item " + toName + " appears in its own want list.");	+
-	}	+
-	else if (wants.get(fromNode).indexOf(toNode) != -1) {	+
-	errors.add("**** Item " + toName + " appears twice in want list for " + fromName + ".");	+
-	}	+
-	else {	+
-	wants.get(fromNode).add(toNode);	+
-	wantCost.get(fromNode).add(UNIT);	+
-	cheapestWantCost.set(toNode,UNIT);	+
-	}	+
-	}	+
-	}	+
-		+
-	this.names = new String[ITEMS];	+
-	this.wants = new int[ITEMS][];	+
-	this.wantCost = new long[ITEMS][];	+
-	this.cheapestWantCost = new long[ITEMS];	+
-		+
-	for (int i = 0; i < ITEMS; i++) {	+
-	this.names[i] = nameList.get(i);	+
-	this.cheapestWantCost[i] = cheapestWantCost.get(i).longValue();	+
-		+
-	this.wants[i] = new int[wants.get(i).size()];	+
-	this.wantCost[i] = new long[wantCost.get(i).size()];	+
-	for (int j = 0; j < wants.get(i).size(); j++) {	+
-	this.wants[i][j] = wants.get(i).get(j);	+
-	this.wantCost[i][j] = wantCost.get(i).get(j);	+
-	}	+
-	}	+
-	}	+
-		+
-	//////////////////////////////////////////////////////////////////////	+
-		+
-	int NONE = -1;	+
-	int[] match;	+
-	long[] price;	+
-	Heap[] heap;	+
-	int[] from;	+
-		+
-	int sinkFrom;	+
-	long sinkCost;	+
-	long[] matchCost;	+
-		+
-	void dijkstra() {	+
-	clearHeap();	+
-	Arrays.fill(heap,null);	+
-	Arrays.fill(from,NONE);	+
-	sinkFrom = NONE;	+
-	sinkCost = INFINITY;	+
-		+
-	for (int i = ITEMS; i < 2*ITEMS; i++)	+
-	heap[i] = insert(i,INFINITY);	+
-	for (int i = 0; i < ITEMS; i++)	+
-	heap[i] = insert(i, (match[i] == NONE) ? 0 : INFINITY);	+
-		+
-	while (!isEmpty()) {	+
-	Heap h = extractMin();	+
-	int id = h.id;	+
-	long cost = h.cost;	+
-	if (cost == INFINITY) break; // everything left is unreachable	+
-	if (id < ITEMS) {	+
-	for (int j = 0; j < wants[id].length; j++) {	+
-	int other = wants[id][j] + ITEMS;	+
-	if (other == match[id]) continue;	+
-	long c = price[id] + wantCost[id][j] - price[other];	+
-	if (cost + c < heap[other].cost) {	+
-	from[other] = id;	+
-	decreaseCost(heap[other],cost + c);	+
-	}	+
-	}	+
-	}	+
-	// id >= ITEMS	+
-	else if (match[id] == NONE) {	+
-	if (cost < sinkCost) {	+
-	sinkFrom = id;	+
-	sinkCost = cost;	+
-	}	+
-	}	+
-	else {	+
-	int other = match[id];	+
-	long c = price[id] - matchCost[other] - price[other];	+
-	assert c >= 0;	+
-	if (cost + c < heap[other].cost) {	+
-	from[other] = id;	+
-	decreaseCost(heap[other],cost + c);	+
-	}	+
-	}	+
-	}	+
-	}	+
-		+
-	void findMatches() {	+
-	int V = 2*ITEMS;	+
-	match = new int[V];	+
-	price = new long[V];	+
-	heap = new Heap[V];	+
-	from = new int[V];	+
-	matchCost = new long[ITEMS];	+
-		+
-	Arrays.fill(match,NONE);	+
-	for (int i = 0; i < ITEMS; i++) price[i+ITEMS] = cheapestWantCost[i];	+
-		+
-	for (int round = 0; round < V; round++) {	+
-	dijkstra();	+
-		+
-	// update the matching	+
-	int right = sinkFrom;	+
-	while (right != NONE) {	+
-	int left = from[right];	+
-		+
-	// unlink right and left from current matches	+
-	if (match[right] != NONE) match[match[right]] = NONE;	+
-	if (match[left] != NONE) match[match[left]] = NONE;	+
-		+
-	match[right] = left;	+
-	match[left] = right;	+
-		+
-	// update matchCost	+
-	int pos = 0;	+
-	while (wants[left][pos] != right-ITEMS) pos++;	+
-	matchCost[left] = wantCost[left][pos];	+
-		+
-	right = from[left];	+
-	}	+
-		+
-	// update the prices	+
-	for (int i = 0; i < V; i++) {	+
-	// if (heap[i].cost < INFINITY) price[i] += heap[i].cost;	+
-	price[i] += heap[i].cost;	+
-	}	+
-	}	+
-	}	+
-		+
-	//////////////////////////////////////////////////////////////////////	+
-		+
-	void displayMatches() {	+
-	int countTrades = 0;	+
-	for (int i = 0; i < ITEMS; i++)	+
-	if (match[i] != i+ITEMS) countTrades++;	+
-		+
-	System.out.println("FOUND " + countTrades + " TRADES");	+
-	System.out.println();	+
-	System.out.println("TRADE LOOPS:");	+
-	System.out.println();	+
-	List< String > summary = new ArrayList< String >();	+
-		+
-	boolean[] used = new boolean[ITEMS];	+
-		+
-	for (int i = 0; i < ITEMS; i++) {	+
-	if (used[i]) continue;	+
-	if (match[i] == i+ITEMS) {	+
-	summary.add(pad(names[i]) + " does not trade");	+
-	}	+
-	else {	+
-	for (int j = i; !used[j]; j = match[j] - ITEMS) {	+
-	used[j] = true;	+
-	assert match[j] != NONE;	+
-	int other = match[j] - ITEMS;	+
-	System.out.println(pad(names[j]) + " receives " + names[other]);	+
-	summary.add(pad(names[j]) + " receives " + names[other] + " and sends to " + names[match[j + ITEMS]]);	+
-	}	+
-	System.out.println();	+
-	}	+
-	}	+
-		+
-	Collections.sort(summary);	+
-	System.out.println("ITEM SUMMARY:");	+
-	System.out.println();	+
-	for (String item : summary) System.out.println(item);	+
-		+
-	System.out.println();	+
-	System.out.println(countTrades + " TRADES");	+
-		+
-	// long totalCost = 0;	+
-	// for (long cost : matchCost) totalCost += cost;	+
-	// System.out.println("Total Cost = " + totalCost);	+
-	}	+
-		+
-	int width = 1;	+
-	String pad(String name) {	+
-	while (name.length() < width) name += " ";	+
-	return name;	+
-	}	+
-		+
-	//////////////////////////////////////////////////////////////////////	+
-	// priority queues implemented as skew heaps	+
-		+
-	static class Heap {	+
-	int id;	+
-	long cost;	+
-	Heap left,right,parent;	+
-	Heap(int id,long cost) {	+
-	this.id = id;	+
-	this.cost = cost;	+
-	}	+
-	}	+
-		+
-	static Heap root = null;	+
-		+
-	static void clearHeap() { root = null; }	+
-	static boolean isEmpty() { return root==null; }	+
-		+
-	static Heap merge(Heap a,Heap b) {	+
-	if (a == null) return b;	+
-	if (b == null) return a;	+
-	if (b.cost < a.cost) { Heap tmp = a; a = b; b = tmp; }	+
-	{ Heap tmp = a.left; a.left = a.right; a.right = tmp; }	+
-	Heap left = merge(a.left,b);	+
-	if (left != null) left.parent = a;	+
-	a.left = left;	+
-	return a;	+
-	}	+
-		+
-	static Heap insert(int id,long cost) {	+
-	Heap h = new Heap(id,cost);	+
-	root = merge(h,root);	+
-	root.parent = null;	+
-	return h;	+
-	}	+
-		+
-	static void decreaseCost(Heap h,long cost) {	+
-	assert cost < h.cost;	+
-	h.cost = cost;	+
-	if (h == root \|\| cost >= h.parent.cost) return;	+
-	if (h == h.parent.left) h.parent.left = null;	+
-	else {	+
-	assert h == h.parent.right;	+
-	h.parent.right = null;	+
-	}	+
-	h.parent = null;	+
-	root = merge(root,h);	+
-	root.parent = null;	+
-	}	+
-		+
-	static Heap extractMin() {	+
-	Heap min = root;	+
-	root = merge(root.left,root.right);	+
-	if (root != null) root.parent = null;	+
-	return min;	+
-	}	+

-	}	+	The source code has been moved to the [[TradeMaximizer_Source_Code]] page.
-	</pre>	+

	==How It Works==		==How It Works==

TradeMaximizer: - added Wikipedia links

2007-08-17T03:00:59-05:00

From DrChek 2007-08-17 02:57:54		To DrChek 2007-08-17 03:00:59

	Although it is relatively straightforward to understand how prices work, it is extremely difficult to understand ''why'' they work to produce the desired result. I take no credit for inventing this part of the algorithm, which is a standard--albeit fairly obscure--algorithm in the computer science toolkit. My Eureka moment was in figuring out how to model the problem as a bipartite graph in such a way that the standard algorithm could be applied.		Although it is relatively straightforward to understand how prices work, it is extremely difficult to understand ''why'' they work to produce the desired result. I take no credit for inventing this part of the algorithm, which is a standard--albeit fairly obscure--algorithm in the computer science toolkit. My Eureka moment was in figuring out how to model the problem as a bipartite graph in such a way that the standard algorithm could be applied.

-	That's pretty much it for how '''TradeMaximizer''' works. The only major parts that I haven't explained are Dijkstra's algorithm, which is widely known (somebody posted a Wikipedia link earlier), and skew heaps, which are used as a priority queue by Dijkstra's algorithm (many other kinds of priority queues could be used instead).	+	That's pretty much it for how '''TradeMaximizer''' works. The only major parts that I haven't explained are Dijkstra's algorithm, which is widely known, and [http://en.wikipedia.org/wiki/Skew_heap skew heaps], which are used as a [http://en.wikipedia.org/wiki/Priority_queue priority queue] by Dijkstra's algorithm (many other kinds of priority queues could be used instead).

	--[username=cokasaki]		--[username=cokasaki]

TradeMaximizer: - Added explanation, TOC

2007-08-17T02:57:54-05:00

From cokasaki 2007-08-15 14:16:12		To DrChek 2007-08-17 02:57:54

-	Source code for Version 1.0 of TradeMaximizer:	+	[[toc]]
		+
		+	==Source Code==
		+	Source code for Version 1.0 of '''TradeMaximizer''':

	<pre>		<pre>

	}		}
	</pre>		</pre>
-		+
		+	==How It Works==
		+	Ok, here's how '''TradeMaximizer''' works.
		+
		+	First, split each item into two parts called ''nodes''. One node is called the ''receiving'' node and the other node is called the ''sending node''. For example, if a trade involved three items (1, 2, and 3) then there would be six nodes (1R, 1S, 2R, 2S, 3R, and 3S).
		+
		+	Now, for each want in the want lists, add a connection (called an [http://en.wikipedia.org/wiki/Edge_%28graph_theory%29 edge]) between the corresponding receiving and sending nodes. For example, if item 1 wanted item 2, then there would be an edge between nodes 1R and 2S.
		+
		+	Technically, this kind of structure is called a [http://en.wikipedia.org/wiki/Bipartite_graph bipartite graph]. A [http://en.wikipedia.org/wiki/Graph_%28mathematics%29 graph] is a set of nodes and edges, and bipartite means that the nodes can be partitioned into two groups, such that all of the edges go between the two groups (and no edges go between nodes in the same group). In this graph, the two groups are the receiving nodes and the sending nodes.
		+
		+	We will be trying to find a [http://en.wikipedia.org/wiki/Matching matching], which is a subset of the edges such that no node is touched by more than one edge. Each edge in the chosen matching will mean than the owner of the sending node sends the item to the owner of the receiving node. In our context, no item can be sent more than once, and no item will receive more than one item in exchange, so the limitations of a matching make sense.
		+
		+	Naturally, because we are trying to maximize the number of trades, we want a ''maximum matching'', which is a matching that contains as many edges as possible. However, there's a problem. A maximum matching does not guarantee trade loops. For example, a maximum matching might include the edges 1R-2S and 2R-3S. Here the owner of item 2 receives item 3, and sends his item to the owner of item 1. However, the owner of item 1 receives something without sending anything, and the owner of item 3 sends something without receiving.
		+
		+	To prevent this, we add a ''self edge'' between each receiving node and its corresponding sending node (eg, 1R-1S, 2R-2S, etc.). Now it is always possible to find a ''perfect matching'', which is a matching that contains every node in the graph. Any perfect matching corresponds to a valid set of trades. Each self edge chosen means that that item does not trade. All the remaining edges make up one or more trade loops.
		+
		+	This last point is key. One of the advantages of this algorithm is that it doesn't actually look for loops, which are pretty hard to deal with. Instead, it looks for matchings, which are much easier to deal with. But because of the way we've constructed the graph, matchings can automatically be turned into loops.
		+
		+	For example, suppose edge 1R-2S is in the matching. Then we look at what node 2R is connected to. Maybe it's connected to 1S, in which case we have a loop of two items. Or maybe it's connected to another node, say 7S. Then we look at what node 7R is connected to. Maybe it's connected to 1S, in which case we have a loop of three items. Or maybe it's connected to a fourth node. We can't continue like this forever (because we would run out of items), and we can't go back to one of the S nodes we've already visited (because that would mean that S-node was touched twice, which would mean it wasn't a matching), and we can't just stop (because that would mean it wasn't a '''perfect''' matching), so eventually we'll reach 1S and complete the trade loop.
		+
		+	Now, assign a cost to each edge: 1 to each of the "real" edges and 1 million to each of the self edges. Then we try to find the ''minimum-cost perfect matching''. To qualify as minimum cost, it must contain as few self edges as possible. In other words, it contains as many real edges as possible. Every additional real edge means an additional trade, so minimizing the cost means maximizing the number of trades.
		+
		+	Ok, so we're trying to find the minimum-cost perfect matching in a bipartite graph. The approach I took starts with an empty matching, and grows the matching by one edge at a time, until the matching is perfect (that is, until every node is matched).
		+
		+	Although it grows the matching by one edge at a time, that does not mean that it simply adds a new edge every time. No, it might change some of the existing edges along the way to adding the new edge. The idea is to find an ''augmenting path''.
		+
		+	An augmenting path starts at an unmatched receiving node and ends at an unmatched sending node. This could be a path of a single edge, in which case we simply add the new edge. However, the path can also be longer, in which case it alternates between edges that are not in the current matching and edges that are in the current matching. The edges that are not in the current matching go from a receiving node to a sending node, and the edges that are in the current matching go from a sending node back to its matched receiving node.
		+
		+	For example, suppose 1R and 3S are currently unmatched, but there is an edge between 2S and 4R in the current matching. If edges 1R-2S and 4R-3S are in the graph (just not in the current matching), then the augmenting path could be 1R-2S-4R-3S. Notice that the augmenting path always contains an odd number of edges.
		+
		+	Once we find the augmenting path, we flip the status of all its edges. In other words, we add the non-matching edges to the matching, and remove the currently matching edges from the matching. In the above example, we would add edges 1R-2S and 4R-3S to the matching and remove edge 2S-4R from the matching. Notice that we always add one more edge than we remove, so the size of the matching goes up by one. After doing this N times, where N is the number of items in the math trade, we'll have a perfect matching.
		+
		+	(As an aside, there is a small inefficiency in the 1.0 code. It actually loops 2N times, instead of just N times, trying to find augmenting paths. After the first N iterations, it won't be able to find any more augmenting paths, so the last N iterations are wasted.)
		+
		+	So we grow the matching by finding augmenting paths. But we don't want just any old augmenting path. Instead, at each stage, we want the mininimum-cost augmenting path. We find this minimum-cost path using [http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm Dijkstra's algorithm].
		+
		+	One confusing catch, however, is that the "costs" in the minimum-cost augmenting path are different from the normal costs on the edges. Instead, the costs used by Dijkstra's algorithm incorporate a notion of ''prices''.
		+
		+	First, we will only look for paths where all steps from a receiving node to a sending node are along an edge not in the current matching, and all steps from a sending node back to a receiving node are along an edge that is in the current matching.
		+
		+	The "costs" for these edges are modified by ''prices'' that are maintained for every node. The modified cost for a step from a receiving node R to a sending node S is the price of R ''plus the'' normal cost of the edge ''minus'' the price of S. The modified cost for an edge from a sending node S to a receiving node R is the price of S ''minus'' the normal cost of the edge ''minus'' the price of R. Even with the minuses, it will turn out that these modified costs will never be negative, which is important because Dijkstra's algorithm doesn't work with negative edges.
		+
		+	One way to think about the price of a node X is it is both the price that is charged to leave that node, and the reward that is given to enter that node. A reward is just a negative price. So if you are leaving node X and entering node Y, then the cost of the edge is modified by the price of X ''minus'' the price of Y.
		+
		+	Also note that, for edges currently in the matching, we subtract the normal edge cost instead of adding it, because that edge will be taken out of the matching if this path is chosen.
		+
		+	The prices are initialized as follows: All receiving nodes are initialized with price 0, and all sending nodes are initialized with a price equal to the cost of the cheapest edge entering that node. (This will be 1 if somebody wants that item, or 1 million if nobody wants the item, in which case the self edge will be the only edge entering that node.)
		+
		+	After each run of Dijkstra's algorithm to find the minimum-cost augmenting path, we update the matching (add the edges from the augmenting path that weren't in the matching, and removing the edges from the augmenting path that were in the matching).
		+
		+	We also update the prices for all the nodes. Dijkstra's algorithm will tell us, not only the minimum-cost path from an unmatched receiving node to an unmatched sending node, but also the minimum-cost path to every individual node in the graph (from any unmatched receiving node). Note that some nodes cannot be reached starting from an unmatched receiving node. The "minimum-cost" path to unreachable path will be considered to have an infinite cost. We update all of the prices by adding the cost of the minimum-cost path to each node to the price of that node. (We even do this for unreachable nodes, for which the minimum cost is infinite, so we need to be careful how we handle infinity.)
		+
		+	Although it is relatively straightforward to understand how prices work, it is extremely difficult to understand ''why'' they work to produce the desired result. I take no credit for inventing this part of the algorithm, which is a standard--albeit fairly obscure--algorithm in the computer science toolkit. My Eureka moment was in figuring out how to model the problem as a bipartite graph in such a way that the standard algorithm could be applied.
		+
		+	That's pretty much it for how '''TradeMaximizer''' works. The only major parts that I haven't explained are Dijkstra's algorithm, which is widely known (somebody posted a Wikipedia link earlier), and skew heaps, which are used as a priority queue by Dijkstra's algorithm (many other kinds of priority queues could be used instead).
		+
		+	--[username=cokasaki]

TradeMaximizer: - Fixing angle brackets, take 3.

2007-08-15T14:16:12-05:00

From cokasaki 2007-08-15 14:12:29		To cokasaki 2007-08-15 14:16:12

	System.out.println();		System.out.println();

-	List<String[]> wantLists = readWantLists();	+	List< String[] > wantLists = readWantLists();
	if (wantLists == null) return;		if (wantLists == null) return;


	//////////////////////////////////////////////////////////////////////		//////////////////////////////////////////////////////////////////////

-	List<String[]> readWantLists() {	+	List< String[] > readWantLists() {
	try {		try {
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
-	List<String[]> wantLists = new ArrayList<String[]>();	+	List< String[] > wantLists = new ArrayList< String[] >();

	for (;;) {		for (;;) {

	//////////////////////////////////////////////////////////////////////		//////////////////////////////////////////////////////////////////////

-	List<String> errors = new ArrayList<String>();	+	List< String > errors = new ArrayList< String >();

	final long INFINITY = 1000000000000L;		final long INFINITY = 1000000000000L;

	long[] cheapestWantCost;		long[] cheapestWantCost;

-	void buildGraph(List<String[]> wantLists) {	+	void buildGraph(List< String[] > wantLists) {

-	ArrayList<String> nameList = new ArrayList<String>();	+	ArrayList< String > nameList = new ArrayList< String >();
-	HashMap<String,Integer> nameMap = new HashMap<String,Integer>();	+	HashMap< String,Integer > nameMap = new HashMap< String,Integer >();

-	ArrayList< ArrayList<Integer> > wants = new ArrayList< ArrayList<Integer> >();	+	ArrayList< ArrayList< Integer > > wants = new ArrayList< ArrayList< Integer > >();
-	ArrayList< ArrayList<Long> > wantCost = new ArrayList< ArrayList<Long> >();	+	ArrayList< ArrayList< Long > > wantCost = new ArrayList< ArrayList< Long > >();
-	ArrayList< Long > cheapestWantCost = new ArrayList<Long>();	+	ArrayList< Long > cheapestWantCost = new ArrayList< Long >();

	// create the nodes		// create the nodes

	nameList.add(name);		nameList.add(name);
	cheapestWantCost.add(NOTRADE);		cheapestWantCost.add(NOTRADE);
-	wants.add(new ArrayList<Integer>());	+	wants.add(new ArrayList< Integer >());
-	wantCost.add(new ArrayList<Long>());	+	wantCost.add(new ArrayList< Long >());

	width = Math.max(width, name.length());		width = Math.max(width, name.length());

	System.out.println("TRADE LOOPS:");		System.out.println("TRADE LOOPS:");
	System.out.println();		System.out.println();
-	List<String> summary = new ArrayList<String>();	+	List< String > summary = new ArrayList< String >();

	boolean[] used = new boolean[ITEMS];		boolean[] used = new boolean[ITEMS];

TradeMaximizer: - Still trying to fix angle brackets.

2007-08-15T14:12:29-05:00

From cokasaki 2007-08-15 14:10:43

To cokasaki 2007-08-15 14:12:29

TradeMaximizer: - Fixed angle brackets.

2007-08-15T14:10:43-05:00

From cokasaki 2007-08-15 12:31:16

To cokasaki 2007-08-15 14:10:43

From cokasaki 2007-08-19 18:22:40		To cokasaki 2007-08-20 19:55:38


	You can use multiple semicolons in a row to indicate even bigger gaps.		You can use multiple semicolons in a row to indicate even bigger gaps.
-
-	==What do the error messages mean?==
-
-	Coming soon...

	==What options are available?==		==What options are available?==

	* SORT-BY-ITEM: Sort the item summary by item, instead of by username.		* SORT-BY-ITEM: Sort the item summary by item, instead of by username.
	* CASE-SENSITIVE: Treat item names as case-sensitive instead of converting all lowercase letters to uppercase.		* CASE-SENSITIVE: Treat item names as case-sensitive instead of converting all lowercase letters to uppercase.
		+
		+	* NONTRADE-COST=''num'': Adjust the cost of not trading an item from its default value of 1 billion to ''num''. (Warning: this option is experimental and may be removed at some point.)

	Note that the default priority scheme is not to use priorities (ie, the 1,1,1,... scheme). Also note that dummy items are not allowed unless the moderator explicitly says so.		Note that the default priority scheme is not to use priorities (ie, the 1,1,1,... scheme). Also note that dummy items are not allowed unless the moderator explicitly says so.

-	==How does it work?==	+	==What do the error messages mean?==
		+
		+	Coming soon...
		+
		+	==How does the algorithm work?==

	(Compiled from a series of posts by [username=cokasaki])		(Compiled from a series of posts by [username=cokasaki])

	For example, suppose edge 1R-2S is in the matching. Then we look at what node 2R is connected to. Maybe it's connected to 1S, in which case we have a loop of two items. Or maybe it's connected to another node, say 7S. Then we look at what node 7R is connected to. Maybe it's connected to 1S, in which case we have a loop of three items. Or maybe it's connected to a fourth node. We can't continue like this forever (because we would run out of items), and we can't go back to one of the S nodes we've already visited (because that would mean that S-node was touched twice, which would mean it wasn't a matching), and we can't just stop (because that would mean it wasn't a '''perfect''' matching), so eventually we'll reach 1S and complete the trade loop.		For example, suppose edge 1R-2S is in the matching. Then we look at what node 2R is connected to. Maybe it's connected to 1S, in which case we have a loop of two items. Or maybe it's connected to another node, say 7S. Then we look at what node 7R is connected to. Maybe it's connected to 1S, in which case we have a loop of three items. Or maybe it's connected to a fourth node. We can't continue like this forever (because we would run out of items), and we can't go back to one of the S nodes we've already visited (because that would mean that S-node was touched twice, which would mean it wasn't a matching), and we can't just stop (because that would mean it wasn't a '''perfect''' matching), so eventually we'll reach 1S and complete the trade loop.

-	Now, assign a cost to each edge: 1 to each of the "real" edges and 1 million to each of the self edges. Then we try to find the ''minimum-cost perfect matching''. To qualify as minimum cost, it must contain as few self edges as possible. In other words, it contains as many real edges as possible. Every additional real edge means an additional trade, so minimizing the cost means maximizing the number of trades.	+	Now, assign a cost to each edge: 1 to each of the "real" edges and 1 billion to each of the self edges. Then we try to find the ''minimum-cost perfect matching''. To qualify as minimum cost, it must contain as few self edges as possible. In other words, it contains as many real edges as possible. Every additional real edge means an additional trade, so minimizing the cost means maximizing the number of trades.

	Ok, so we're trying to find the minimum-cost perfect matching in a bipartite graph. The approach I took starts with an empty matching, and grows the matching by one edge at a time, until the matching is perfect (that is, until every node is matched).		Ok, so we're trying to find the minimum-cost perfect matching in a bipartite graph. The approach I took starts with an empty matching, and grows the matching by one edge at a time, until the matching is perfect (that is, until every node is matched).

	Also note that, for edges currently in the matching, we subtract the normal edge cost instead of adding it, because that edge will be taken out of the matching if this path is chosen.		Also note that, for edges currently in the matching, we subtract the normal edge cost instead of adding it, because that edge will be taken out of the matching if this path is chosen.

-	The prices are initialized as follows: All receiving nodes are initialized with price 0, and all sending nodes are initialized with a price equal to the cost of the cheapest edge entering that node. (This will be 1 if somebody wants that item, or 1 million if nobody wants the item, in which case the self edge will be the only edge entering that node.)	+	The prices are initialized as follows: All receiving nodes are initialized with price 0, and all sending nodes are initialized with a price equal to the cost of the cheapest edge entering that node. (This will be 1 if somebody wants that item, or 1 billion if nobody wants the item, in which case the self edge will be the only edge entering that node.)

	After each run of Dijkstra's algorithm to find the minimum-cost augmenting path, we update the matching (add the edges from the augmenting path that weren't in the matching, and removing the edges from the augmenting path that were in the matching).		After each run of Dijkstra's algorithm to find the minimum-cost augmenting path, we update the matching (add the edges from the augmenting path that weren't in the matching, and removing the edges from the augmenting path that were in the matching).