Facebook Superpatterns puzzle - The solution 2
My earlier blog post had a brute force approach to solving the super patterns puzzle. The order of the program was in the order of n!. Didnt think it was worth coding it up. Might use it to validate this new solution. The solution is based on building larger superpatterns from smaller ones. This is how the solution would look like ..
Take a 2 -subpattern for eg. The subpatterns would be
{1,2} and {2,1} .. the superpattern is {1,3,2} other "superpatterns" that are not combinatorially smallest are {2,1,3}, {2,3,1} and {3,1,2}.
We can build higher superpattern from lower ones like this.
For the 2-subpatterns to become a 3 -subpatterns, it would have to satisfy ..
{3,1,2}
{3,2,1}
{1,3,2}
{2,3,1}
{1,2,3}
{2,1,3}
Which in a way means that we will have to add a "higher" element in the sequence or superpatterns that generated the lower or 2-subpatterns to get the 3-subpattern.
The trick if figuring out the smallest combination of adding this additional number. More commong soon ...
4 comments:
I have been trying to stab at this same puzzle you are working on, but I feel like I'm climbing a handholdless vertical wall with greased fingers.
I have considered doing what you are suggesting in the article, and it is definitely possible to start with a small pattern and then add numbers in select places until it can be shown that it contains all of permutations of size k. As you said the problem seems to stem from the difficulty knowing where to stick those numbers so that the pattern is as compact as possible.
The real question to me seems to be this, How do we know that any pattern which contains a set of some permutations (let alone all of them) is as compact as possible?
If we could answer that then each pattern could be tested to see if it is indeed good. Also, if the question had an answer then there might be some additional insight as to where to put the numbers to produce compact patterns to our desire.
I know this comment is out of the blue, but I'm working on the problem the same as you.
Ciow
"The real question to me seems to be this, How do we know that any pattern which contains a set of some permutations (let alone all of them) is as compact as possible?"
I've been working on this problem for about a week and I'll say that this is pretty difficult to ascertain. Namely b/c the amount of data that you can pack into a given combination can be higher than necessary.
[5, 2, 6, 4, 1, 7, 3], for example is of length 7, and contains 19/24 of the 4-subpatterns*.
But trying to proceed by using this combination using the method mentioned in this article will not produce the lexicographically smallest 4-superpattern.
It's almost like it's too packed with "information". In the lexicographically smallest 4-superpattern I found, the subset ranging from the 3rd to the 9th element only contained 15 4-subpatterns, strangely enough.
One thing I've noticed that is in the incremental approach, elements with low rotational and reflectional symmetry seem to work better. e.g. [4, 2, 1, 3] and [3,1,4,2] both contain 3 3-subpatterns but the first one produces 8 distinct patterns when rotated 90 degrees at a time and flipped horizontally. The other one only produces 4 distinct patterns.
*You need at least a pattern of length 9 to get all 24. but that was found through brute force, and also assumes all numbers in the combination are unique)
I've come up with a solution (in Python) and there's a few things I'd like to point out:
1. This is serious number crunching. Once I'd written my brute-force implementation the first thing I optimized was my permutation and combination generator functions, turning them into memoizing iterators.
2. You seem to have overlooked a big hint they gave on the problem page: the trick is to figure out how to build patterns out of previous k-superpatterns.
Take 25314, the smallest 3-superpattern. The first three digits reduce to 132, so figure out how to sort the numbers 1-5 so that 2,3, and 5 all end on one end.
When exploring the problem some I brute-forced the smallest 4-superpattern which turned out to be 137962584. The last 5 digits reduce to 25314 in reverse. The method of sorting such that 62584 end up on one end is similar, but slightly different.
Once you have those two methods down, you have a way to construct potential patterns. Here we worked backwards from solution to part of the answer. The gain is that once you have one "end" of the pattern to test, you only have to generate perms for the remaining numbers. Actually, once you've sorted the numbers you have to test with the previous k-superpattern 'laying over' both the front and the back.
3. You need a way to renumber patterns to their base pattern (465 -> 132) and based on other patterns [(52846, 25314) -> 48526]. I also included simple index based re-ordering since my memoized combination iterator used it [(25314, 124) -> 534].
All that being said, this is still some serious CPU work. My solution will just about instantly spit out the 4-superpattern, takes just over a minute for the 5-superpattern, and over that I'm still back to starting the script and walking away. I'm going to ask work if they mind me running this on our testbed db servers during off hours :)
If you want to see my source code to better understand what I've said, let me know and I can send it to you. I'd rather not post actual source here or online otherwise as I'd rather not give Facebook hopefuls a way to cheat their way past one of their posted problems.
Can someone send me their solution for the Superpatterns puzzle?
rojakian@yahoo.com
Thanks
RO
Post a Comment