---
title: "FBP0 - Google Foobar Plus - Disorderly Escape"
description: "Level 5: After completing all the levels I tried typing `request` to see what happens, then this challenge is the result"
pubDate: "2022-10-03"
lang: "en"
slug: "fbp0-google-foobar-plus-disorderly-escape"
url: "https://hoangyell.com/fbp0-google-foobar-plus-disorderly-escape/"
author: "HoangYell"
categories: ["Software Craft"]
tags: ["google-foobar", "algorithms", "python"]
heroImage: "https://raw.githubusercontent.com/HoangGeek/store/main/webp/HU8B1s0.webp"
---

### readme.txt:
#### challenge I - Disorderly Escape:
>*Oh no! You've managed to free the bunny workers and escape Commander Lambdas exploding space station, but Lambda's team of elite starfighters has flanked your ship. If you dont jump to hyperspace, and fast, youll be shot out of the sky!*

>*Problem is, to avoid detection by galactic law enforcement, Commander Lambda planted the space station in the middle of a quasar quantum flux field. In order to make the jump to hyperspace, you need to know the configuration of celestial bodies in the quadrant you plan to jump through. In order to do *that*, you need to figure out how many configurations each quadrant could possibly have, so that you can pick the optimal quadrant through which youll make your jump.*

>*There's something important to note about quasar quantum flux fields' configurations: when drawn on a star grid, configurations are considered equivalent by grouping rather than by order. That is, for a given set of configurations, if you exchange the position of any two columns or any two rows some number of times, youll find that all of those configurations are equivalent in that way -- in grouping, rather than order.*

>*Write a function solution(w, h, s) that takes 3 integers and returns the number of unique, non-equivalent configurations that can be found on a star grid w blocks wide and h blocks tall where each celestial body has s possible states. Equivalency is defined as above: any two star grids with each celestial body in the same state where the actual order of the rows and columns do not matter (and can thus be freely swapped around). Star grid standardization means that the width and height of the grid will always be between 1 and 12, inclusive. And while there are a variety of celestial bodies in each grid, the number of states of those bodies is between 2 and 20, inclusive. The solution can be over 20 digits long, so return it as a decimal string.  The intermediate values can also be large, so you will likely need to use at least 64-bit integers.* 

>*For example, consider w=2, h=2, s=2. We have a 2x2 grid where each celestial body is either in state 0 (for instance, silent) or state 1 (for instance, noisy).  We can examine which grids are equivalent by swapping rows and columns.*
```python
00
0
```

>*In the above configuration, all celestial bodies are "silent" - that is, they have a state of 0 - so any swap of row or column would keep it in the same state.*
```python
00 00 01 10
01 10 00 00
```

>*1 celestial body is emitting noise - that is, has a state of 1 - so swapping rows and columns can put it in any of the 4 positions.  All four of the above configurations are equivalent.*
```python
00 11
11 00
```

>*2 celestial bodies are emitting noise side-by-side.  Swapping columns leaves them unchanged, and swapping rows simply moves them between the top and bottom.  In both, the *groupings* are the same: one row with two bodies in state 0, one row with two bodies in state 1, and two columns with one of each state.*
```python
01 10
01 10
```

>*2 noisy celestial bodies adjacent vertically. This is symmetric to the side-by-side case, but it is different because there's no way to transpose the grid.*
```python
01 10
10 01
```

>*2 noisy celestial bodies diagonally.  Both have 2 rows and 2 columns that have one of each state, so they are equivalent to each other.*
```python
01 10 11 11
11 11 01 10
```

>*3 noisy celestial bodies, similar to the case where only one of four is noisy.*
```python
11
11
```

>*4 noisy celestial bodies.*
>*There are 7 distinct, non-equivalent grids in total, so solution(2, 2, 2) would return 7.*

```python
solution.solution(2, 3, 4)
430

solution.solution(2, 2, 2)
7
```

### solution.py:
#### challenge I - Disorderly Escape:
```python
# source: https://franklinvp.github.io/2020-06-05-PolyaFooBar/

from collections import Counter

def buildGCDTable(n):
    result = [[0 for x in range(n)] for y in range(n)]
    for i in range(n):
        for j in range(i,n):
            if i == 0 or j == 0:
                result[i][j] = 1
                result[j][i] = 1
            elif i == j:
                result[i][j] = i+1
            else:
                result[i][j] = result[i][j-i-1]
                result[j][i] = result[i][j-i-1]
    return result

def gcd(x,y, gcdTable):
    return gcdTable[x-1][y-1]

def buildFactorialTable(n):
    result = [1]
    for i in range(n-1):
        result.append(result[-1]*(i+2))
    return result

def factorial(x, factorialTable):
    return factorialTable[x-1]

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

def partitionsAndCycleCount(n, factorialTable):
    k = 0 
    p = n*[0]
    p[0] = n
    result = [] 
    a = [0 for i in range(n + 1)]
    k = 1
    y = n - 1
    result = []
    while k != 0:
        x = a[k - 1] + 1
        k -= 1
        while 2 * x <= y:
            a[k] = x
            y -= x
            k += 1
        l = k + 1
        while x <= y:
            a[k] = x
            a[l] = y
            partition = a[:k+2]
            result.append((partition, coefficientFactor(partition,n,factorialTable)))
            x += 1
            y -= 1
        a[k] = x + y
        y = x + y - 1
        partition = a[:k+1]
        result.append((partition, coefficientFactor(partition,n,factorialTable)))
    return result

def solution(w, h, s):
    n = max(w,h)
    gcdTable = buildGCDTable(n)
    factorialTable = buildFactorialTable(n)
    grid=0
    for cpw in partitionsAndCycleCount(w,factorialTable):
        for cph in partitionsAndCycleCount(h,factorialTable):
            m=cpw[1]*cph[1]
            grid+=m*(s**sum([sum([gcd(i, j, gcdTable) for i in cpw[0]]) for j in cph[0]]))
    return str(grid//(factorial(w,factorialTable)*factorial(h,factorialTable)))
```

![Image](https://raw.githubusercontent.com/HoangGeek/store/main/webp/ke0Dd3R.webp)