Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @pardouin,validated by @Westicles,@Exanc and @pluieciel.
If you have any issues, feel free to ping them.
Pearl, not Perl (that is a language).
1 Like
Ahah I don’t know how I could even miss that, but thanks, I corrected it.
The forum url is now wrong but it still redirects to the right url so it should be ok.
Edit: now all urls are ok.
1 Like
A nice heavy-on-math, light-on-coding kind of puzzle. While it is classified as hard, I think it falls into either easy, expert++, or medium category, but never in hard: 
- easy, if you are mathematician: you might simply know the formula already.
- super-expert, if you want to figure out (and even prove) the formula by yourself - from scratch and without attending a semester of group theory class beforehand. I think it is nearly impossible, unless you are as clever as György Pólya, Leonhard Euler and Stirling combined.
- medium: if you just google the base problem, which is easy-to-find as it is really called necklaces (or bracelets to be more precise).
Not qualified for the first two options, I took the third option and passed. But the learning factor is unfortunatelly limited for me, because I don’t really understand why this formula works. (Except the going from “at most c colors” to the “exactly c colors” part.)
2 Likes
Hmmm, well I guess I took the fourth option and just plugged one of the bigger numbers into OEIS and found the formula there.
2 Likes
I totally get your point, the difficulty for this one was hard to set.
I actually even hesitated before creating the puzzle but what decided me was the strong conviction that combinatorics is always good to know, you always encounter combinatorics problem when you program so the more you know, the best.
My first idea was to use an actual problem that I encountered, which was “how many actually different grids of Light Out of size h x w there is?”.
Answer for 3 x 3 was 51 for example, but I had to remember about my group theory classes to understand why.
I tried to make a puzzle out of it but the algorithmic problem wasn’t very interesting as the underlying rotation group is either the rectangle group or the square group so there wasn’t much to do, it was basically a formula with switch cases depending on parity and equality of h and w.
So I changed for this necklace problem, the groups are slightly more interesting and it requires a bit more thinking with the condition that all colors must be used at least once.
2 Likes