30430-medium-tower-of-hanoi

Back 

// your answers
// 汉诺塔算法：递归，步骤 1 和 3 是递归子问题
// 1. 将 n-1 个盘子经过 B 移动到 C
// 2. 将第 n 个盘子从 A 移动到 B
// 3. 将 n-1 个盘子从 C 经过 A 移动到 B
type Hanoi<
  N extends number,
  From = "A",
  To = "B",
  Intermediate = "C",
  CurrentIndex extends number[] = []
> = CurrentIndex["length"] extends N
  ? []
  : [
      ...Hanoi<N, From, Intermediate, To, [...CurrentIndex, 1]>,
      [From, To],
      ...Hanoi<N, Intermediate, To, From, [...CurrentIndex, 1]>
    ];

Solution by BruceYuj #35471 

type Decrease<N extends number, U extends any[] = []> = [...U, any]['length'] extends N ? U['length'] : Decrease<N, [...U, any]>
type Hanoi<N extends number, From = 'A', To = 'B', Intermediate = 'C'> = N extends 0 ? [] : [...Hanoi<Decrease<N>, From, Intermediate, To>, [From, To], ...Hanoi<Decrease<N>, Intermediate, To, From>]

Solution by 2083335157 #34990 


type MinusOne<N, Result extends 0[] = []> =
  [...Result, 0]['length'] extends N
    ? Result['length']
    : MinusOne<N, [...Result, 0]>


type Hanoi<N extends number, From = 'A', To = 'B', Intermediate = 'C'> =
  N extends 0
    ? []
    : N extends 1
      ? [[From, To]]
      : [
        ...Hanoi<MinusOne<N>, From, Intermediate, To>,
        [From, To],
        ...Hanoi<MinusOne<N>, Intermediate, To, From>
      ]

Solution by drylint #34195 

type Hanoi<N extends number, From = 'A', To = 'B', Temp = 'C', CurIdx extends 0[] = []> =CurIdx['length'] extends N ? [] : [
  ...Hanoi<N, From, Temp, To, [...CurIdx, 0]>, [From, To], ...Hanoi<N, Temp, To, From, [...CurIdx, 0]>
]

Solution by ouzexi #34174 

// Type to simulate the steps required to solve the Tower of Hanoi puzzle for N disks.
// `From`, `To`, and `Aux` represent the three rods involved.
type Hanoi<N extends number, From = 'A', To = 'B', Aux = 'C'>
  = N extends 0 ? [] : [  // Base case: no moves needed for zero disks.
    ...Hanoi<MinusOne<N>, From, Aux, To>,
    [From, To],
    ...Hanoi<MinusOne<N>, Aux, To, From>,
  ]

type MinusOne<N extends number, D extends number[] = [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8]>
  = (`${N}` extends `${infer L extends number}0` ? `${L extends 1 ? '' : MinusOne<L>}9`
  : {[I in keyof D]: `${N}` extends `${infer L}${I}` ? `${L}${D[I]}` : never}[number]
  ) extends `${infer N extends number}` ? N : never

Playground

// Type to simulate the steps required to solve the Tower of Hanoi puzzle for N disks.
// `From`, `To`, and `Aux` represent the three rods involved.
type Hanoi<N extends number, From = 'A', To = 'B', Aux = 'C'> =  N extends 0 ? [] : IterativeHanoi<[[N, From, To, Aux]]>

type IterativeHanoi<Stack extends unknown[], Moves extends unknown[] = []>
  = Stack extends [...infer Stack, [infer N extends number, infer From, infer To, infer Aux]]
    ? N extends 1
      ? IterativeHanoi<Stack, [...Moves, [From, To]]>
      : IterativeHanoi<[...Stack,
        [MinusOne<N>, Aux, To, From],
        [1, From, To, Aux],
        [MinusOne<N>, From, Aux, To]], Moves>
    : Moves

type MinusOne<N extends number, D extends number[] = [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8]>
  = (`${N}` extends `${infer L extends number}0` ? `${L extends 1 ? '' : MinusOne<L>}9`
  : {[I in keyof D]: `${N}` extends `${infer L}${I}` ? `${L}${D[I]}` : never}[number]
  ) extends `${infer N extends number}` ? N : never

Playground

Solution by teamchong #32993 

type Hanoi<
  N extends number,
  From = "A",
  To = "B",
  Intermediate = "C"
> = HanoiByArr<NumToArr<N>, From, To, Intermediate>;

type HanoiByArr<
  Count extends any[],
  From = "A",
  To = "B",
  Intermediate = "C"
> = Count extends [infer _, ...infer R]
  ? [
      ...HanoiByArr<R, From, Intermediate, To>,
      [From, To],
      ...HanoiByArr<R, Intermediate, To, From>
    ]
  : [];

type NumToArr<N extends number, Count extends any[] = []> = number extends N
  ? []
  : N extends Count["length"]
  ? Count
  : NumToArr<N, [...Count, 1]>;

Solution by Vampirelee #32596 

type Hanoi<
  N extends number,
  From = "A",
  To = "B",
  Intermediate = "C",
  C extends 0[] = [0]
> = N extends 0
  ? []
  : C["length"] extends N
  ? [[From, To]]
  : [
      ...Hanoi<N, From, Intermediate, To, [...C, 0]>,
      [From, To],
      ...Hanoi<N, Intermediate, To, From, [...C, 0]>
    ];

Solution by vangie #32212 

type MakeNumberToArray<T extends number, U extends unknown[] = []> = U['length'] extends T
  ? U
  : MakeNumberToArray<T, [...U, unknown]>;

type Hanoi<
  N extends number,
  From = 'A',
  To = 'B',
  Intermediate = 'C',
  U extends unknown[] = MakeNumberToArray<N>,
> = U['length'] extends 1
  ? [[From, To]]
  : U extends [unknown, ...infer Rest]
  ? [...Hanoi<Rest['length'], From, Intermediate, To>, [From, To], ...Hanoi<Rest['length'], Intermediate, To, From>]
  : [];

Solution by leejaehyup #30993

type Hanoi<Rings extends number, FromRod extends string = 'A', ToRod extends string = 'B', IntermediateRod extends string = 'C', Acc extends '🇺🇦'[] = []> = Acc['length'] extends Rings ? [] : [ ...Hanoi<Rings, FromRod, IntermediateRod, ToRod, [...Acc, '🇺🇦']>, [FromRod, ToRod], ...Hanoi<Rings, IntermediateRod, ToRod, FromRod, [...Acc, '🇺🇦']> ]

/* We should move disk from rod-A to rod-B using rod-C as a intemediate helper rod. Only one disk at a time. So, I explain on Hanoi<1> example. By default Acc is empty array and it's length 0, so we skip true branch of our comparison and go to false branch.

  1. We should get an array of arrays (combination of A | B | C). So, wrap false branch with [].
  2. First recursive spread. 2.1 We run "Hanoi" type with Hanoi<1, 'A', 'C', 'B', [...[], '🇺🇦']>.
    • Here we should take a look on number of rings and length of Acc.
    • We have Rings = 1 and Acc with one '🇺🇦'. So, result gonna be an empty [] with length 1.
    • That's why we use spread operator. When we spread an empty array we get 'never' type and it skiped in our RESULT ARRAY. 2.2 Just an array with ['A', 'B'] 2.3 The same explanation as in a 2.1. */

Solution by ArtDorfman #30769 

type Hanoi<N extends number, From = 'A', To = 'B', Intermediate = 'C'> = Helper<N, [], From, To, Intermediate>
type Helper<N extends number, C extends 1[], From extends unknown, To extends unknown, Intermediate extends unknown> = C['length'] extends N
  ? []
  : [...Helper<N, [...C, 1], From, Intermediate, To>, [From, To], ...Helper<N, [...C, 1], Intermediate, To, From>]

Solution by Sun79 #30479