Questions about a two-way table

Survey results are often a table of counts by two categories. Answer conditional questions about one, and decide whether its two categories are independent.

What to build

A program that reads a table, answers "X given Y" questions and tests independence.

Requirements

  • For each question X Y (one of them a row name, the other a column name), print P(X | Y) = F: the count where X and Y meet divided by the total of Y, as a reduced fraction.
  • Finally print independent if every cell equals its row total times its column total divided by the grand total, and not independent otherwise.

Input

Line 1: the number of rows r and columns c. Line 2: the c column names. Then r lines, each a row name and its c counts. Then a line with q, and q questions X Y.

Output

q lines, then the verdict.

Constraints

1 ≤ r, c ≤ 6; counts are whole numbers from 0 to 1000; every row and column total is more than 0; names are distinct words.

Example

Input:

2 2
pass fail
study 30 10
rest 24 36
2
pass study
study pass

Output:

P(pass | study) = 3/4
P(study | pass) = 5/9
not independent

Why it works

A condition picks out one row or one column, so the answer divides by that line's total; independence means every row has the same mix of columns, which is the same as each cell matching the product of its totals.

Examples

Example 1 · Input
2 2
pass fail
study 30 10
rest 24 36
2
pass study
study pass
Expected output
P(pass | study) = 3/4
P(study | pass) = 5/9
not independent
Example 2 · Input
2 2
yes no
a 2 4
b 3 6
1
yes a
Expected output
P(yes | a) = 1/3
independent

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Store the counts in a dictionary keyed by (row, column), with totals for every row and column.

Hint 2

Independence: every cell must equal row total × column total ÷ grand total; compare cell × grand with row × column to stay exact.

Solution

Show one correct solution (try it yourself first)
from fractions import Fraction

r, c = map(int, input().split())
cols = input().split()
cell = {}
total = {}
rows = []
for _ in range(r):
    name, *counts = input().split()
    rows.append(name)
    for col, n in zip(cols, map(int, counts)):
        cell[(name, col)] = n
        total[name] = total.get(name, 0) + n
        total[col] = total.get(col, 0) + n
grand = sum(total[name] for name in rows)
q = int(input())
for _ in range(q):
    x, y = input().split()
    count = cell[(x, y)] if (x, y) in cell else cell[(y, x)]
    print(f"P({x} | {y}) =", Fraction(count, total[y]))
independent = all(cell[(row, col)] * grand == total[row] * total[col] for row in rows for col in cols)
print("independent" if independent else "not independent")

Lesson: Conditional probability →