Thread: Generating Rule-Based Strings/Sets (Project Euler)

DISCLAIMER: This is for a project euler problem, number 68.

Hello all. I have a certain issue, which isn't exactly C-specific, but I was hoping for some advice.

My goal is to generate ordered sets of 5 triples, such that they can be interpreted as a possible solution to the "5-gon" problem seen at the following link.

https://projecteuler.net/problem=68.

An example would be:

Code:

{(1,2,3), (4,3,5), (6,5,7), (8,7,9), (10,9,2)}

Now this example is not a solution to the problem, but it does show some of the rules I need to employ in generating these sets. One rule is that for every triple, the last number in the triple must be the second number in the next triple (with wrapping from 5 to 1). Also some numbers must not be repeated.

I know there exist tools that do things like this for the purpose of password cracking. I haven't found one that does quite what I need however.

Does anyone know of any tool that would solve this problem? If not, does anyone have any advice on how to implement something like this? I know that at the very least I could use many for loops with a list of already used numbers to prevent unwanted number reuse, but I'm hoping to find something better (more efficient) than this.

It looks like you could just permute the numbers 1 to 10 and fill in your triplets from that.

You could use Heap's algorithm to generate the permutations: Heap's algorithm - Wikipedia, the free encyclopedia

There are 10! = 3,628,800 permutations of 10 numbers.

For each permutation you would arrange the result into your triples. E.g.,

1 2 3 4 5 6 7 8 9 10
becomes
1 _ 2
3 _ 4
5 _ 6
7 _ 8
9 _ 10
which becomes
1 10 2
3 2 4
5 4 6
7 6 8
9 8 10

You would them presumably test them to see if it's "magic" and also ensure that 10 only appears once (so you get a 16-digit string).

This seems inefficient, though. Note that the solution they're looking for presumably starts with the number 6, where the magic 5-gon would have the numbers 6,7,8,9,and 10 (not necessarily in that order) around the outside, since they're asking for the highest value string.

Yes, this is exactly the kind of algorithm I was looking for. Seeing as the possible solution space is so small (10! as you pointed out), and you have provided a very tidy mapping (bijection I think!) of a permutation to a unique ordered set, I think this will finish in, like, no time at all. Although I wonder (like I bet you do) if there exists a more efficient solution.

I think I can reduce the solution space by noticing that a ten must occupy the first position of one of the triples to avoid being listed twice. Proof would be that if it were listed in the middle of a triple, then if must appear at the end of the previous triple. Likewise for a ten appearing at the end of a triple, it would then have to appear in the middle of the next triple.

Thank you very much for your time algorism.

That's a good point about the 10. So you could generate the permutations for the numbers 1 to 9 and just stick the 10 in the first position, reducing the perms to 9! = 362,880

If you further assume that 6, 7, 8, 9, and 10 would have to be on the outside (in order to create the highest value string, starting with 6 (if there is such a solution!)), then the other numbers would be on the inside and you can reduce it to 5! * 5! = 14400 (permuting each group of 5 separately). You could remove duplicate rotations by fixing the location of the 6 (which also means you don't have to search for it to create the string), giving 4! * 5! = 2880

A quick-and-dirty (very dirty!) implementation gives me an answer of 6531031914842725. Could be wrong, though.

Just a heads up, you're not wrong.

Solution finishes in less than a second, so I'm pretty happy.