Project Euler/61: Difference between revisions
From charlesreid1
(Created page with "==Problem Statement== Link: https://projecteuler.net/problem=61 ==Solution Technique== ==Code== ==Flags== {{ProjectEulerFlag}}") |
(→Code) |
||
| (7 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
==Problem Statement== | ==Problem Statement== | ||
This problem explores an extension of the concept of a triangular number, generated by the formula <math>\dfrac{n(n+1)}{2}</math>, to other shapes. | |||
Exploring triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers - numbers that are generated according to particular formulae: | |||
<math> | |||
P_{3,n} = \dfrac{n(n+1)}{2} | |||
</math> | |||
<math> | |||
P_{4,n} = n^2 | |||
</math> | |||
<math> | |||
P_{5,n} = \dfrac{n(3n-1)}{2} | |||
</math> | |||
<math> | |||
P_{6,n} = n(2n-1) | |||
</math> | |||
<math> | |||
P_{7,n} = \dfrac{n(5n-3)}{2} | |||
</math> | |||
<math> | |||
P_{8,n} = n(3n-2) | |||
</math> | |||
Link: https://projecteuler.net/problem=61 | Link: https://projecteuler.net/problem=61 | ||
==Solution Technique== | ==Solution Technique== | ||
<s>'''CURRENTLY UNSOLVED'''</s> | |||
Our solution technique is to generate a graph (for this, we use the Guava library). | |||
We wish to find the sum of the ordered set of six cyclic 4-digit numbers for which ''each'' polygonal type, triangle/square/pentagonal/hexaongal,/heptagonal,octagonal, is represented by a different permutation of the digits (maintaining original order). | |||
To do this, we create a graph, with each possible connection between a prefix and a suffix marked with an edge. | |||
This results in a 6-partite graph, and we seek a path, a cycle, that passes through all 6 partitions. | |||
===crux (several years later)=== | |||
The approach described above was sound, the implementation was logical, but the program just contained one significant, fatal bug: when we assembled the graph connecting four-digit numbers with shared first-two-digits and last-two-digits, we incorrectly implemented it to connect last-two-digits to last-two-digits. Change a % to a / and it worked okay. | |||
==Code== | ==Code== | ||
<s>https://git.charlesreid1.com/cs/euler/src/branch/master/scratch/Round2_050-070/061/GuavaFigurate.java</s> | |||
https://git.charlesreid1.com/cs/euler/src/branch/master/java/Problem061.java | |||
==Flags== | ==Flags== | ||
{{ProjectEulerFlag}} | {{ProjectEulerFlag}} | ||
Latest revision as of 01:13, 15 April 2025
Problem Statement
This problem explores an extension of the concept of a triangular number, generated by the formula $ \dfrac{n(n+1)}{2} $, to other shapes.
Exploring triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers - numbers that are generated according to particular formulae:
$ P_{3,n} = \dfrac{n(n+1)}{2} $
$ P_{4,n} = n^2 $
$ P_{5,n} = \dfrac{n(3n-1)}{2} $
$ P_{6,n} = n(2n-1) $
$ P_{7,n} = \dfrac{n(5n-3)}{2} $
$ P_{8,n} = n(3n-2) $
Link: https://projecteuler.net/problem=61
Solution Technique
CURRENTLY UNSOLVED
Our solution technique is to generate a graph (for this, we use the Guava library).
We wish to find the sum of the ordered set of six cyclic 4-digit numbers for which each polygonal type, triangle/square/pentagonal/hexaongal,/heptagonal,octagonal, is represented by a different permutation of the digits (maintaining original order).
To do this, we create a graph, with each possible connection between a prefix and a suffix marked with an edge.
This results in a 6-partite graph, and we seek a path, a cycle, that passes through all 6 partitions.
crux (several years later)
The approach described above was sound, the implementation was logical, but the program just contained one significant, fatal bug: when we assembled the graph connecting four-digit numbers with shared first-two-digits and last-two-digits, we incorrectly implemented it to connect last-two-digits to last-two-digits. Change a % to a / and it worked okay.
Code
https://git.charlesreid1.com/cs/euler/src/branch/master/java/Problem061.java
Flags
