+/foobar
google programming puzzles
git clone https://git.julia.blue/+/foobar
2e1d345
master
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 : 13def __init__ (self ,height ,width ): 14self .rows = height 15self .cols = width 16self .m = [[0 for i in range (height )]for j in range (width )] 17 18def minor (self ,r ,c ): 19result = Matrix (self .rows - 1 ,self .cols - 1 ) 20result .m = [row [:]for row in self .m ] 21del result .m [r ] 22for row in result .m : 23del row [c ] 24return result 25 26def cofactor (self ,r ,c ): 27return (self .m [r ][c ]* (1 if (r + c )% 2 == 0 else - 1 ) 28* self .minor (r ,c ).det ()) 29 30def det (self ): 31if self .rows == 2 : 32return self .m [0 ][0 ]* self .m [1 ][1 ]- self .m [1 ][0 ]* self .m [0 ][1 ] 33return sum (self .cofactor (0 ,i )for i in range (self .cols )) 34 35def adjoint (self ): 36result = Matrix (self .rows ,self .cols ) 37result .m = [row [:]for row in self .m ] 38for i in range (result .rows ): 39for j in range (i + 1 ,result .cols ): 40result .m [i ][j ],result .m [j ][i ]= result .m [j ][i ],result .m [i ][j ] 41return result 42 43def inverse (self ): 44det = self .det () 45if self .rows == 2 : 46result = Matrix (2 ,2 ) 47result .m [0 ][0 ]= self .m [1 ][1 ]/ det 48result .m [1 ][0 ]= - self .m [1 ][0 ]/ det 49result .m [0 ][1 ]= - self .m [0 ][1 ]/ det 50result .m [1 ][1 ]= self .m [0 ][0 ]/ det 51return result 52temp = Matrix (self .rows ,self .cols ) 53temp .m = [row [:]for row in self .m ] 54for i in range (temp .rows ): 55for j in range (temp .cols ): 56temp .m [i ][j ]= (self .minor (i ,j ).det () 57* - (((i + j )% 2 )* 2 - 1 )) 58temp = temp .adjoint () 59for i in range (temp .rows ): 60for j in range (temp .cols ): 61temp .m [i ][j ]/= det 62return temp 63 64def __sub__ (self ,other ): 65result = Matrix (self .rows ,self .cols ) 66for i in range (self .rows ): 67for j in range (self .cols ): 68result .m [i ][j ]= self .m [i ][j ]- other .m [i ][j ] 69return result 70 71def __mul__ (self ,other ): 72result = Matrix (other .cols ,self .rows ) 73for i in range (result .cols ): 74for j in range (result .rows ): 75dot = 0 76for k in range (self .cols ): 77dot += self .m [i ][k ]* other .m [k ][j ] 78result .m [i ][j ]= dot 79return result 80 81def __str__ (self ): 82return '\n' .join ( 83 [' ' .join (["{0:>3}" .format (i )for i in row ])for row in self .m ]) 84 85 86def identity (size ): 87result = Matrix (size ,size ) 88for i in range (size ): 89result .m [i ][i ]= 1 90return result 91 92 93def answer (m ): 94if len (m )<= 2 : 95return [1 ,1 ] 96fixed = [m [0 ]] 97front = 1 98for i in range (1 ,len (m )): 99if any (m [i ]): 100fixed .append (m [i ]) 101while i > front : 102for row in m : 103row [i ],row [i - 1 ]= row [i - 1 ],row [i ] 104i -= 1 105front += 1 106m = fixed 107for row in m : 108temp = sum (row ) 109for i in range (len (row )): 110row [i ]= Fraction (row [i ])/ temp 111size = len (m ) 112q = Matrix (size ,size ) 113q .m = [row [:size ]for row in m [:size ]] 114r = Matrix (size ,len (m [0 ])- size ) 115r .m = [row [size :]for row in m [:size ]] 116i = 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 129ans = r if q .rows == 1 else (i - q ).inverse ()* r 130total_gcd = reduce ((lambda x ,y :gcd (x ,y )),ans .m [0 ]) 131return [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 b 151# 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 195answer (test1 ) 196answer (test2 ) 197 198assert ( 199answer ([ 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 ( 209answer ([ 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 ( 220answer ([ 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 ( 230answer ([ 231 [0 ] 232 ])== [1 ,1 ] 233) 234 235assert ( 236answer ([ 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 ( 250answer ([ 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 ( 265answer ([ 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 ( 280answer ([ 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 ( 295answer ([ 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 ( 310answer ([ 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)