Project Euler/227 - Revision history

Unknown user: /* Solution */

2025-04-19T23:16:37Z

Solution

← Older revision		Revision as of 23:16, 19 April 2025
Line 282:		Line 282:
	I thought the slow part was inverting using gaussian elimination, but re-implementing it as an AX=B linear system and solving with LU took almost twice as long		I thought the slow part was inverting using gaussian elimination, but re-implementing it as an AX=B linear system and solving with LU took almost twice as long

	Checking posts, first person to solve it did it in 0.1 seconds in C++ (??) - utilized multiple tricks. 6 die faces -> 3 outcomes. 2 rolls -> 1 event. (and a wildly different approach.)		Checking posts, first person to solve it did it in 0.1 seconds in C++ (??) in 2009 - utilized multiple tricks. 6 die faces -> 3 outcomes. 2 rolls -> 1 event. (and a wildly different approach.)

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Solution */

2025-04-19T23:16:06Z

Solution

← Older revision		Revision as of 23:16, 19 April 2025
Line 282:		Line 282:
	I thought the slow part was inverting using gaussian elimination, but re-implementing it as an AX=B linear system and solving with LU took almost twice as long		I thought the slow part was inverting using gaussian elimination, but re-implementing it as an AX=B linear system and solving with LU took almost twice as long

	Checking posts, first person to solve it did it in 0.1 seconds in C++ (??) - utilized multiple tricks. 6 die faces -> 3 outcomes. 2 rolls -> 1 event.		Checking posts, first person to solve it did it in 0.1 seconds in C++ (??) - utilized multiple tricks. 6 die faces -> 3 outcomes. 2 rolls -> 1 event. (and a wildly different approach.)

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Flags */

2025-04-19T23:15:48Z

Flags

← Older revision		Revision as of 23:15, 19 April 2025
Line 275:		Line 275:
	* Rather than inverting I-Q directly, use iterative methods (more efficient for large sparse)		* Rather than inverting I-Q directly, use iterative methods (more efficient for large sparse)
	* Better yet, solve (I-Q) X = 1 using an AX=B solver		* Better yet, solve (I-Q) X = 1 using an AX=B solver

			==Solution==

			Took 1687 seconds (28 minutes)

			I thought the slow part was inverting using gaussian elimination, but re-implementing it as an AX=B linear system and solving with LU took almost twice as long

			Checking posts, first person to solve it did it in 0.1 seconds in C++ (??) - utilized multiple tricks. 6 die faces -> 3 outcomes. 2 rolls -> 1 event.

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Computing Fundamental Matrix */

2025-04-19T20:25:54Z

Computing Fundamental Matrix

← Older revision		Revision as of 20:25, 19 April 2025
Line 270:		Line 270:
	return N		return N
	</pre>		</pre>

			A few optimization ideas:
			* Sparse matrix representation for Q
			* Rather than inverting I-Q directly, use iterative methods (more efficient for large sparse)
			* Better yet, solve (I-Q) X = 1 using an AX=B solver

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Building Fundamental Matrix */

2025-04-19T20:20:02Z

Building Fundamental Matrix

← Older revision		Revision as of 20:20, 19 April 2025
Line 148:		Line 148:
	'''The expected number of steps until absorption, starting from each transient state, can be obtained by summing across the rows of N. This is because the expected number of steps is the sum of the expected number of visits to each transient state.'''		'''The expected number of steps until absorption, starting from each transient state, can be obtained by summing across the rows of N. This is because the expected number of steps is the sum of the expected number of visits to each transient state.'''

	===~~Building~~ Fundamental Matrix===		===Computing Fundamental Matrix===

	For large number of players, we need a procedure to assemble Q and use it to calculate N.		For large number of players, we need a procedure to assemble Q and use it to calculate N.
Line 258:		Line 258:

	return Q		return Q
			</pre>

			Now going from Q to N uses the formula above:

			<pre>
			function computeFundamentalMatrix(Q):
			size = Q.rows
			I = new Identity Matrix(size)
			difference = I - Q
			N = inverse(difference)
			return N
	</pre>		</pre>

Unknown user: /* Building Fundamental Matrix */

2025-04-19T20:06:42Z

Building Fundamental Matrix

@@ Line 155: / Line 155: @@
 There are n(n-1) transient states: all pairs <math>(i,j), i \neq j</math>
 ==Flags==
 {{ProjectEulerFlag}}

Unknown user: /* Fundamental Matrix */

2025-04-19T19:30:48Z

Fundamental Matrix

← Older revision		Revision as of 19:30, 19 April 2025
Line 147:		Line 147:

	'''The expected number of steps until absorption, starting from each transient state, can be obtained by summing across the rows of N. This is because the expected number of steps is the sum of the expected number of visits to each transient state.'''		'''The expected number of steps until absorption, starting from each transient state, can be obtained by summing across the rows of N. This is because the expected number of steps is the sum of the expected number of visits to each transient state.'''

			===Building Fundamental Matrix===

			For large number of players, we need a procedure to assemble Q and use it to calculate N.

			For n players, there are n absorbing states <math>(0,0), (1,1), \dots, (n-1,n-1)</math>

			There are n(n-1) transient states: all pairs <math>(i,j), i \neq j</math>

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Markov Insights */

2025-04-19T19:28:40Z

Markov Insights

← Older revision		Revision as of 19:28, 19 April 2025
Line 47:		Line 47:
	Switching to a compiled language like Java should help, as should implementing multi-threading. But because the game is so simple - just modular arithmetic with pointers - it doesn't seem like there is a whole lot of places to look for other optimizations.		Switching to a compiled language like Java should help, as should implementing multi-threading. But because the game is so simple - just modular arithmetic with pointers - it doesn't seem like there is a whole lot of places to look for other optimizations.

	===Markov Insights===		==Markov Insights==

	Denote the Markov state as <math>(i, j)</math>, where <math>i, j \in \{0, 1, 2, 3\}</math>		Denote the Markov state as <math>(i, j)</math>, where <math>i, j \in \{0, 1, 2, 3\}</math>
Line 83:		Line 83:
	In other words, we have a large system of equations.		In other words, we have a large system of equations.

	~~...~~		===System of Equations for Expected Number of Rounds===

	Suppose we have 4 players. Then the expression for E[0, 2], which is the starting state of player 0 and player 2 sitting across the table from each other with the die, would be		Suppose we have 4 players. Then the expression for E[0, 2], which is the starting state of player 0 and player 2 sitting across the table from each other with the die, would be
Line 99:		Line 99:
	* b/c there are two players, transition probability is the product of the two die probabilities		* b/c there are two players, transition probability is the product of the two die probabilities

	~~...~~		===Fundamental Matrix of Markov Chain===

	To make this easier, we can utilize the fundamental matrix of the Markov Chain.		To make this easier, we can utilize the fundamental matrix of the Markov Chain.
Line 134:		Line 134:
	I is an r x r identity matrix, representing absorbing states staying in themselves		I is an r x r identity matrix, representing absorbing states staying in themselves

	~~...~~		The transition probability matrix P covers all states (transient and absorbing), so its size is (t + r) x (t + r)

	~~The transition probability matrix covers all states, but the fundamental matrix only covers transient states.~~		===Fundamental Matrix===

	Fundamental matrix N is defined as:		Fundamental matrix N is defined as:
Line 142:		Line 142:
	N = (I - Q)^(-1)		N = (I - Q)^(-1)

	where I is the t x t identity matrix. (Matrix inversion is well-defined as long as all states are either transient or absorbing.)		where Q is the t x t matrix of transition probabilities between transient states, I is the t x t identity matrix. (Matrix inversion is well-defined as long as all states are either transient or absorbing.)

	~~Entry~~ N(i,j) represents the expected number of times the Markov chain will visit state j when starting from state i, before being absorbed.		The entry N(i,j) represents the expected number of times the Markov chain will visit state j when starting from state i, before being absorbed.

	'''The expected number of steps until absorption, starting from each transient state, can be obtained by summing across the rows of N. This is because the expected number of steps is the sum of the expected number of visits to each transient state.'''		'''The expected number of steps until absorption, starting from each transient state, can be obtained by summing across the rows of N. This is because the expected number of steps is the sum of the expected number of visits to each transient state.'''

Unknown user at 19:14, 19 April 2025

2025-04-19T19:14:50Z

← Older revision		Revision as of 19:14, 19 April 2025
Line 61:		Line 61:
	Let E(i,j) be expected number of additional rounds starting from state (i,j) until a player loses (absorbing state)		Let E(i,j) be expected number of additional rounds starting from state (i,j) until a player loses (absorbing state)

	We can think about E(i,j) as a recursive expression.		We can think about E(i,j) as being kind of like a recursive expression.

	The base case are the absorbing states, where the expected number of additional rounds is 0		The "base" case are the absorbing states, where the expected number of additional rounds is 0

	<math>		<math>
Line 69:		Line 69:
	</math>		</math>

	The recursive case are the transient (non-absorbing) states, where the expected number of additional rounds is		The "recursive" case are the transient (non-absorbing) states, where the expected number of additional rounds is

	<math>		<math>
Line 78:		Line 78:
	* We know there will be at least 1 more round (b/c this is a transient state), hence the 1		* We know there will be at least 1 more round (b/c this is a transient state), hence the 1
	* We are also summing over each potential next state (i',j'). We multiply the transition probability for that state by E(i,j) for that state.		* We are also summing over each potential next state (i',j'). We multiply the transition probability for that state by E(i,j) for that state.

			(Of course, the summation over each state means that this isn't really one recursive function referencing itself, it is actually many recursive functions, one for each transient state, referring to many other recursive functions.

			In other words, we have a large system of equations.

	...		...

	~~This approach leads to a large system of equations.~~

	Suppose we have 4 players. Then the expression for E[0, 2], which is the starting state of player 0 and player 2 sitting across the table from each other with the die, would be		Suppose we have 4 players. Then the expression for E[0, 2], which is the starting state of player 0 and player 2 sitting across the table from each other with the die, would be
Line 132:		Line 134:
	I is an r x r identity matrix, representing absorbing states staying in themselves		I is an r x r identity matrix, representing absorbing states staying in themselves

	Fundamental matrix N is ~~now~~ defined as:		...

			The transition probability matrix covers all states, but the fundamental matrix only covers transient states.

			Fundamental matrix N is defined as:

	N = (I - Q)^(-1)		N = (I - Q)^(-1)

	I is a t x t identity matrix. Matrix inversion is well-defined as long as all states are either transient or absorbing.		where I is the t x t identity matrix. (Matrix inversion is well-defined as long as all states are either transient or absorbing.)

	Entry N(i,j) represents the expected number of times the Markov chain will visit state j when starting from state i, before being absorbed.		Entry N(i,j) represents the expected number of times the Markov chain will visit state j when starting from state i, before being absorbed.

Unknown user: /* Markov Insights */

2025-04-19T19:04:40Z

Markov Insights

@@ Line 69: / Line 69: @@
 </math>
-The recursive case are the non-absorbing states, where the expected number of additional rounds is
+The recursive case are the transient (non-absorbing) states, where the expected number of additional rounds is
 <math>
@@ Line 76: / Line 76: @@
 Explanation:
-* We know there will be at least 1 more round (b/c this is a non-absorbing state), hence the 1
+* We know there will be at least 1 more round (b/c this is a transient state), hence the 1
 * We are also summing over each potential next state (i',j'). We multiply the transition probability for that state by E(i,j) for that state.
-Unfortunately, this approach gets complicated fast.
+...
-Suppose we have 4 players. Then the expression for E[0, 2] would be
+This approach leads to a large system of equations.
 <pre>
@@ Line 89: / Line 91: @@
           + (1/6)(1/6)E[1,3]
 </pre>
 ==Flags==
 {{ProjectEulerFlag}}