fork download
copy 
  1. P1 = [[0, 1, 0, 0, 0, 1], [4, 0, 0, 3, 2, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]
  2. P2 = [[0, 2, 1, 0, 0], [0, 0, 0, 3, 4], [0, 0, 0, 0, 0], [0, 0, 0, 0,0], [0, 0, 0, 0, 0]]
  3. import numpy as np
  4.  
  5. def solution(m):
  6.     m = np.matrix(m, dtype=float)
  7.     # Diagonal cases are not relevant
  8.     for i in range(len(m)):
  9.         m[i, i] = 0
  10.     active, stable = separate(m)
  11.     # Check if first state is stable
  12.     if 0 in stable:
  13.         return [1] + [0]*(len(m)-2) + [1]
  14.     # Take only active states
  15.     m = m[active]
  16.     # Get common denominator
  17.     c_denom = np.lcm.reduce(np.sum(m, axis=1).A1.astype(int))
  18.     row_metric = np.sum(m, axis=1)
  19.     prob_matrx = m / row_metric
  20.     # Take matrix Q
  21.     Q = prob_matrx[:, active]
  22.     # Take matrix R
  23.     R = prob_matrx[:, stable]
  24.  
  25.     # Compute fundamental matrix
  26.     F = (np.identity(len(active)) - Q) ** -1
  27.     FR = F.dot(R)
  28.     # Re-apply metric and correct the inverse distortion
  29.     # Found after headaching trial and error
  30.     FR = np.multiply(FR, c_denom) / np.linalg.det(F)
  31.     print((np.multiply(FR, c_denom) / np.linalg.det(F)).dtype)
  32.     # Integer black magic
  33.     FR = FR.round().astype(np.int32)
  34.     ret = list(FR[0].A1) + [np.sum(FR[0]).astype(np.int32)]
  35.     for i in range(len(ret)):
  36.     	print(type(ret[i]))
  37.     return list(FR[0].A1) + [np.sum(FR[0])]
  38. def separate(m):
  39.     act_idx, stb_idx = [], []
  40.     for i, el in enumerate(m):
  41.         if np.any(el):
  42.             act_idx.append(i)
  43.         else:
  44.             stb_idx.append(i)
  45.     return act_idx, stb_idx
  46. print(solution(P1))
  47. print(solution(P2))
Success #stdin #stdout 0.07s 24392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
float64
<type 'numpy.int32'>
<type 'numpy.int32'>
<type 'numpy.int32'>
<type 'numpy.int32'>
<type 'numpy.int32'>
[0, 3, 2, 9, 14]
float64
<type 'numpy.int32'>
<type 'numpy.int32'>
<type 'numpy.int32'>
<type 'numpy.int32'>
[7, 6, 8, 21]
https://ideone.com/kpxbqq
language:
Python (cpython 2.7.16)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!