type Coins = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13

// Defines weighing setup to systematically compare two groups of coins
type WeighingSetup1 = {Left: readonly Coins[], Right: readonly Coins[]}
type WeighingSetup2 = {HeavierOnLeft: WeighingSetup1, HeavierOnRight: WeighingSetup1, EqualWeight: WeighingSetup1}
type WeighingSetup3 = {HeavierOnLeft: WeighingSetup2, HeavierOnRight: WeighingSetup2, EqualWeight: WeighingSetup2}

/**
 * Below is the templates to get start
 */


const Weigh1 = {
  Left: [1, 2, 3, 4, 5, 6], Right: [7, 8, 9, 10, 11, 12]
} as const satisfies WeighingSetup1
/**
 * Weigh1: Initial weighing setup
 * 
 *        Left Side               Right Side
 *    1  2  3  4  5  6       7  8  9  10  11  12   
 * \-------------------/    \-------------------/
 *           \                        /
 *            \----------------------/
 *                        ^
 * 
 * This const is used to explain how the first weighing setup works.
 * Coins 1 to 6 are placed on the left side of the scale,
 * and coins 7 to 12 are placed on the right side of the scale.
 * Coin 13 is not included in this weighing.
 **/

const Weigh2 = {
  HeavierOnLeft: {Left: [1, 2, 3], Right: [4, 5, 6]},
  HeavierOnRight: {Left: [7, 8, 9], Right: [10, 11, 12]},
  EqualWeight: {Left: [1], Right: [13]},
} as const satisfies WeighingSetup2
/**
 * Weigh2: Determines the second weighing setup based on the outcome of the first weighing
 *
 * If the left side is heavier:
 *    { Left: [1, 2, 3], Right: [4, 5, 6] }
 * If the right side is heavier:
 *    { Left: [7, 8, 9], Right: [10, 11, 12] }
 * If both sides are equal:
 *    { Left: [1], Right: [13] }
 */

const Weigh3 = {
  HeavierOnLeft: {
    HeavierOnLeft: {Left: [1], Right: [2]},
    HeavierOnRight: {Left: [4], Right: [5]},
    EqualWeight: {Left: [], Right: []}
  },
  HeavierOnRight: {
    HeavierOnLeft: {Left: [7], Right: [8]},
    HeavierOnRight: {Left: [10], Right: [11]},
    EqualWeight: {Left: [], Right: []}
  },
  EqualWeight: {
    HeavierOnLeft: {Left: [], Right: []},
    HeavierOnRight: {Left: [], Right: []},
    EqualWeight: {Left: [], Right: []}
  }
} as const satisfies WeighingSetup3
/**
 * Weigh3: Determines the third weighing setup based on the outcome of the first and second weighings
 *
 * If Outcome1 indicates the left side is heavier:
 *    - If Outcome2 also indicates the left side is heavier:
 *        { Left: [1], Right: [2] }
 *    - If Outcome2 indicates the right side is heavier:
 *        { Left: [4], Right: [5] }
 *    - Otherwise:
 *        { Left: [], Right: [] }
 *
 * If Outcome1 indicates the right side is heavier:
 *    - If Outcome2 indicates the left side is heavier:
 *        { Left: [7], Right: [8] }
 *    - If Outcome2 also indicates the right side is heavier:
 *        { Left: [10], Right: [11] }
 *    - Otherwise:
 *        { Left: [], Right: [] }
 *
 * If Outcome1 indicates both sides are equal:
 *    - If Outcome2 indicates the left side is heavier:
 *        { Left: [], Right: [] }
 *    - If Outcome2 indicates the right side is heavier:
 *        { Left: [], Right: [] }
 *    - Otherwise:
 *        { Left: [], Right: [] }
 */

/**
 * Instructions to Solve the Puzzle:
 *
 * 1. Scroll Down to Check Test Cases:
 *    - Specifically look for how many unidentified fake coins.
 *
 * 2. Why It Is Not Working:
 *    - The above template assumes the fake coin is heavier than the real coin. This assumption might not always hold true.
 *
 * 3. Guide to Revise All Three Weigh Types:
 *    - `Weigh1`, `Weigh2`, `Weigh3`: Ensure that the weighing setup is designed so that no matter which coin is fake, it can be identified.
 *    - Coins not appearing in previous weighing setups can also be used.
 */

printFakeCoin(Weigh1, Weigh2, Weigh3)

import type { Equal, Expect } from '@type-challenges/utils'

type UnidentifiedFakeCoins = FindUnidentifiedFakeCoins<typeof Weigh1, typeof Weigh2, typeof Weigh3>
type UnknownFakeCoinStatuses = FindUnknownFakeCoinStatuses<typeof Weigh1, typeof Weigh2, typeof Weigh3>

type cases = [
  Expect<Equal<UnidentifiedFakeCoins, never>>,
  Expect<Equal<HasMoreCoinsThaan<UnknownFakeCoinStatuses, 1>, false>>,
]

declare function printFakeCoin<
  Setup1 extends WeighingSetup1, Setup2 extends WeighingSetup2, Setup3 extends WeighingSetup3,
  UnidentifiedFakeCoins extends Coins = FindUnidentifiedFakeCoins<Setup1, Setup2, Setup3>,
  UnknownFakeCoinStatuses extends Coins = FindUnknownFakeCoinStatuses<Setup1, Setup2, Setup3>,
  Unidentified extends Coins = [UnidentifiedFakeCoins] extends [never] ? HasMoreCoinsThaan<UnknownFakeCoinStatuses, 1> extends false ? never : UnknownFakeCoinStatuses : UnidentifiedFakeCoins
  >(
    s1: Setup1, s2: Setup2,
    s3: [Unidentified] extends [never] ? Setup3 : {error: `Unidentified: ${Unidentified}`}
  ): void

// Defines possible outcomes to determine the weight relationship between two groups of coins
type WeighingOutcome = 'HeavierOnLeft' | 'HeavierOnRight' | 'EqualWeight'
type WeighingResult = {Heavier: Coins, Lighter: Coins, Equal: Coins}

type FakeCoinStatuses = 'Heavier' | 'Lighter'

type DetermineOutcome<Setup extends WeighingSetup1, FakeCoin extends Coins, FakeCoinStatus extends FakeCoinStatuses>
  = [Setup] extends [never] ? never
  : IsCoinsValid<Setup['Left'], Setup['Right']> extends false ? never
  : HasMoreCoinsThaan<Setup['Left'][number], Setup['Right'][number]> extends true ? 'HeavierOnLeft'
  : HasMoreCoinsThaan<Setup['Right'][number], Setup['Left'][number]> extends true ? 'HeavierOnRight'
  : [FakeCoin, FakeCoinStatus] extends [Setup['Left'][number], 'Heavier'] | [Setup['Right'][number], 'Lighter'] ? 'HeavierOnLeft'
  : [FakeCoin, FakeCoinStatus] extends [Setup['Right'][number], 'Heavier'] | [Setup['Left'][number], 'Lighter'] ? 'HeavierOnRight'
  : 'EqualWeight'

type DetermineResult<Setup extends WeighingSetup1, FakeCoin extends Coins, FakeCoinStatus extends FakeCoinStatuses>
  = [Setup] extends [never] ? never
  : IsCoinsValid<Setup['Left'], Setup['Right']> extends false ? never
  : HasMoreCoinsThaan<Setup['Left'][number], Setup['Right'][number]> extends true ? {Heavier: Setup['Left'][number], Lighter: Setup['Right'][number], Equal: never}
  : HasMoreCoinsThaan<Setup['Right'][number], Setup['Left'][number]> extends true ? {Heavier: Setup['Right'][number], Lighter: Setup['Left'][number], Equal: never}
  : [FakeCoin, FakeCoinStatus] extends [Setup['Left'][number], 'Heavier'] | [Setup['Right'][number], 'Lighter'] ? {Heavier: Setup['Left'][number], Lighter: Setup['Right'][number], Equal: never}
  : [FakeCoin, FakeCoinStatus] extends [Setup['Right'][number], 'Heavier'] | [Setup['Left'][number], 'Lighter'] ? {Heavier: Setup['Right'][number], Lighter: Setup['Left'][number], Equal: never}
  : {Heavier: never, Lighter: never, Equal: Setup['Left'][number] | Setup['Right'][number]}

type IsCoinsValid<Left extends readonly Coins[], Right extends readonly Coins[]>
  = number extends Left | Right ? false
  : [ keyof {[I in keyof Left & `${number}` as keyof {[J in Exclude<keyof Left & `${number}`, I> as Left[I] extends Left[J] ? J : never]: J}]: I} | 
      keyof {[I in keyof Right & `${number}` as keyof {[J in Exclude<keyof Right & `${number}`, I> as Right[I] extends Right[J] ? J : never]: J}]: I}
  ] extends [never]
    ? [Left[number] & Right[number]] extends [never] ? true
    : false
  : false

type HasMoreCoinsThaan<A extends Coins, B extends Coins>
  = [A, B] extends [never, never] ? false
  : [A] extends [never] ? false
  : [B] extends [never] ? true
  : true extends {[X in A]: {[Y in B]: HasMoreCoinsThaan<Exclude<A, X>, Exclude<B, Y>>}[B]}[A] ? true : false

type OneCoinOrNever<LeftOrRight extends Coins, U extends Coins = LeftOrRight>
  = [U] extends [never] ? never
  : [U extends U ? Exclude<LeftOrRight, U> : never] extends [never] ? U
  : never

type FindUnidentifiedFakeCoins<Setup1 extends WeighingSetup1, Setup2 extends WeighingSetup2, Setup3 extends WeighingSetup3>
  = {[FakeCoin in Coins]: {[FakeCoinStatus in FakeCoinStatuses]
      : DetermineOutcome<Setup1, FakeCoin, FakeCoinStatus> extends infer Outcome1 extends WeighingOutcome
        ? DetermineOutcome<Setup2[Outcome1], FakeCoin, FakeCoinStatus> extends infer Outcome2 extends WeighingOutcome
          ? DetermineFakeCoin<DetermineResult<Setup1, FakeCoin, FakeCoinStatus>
            | DetermineResult<Setup2[Outcome1], FakeCoin, FakeCoinStatus>
            | DetermineResult<Setup3[Outcome1][DetermineOutcome<Setup2[DetermineOutcome<Setup1, FakeCoin, FakeCoinStatus>], FakeCoin, FakeCoinStatus>], FakeCoin, FakeCoinStatus>
            > extends FakeCoin ? never
          : FakeCoin
        : FakeCoin
      : FakeCoin
    }[FakeCoinStatuses]}[Coins]

type FindUnknownFakeCoinStatuses<Setup1 extends WeighingSetup1, Setup2 extends WeighingSetup2, Setup3 extends WeighingSetup3>
  = {[FakeCoin in Coins]: {[FakeCoinStatus in FakeCoinStatuses]
      : DetermineOutcome<Setup1, FakeCoin, FakeCoinStatus> extends infer Outcome1 extends WeighingOutcome
        ? DetermineOutcome<Setup2[Outcome1], FakeCoin, FakeCoinStatus> extends infer Outcome2 extends WeighingOutcome
          ? DetermineFakeCoin<DetermineResult<Setup1, FakeCoin, FakeCoinStatus>
            | DetermineResult<Setup2[Outcome1], FakeCoin, FakeCoinStatus>
            | DetermineResult<Setup3[Outcome1][DetermineOutcome<Setup2[DetermineOutcome<Setup1, FakeCoin, FakeCoinStatus>], FakeCoin, FakeCoinStatus>], FakeCoin, FakeCoinStatus>
            > extends FakeCoin
            ? UnknownFakeCoinStatus<FakeCoin, DetermineResult<Setup1, FakeCoin, FakeCoinStatus>
              | DetermineResult<Setup2[Outcome1], FakeCoin, FakeCoinStatus>
              | DetermineResult<Setup3[Outcome1][Outcome2], FakeCoin, FakeCoinStatus>
              >
          : FakeCoin
        : FakeCoin
      : FakeCoin
    }[FakeCoinStatuses]}[Coins]

/*******************************************
 *             Spoiler Alert
 *******************************************
 */
type DetermineFakeCoin<Results extends WeighingResult, O extends Results = Results>
  = (O extends O
      ? O extends {Heavier: Coins, Lighter: Coins}
        ? O['Heavier'] extends IdentifiedRealCoin<Results> ? OneCoinOrNever<Exclude<O['Lighter'], IdentifiedRealCoin<Results>>>
        : O['Lighter'] extends IdentifiedRealCoin<Results> ? OneCoinOrNever<Exclude<O['Heavier'], IdentifiedRealCoin<Results>>>
        : never
      : never
    : never) extends infer FakeCoin extends Coins
      ? [FakeCoin] extends [never] ? Exclude<Coins, IdentifiedRealCoin<Results>>
      : FakeCoin
    : Exclude<Coins, IdentifiedRealCoin<Results>>

type IdentifiedRealCoin<Results extends WeighingResult, C extends Coins = Coins>
  = C extends C
    ? C extends Results['Heavier'] & Results['Lighter'] ? C
    : C extends Results['Equal'] ? C
    : never
  : never

type UnknownFakeCoinStatus<FakeCoin extends Coins, Reaults extends WeighingResult, O extends Reaults = Reaults>
  = FakeCoin extends (O extends O ? O['Heavier'] | O['Lighter'] | O['Equal'] : never) ? never : FakeCoin