<s> def is_zero ( x ) : <EOL> """<STR_LIT>""" <EOL> return - <NUM_LIT> < x and x < <NUM_LIT> <EOL> GJ_ZERO_SOLUTIONS = <NUM_LIT:0> <EOL> GJ_UNE_SOLUTION = <NUM_LIT:1> <EOL> GJ_PLUSIEURS_SOLUTIONS = <NUM_LIT:2> <EOL> def gauss_jordan ( A , x , b ) : <EOL> """<STR_LIT>""" <EOL> n = len ( x ) <EOL> m = len ( b ) <EOL> assert len ( A ) == m and len ( A [ <NUM_LIT:0> ] ) == n <EOL> S = [ ] <EOL> for i in range ( m ) : <EOL> S . append ( A [ i ] [ : ] + [ b [ i ] ] ) <EOL> S . append ( list ( range ( n ) ) ) <EOL> k = diagonalize ( S , n , m ) <EOL> if k < m : <EOL> for i in range ( k , m ) : <EOL> if not is_zero ( S [ i ] [ n ] ) : <EOL> return GJ_ZERO_SOLUTIONS <EOL> for j in range ( k ) : <EOL> x [ S [ m ] [ j ] ] = S [ j ] [ n ] <EOL> if k < n : <EOL> for j in range ( k , n ) : <EOL> x [ S [ m ] [ j ] ] = <NUM_LIT:0> <EOL> return GJ_PLUSIEURS_SOLUTIONS <EOL> return GJ_UNE_SOLUTION <EOL> def diagonalize ( S , n , m ) : <EOL> for k in range ( min ( n , m ) ) : <EOL> val , i , j = max ( ( abs ( S [ i ] [ j ] ) , i , j ) <EOL> for i in range ( k , m ) for j in range ( k , n ) ) <EOL> if is_zero ( val ) : <EOL> return k <EOL> S [ i ] , S [ k ] = S [ k ] , S [ i ] <EOL> for r in range ( m + <NUM_LIT:1> ) : <EOL> S [ r ] [ j ] , S [ r ] [ k ] = S [ r ] [ k ] , S [ r ] [ j ] <EOL> pivot = float ( S [ k ] [ k ] ) <EOL> for j in range ( k , n + <NUM_LIT:1> ) : <EOL> S [ k ] [ j ] /= pivot <EOL> for i in range ( m ) : <EOL> if i != k : <EOL> fact = S [ i ] [ k ] <EOL> for j in range ( k , n + <NUM_LIT:1> ) : <EOL> S [ i ] [ j ] -= fact * S [ k ] [ j ] <EOL> return min ( n , m ) </s>
