-

I = [5, 6, 7]
matrix = [
  [1, 10, -57, -9, -24, 0, 0, 0, 0]
  [0, 0.5, -5.5, -2.5, 9, 1, 0, 0, 0]
  [0, 0.5, -1.5, -0.5, 1, 0, 1, 0, 0]
  [0, 1, 0, 0, 0, 0, 0, 1, 1]
]

max = (array) ->
  m = -Infinity
  mI = 0
  for el, i in array
    if el > m
      m = el
      mI = i
  [m, mI]

min = (array) ->
  m = Infinity
  mI = 0
  for el, i in array
    if el < m
      m = el
      mI = i
  [m, mI]


step = (matrix, I) ->
  [objective, basics...] = matrix
  [value, newBasic] = max objective
  if value <= 0
    return
  [value, newNonBasicI] = min (row[row.length - 1] / row[newBasic] for row in basics)

  newNonBasic = I[newNonBasicI]
  pivotRow = basics[newNonBasicI]
  pivot = pivotRow[newBasic]

  pivotRow = (el / pivot for el in pivotRow)

  newMatrix =
    for row in matrix
      q = row[newBasic]
      for el, i in row
        el - q * pivotRow[i]
  newMatrix[1 + newNonBasicI] = pivotRow

  newI = for v in I
    if v is newNonBasic
      newBasic
    else
      v

  [newMatrix, newI]


simplex = (matrix, I, limit) ->
  for i in [0...limit]
    res = step matrix, I
    break unless res
    printTableau [matrix, I] = res

printTableau = ([matrix, I]) ->
  head = "\tz\t" + ("x<sub>#{i}</sub>" for i in [1...matrix[0].length - 1]).join '\t'
  
  I = ["z"].concat I
  head += "<br>" + ((for row, i in matrix
    I[i] + "\t" + (toSimpleFraction el for el in row).join '\t'
  ).join '<br>') + "<br><br>"
      
    
  
  
  
toSimpleFraction = (x) ->  
  [v, d] = toFraction x
  if d == 1
    v
  else
    "#{v}/#{d}"
  
toFraction = (x, error = 0.000001) ->
  n = Math.floor x
  x -= n
  if x < error
    return [n, 1]
  else if 1 - error < x
    return [n + 1, 1]

  # The lower fraction is 0/1
  lower_n = 0
  lower_d = 1
  # The upper fraction is 1/1
  upper_n = 1
  upper_d = 1
  loop
    # The middle fraction is (lower_n + upper_n) / (lower_d + upper_d)
    middle_n = lower_n + upper_n
    middle_d = lower_d + upper_d
    # If x + error < middle
    if middle_d * (x + error) < middle_n
      # middle is our new upper
      upper_n = middle_n
      upper_d = middle_d
    # Else If middle < x - error
    else if middle_n < (x - error) * middle_d
      # middle is our new lower
      lower_n = middle_n
      lower_d = middle_d
    # Else middle is our best fraction
    else
      return [n * middle_d + middle_n, middle_d]