25270-medium-transpose

Back

A very blunt solution ...

type InitRetItems<
  M extends number[][],
  Ret extends number[][] = []
> = Ret['length'] extends M[0]['length'] ? Ret : InitRetItems<M, [[], ...Ret]>;

type RemoveFirstItem<Arr extends any[]> = Arr extends [any, ...infer Rest]
  ? Rest
  : [];

// append every line
type AppendEveryLine<
  Line extends number[],
  Ret extends number[][]
> = Line extends [infer FirstNum, ...infer Rest extends number[]]
  ? [[...Ret[0], FirstNum], ...AppendEveryLine<Rest, RemoveFirstItem<Ret>>]
  : [];

type Transpose<
  M extends number[][],
  Ret extends number[][] = InitRetItems<M>
> = M extends [infer Arr extends number[], ...infer Rest extends number[][]]
  ? Transpose<Rest, AppendEveryLine<Arr, Ret>>
  : Ret;

Solution by sunupupup #33481 

type Transpose<M extends number[][]> =
  M[0] extends infer M0 extends number[]
    ? {[I in keyof M0]: {[J in keyof M]: M[J][I & keyof M[J]]}}
  : []

Playground

Solution by teamchong #33056

分析

  1. 把过程分为以下几步， 假设二维数组为：[[1, 2, 3], [4, 5, 6]] - 第一步, 取二维数组的第一个元素组成一个数组，取到的数组为: [1, 4], - 第二步, 去除掉每个数组的第一个元素， 得到数组为: [[2, 4],[5, 6]] - 第三步，递归重复第一步和第二步，将所有第一步执行的结果保存下来，即得到答案。

代码如下：

// 取每个数组的第一个元素
type FirstEl<T extends any[][] = []> = T extends [
  infer L,
  ...infer R extends any[][]
]
  ? L extends []
    ? FirstEl<R>
    : L extends [infer L1, ...infer R1]
    ? [L1, ...FirstEl<R>]
    : []
  : [];

// 去掉第一个元素后得到的二维数组
type RemoveFirstEl<T extends any[][]> = T extends [
  infer L,
  ...infer R extends any[][]
]
  ? L extends []
    ? RemoveFirstEl<R>
    : L extends [infer L1, ...infer R1]
    ? R1 extends []
      ? RemoveFirstEl<R>
      : [R1, ...RemoveFirstEl<R>]
    : []
  : [];

type Transpose<T extends number[][]> = T extends []
  ? []
  : [FirstEl<T>, ...Transpose<RemoveFirstEl<T>>];

Solution by Vampirelee #32573 

type AppendToRow<
  M extends number[][],
  Row extends number,
  Val extends number,
  C extends 0[] = []
> = M extends [infer L extends number[], ...infer R extends number[][]]
  ? Row extends C["length"]
    ? [[...L, Val], ...R]
    : [L, ...AppendToRow<R, Row, Val, [...C, 0]>]
  : [];

type Transpose<
  M extends number[][],
  Row_Idx extends 0[] = [],
  Col_Idx extends 0[] = [],
  MT extends number[][] = [],
  Row = M[Row_Idx["length"]]
> = Row_Idx["length"] extends M["length"]
  ? MT
  : Row extends [infer C extends number, ...infer RowRest]
  ? Transpose<
      M,
      Row_Idx,
      [...Col_Idx, 0],
      AppendToRow<
        Row_Idx["length"] extends 0 ? [...MT, []] : MT,
        Col_Idx["length"],
        C
      >,
      RowRest
    >
  : Transpose<M, [...Row_Idx, 0], [], MT>;

Solution by vangie #32210 

type Transpose<
    M extends unknown[][], 
    _Acc extends unknown[][] = [], 
> = 
    _Acc["length"] extends M[0]["length"]
        ? _Acc 
        : Transpose<M, [..._Acc, TransposeColumnToRow<M, _Acc["length"]>]>
;

type TransposeColumnToRow<
    M extends unknown[][], 
    CurrentCol extends number, 
    Acc extends unknown[] = [],
> = 
    Acc["length"] extends M["length"] 
        ? Acc 
        : TransposeColumnToRow<M, CurrentCol, [...Acc, M[Acc["length"]][CurrentCol]]>
;

Solution by RusJstudent #31939 

// your answers
type GetValuesByIndex<M extends number[][], I extends number> =
  M extends [infer F extends number[], ...infer R extends number[][]]
    ? [F[I], ...GetValuesByIndex<R, I>]
    : []

type Transpose<M extends number[][], U extends unknown[] = []> =
  M extends []
    ? []
    : U['length'] extends M[number]['length']
        ? []
        : [GetValuesByIndex<M, U['length']>, ...Transpose<M, [...U, unknown]>]

Solution by milletlovemouse #30957 

// your answers
type TransposeOne<T extends number[], R extends number[][], NR extends number[][] = []> =
  T extends [infer F extends number, ...infer Rest extends number[]]
    ? R extends [infer RF extends number[], ...infer RRest extends number[][]]
      ? TransposeOne<Rest, RRest, [...NR, [...RF, F]]>
      : TransposeOne<Rest, [], [...NR, [F]]>
    : NR

type Transpose<M extends number[][], R extends number[][] = []> =
  M extends [infer F extends number[], ...infer Rest extends number[][]]
    ? Transpose<Rest, TransposeOne<F, R>>
    : R

Solution by enochjs #30543 

type Transpose<
  M extends number[][],
  Row extends unknown[] = M extends [] ? [] : M[0]
> = {
  [K in keyof Row]: {
    [Key in keyof M]: K extends keyof M[Key] ? M[Key][K] : never;
  };
};

Solution by DoubleWoodLin #28915

这题有点变态，意思是，将多个数组按照 index 进行重拍，这里的思路是每次把所有数组的同一位拿出来，构造成一个数组，这样每次可以处理完一位

例如 [[1, 2], [3, 4]]，我们先把第一位拿出来 得到数组 [1, 3] 再拿第二位 [2, 4] ，合并就好

按照这个思路，我们需要一个方法用来获取二元数组中的某一位组成的数组，通过遍历 二维数组 M，递归可以得到结果 [F[I], ...Temp<Res, I>]

那么主流程只需要处理 获取的是哪一位即可，可以借助数组 length 来计算当前是获取第几位的值

type Temp<M extends number[][], I extends number> = M extends [infer F extends number[], ...infer Res extends number[][]]
  ? [F[I], ...Temp<Res, I>]
  : []

type Transpose<M extends number[][], Res extends number[][] = []> = M extends [infer F extends number[], ...any]
  ? F['length'] extends Res['length']
    ? []
    : [Temp<M, Res['length']>, ...Transpose<M, [...Res, any]>]
  : []

Solution by linjunc #28364 


/** Appends each Row[i] to each M_T[i].
 *
 * AppendDown<[], [1,2,3]> => [[1],[2],[3]]
 * AppendDown<[[1],[2],[3]], [4,5,6]> => [[1,4],[2,5],[3,6]]
 */
type AppendDown<
  M_T extends number[][],
  Row extends number[],
  Result extends number[][] = []
> = Row extends [
  infer FirstVal extends number,
  ...infer RestVals extends number[]
]
  ? M_T extends [
      infer FirstRow extends number[],
      ...infer RestRows extends number[][]
    ]
    ? AppendDown<RestRows, RestVals, [...Result, [...FirstRow, FirstVal]]>
    : AppendDown<[], RestVals, [...Result, [FirstVal]]>
  : Result;

type Transpose<M extends number[][], M_T extends number[][] = []> = M extends [
  infer First extends number[],
  ...infer Rest extends number[][]
]
  ? Transpose<Rest, AppendDown<M_T, First>>
  : M_T;

Solution by alythobani #27666

#25297 's solution is better for the origin test cases:

  Expect<Equal<Transpose<[]>, []>>,
  Expect<Equal<Transpose<[[1]]>, [[1]]>>,
  Expect<Equal<Transpose<[[1, 2]]>, [[1], [2]]>>,
  Expect<Equal<Transpose<[[1, 2], [3, 4]]>, [[1, 3], [2, 4]]>>,
  Expect<Equal<Transpose<[[1, 2, 3], [4, 5, 6]]>, [[1, 4], [2, 5], [3, 6]]>>,
  Expect<Equal<Transpose<[[1, 4], [2, 5], [3, 6]]>, [[1, 2, 3], [4, 5, 6]]>>,
  Expect<Equal<Transpose<[[1, 2, 3], [4, 5, 6], [7, 8, 9]]>, [[1, 4, 7], [2, 5, 8], [3, 6, 9]]>>,

But, it can not pass these edge cases:

  Expect<Equal<Transpose<[[], [4, 5, 6], [7, 8, 9]]>, [[4, 7], [5, 8], [6, 9]]>>,
  Expect<Equal<Transpose<[[1, 2], [4, 5, 6], [7, 8, 9]]>, [[1, 4, 7], [2, 5, 8], [6, 9]]>>,
  Expect<Equal<Transpose<[[1, 2, 3], [4, 5], [7, 8, 9]]>, [[1, 4, 7], [2, 5, 8], [3, 9]]>>,
  Expect<Equal<Transpose<[[1, 2, 3], [4, 5, 6], [7, 8]]>, [[1, 4, 7], [2, 5, 8], [3, 6]]>>,
  Expect<Equal<Transpose<[[1, 2], [4, 5], [7, 8, 9]]>, [[1, 4, 7], [2, 5, 8], [9]]>>,
  Expect<Equal<Transpose<[[1, 2], [4, 5, 6], [7, 8]]>, [[1, 4, 7], [2, 5, 8], [6]]>>,
  Expect<Equal<Transpose<[[1, 2, 3], [4, 5], [7, 8]]>, [[1, 4, 7], [2, 5, 8], [3]]>>,

I think we should consider to be compatible with these:

type MergeToResult<R extends number[][], M extends number[], newR extends number[][] = []> =
  M extends [infer M1 extends number, ...infer RestM extends number[]]
    ? R extends [infer R1 extends number[], ...infer RestR extends number[][]]
      ? MergeToResult<RestR, RestM, [...newR, [...R1, M1]]>
      : MergeToResult<R, RestM, [...newR, [M1]]>
    : [...newR, ...R]

type Transpose<M extends number[][], R extends number[][] = []> =
  M extends [infer M1 extends number[], ...infer Rest extends number[][]]
    ? Transpose<Rest, MergeToResult<R, M1>>
    : R

Solution by drylint #27431 

type Transpose<M extends number[][], T extends number[] = M[0]> = M extends [] ? [] : {
  [K1 in keyof T]: {
    [K2 in keyof M]: K1 extends keyof M[K2] ? M[K2][K1] : never
  }
}

Solution by smileboyi #27303 

type Transpose<M extends number[][],arr extends number[][] = [],item extends number[] = []> = arr['length'] extends M[0]['length'] ? arr : 
    item['length'] extends M['length'] ? Transpose<M,[...arr,item],[]> : Transpose<M,arr,[...item,M[item['length']][arr['length']]]>

Solution by WangZiChu199910252255 #27100 

type TransposeBase<M extends any[][], I extends number> = M extends [infer First extends any[] , ...infer Rest extends any[][]] ? 
  [First[I], ...TransposeBase<Rest, I>] : [];
  
type Transpose<M extends number[][], C extends any[] = []> = M extends [infer First extends number[], ...any] ? 
  First["length"] extends C["length"] ? [] : [TransposeBase<M, C["length"]>, ...Transpose<M, [...C, any]>]
  :
  [];

Solution by shhhplus #26833 

type GetValues<M extends number[][], I extends number = 0, R extends number[] = []> = M extends [infer F extends number[], ...infer Rest extends number[][]]
  ? GetValues<Rest, I, [...R, F[I]]>
  : R

type Transpose2<M extends number[][], R extends number[][] = []> = M extends []
  ? []
  : M[0]['length'] extends R['length']
    ? R
    : Transpose2<M, [...R, GetValues<M, R['length']>]>

更好的写法: 25297

Solution by XkSuperCool #26095 

type Col<T extends number[][], I extends number> = T extends [infer F extends number[], ...infer R extends number[][]] ? [F[I], ...Col<R, I>] : [];

type Transpose<M extends number[][], _Result extends number[][] = []> = _Result[`length`] extends M[0][`length`] ?
  _Result/*return*/ : Transpose<M, [..._Result, Col<M, _Result[`length`]>]>;

Solution by E-uler #25376 

type Transpose<M extends number[][],R = M['length'] extends 0?[]:M[0]> = {
  [X in keyof R]:{
    [Y in keyof M]:X extends keyof M[Y]?M[Y][X]:never
  }
}

Solution by jiangshanmeta #25297