// Linear representation of <a, b | aaa=1, abbbba=b>

// If you need to perform calculations in this monoid, you could,
// of course, encode it as a Swift protocol, and then operate on
// the 1083 distinct type parameters at compile time:
//
// protocol M {
//   associatedtype A: M
//   associatedtype B: M where A.A.A == Self, A.B.B.B.B.A == B
// }
// 
// struct G<T: M> {
//   func f(_ t: T.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B) -> T.B {   
//     return t  // Success! b^91 = b
//   }
// }
//
// However, this is a bit slow, and requires passing a special frontend
// flag -Xfrontend -requirement-machine-max-rule-length=15. Here is a
// more direct approach.
//
// An element of this monoid is represented as a triple consisting of
// of an integer mod 9, a 2x2 matrix with integer entries and
// determinant equal to 1 mod 5, and a boolean flag.
//
// Don't call the initializer directly; not every combination of stored
// property values defines a valid element of the monoid. Only elements
// obtained by applying * to a, b, and identity are valid. There are
// exactly 1083 such possible values.
struct M: Hashable {
  // The Z9 part:
  let x: Int8

  // The SL(2, 5) part:
  let y00: Int8
  let y01: Int8
  let y10: Int8
  let y11: Int8

  // The "pure power of a" flag:
  let z: Bool

  // The identity element:
  static let identity = M(x: 0, y00: 1, y01: 0, y10: 0, y11: 1, z: true)
  
  // Two generators:
  static let a = M(x: 3, y00: 0, y01: 1, y10: 4, y11: 4, z: true)
  static let b = M(x: 1, y00: 0, y01: 2, y10: 2, y11: 3, z: false)

  // Multiply two elements:
  static func *(lhs: Self, rhs: Self) -> Self {
    return M(x: (lhs.x + rhs.x) % 9,
             y00: (lhs.y00 * rhs.y00 + lhs.y01 * rhs.y10) % 5,
             y01: (lhs.y00 * rhs.y01 + lhs.y01 * rhs.y11) % 5,
             y10: (lhs.y10 * rhs.y00 + lhs.y11 * rhs.y10) % 5,
             y11: (lhs.y10 * rhs.y01 + lhs.y11 * rhs.y11) % 5,
             z: lhs.z && rhs.z)
  }
}

// Check that the two given elements satisfy the defining relations.
func relations(_ a: M, _ b: M) -> Bool {
   return a * a * a == .identity &&
          a * b * b * b * b * a == b
}

// Compute the size of the submonoid generated by the two given elements.
func closure(_ a: M, _ b: M) -> Int {
  var unique: Set<M> = []
  var worklist: [M] = []

  worklist.append(.identity)

  while !worklist.isEmpty {
    let x = worklist.removeLast()
    for y in [a, b] {
      let xy = x * y
      if unique.insert(xy).inserted {
        worklist.append(xy)
      }
    }
  }

  return unique.count
}

// Our 'a' and 'b' defined above should satisfy the defining relations.
precondition(relations(.a, .b))

// They should also generate the entire monoid.
precondition(closure(.a, .b) == 1083)