+/foobar

google programming puzzles

git clone https://git.julia.blue/+/foobar

Joseph RyanI made it2e1d345

master
8.6 KiB322 linesraw
1import sys
2
3# Get the matrix into the form:
4# Q R
5# 0 I
6# and then return the first row of ((I-Q)^-1)R
7# because markov chains are magic and solve the infinite sum for you
8
9from fractions import *
10
11
12class Matrix:
13    def __init__(self, height, width):
14        self.rows = height
15        self.cols = width
16        self.m = [[0 for i in range(height)] for j in range(width)]
17
18    def minor(self, r, c):
19        result = Matrix(self.rows - 1, self.cols - 1)
20        result.m = [row[:] for row in self.m]
21        del result.m[r]
22        for row in result.m:
23            del row[c]
24        return result
25
26    def cofactor(self, r, c):
27        return (self.m[r][c] * (1 if (r + c) % 2 == 0 else -1)
28                             * self.minor(r, c).det())
29
30    def det(self):
31        if self.rows == 2:
32            return self.m[0][0] * self.m[1][1] - self.m[1][0] * self.m[0][1]
33        return sum(self.cofactor(0, i) for i in range(self.cols))
34
35    def adjoint(self):
36        result = Matrix(self.rows, self.cols)
37        result.m = [row[:] for row in self.m]
38        for i in range(result.rows):
39            for j in range(i + 1, result.cols):
40                result.m[i][j], result.m[j][i] = result.m[j][i], result.m[i][j]
41        return result
42
43    def inverse(self):
44        det = self.det()
45        if self.rows == 2:
46            result = Matrix(2, 2)
47            result.m[0][0] = self.m[1][1] / det
48            result.m[1][0] = -self.m[1][0] / det
49            result.m[0][1] = -self.m[0][1] / det
50            result.m[1][1] = self.m[0][0] / det
51            return result
52        temp = Matrix(self.rows, self.cols)
53        temp.m = [row[:] for row in self.m]
54        for i in range(temp.rows):
55            for j in range(temp.cols):
56                temp.m[i][j] = (self.minor(i, j).det()
57                                * -(((i + j) % 2) * 2 - 1))
58        temp = temp.adjoint()
59        for i in range(temp.rows):
60            for j in range(temp.cols):
61                temp.m[i][j] /= det
62        return temp
63
64    def __sub__(self, other):
65        result = Matrix(self.rows, self.cols)
66        for i in range(self.rows):
67            for j in range(self.cols):
68                result.m[i][j] = self.m[i][j] - other.m[i][j]
69        return result
70
71    def __mul__(self, other):
72        result = Matrix(other.cols, self.rows)
73        for i in range(result.cols):
74            for j in range(result.rows):
75                dot = 0
76                for k in range(self.cols):
77                    dot += self.m[i][k] * other.m[k][j]
78                result.m[i][j] = dot
79        return result
80
81    def __str__(self):
82        return '\n'.join(
83            [' '.join(["{0:>3}".format(i) for i in row]) for row in self.m])
84
85
86def identity(size):
87    result = Matrix(size, size)
88    for i in range(size):
89        result.m[i][i] = 1
90    return result
91
92
93def answer(m):
94    if len(m) <= 2:
95        return [1, 1]
96    fixed = [m[0]]
97    front = 1
98    for i in range(1, len(m)):
99        if any(m[i]):
100            fixed.append(m[i])
101            while i > front:
102                for row in m:
103                    row[i], row[i - 1] = row[i - 1], row[i]
104                i -= 1
105            front += 1
106    m = fixed
107    for row in m:
108        temp = sum(row)
109        for i in range(len(row)):
110            row[i] = Fraction(row[i]) / temp
111    size = len(m)
112    q = Matrix(size, size)
113    q.m = [row[:size] for row in m[:size]]
114    r = Matrix(size, len(m[0]) - size)
115    r.m = [row[size:] for row in m[:size]]
116    i = identity(size)
117    # print "Q"
118    # print q
119    # print "R"
120    # print r
121    # print "I"
122    # print i
123    # print "I-Q"
124    # print i - q
125    # print "(I-Q)^-1"
126    # print (i - q).inverse()
127    # print "(I-Q)^-1 * r"
128    # print (i - q).inverse() * r
129    ans = r if q.rows == 1 else (i - q).inverse() * r
130    total_gcd = reduce((lambda x, y: gcd(x, y)), ans.m[0])
131    return [int(n / total_gcd) for n in ans.m[0]] + [total_gcd.denominator]
132
133
134# a = Matrix(3, 3)
135# a.m = [[3., 0., 2.], [2., 0., -2.], [0., 1., 1.]]
136# a.m = [[Fraction(i) for i in row] for row in a.m]
137# a = a.inverse()
138# print "Final:"
139# print a
140# print "Identity"
141# print identity(3)
142
143# a = Matrix(2, 3)
144# a.m = [[1, 2, 3], [4, 5, 6]]
145# b = Matrix(3, 2)
146# b.m = [[7, 8], [9, 10], [11, 12]]
147
148# print a
149# print
150# print b
151# print
152# print a * b
153# sys.exit()
154
155test1 = [[0, 2, 1, 0, 0],
156         [0, 0, 0, 3, 4],
157         [0, 0, 0, 0, 0],
158         [0, 0, 0, 0, 0],
159         [0, 0, 0, 0, 0]]
160
161sol1 = [7, 6, 8, 21]
162
163test2 = [[0, 1, 0, 0, 0, 1],
164         [4, 0, 0, 3, 2, 0],
165         [0, 0, 0, 0, 0, 0],
166         [0, 0, 0, 0, 0, 0],
167         [0, 0, 0, 0, 0, 0],
168         [0, 0, 0, 0, 0, 0]]
169
170sol2 = [0, 3, 2, 9, 14]
171
172test3 = [[2, 3, 1, 1, 0, 1],
173         [0, 0, 0, 0, 0, 0],
174         [4, 1, 0, 3, 2, 0],
175         [2, 3, 0, 1, 3, 0],
176         [0, 0, 0, 0, 0, 0],
177         [0, 0, 0, 0, 0, 0]]
178
179test4 = [
180    [0, 1, 0, 0, 0, 1, 2, 3, 2, 1],
181    [4, 0, 0, 3, 2, 0, 9, 2, 2, 3],
182    [1, 0, 0, 1, 0, 0, 0, 0, 0, 0],
183    [0, 1, 0, 0, 1, 0, 0, 0, 0, 0],
184    [0, 1, 0, 0, 0, 0, 0, 2, 0, 0],
185    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
186    [0, 0, 0, 0, 3, 0, 0, 0, 0, 0],
187    [0, 0, 4, 0, 0, 3, 0, 0, 0, 0],
188    [0, 0, 0, 0, 0, 10, 2, 0, 0, 0],
189    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
190]
191
192test5 = [[1, 2, 3, 0, 0, 0], [4, 5, 6, 0, 0, 0], [7, 8, 9, 1, 0, 0],
193         [0, 0, 0, 0, 1, 2], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]
194
195print answer(test1)
196print answer(test2)
197
198assert (
199    answer([
200        [0, 2, 1, 0, 0],
201        [0, 0, 0, 3, 4],
202        [0, 0, 0, 0, 0],
203        [0, 0, 0, 0, 0],
204        [0, 0, 0, 0, 0]
205    ]) == [7, 6, 8, 21]
206)
207
208assert (
209    answer([
210        [0, 1, 0, 0, 0, 1],
211        [4, 0, 0, 3, 2, 0],
212        [0, 0, 0, 0, 0, 0],
213        [0, 0, 0, 0, 0, 0],
214        [0, 0, 0, 0, 0, 0],
215        [0, 0, 0, 0, 0, 0]
216    ]) == [0, 3, 2, 9, 14]
217)
218
219assert (
220    answer([
221        [1, 2, 3, 0, 0, 0],
222        [4, 5, 6, 0, 0, 0],
223        [7, 8, 9, 1, 0, 0],
224        [0, 0, 0, 0, 1, 2],
225        [0, 0, 0, 0, 0, 0],
226        [0, 0, 0, 0, 0, 0]
227    ]) == [1, 2, 3]
228)
229assert (
230    answer([
231        [0]
232    ]) == [1, 1]
233)
234
235assert (
236    answer([
237        [0, 0, 12, 0, 15, 0, 0, 0, 1, 8],
238        [0, 0, 60, 0, 0, 7, 13, 0, 0, 0],
239        [0, 15, 0, 8, 7, 0, 0, 1, 9, 0],
240        [23, 0, 0, 0, 0, 1, 0, 0, 0, 0],
241        [37, 35, 0, 0, 0, 0, 3, 21, 0, 0],
242        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
243        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
244        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
245        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
246        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
247    ]) == [1, 2, 3, 4, 5, 15]
248)
249assert (
250    answer([
251        [0, 7, 0, 17, 0, 1, 0, 5, 0, 2],
252        [0, 0, 29, 0, 28, 0, 3, 0, 16, 0],
253        [0, 3, 0, 0, 0, 1, 0, 0, 0, 0],
254        [48, 0, 3, 0, 0, 0, 17, 0, 0, 0],
255        [0, 6, 0, 0, 0, 1, 0, 0, 0, 0],
256        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
257        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
258        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
259        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
260        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])
261    == [4, 5, 5, 4, 2, 20]
262)
263
264assert (
265    answer([
266        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
267        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
268        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
269        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
270        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
271        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
272        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
273        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
274        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
275        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
276    ]) == [1, 1, 1, 1, 1, 5]
277)
278
279assert (
280    answer([
281        [1, 1, 1, 0, 1, 0, 1, 0, 1, 0],
282        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
283        [1, 0, 1, 1, 1, 0, 1, 0, 1, 0],
284        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
285        [1, 0, 1, 0, 1, 1, 1, 0, 1, 0],
286        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
287        [1, 0, 1, 0, 1, 0, 1, 1, 1, 0],
288        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
289        [1, 0, 1, 0, 1, 0, 1, 0, 1, 1],
290        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
291    ]) == [2, 1, 1, 1, 1, 6]
292)
293
294assert (
295    answer([
296        [0, 86, 61, 189, 0, 18, 12, 33, 66, 39],
297        [0, 0, 2, 0, 0, 1, 0, 0, 0, 0],
298        [15, 187, 0, 0, 18, 23, 0, 0, 0, 0],
299        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
300        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
301        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
302        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
303        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
304        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
305        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
306    ]) == [6, 44, 4, 11, 22, 13, 100]
307)
308
309assert (
310    answer([
311        [0, 0, 0, 0, 3, 5, 0, 0, 0, 2],
312        [0, 0, 4, 0, 0, 0, 1, 0, 0, 0],
313        [0, 0, 0, 4, 4, 0, 0, 0, 1, 1],
314        [13, 0, 0, 0, 0, 0, 2, 0, 0, 0],
315        [0, 1, 8, 7, 0, 0, 0, 1, 3, 0],
316        [1, 7, 0, 0, 0, 0, 0, 2, 0, 0],
317        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
318        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
319        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
320        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
321    ]) == [1, 1, 1, 2, 5]
322)