ritchie/hand/decompose

Tile decomposer. Takes a hand, and finds waiting patterns. Importantly, it finds all possible patterns, which is important, because we want the most valuable potential winning hand, scoring-wise. Waits break down into the following categories:

• Regular waits: The classic 3N+2 pattern, waiting on either a group or a pair. Can break down into the basic wait patterns (ryanmen/open, kanchan/middle, penchan/edge, tanki/pair)
• Irregular waits:
  • Kokushi mosou (thirteen orphans): Waiting on a terminal/honor with all other tiles being unique (+1) terminal/honor
  • Chiitoitsu (seven pairs): Six other pairs, tanki wait, no other wait patterns possible

The algorithm for decomposition works roughly like this:

• The hand gets passed in as TileSet37. We convert it into a TileSet34 first, to save us the trouble of dealing with red tiles. The red tiles are saved and reattached at the end.
• We first validate the possible shapes of the hand. To do this, we take each suit, and systematically remove 1) triplets, 2) sequences, 3) pairs, 4) waiting sets, and 5) tanki waits (single tiles waiting for pair). We do this recursively, building up a tree structure. Only branches with empty leaves (meaning all tiles get popped along the way) are valid.
• Still for each suit, we then turn each possible tree node path into its own tree, so that we end up with a list of full decompositions of the hand. We then sort and deduplicate them.
• Now, we combine each suit’s list with each other (so we create the cartesian product). We re-append the melds to each of the resulting combinations.
• We now filter combinations that would constitute a regular hand. This means only accepting:
  • 4 blocks + 1 tanki/pair wait
  • 3 blocks + 1 pair + 1 wait (ryanmen/kanchan/penchan)
• We also filter out “illegal” hands. This means empty hands, a shanpon (double pair) wait where the pair and the wait need the same tile, or a tanki (pair) wait where three of that tile are already in hand.
• In addition to the regular decomposition, we count pairs directly (for chiitoitsu) and distinct terminal/honor tiles (for kokushi mosou). These irregular shapes are mutually exclusive with each other, but can coexist with a regular interpretation (e.g. 1122334455667m is both a regular hand and chiitoitsu), so all interpretations are returned. 13 distinct terminals/honors here means a 13-sided wait, and 11 distinct plus a pair means a single wait.
• Finally, we re-attach the red fives. wtiles (the tiles that would complete the hand) are always reported as normal tiles: a wait on 0m is reported as 5m, since either copy completes the hand.

pub type Block {
  Block(kind: BlockKind, t: List(tile.Tile))
}

pub type BlockKind {
  Sequence
  Triplet
  MeldedSequence
  MeldedTriplet
  MeldedKan
  MeldedAnkan
}

pub type DecompNode {
  DecompNode(
    kind: DecompNodeKind,
    tiles: List(tile.Tile),
    children: List(DecompNode),
  )
}

pub type DecompNodeKind {
  DTriplet
  DSequence
  DPair
  DWait(WaitingKind)
}

pub type DecomposedHand {
  RegularHand(
    blocks: List(Block),
    pair: option.Option(List(tile.Tile)),
    wkind: WaitingKind,
    wtiles: List(tile.Tile),
  )
  SevenPairs(
    pairs: List(List(tile.Tile)),
    wkind: WaitingKind,
    wtiles: List(tile.Tile),
  )
  ThirteenOrphans(
    tiles: List(tile.Tile),
    pair: option.Option(List(tile.Tile)),
    wkind: WaitingKind,
    wtiles: List(tile.Tile),
  )
}

pub type FlattenedDecompNode {
  FlattenedDecompNode(
    kind: DecompNodeKind,
    tiles: List(tile.Tile),
  )
}

pub type Shape {
  ShapeBlock(block: Block)
  ShapePair(tiles: List(tile.Tile))
  ShapeWait(kind: WaitingKind)
}

pub type WaitingKind {
  Pattern(pattern: WaitingPattern, tiles: List(tile.Tile))
  Tanki(tile: tile.Tile)
  Single(tile: tile.Tile)
  AllOrphans(tiles: List(tile.Tile))
}

pub type WaitingPattern {
  Penchan
  Kanchan
  Ryanmen
  Shanpon
}

pub fn decomp_to_thing(decomp: FlattenedDecompNode) -> Shape

pub fn decompose(
  hand: tile_set37.TileSet37,
  melds: List(meld.Meld),
) -> List(DecomposedHand)

pub fn decompose_regular(
  hand: tile_set34.TileSet34,
  melds: List(Block),
) -> List(DecomposedHand)

pub fn decompose_seven_pairs(
  hand: tile_set34.TileSet34,
) -> List(DecomposedHand)

pub fn decompose_suit(
  hand: tile_set34.TileSet34,
  suit: Int,
) -> List(DecompNode)

pub fn decompose_thirteen_orphans(
  hand: tile_set34.TileSet34,
) -> option.Option(DecomposedHand)

pub fn expected_hand_size(melds: List(meld.Meld)) -> Int

pub fn flatten_decomposition(
  nodes: List(DecompNode),
) -> List(List(FlattenedDecompNode))

pub fn pop_pairs(
  hand: tile_set34.TileSet34,
  suit: Int,
) -> List(#(tile_set34.TileSet34, List(tile.Tile)))

pub fn pop_sequences(
  hand: tile_set34.TileSet34,
  suit: Int,
) -> List(#(tile_set34.TileSet34, List(tile.Tile)))

pub fn pop_tanki(
  hand: tile_set34.TileSet34,
  suit: Int,
) -> List(#(tile_set34.TileSet34, tile.Tile))

pub fn pop_triplets(
  hand: tile_set34.TileSet34,
  suit: Int,
) -> List(#(tile_set34.TileSet34, List(tile.Tile)))

pub fn pop_waiting_sets(
  hand: tile_set34.TileSet34,
  suit: Int,
) -> List(
  #(WaitingPattern, tile_set34.TileSet34, List(tile.Tile)),
)

pub fn wtiles(decomp: DecomposedHand) -> List(tile.Tile)