Guilds/Bastet/Our Two Scents Worth/Energy Graph - Revision history

Akiiki Bastet: /* Solving the Resin Map */

2010-09-18T05:21:40Z

Solving the Resin Map

Akiiki Bastet: /* Solving the Resin Map */

2010-09-18T05:11:58Z

Solving the Resin Map

Akiiki Bastet: /* SS1R1 */

2010-09-18T05:08:03Z

SS1R1

Akiiki Bastet: /* Solving the Resin Map */

2010-09-18T05:07:26Z

Solving the Resin Map

Akiiki Bastet: /* Nitty-Gritty */

2010-09-18T04:52:15Z

Nitty-Gritty

Akiiki Bastet: New page: == Solving the Resin Map == === Introduction === A number of fellow programmer-types have expressed interested in the domain problem of solving the incense resin map. This is a problem ...

2010-09-18T04:49:09Z

New page: == Solving the Resin Map == === Introduction === A number of fellow programmer-types have expressed interested in the domain problem of solving the incense resin map. This is a problem ...

New page

== Solving the Resin Map ==

=== Introduction ===

A number of fellow programmer-types have expressed interested in the domain problem of solving the incense resin map. This is a problem primer and some data to aid in that goal.

I'm inclined to solve the Resin map using a spring graph solving algorithm. This is complicated by the nature of the data we have and the the problem we're solving, so it's not as cut-and-dried as solving a normal graph. However, given the data I have collected and some initial discoveries to provide seed values, I think it can be solved best this way.

=== The Nature of the Problem ===

The graph we're trying to solve is the map of the Resin Plane of incense in Tale 4 Bastet. So there is an ideal solution, barring small numerical errors due to the rounding.

There are three types of points in the map. There are "start points", "resin points" and "stat points". When a batch of incense is started, it is randomly assigned one of the 12 start points on the plane as a working point. The user is then given a resin quality measurement and told which stat point (of 17) is closest. The quality measurement is (Q-D) where Q is some arbitrary base quality and D is the distance from the working point (which begins as a "Start point") to the named stat point.

As a resin is added, the working point moves in a straight line from the start point to the resin point in decreasing steps. (We ignore multiple resin types as an unnecessary complication right now) At each step the user is given a quality measurement which uses the same base Q value and reflects the distance to the nearest stat point, and the identity of that stat point.

A considerable amount of data has been collected using different starts and resins. We'll use this to regenerate the map.

=== How the Problem Deviates From a Traditional Spring Graph ===

Normally we use damped springs to solve graphs with dimensionless nodes connected by weighted edges of known value. This problem has a few differences:

There are effectively two entities in the graph we're solving: "Sticks" which are a series of nodes beginning at a "start point" and ending at a "resin point"; and "atoms" which are more traditional dimensionless nodes representing the "Stat points" we get measurements to. We can constrain the problem to keep these nodes collinear and regularly spaced according to a known formula.

Furthermore, the nature of the data means that any resin runs we do from a common start point will share the starting point, so these "sticks" share their zeroth node. Also, any data runs using the same resin will begin at different start points, but terminate in a common "resin point".

The values we have recorded are not distances to the atoms, but are arithmetically related to those distances. All the data from a single run uses the same Q value, so we need to relate these to determine actual distances.

Finally, the length of the stick is not known but needs to be determined. Luckily, the nodes are regularly spaced, so they will all compress or expand together.

=== Nitty-Gritty ===

I will designate the stat points - the atoms - as A1 A2 etc. I'll provide a legend to convert them to the stats for those of us not only looking at the pure math side of the problem. :) These are graph nodes in the traditional sense. There are no atom-atom edges. There are atom-stick edges.

I will designate sticks as SS1R1 as a code for which start point and resin they represent. Any sticks which share the "S#" designation, such as SS3R4, SS3R12 and SS3R7, all start from the same point; that is their zeroth node is the same. Similarly, any sticks which share the "R#" designation share their endpoint, which I refer to as the Rth node, or node R.

Nodes are regularly distributed along a stick. Node0 is one endpoint, and NodeR is the other. Nodek is at position

( 7 x Node0 + k x NodeR ) / ( 7 + k )

Each node on a stick will have a single edge connected to an atom. For sanity-checking purposes, it will always be the closest atom. The data for a stick will name the atom and give a value. The value is equal to (Q-D) where Q is an arbitrary value which is constant ''for this stick only'' and D is the distance from the node to the atom. To reiterate, for nodes 0, 1, 2, ... we will have values X0, X1, X2, ... where Xk = Q - Dk where Dk is the distance from Nodek of this stick to the atom.

@@ Line 111: / Line 111: @@
 |-
 | Node<sub>7</sub> || 487 || A<sub>2</sub>
 |}

@@ Line 81: / Line 81: @@
 |-
 | Node<sub>7</sub> || 220 || A<sub>1</sub>
 |}

@@ Line 53: / Line 53: @@
 The Sticks
-==== S<sub>S1</sub><sub>R1</sub> ====
+==== Stick S<sub>S1</sub><sub>R1</sub> ====
 Start point: STRconf
@@ Line 68: / Line 68: @@
 | Node<sub>0</sub> || 213 || A<sub>1</sub>
 |-
-| Node<sub>0</sub> || 273 || A<sub>1</sub>
+| Node<sub>1</sub> || 273 || A<sub>1</sub>
 |-
-| Node<sub>0</sub> || 318 || A<sub>1</sub>
+| Node<sub>2</sub> || 318 || A<sub>1</sub>
 |-
-| Node<sub>0</sub> || 314 || A<sub>1</sub>
+| Node<sub>3</sub> || 314 || A<sub>1</sub>
 |-
-| Node<sub>0</sub> || 285 || A<sub>1</sub>
+| Node<sub>4</sub> || 285 || A<sub>1</sub>
 |-
-| Node<sub>0</sub> || 259 || A<sub>1</sub>
+| Node<sub>5</sub> || 259 || A<sub>1</sub>
 |-
-| Node<sub>0</sub> || 238 || A<sub>1</sub>
+| Node<sub>6</sub> || 238 || A<sub>1</sub>
 |-
-| Node<sub>0</sub> || 220 || A<sub>1</sub>
+| Node<sub>7</sub> || 220 || A<sub>1</sub>
 |}

← Older revision		Revision as of 05:07, 18 September 2010
Line 39:		Line 39:
	( 7 × Node<sub>0</sub> + k × Node<sub>R</sub> ) / ( 7 + k )		( 7 × Node<sub>0</sub> + k × Node<sub>R</sub> ) / ( 7 + k )

−	Each node on a stick will have a single edge connected to an atom. For sanity-checking purposes, it will always be the closest atom. The data for a stick will name the atom and give a value. The value is equal to (Q-D) where Q is an arbitrary value which is constant ''for this stick only'' and D is the distance from the node to the atom. To reiterate, for nodes 0, 1, 2, ... we will have values X<sub>0</sub>, X<sub>1</sub>, X<sub>2</sub>, ... where X<sub>k</sub> = Q - D<sub>k</sub> where D<sub>k</sub> is the distance from Node<sub>k</sub> of this stick to the atom.	+	Each node on a stick will have a single edge connected to an atom. For sanity-checking purposes, it will always be the closest atom. The data for a stick will name the atom and give a value. The value is equal to (Q-D) where Q is an arbitrary value which is constant ''for this stick only'' and D is the distance from the node to the atom. To reiterate, for nodes 0, 1, 2, ... we will have values X<sub>0</sub>, X<sub>1</sub>, X<sub>2</sub>, ... where X<sub>k</sub> = Q - D<sub>k</sub> where D<sub>k</sub> is the distance from Node<sub>k</sub> of this stick to the atom.
		+
		+	Where a length is given, this is the Node<sub>0</sub> to Node<sub>R</sub> distance. Where a Q-value is given, this is the value we can use to calculate the accurate edge weights to atoms within this stick. These are usually pretty close approximations and will serve to help set up an initial state that is more likely to solve.
		+
		+	=== The Data ===
		+
		+	The atoms
		+	* A<sub>1</sub> = STRconf
		+	* A<sub>2</sub> = PERweak
		+	* A<sub>3</sub> = ENDconf
		+	* A<sub>4</sub> = FOCclum
		+	* A<sub>5</sub> = DEXfrag
		+
		+	The Sticks
		+	==== S<sub>S1</sub><sub>R1</sub> ====
		+	Start point: STRconf
		+
		+	Resin: Arconis
		+
		+	Length: ~478
		+
		+	Q value: ~336
		+
		+	Data:
		+	{\| border="1"
		+	\| Node \|\| Quality \|\| Atom
		+	\|-
		+	\| Node<sub>0</sub> \|\| 213 \|\| A<sub>1</sub>
		+	\|-
		+	\| Node<sub>0</sub> \|\| 273 \|\| A<sub>1</sub>
		+	\|-
		+	\| Node<sub>0</sub> \|\| 318 \|\| A<sub>1</sub>
		+	\|-
		+	\| Node<sub>0</sub> \|\| 314 \|\| A<sub>1</sub>
		+	\|-
		+	\| Node<sub>0</sub> \|\| 285 \|\| A<sub>1</sub>
		+	\|-
		+	\| Node<sub>0</sub> \|\| 259 \|\| A<sub>1</sub>
		+	\|-
		+	\| Node<sub>0</sub> \|\| 238 \|\| A<sub>1</sub>
		+	\|-
		+	\| Node<sub>0</sub> \|\| 220 \|\| A<sub>1</sub>
		+	\|}

@@ Line 37: / Line 37: @@
 Nodes are regularly distributed along a stick.  Node<sub>0</sub> is one endpoint, and Node<sub>R</sub> is the other.  Node<sub>k</sub> is at position
-( 7 x Node<sub>0</sub> + k x Node<sub>R</sub> ) / ( 7 + k )
+( 7 × Node<sub>0</sub> + k × Node<sub>R</sub> ) / ( 7 + k )
 Each node on a stick will have a single edge connected to an atom.  For sanity-checking purposes, it will always be the closest atom.  The data for a stick will name the atom and give a value.  The value is equal to (Q-D) where Q is an arbitrary value which is constant ''for this stick only'' and D is the distance from the node to the atom.  To reiterate, for nodes 0, 1, 2, ... we will have values X<sub>0</sub>, X<sub>1</sub>, X<sub>2</sub>, ...  where X<sub>k</sub> = Q - D<sub>k</sub> where D<sub>k</sub> is the distance from Node<sub>k</sub> of this stick to the atom.