Disorderly escape-Google Foobar 2020 not passing test cases

user_9246917 0
Viewed 3609

The code is running fine and is executing in python compiler online but failing all test cases in the Google Foobar 

from math import factorial
from collections import Counter
from fractions import gcd

def cycle_count(c, n):
    cc=factorial(n)
    for a, b in Counter(c).items():
        cc//=(a**b)*factorial(b)
    return cc        

def cycle_partitions(n, i=1):
    yield [n]
    for i in range(i, n//2+1):
        for p in cycle_partitions(n-i, i):
            yield [i]+p

def solution(w, h, s):    
    grid=0
    for cpw in cycle_partitions(w):
        for cph in cycle_partitions(h):            
            m=cycle_count(cpw, w)*cycle_count(cph, h)
            grid+=m*(s**sum([sum([gcd(i, j) for i in cpw]) for j in cph]))
    return grid//(factorial(w)*factorial(h))

Check out this code which is to be executed .Would love suggestions !!!

python-2.7 data-structures python-3.x python
2 Answers

This is a gorgeous problem, both mathematically and from the algorithmic point of view.

Let me try to explain each part.

The mathematics

This part is better read with nicely typeset formulas. See a concise explanation here where links to further reading are given.

Let me add a reference directly here: For example Harary and Palmer's Graphical enumeration, Chapter 2.

In short, there is a set (the whole set of h x w-matrices, where the entries can take any of s different values) and a group of permutations that transforms some matrices in others. In the problem the group consists of all permutations of rows and/or columns of the matrices.

The set of matrices gets divided into classes of matrices that can be transformed into one another. The goal of the problem is to count the number of these classes. In technical terminology the set of classes is called the quotient of the set by the action of the group, or orbit space.

The good thing is that there is a powerful theorem (with many generalizations and versions) that does exactly that. That is Polya's enumeration theorem. The theorem expresses the number of elements of the orbit space in terms of the value of a polynomial known in the area as Cycle Index. Now, in this problem the group is a direct product of two special groups the group of all permutations of h and w elements, respectively. The Cycle Index polynomials for these groups are known, and so are formulas for computing the Cycle Index polynomial of the product of groups in terms of the Cycle Index polynomials of the factors.

Maybe a comment worth making that motivates the name of the polynomial is the following: Every permutation of elements can be seen as cycling disjoint subsets of those elements. For example, a permutation of (1,2,3,4,5) and can be (2,3,1,5,4), where we mean that 2 moved to the position of 1, 3 moved to the position of 2, 1 to the position of 3, 5 to the position of 4 and 4 to the position of 5. The effect of this permutation is the same as cycling 1-> 3 -> 2 and 2 back to 1, and cycling 4 -> 5 and 5 back to 4. Similar to how natural numbers can be factored into a product of prime factors, each permutation can be factored into disjoint cycles. For each permutation, the cycles are unique in a sense for each permutation. The Cycle Index polynomial is computed in terms of the number of cycles of each length for each permutation in the group.

Putting all these together we get that the total count is given by the last formula in the link.

Implementation

As seen in the final formula, we need to compute:

  1. Partitions of a number
  2. Greatest common divisors (gcd) of many numbers.
  3. Factorials of many numbers.

For these, we can do:

  1. To compute all partitions one can use the iterative algorithms here. Already written in Python here.
  2. An efficient way to compute gcd one could use Euclidean algorithm. However, since we are going to need the gcd of all pairs of numbers in a range and each one many times. It is better to pre-compute the full table of gcd all at once by dynamic programming. If a>b, then gcd(a,b)=gcd(a-b,b). This recurrence equation allows to compute gcd of larger pairs in terms of that of smaller pairs. In the table, one has the initial values gcd(1,a)=gcd(a,1)=1 and gcd(a,a)=a, for all a.
  3. The same happens for factorials. The formula will require the factorials of all numbers in a range many times each. So, it is better to compute them all from the bottom up using that n! = n(n-1)! and 0!=1!=1.

An implementation in Python could look like this. Feel free to improve it.

user_137768720

I know this is a copied code but you have to : 1) write your own factorial function 2) write your own gcd function 3) cast to string before returning final value.

user_47763740
Related