Project Euler/334 - Revision history

Unknown user: /* Quadratic potential */

2025-04-21T23:33:41Z

Quadratic potential

@@ Line 244: / Line 244: @@
 (Take the difference in the second moment from the start and end states, divide by 2, and that's your number of moves. Confirmed because each move changes Q by 2.)
 ==Flags==
 {{ProjectEulerFlag}}

Unknown user: /* Quadratic potential */

2025-04-21T23:07:22Z

Quadratic potential

← Older revision		Revision as of 23:07, 21 April 2025
Line 183:		Line 183:

	Given that it is totally impossible to reach the final state by simulating every move, let's take an alternative approach, which is, to use the two invariants (0th moment, number of beans, and 1st moment, avg location of beans) and find a final state that satisfies those invariants while also minimizing number of moves		Given that it is totally impossible to reach the final state by simulating every move, let's take an alternative approach, which is, to use the two invariants (0th moment, number of beans, and 1st moment, avg location of beans) and find a final state that satisfies those invariants while also minimizing number of moves

			'''NOTE: we aren't using the definition of moment exactly correctly, b/c normally we would divide moment 1 by N, moment 2 by N^2, etc, but we can think of these as "non-normalized" moments

	Game conserves two key quantities:		Game conserves two key quantities:
Line 227:		Line 229:

	We want the value of M2 to be at a minimum, but while acknowledging that it must increase for each round		We want the value of M2 to be at a minimum, but while acknowledging that it must increase for each round

	~~The game stops when no bowl has > 1 bean. Th~~

	The stability condition corresponds to having the minimum possible value of the second moment amongst all possible configurations F satisfying our constraints:		The stability condition corresponds to having the minimum possible value of the second moment amongst all possible configurations F satisfying our constraints:
Line 236:		Line 236:

	Unique final state is most "compact" arrangement of L beans (minimum sum of squared indices) producing the required moment		Unique final state is most "compact" arrangement of L beans (minimum sum of squared indices) producing the required moment

			We can also determine the number of moves from the final state:

			<math>
			N_{moves} = \dfrac{M_{2,F} - M_{2}}{2}
			</math>

			(Take the difference in the second moment from the start and end states, divide by 2, and that's your number of moves. Confirmed because each move changes Q by 2.)

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Quadratic potential */

2025-04-21T22:47:58Z

Quadratic potential

← Older revision		Revision as of 22:47, 21 April 2025
Line 221:		Line 221:

	If we look at the way the second moment changes with each move, it increases by 2,		If we look at the way the second moment changes with each move, it increases by 2,
	* Removing 2 beans from bowl i changes Q by <math>-2 \cdot i^2</math>		* Removing 2 beans from bowl i changes M2 by <math>-2 \cdot i^2</math>
	* Adding one bean to bowl i-1 changes Q by <math>i^2 - 2i + 1</math>		* Adding one bean to bowl i-1 changes M2 by <math>i^2 - 2i + 1</math>
	* Adding one bean to bowl i+1 changes Q by <math>i^2 + 2i + 1</math>		* Adding one bean to bowl i+1 changes M2 by <math>i^2 + 2i + 1</math>
	* Total change = 2		* Total change = 2

			We want the value of M2 to be at a minimum, but while acknowledging that it must increase for each round

			The game stops when no bowl has > 1 bean. Th

			The stability condition corresponds to having the minimum possible value of the second moment amongst all possible configurations F satisfying our constraints:
			* <math>F_{k} \in {0,1}</math>
			* <math>\sum F_k = L</math>
			* <math>\sum k F_k = M</math>

			Unique final state is most "compact" arrangement of L beans (minimum sum of squared indices) producing the required moment

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Quadratic potential */

2025-04-21T22:43:35Z

Quadratic potential

← Older revision		Revision as of 22:43, 21 April 2025
Line 225:		Line 225:
	* Adding one bean to bowl i+1 changes Q by <math>i^2 + 2i + 1</math>		* Adding one bean to bowl i+1 changes Q by <math>i^2 + 2i + 1</math>
	* Total change = 2		* Total change = 2

	~~So we now know that in addition to the two invariant constraints, we also have a maximum constraint:~~
	* preserve <math>M_{0} = M_{0,F}</math>
	* preserve <math>M_{1} = M_{1,F}</math>
	* maximize <math>M_{2,F}</math>

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Quadratic potential */

2025-04-21T22:35:47Z

Quadratic potential

@@ Line 183: / Line 183: @@
 Given that it is totally impossible to reach the final state by simulating every move, let's take an alternative approach, which is, to use the two invariants (0th moment, number of beans, and 1st moment, avg location of beans) and find a final state that satisfies those invariants while also minimizing number of moves
 ==Flags==
 {{ProjectEulerFlag}}

Unknown user: /* Maximum bowls */

2025-04-21T22:25:28Z

Maximum bowls

← Older revision		Revision as of 22:25, 21 April 2025
Line 179:		Line 179:
	Final State: [-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]		Final State: [-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
	</pre>		</pre>

			===Quadratic potential===

			Given that it is totally impossible to reach the final state by simulating every move, let's take an alternative approach, which is, to use the two invariants (0th moment, number of beans, and 1st moment, avg location of beans) and find a final state that satisfies those invariants while also minimizing number of moves

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Map representation ideas */

2025-04-21T22:16:46Z

Map representation ideas

@@ Line 130: / Line 130: @@
 That kind of scale-up (nearly 1000x increase in computational cost for every 10x increase in beans) means this approach is totally unscalable. Not surprising, but at least we can get some insight from smaller cases.
 ==Flags==
 {{ProjectEulerFlag}}

Unknown user: /* Maximum bowls */

2025-04-21T22:16:01Z

Maximum bowls

← Older revision		Revision as of 22:16, 21 April 2025
Line 116:		Line 116:

	We could find the unique set of bean indices that (1) preserves total number of beans, (2) preserves average location of beans, and (3) minimizes sum of indices <math>\sum i^2</math> (where i is the index of the bowl)		We could find the unique set of bean indices that (1) preserves total number of beans, (2) preserves average location of beans, and (3) minimizes sum of indices <math>\sum i^2</math> (where i is the index of the bowl)

	~~===Maximum bowls===~~

	~~Figuring out the maximum number of bowls needed for a given starting setup can be determined, with some trial and error:~~

	~~====single bowl case====~~

	~~Single bowl case:~~
	* Suppose we start with b beans in bowl k. No other bowls have any beans.
	* The number of bowls needed to distribute b beans located in bowl k is b/2
	* The bowls used will range from k - b/2 to k + b/2

	* Example:
	** start with 100 beans in bowl 0
	** end with 1 bean in bowl -50, 1 bean in bowl -49, ..., 1 bean in bowl 49, 1 bean in bowl 50

	* Example:
	** start with 100 beans in bowl 7
	** end with 1 bean in bowl -43, 1 bean in bowl -42, ..., 1 bean in bowl 57

	~~====two bowl case====~~

	~~Two bowl case:~~
	* suppose we start with b1 beans in bowl k1, and b2 beans in k2. No other bowls have any beans.
	* If k1 and k2 are very far apart, we can expect that neither bowl will interact, so reduces to single bowl case for each

	* Example:
	** start with 10 beans in bowl 0, 10 beans in bowl 80
	** end with 1 bean in bowl -5, 1 bean in bowl -4, ..., 1 bean in bowl 4, 1 bean in bowl 5,
	** then 1 bean in bowl 75, 1 bean in bowl 76, ..., 1 bean in 84, 1 bean in bowl 85

	* If k1 and k2 are close together, they will interact:

	~~<pre>~~
	~~Initial State: {0: 10, 1: 10}~~
	~~Final State: [-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]~~

	~~Initial State: {0: 10, 2: 10}~~
	~~Final State: [-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]~~

	~~Initial State: {0: 10, 3: 10}~~
	~~Final State: [-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]~~

	~~Initial State: {0: 10, 4: 10}~~
	~~Final State: [-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]~~

	~~Initial State: {0: 10, 5: 10}~~
	~~Final State: [-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]~~
	~~</pre>~~

	===Map representation ideas===		===Map representation ideas===

Unknown user: /* Map representation ideas */

2025-04-21T22:15:53Z

Map representation ideas

← Older revision		Revision as of 22:15, 21 April 2025
Line 168:		Line 168:
	===Map representation ideas===		===Map representation ideas===

	~~It seems a lot easier, for~~ a first-pass implementation, to use a map instead of a bitwise vector. That avoids the need to allocate space for every bowl in advance, and just keep track of bowls that have/have seen beans.		For a first-pass implementation, use a map instead of a bitwise vector. That avoids the need to allocate space for every bowl in advance, and just keep track of bowls that have/have seen beans.

	(In Python, we can use a default dict, with the bowl index as the key and the number of beans (default 0) as the value.)		(In Python, we can use a default dict, with the bowl index as the key and the number of beans (default 0) as the value.)

	~~'''PROBLEM: implementation is extremely slow.'''~~

	For N = 10 beans in one starting bowl, it takes 0.000132 seconds		For N = 10 beans in one starting bowl, it takes 0.000132 seconds
Line 180:		Line 178:
	For N = 1000 beans in one starting bowl, it takes 57.2 seconds		For N = 1000 beans in one starting bowl, it takes 57.2 seconds

	That kind of scale-up (nearly 1000x increase in computational cost for every 10x increase in beans) means this approach is totally ~~unsustainable~~. Not surprising, but at least we can get some insight from smaller cases.		That kind of scale-up (nearly 1000x increase in computational cost for every 10x increase in beans) means this approach is totally unscalable. Not surprising, but at least we can get some insight from smaller cases.

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Maximum bowls */

2025-04-21T22:12:04Z

Maximum bowls

@@ Line 147: / Line 147: @@
 ** then 1 bean in bowl 75, 1 bean in bowl 76, ..., 1 bean in 84, 1 bean in bowl 85
-* If k1 and k2 are close together, they will interact
+* If k1 and k2 are close together, they will interact:
 ===Map representation ideas===