We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

# Project Euler #68: Magic N-gon ring

# Project Euler #68: Magic N-gon ring

Contest ends in

#### Sort by

recency

#### |

#### 10 Discussions

#### |

Please Login in order to post a comment

I have a question about how many digits to employ. Given n & s, how do i know how many digits to use? In the example, it indicated only 1-6 digits.

I first sorted results in

numericalorder, failing test cases # 5, 8, 9, and 11-21. Then I read the problem description again, found that results should be sorted inalphabeticalorder, which let me pass all of the test cases.Another one of those problems where I started to invent a "rocket ship" when actually there was no need for. Thus I would advise to make a solution you know will work for small n-s and it might just happen that you find out that it works for larger n-s as well.

Is there any trick to quickly get the sequence of inner elements given their corresponding sum? (e.g. given the sums

`5 4 3`

, results in`2, 3; 3, 1; 1, 2`

)Previously without such method, my implementation uses permutations to generate inner sequence which is very slow. For it runs like forever.

EDIT: Got a function to generate the inner sequence. This function starts with picking (from the chosen inner elements) two valid elements according to their sum, and use them as the first two elements of the inner sequence, and then all the rest can be calculated based on the outer sequence (if it exists). But the problem with this method is that plenty of time is wasted on invalid set of chosen inner elements, where it can only be quitted when it hits the end of the loop.Still getting TLE #13 to #21 (with Pypy, #15 to #21). Could I be completely wrong from the very beginning to start with multichoosing outer elements? I already have a guard to skip choices of outer sequence which does not satisfy

`sum(outer) == 2 * N * (2 * N + 1) - S * N`

, but still no hope.EDIT 2: Finally cleared everything without switching to another language. As it turns out, if we start over and get rid of the mindset from the original problem, it's not that difficult.The key insight here is to think about the triplets and combinations at the same time (somehow a hybrid method). I first generate an array of valid triplets (whose index is the sum of the 3 elements) similar to how we generate a list of factors of composite numbers.

We are concerned only about

`triplets[S]`

. Based on the multichoose combinations of the outer sequence and the`sum(outer) == 2 * N * (2 * N + 1) - S * N`

condition, we get`outer`

and`inner`

without knowing their positions yet, except`outer[0]`

.To make it more clear, I also created

`out_triplets`

whose elements are list of`[inn1, inn2]`

and`inn_triplets`

whose elements are list of`[out, inn2]`

. Then we use a`deque()`

which starts by appending elements from`out_triplets[outer[0]]`

(both`out, inn1, inn2`

and`out, inn2, inn1`

).After that, we can use the last

`inn2`

from`popleft()`

as the index of`inn_triplets`

to find all the valid (there's some conditions to it, such as no repeating`out`

, no repeating`inn2`

except if it is the last element etc) next`out, inn1, inn2`

to add to the queue. When the sequence we get from`popleft()`

is of desirable length, add it to the`answers`

pool and don't add it to the queue. Repeat untill the queue is empty. Then do that again with another multichoose combination with brand new`out_triplets`

and`inn_triplets`

...This implementation may look complicated, but once you get it straight, it is sort of clean and beautiful. The slowest test I got was 1.82s #21, and it is Python 2! That's of comparable speed to another C++ solution I found on the web.

And if you got WA #18, #20 and #21, make sure you sort the answers after joining them as string, not before joining.

EDIT 3: It's a solid 0.64s with Pypy. Fantastic.I suggest looking at this link to get a clearer picture of what an N-gon ring looks like for N > 3, and which numbers are used for the N-gon ring. https://projecteuler.net/problem=68