type DigitLast = {
1: 0;
2: 1;
3: 2;
4: 3;
5: 4;
6: 5;
7: 6;
8: 7;
9: 8;
};
type Reverse<
T extends string,
Res extends string = ""
> = T extends `${infer First}${infer Rest}`
? Reverse<Rest, `${First}${Res}`>
: Res;
type ReverseSubOne<
T extends string,
Res extends string = ""
> = T extends `${infer First extends number}${infer Rest}`
? First extends 0
? ReverseSubOne<Rest, `${Res}9`>
: `${Res}${DigitLast[First & keyof DigitLast]}${Rest}`
: never;
type ReverseGreaterThan<A extends string, B extends string> = A extends "0" | ""
? false
: B extends "0"
? true
: A extends `${infer FA}${infer RA}`
? B extends `${infer FB}${infer RB}`
? FB extends "0"
? RA extends RB
? FA extends "0"
? false
: true
: ReverseGreaterThan<RA, RB>
: ReverseGreaterThan<ReverseSubOne<A>, ReverseSubOne<B>>
: never
: never;
type GreaterThan<A extends number, B extends number> = ReverseGreaterThan<
Reverse<`${A}`>,
Reverse<`${B}`>
>;
type FirstHalf<T extends any[]> = T extends [infer F, ...infer M, any]
? [F, ...FirstHalf<M>]
: T;
type LastHalf<T extends any[]> = T extends [...FirstHalf<T>, ...infer E]
? E
: never;
type Merge<
A extends any[],
B extends any[],
S extends boolean = false,
Res extends number[] = []
> = [A, B] extends [
[infer FA extends number, ...infer RA extends number[]],
[infer FB extends number, ...infer RB extends number[]]
]
? GreaterThan<FA, FB> extends S
? Merge<RA, B, S, [...Res, FA]>
: Merge<A, RB, S, [...Res, FB]>
: [...Res, ...A, ...B];
type Sort<T extends number[], S extends boolean = false> = T["length"] extends
| 0
| 1
? T
: Merge<Sort<FirstHalf<T>, S>, Sort<LastHalf<T>, S>, S>;
Solution by Barrenboat #37418
Wrote this Bubble Sort type while still learning TypeScript, so it may not be the most elegant solution - but hopefully easy to follow along for someone still getting into this stuff.
I added the Order boolean after finding this repo wanting to pass the challenge! (no extra challenges for now)
type GreaterThan<
A extends number,
B extends number,
Order extends boolean,
T extends any[] = [],
> = T["length"] extends (Order extends false ? B : A)
? true
: T["length"] extends (Order extends false ? A : B)
? false
: GreaterThan<A, B, Order, [any, ...T]>;
type BubblePass<T extends number[], Order extends boolean> = T extends [
infer A extends number,
infer B extends number,
...infer Rest extends number[],
]
? GreaterThan<A, B, Order> extends true
? [B, ...BubblePass<[A, ...Rest], Order>]
: [A, ...BubblePass<[B, ...Rest], Order>]
: T;
type Sort<
T extends number[],
Order extends boolean = false,
Pass extends any[] = [],
> = T["length"] extends Pass["length"]
? T
: Sort<BubblePass<T, Order>, Order, [any, ...Pass]>;
Solution by holoflash #37355
type BuildTuple<
N extends number,
Result extends any[] = []
> = Result["length"] extends N ? Result : BuildTuple<N, [...Result, 1]>;
type MoreThan<A extends number, B extends number> = BuildTuple<A> extends [
...BuildTuple<B>,
...any[]
]
? true
: false;
type Bubble<Arr extends number[], Current extends any[] = []> = Arr extends [
infer A extends number,
infer B extends number,
...infer Rest extends number[]
]
? MoreThan<A, B> extends true
? Bubble<[A, ...Rest], [...Current, B]>
: Bubble<[B, ...Rest], [...Current, A]>
: [...Current, Arr[0]];
type Sort<
Arr extends number[],
Reverse extends boolean = false,
Sorted extends number[] = []
> = Bubble<Arr> extends [...infer R extends number[], infer Max extends number]
? Sort<R, Reverse, Reverse extends true ? [...Sorted, Max] : [Max, ...Sorted]>
: Sorted;
Solution by Gravity2333 #37326
type Reverse<T extends any[]> = T extends [infer F, ...infer R] ? [...Reverse<R>, F] : []
type ExtractElement<T extends any[], U extends number, R extends any[] = []>
= T extends [infer First, ...infer Rest]
? First extends U
? ExtractElement<Rest, U, [...R, First]>
: ExtractElement<Rest, U, R>
: R
type Sort<T extends any[], S = false, U = T[number], Cur extends any[] = [], R extends any[] = []>
= [U] extends [never]
? R
: S extends false
? Cur['length'] extends U
? Sort<T, S, Exclude<U, Cur['length']>, [...Cur, 1], [...R, ...ExtractElement<T, Cur['length']>]>
: Sort<T, S, U, [...Cur, 1], R>
: Reverse<Sort<T, false>>
Solution by Heonys #32498
enum Comparison {
Greater,
Equal,
Lower,
}
type CharComp<A, B, I extends 1[] = [], L = `${I["length"]}`> = A extends B
? Comparison.Equal
: L extends A
? Comparison.Lower
: L extends B
? Comparison.Greater
: CharComp<A, B, [...I, 1]>;
type NaturalComp<
A extends string,
B extends string,
C = Comparison.Equal,
> = A extends `${infer CA}${infer LA}`
? B extends `${infer CB}${infer LB}`
? NaturalComp<LA, LB, C extends Comparison.Equal ? CharComp<CA, CB> : C>
: Comparison.Greater
: B extends `${number}`
? Comparison.Lower
: C;
type Comparator<A extends number | bigint, B extends number | bigint> = `${A}` extends `-${infer X}`
? `${B}` extends `-${infer Y}`
? NaturalComp<Y, X>
: Comparison.Lower
: `${B}` extends `-${infer Y}`
? Comparison.Greater
: NaturalComp<`${A}`, `${B}`>;
type Num = number | bigint;
type Insert<V extends Num, A extends Num[], Cmp extends Comparison, P extends Num[] = []> = A extends []
? [...P, V]
: A extends [infer F extends Num, ...infer T extends Num[]]
? Comparator<V, F> extends Cmp
? Insert<V, T, Cmp, [...P, F]>
: [...P, V, ...A]
: never;
type Sort<A extends Num[], Desc extends boolean = false> = A extends []
? []
: A extends [infer F extends Num, ...infer T extends Num[]]
? Insert<F, Sort<T, Desc>, Desc extends true ? Comparison.Lower : Comparison.Greater>
: never;
Solution by alexandroppolus #32283
type Digit = '0123456789';
type DigitsToArr<S extends string> = S extends `${infer L}${infer R}`
? [0, ...DigitsToArr<R>]
: [];
type ArrLenCompare<
T extends any[],
U extends any[]
> = Digit extends `${string}${T['length']}${string}${U['length']}${string}`
? -1
: Digit extends `${string}${U['length']}${string}${T['length']}${string}`
? 1
: 0;
type ArrLenCompareResult<T extends number, U extends number> = ArrLenCompare<
DigitsToArr<`${T}`>,
DigitsToArr<`${U}`>
>;
type DigitSomeLenCompare<
T extends string,
U extends string
> = T extends `${infer TF}${infer TR}`
? U extends `${infer UF}${infer UR}`
? TF extends UF
? DigitSomeLenCompare<TR, UR>
: Digit extends `${string}${TF}${string}${UF}${string}` // UF 大于 TF
? false
: Digit extends `${string}${UF}${string}${TF}${string}` // TF 大于 UF
? true
: false // TF === UF
: false
: false;
type GreaterThan<T extends number, U extends number> = ArrLenCompareResult<
T,
U
> extends 1
? true
: ArrLenCompareResult<T, U> extends -1
? false
: DigitSomeLenCompare<`${T}`, `${U}`>;
type Insert<
T extends number[],
U extends number,
D extends boolean = false,
Res extends number[] = []
> = T extends [infer F extends number, ...infer R extends number[]]
? D extends false
? GreaterThan<F, U> extends true
? [...Res, U, F, ...R]
: Insert<R, U, D, [...Res, F]>
: GreaterThan<F, U> extends true
? Insert<R, U, D, [...Res, F]>
: [...Res, U, F, ...R]
: [...Res, U];
type Sort<
T extends number[],
U extends boolean = false,
Res extends number[] = []
> = T extends [infer F extends number, ...infer R extends number[]]
? Res extends []
? Sort<R, U, [F]>
: Sort<R, U, Insert<Res, F, U>>
: Res;
Solution by uni-ww #31525
// 解答をここに記入
// 左側（A）が大きいかの真偽値を返す
namespace LeftIsLarger {
export type Main<A extends number, B extends number, Counter extends never[] = []> = Counter["length"] extends A ? false : Counter["length"] extends B ? true : Main<A, B, [never, ...Counter]>
type Test = [
Expect<Equal<Main<1, 2>, false>>,
Expect<Equal<Main<2, 2>, false>>,
Expect<Equal<Main<3, 1>, true>>,
]
}
type LeftIsLarger<A extends number, B extends number> = LeftIsLarger.Main<A, B>
// boolean を reverse して返す
namespace ReverseBoolean {
export type Main<A extends boolean> = Exclude<boolean, A>
type Test = [
Expect<Equal<Main<true>, false>>,
Expect<Equal<Main<false>, true>>,
Expect<Equal<Main<boolean>, never>>,
]
}
type ReverseBoolean<A extends boolean> = ReverseBoolean.Main<A>
// A, B を受け取り、{ small: 小さい方, large: 大きい方 } を返す
namespace MiniSort {
type GetBool<A extends boolean, IsReverse extends boolean> = IsReverse extends true ? ReverseBoolean<A> : A
export type Main<A extends number, B extends number, IsReverse extends boolean = false> = GetBool<LeftIsLarger<A, B>, IsReverse> extends true ? { small: B, large: A } : { small: A, large: B }
type Test = [
Expect<Equal<Main<1, 2>, { small: 1, large: 2 } >>,
Expect<Equal<Main<2, 2>, { small: 2, large: 2 } >>,
Expect<Equal<Main<2, 1>, { small: 1, large: 2 } >>,
Expect<Equal<Main<1, 2, true>, { small: 2, large: 1 } >>,
Expect<Equal<Main<2, 2, true>, { small: 2, large: 2 } >>,
Expect<Equal<Main<2, 1, true>, { small: 2, large: 1 } >>,
]
}
type MiniSort<A extends number, B extends number, IsReverse extends boolean = false> = MiniSort.Main<A, B, IsReverse>
// バブルソートの基盤、一度のソートを゙行う
namespace SortOnce {
export type Main<A extends number[], IsReverse extends boolean = false> = A extends [infer A0 extends number, infer A1 extends number, ...infer Rest extends number[]] ? [MiniSort<A0, A1, IsReverse>["small"], ...Main<[MiniSort<A0, A1, IsReverse>["large"], ...Rest], IsReverse>] : A
type Test = [
Expect<Equal<Main<[1, 2]>, [1, 2]>>,
Expect<Equal<Main<[1, 2], true>, [2, 1]>>,
Expect<Equal<Main<[1, 4, 3, 2]>, [1, 3, 2, 4]>>,
Expect<Equal<Main<[1, 4, 3, 2], true>, [4, 3, 2, 1]>>,
]
}
type SortOnce<A extends number[], IsReverse extends boolean = false> = SortOnce.Main<A, IsReverse>
// バブルソートをする
namespace Sort {
export type Main<A extends number[], IsReverse extends boolean = false, SortedA extends number[] = SortOnce<A, IsReverse>> = SortedA extends [...infer Rest extends number[], infer L] ? [...Main<Rest, IsReverse>, L] : []
type Test = [
Equal<Sort<[3, 2, 1]>, [1, 2, 3]>,
Expect<Equal<Main<[1, 2]>, [1, 2]>>,
Expect<Equal<Main<[1, 2], true>, [2, 1]>>,
Expect<Equal<Main<[1, 4, 3, 2]>, [1, 2, 3, 4]>>,
Expect<Equal<Main<[1, 4, 3, 2], true>, [4, 3, 2, 1]>>,
Expect<Equal<Main<[3, 2, 1]>, [1, 2, 3]>>,
]
}
type Sort<A extends number[], IsReverse extends boolean = false> = Sort.Main<A, IsReverse>
Solution by Kakeru-Miyazaki #31000
// 你的答案
// 三种排序方法都写了（快速排序，冒泡排序，插入排序），支持浮点数，15+
type NTS<T extends number> = `${T}`
type NTA<T extends number, S extends ''[] = []> = S['length'] extends T ? S : NTA<T, [...S, '']>
type NTSA<T extends number, S extends ''[] = [], TA extends string[] = STA<NTS<T>>> = S['length'] extends TA['length'] ? S : NTSA<T, [...S, '']>
type STN<T extends string> = T extends `${infer N extends number}` ? N : never
type STA<T extends string, S extends string[] = []> = T extends `${infer F}${infer R}` ? STA<R, [...S, F]> : S
type ATS<T extends string[], S extends string = ''> = T extends [infer F extends string, ...infer R extends string[]] ? ATS<R, `${S}${F}`> : S
type LenCom<O extends number, T extends number, OS extends ''[] = NTSA<O>, TS extends ''[] = NTSA<T>> =
OS extends TS ? LenSamCom<O, T> : OS extends [...TS, ...any] ? true : false
type LenSamCom<O extends number, T extends number, NA extends ''[] = [], N extends number = NA['length'], OA extends string[] = STA<NTS<O>>, TA extends string[] = STA<NTS<T>>> =
OA[N] extends TA[N] ? LenSamCom<O, T, [...NA, '']> : SingleCom<STN<OA[N]>, STN<TA[N]>>
type SingleCom<O extends number, T extends number, OA extends ''[] = NTA<O>, TA extends ''[] = NTA<T>> =
OA extends [...TA, ...any] ? true : false
type GetPositive<TA extends string[], A extends string[] = [], N extends number = A['length']> =
TA[N] extends string ? TA[N] extends '.' ? STN<ATS<A>> : GetPositive<TA, [...A, TA[N]]> : STN<ATS<TA>>
type GetFloat<TA extends string[]> = TA extends [infer F, ...infer R extends string[]] ? F extends '.' ? STN<ATS<R>> : GetFloat<R> : 0
type FloatCom<O extends number, T extends number, NA extends ''[] = [], N extends number = NA['length'], OA extends string[] = STA<NTS<O>>, TA extends string[] = STA<NTS<T>>> =
OA[N] extends string ? TA[N] extends string ?
OA[N] extends TA[N] ? FloatCom<O, T, [...NA, '']> : SingleCom<STN<OA[N]>, STN<TA[N]>>
: true : TA[N] extends string ? false : true
type SortArr<O extends number, T extends number, OP extends number = GetPositive<STA<NTS<O>>>, OF extends number = GetFloat<STA<NTS<O>>>, TP extends number = GetPositive<STA<NTS<T>>>, TF extends number = GetFloat<STA<NTS<T>>>> =
O extends T ? true :
OP extends TP ? FloatCom<OF, TF> extends true ? true : false :
LenCom<OP, TP> extends true ? true : false
// 获取数组中间值
type GetMiddleArr<TA extends number[], NA extends ''[] = []> =
TA['length'] extends [...NA, ...NA]['length'] ? TA[NA['length']] extends number ? TA[NA['length']] : never :
TA['length'] extends [...NA, '', ...NA]['length'] ? TA[NA['length']] : GetMiddleArr<TA, [...NA, '']>
type GetCompareG<TA extends number[], G extends number, L extends Boolean = false, NA extends ''[] = [], A extends number[] = [], N extends number = NA['length']> =
TA[N] extends number ? SortArr<TA[N], G> extends L ? GetCompareG<TA, G, L, [...NA, ''], [...A, TA[N]]> : GetCompareG<TA, G, L, [...NA, ''], A> : A
type ClearArrG<TA extends number[], G extends number, TAF extends number[] = [], NA extends ''[] = [], N extends number = NA['length']> =
TAF extends TA ? TA : TA extends [...TAF, G, ...infer RA] ? [...TAF, ...RA] : ClearArrG<TA, G, [...TAF, TA[N]], [...NA, '']>
// 快速排序
type FastSort<TA extends number[], I extends Boolean = false, G extends number | never = GetMiddleArr<TA>,
TACG extends number[] = ClearArrG<TA, G>,
L extends number[] = GetCompareG<TACG, G>,
R extends number[] = GetCompareG<TACG, G, true>
> = [G] extends [never] ? [] : I extends true ? [...FastSort<R, I>, G, ...FastSort<L, I>] : [...FastSort<L, I>, G, ...FastSort<R, I>]
// 数组元素调换位置
type Reverse<TA extends number[], J extends number, I extends number, TAF extends number[] = [], NA extends ''[] = [], N extends number = NA['length']> =
TA[N] extends number ?
J extends N ? Reverse<TA, J, I, [...TAF, TA[I]], [...NA, '']> : I extends N ? Reverse<TA, J, I, [...TAF, TA[J]], [...NA, '']> : Reverse<TA, J, I, [...TAF, TA[N]], [...NA, '']>
: TAF
// 插入排序
type InsertSort<TA extends number[],
B extends Boolean = false,
IA extends ''[] = [''],
SA extends ''[] = [''],
JA extends ''[] = [],
I extends number = IA['length'],
S extends number = SA['length'],
J extends number = JA['length']
> =
TA[I] extends number ?
SortArr<TA[I], TA[J]> extends B ?
InsertSort<
Reverse<TA, J, I>,
B,
SortArr<J, S> extends false ? IA :
SortArr<I, TA['length']> extends false ?
[...IA, ''] : IA,
SortArr<J, S> extends false ? SA :
SortArr<I, TA['length']> extends false ?
[...SA, ''] : SA,
SortArr<J, S> extends false ? [...JA, ''] : []
> :
InsertSort<
TA,
B,
SortArr<J, S> extends false ? IA :
SortArr<I, TA['length']> extends false ?
[...IA, ''] : IA,
SortArr<J, S> extends false ? SA :
SortArr<I, TA['length']> extends false ?
[...SA, ''] : SA,
SortArr<J, S> extends false ? [...JA, ''] : []
>
: TA
// 减法 <8, 2> => 6
type Reduce<T extends number, I extends number> = NTA<T> extends [...NTA<I>, ...infer R] ? R['length'] : 0
// 冒泡排序
type BubbleSort<
TA extends number[],
B extends Boolean = false,
IA extends ''[] = [],
JA extends ''[] = [],
I extends number = IA['length'],
J extends number = JA['length']
> = SortArr<I, Reduce<TA['length'], 1>> extends false ?
SortArr<TA[[...JA, '']['length']], TA[J]> extends B ?
BubbleSort<
TA[[...JA, '']['length']] extends undefined ? TA : Reverse<TA, J, [...JA, '']['length']>,
B,
SortArr<J, Reduce<Reduce<TA['length'], I>, 1>> extends false ? IA :
SortArr<I, Reduce<TA['length'], 1>> extends false ? [...IA, ''] : IA,
SortArr<J, Reduce<Reduce<TA['length'], I>, 1>> extends false ? [...JA, ''] : []
>
:
BubbleSort<
TA,
B,
SortArr<J, Reduce<Reduce<TA['length'], I>, 1>> extends false ? IA :
SortArr<I, Reduce<TA['length'], 1>> extends false ? [...IA, ''] : IA,
SortArr<J, Reduce<Reduce<TA['length'], I>, 1>> extends false ? [...JA, ''] : []
>
: TA
// 快速排序
// type Sort<TA extends number[], I extends Boolean = false> = FastSort<TA, I>
// 插入排序
// type Sort<TA extends number[], I extends Boolean = false> = InsertSort<TA, I>
// 冒泡排序
type Sort<TA extends number[], I extends Boolean = false> = BubbleSort<TA, I>
Solution by YE840926098 #30701
Use my solution of challenge 274 #29831 to do comparison，the type Sort traverses the array multiple times, each time gets a list of the max or min number (excluding all the founded number), the recursion stops when the length of the output array equals to the length of original array.
enum Comparison {
Greater,
Equal,
Lower,
}
type JudgeMap = [
'1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9',
'2' | '3' | '4' | '5' | '6' | '7' | '8' | '9',
'3' | '4' | '5' | '6' | '7' | '8' | '9',
'4' | '5' | '6' | '7' | '8' | '9',
'5' | '6' | '7' | '8' | '9',
'6' | '7' | '8' | '9',
'7' | '8' | '9',
'8' | '9',
'9',
never
];
type JudgeOne<A extends string, B extends string> = B extends A
? Comparison.Equal
: B extends keyof JudgeMap
? A extends JudgeMap[B]
? Comparison.Greater
: Comparison.Lower
: Comparison.Equal;
type GetEmpty<A extends string> = A extends `${infer E}${infer R}`
? `.${GetEmpty<R>}`
: '';
type JudgeTemplate<A extends string, B extends string> = A extends B
? Comparison.Equal
: A extends `${infer L}${B}${infer R}`
? Comparison.Greater
: Comparison.Lower;
type JudgeLength<A extends string, B extends string> = JudgeTemplate<
GetEmpty<A>,
GetEmpty<B>
>;
type JudgeString<A extends string, B extends string> = JudgeLength<
A,
B
> extends Comparison.Equal
? A extends `${infer A1}${infer A2}`
? B extends `${infer B1}${infer B2}`
? JudgeOne<A1, B1> extends Comparison.Equal
? JudgeString<A2, B2>
: JudgeOne<A1, B1>
: Comparison.Equal
: Comparison.Equal
: JudgeLength<A, B>;
type Comparator<
A extends number,
B extends number
> = `${A}` extends `-${infer T1}`
? `${B}` extends `-${infer T2}`
? JudgeString<T2, T1>
: Comparison.Lower
: `${B}` extends `-${infer T2}`
? Comparison.Greater
: JudgeString<`${A}`, `${B}`>;
type FindTargetWithExclude<
S extends number[],
De extends boolean,
Ex = never,
H extends number[] = []
> = S extends [infer E extends number, ...infer R extends number[]]
? E extends Ex
? FindTargetWithExclude<R, De, Ex, H>
: H extends []
? FindTargetWithExclude<R, De, Ex, [E]>
: Comparator<E, H[0]> extends Comparison.Equal
? FindTargetWithExclude<R, De, Ex, [E, ...H]>
: Comparator<E, H[0]> extends (
De extends true ? Comparison.Greater : Comparison.Lower
)
? FindTargetWithExclude<R, De, Ex, [E]>
: FindTargetWithExclude<R, De, Ex, H>
: H;
type Sort<
S extends number[],
De extends boolean = false,
O extends number[] = [],
Ex = never
> = O['length'] extends S['length']
? O
: Sort<
S,
De,
[...O, ...FindTargetWithExclude<S, De, Ex>],
Ex | FindTargetWithExclude<S, De, Ex>[0]
>;
Solution by Royce-DaDaDa #29834
This solution implements 4 sorting algorithms (selection sort, insertion sort, merge sort, and quicksort). It supports large real numbers and adds some extreme test cases, although some utility types can be further optimized.
enum Comparison {
Greater,
Equal,
Lower,
}
type GreaterThan<A extends number, B extends number> = CompareString<
`${A}`,
`${B}`
> extends Comparison.Greater
? true
: false;
type CompareString<
A extends string,
B extends string
> = A extends `-${infer AbsA}`
? B extends `-${infer AbsB}`
? CompareFloatString<AbsB, AbsA>
: Comparison.Lower
: B extends `-${number}`
? Comparison.Greater
: CompareFloatString<A, B>;
type CompareFloatString<
A extends string,
B extends string
> = A extends `${infer AI}.${infer AD}`
? B extends `${infer BI}.${infer BD}`
? CompareIntegerString<AI, BI> extends infer R
? R extends Comparison.Equal
? CompareDecimalString<AD, BD>
: R
: never
: CompareIntegerString<AI, B> extends infer R
? R extends Comparison.Equal
? CompareDecimalString<AD, '0'>
: R
: never
: B extends `${infer BI}.${infer BD}`
? CompareIntegerString<A, BI> extends infer R
? R extends Comparison.Equal
? CompareDecimalString<'0', BD>
: R
: never
: CompareIntegerString<A, B>;
type CompareIntegerString<
A extends string,
B extends string,
TempResult extends Comparison = Comparison.Equal
> = A extends `${infer AF}${infer AR}`
? B extends `${infer BF}${infer BR}`
? TempResult extends Comparison.Equal
? CompareIntegerString<AR, BR, CompareDigitString<AF, BF>>
: CompareIntegerString<AR, BR, TempResult>
: Comparison.Greater
: B extends `${infer _}${infer __}`
? Comparison.Lower
: TempResult;
type CompareDecimalString<
A extends string,
B extends string
> = A extends `${infer FA}${infer RA}`
? B extends `${infer FB}${infer RB}`
? CompareDigitString<FA, FB> extends infer Result
? Result extends Comparison.Equal
? CompareDecimalString<RA, RB>
: Result
: never
: Comparison.Greater
: B extends `${infer _}${infer __}`
? Comparison.Lower
: Comparison.Equal;
type CompareDigitString<A extends string, B extends string> = A extends B
? Comparison.Equal
: '0123456789' extends `${string}${A}${string}${B}${string}`
? Comparison.Lower
: Comparison.Greater;
type Sort<T extends number[], Descent extends boolean = false> = SelectionSort<
T,
Descent
>;
type SelectionSort<
T extends number[],
Descent extends boolean = false,
Result extends number[] = []
> = T extends []
? Result
: Select<T, Descent> extends [
infer M extends number,
infer R extends number[]
]
? SelectionSort<R, Descent, [...Result, M]>
: never;
type Select<
T extends number[],
Descent extends boolean,
Result extends [number, number[]] = [never, []],
Checked extends number[] = [],
Target extends number = never
> = T extends [infer F extends number, ...infer R extends number[]]
? Checked extends []
? Select<R, Descent, [F, R], [F], F>
: GreaterThan<F, Target> extends true
? Descent extends true
? Select<R, Descent, [F, [...Checked, ...R]], [...Checked, F], F>
: Select<R, Descent, Result, [...Checked, F], Target>
: Descent extends false
? Select<R, Descent, [F, [...Checked, ...R]], [...Checked, F], F>
: Select<R, Descent, Result, [...Checked, F], Target>
: Result;
type Sort<T extends number[], Descent extends boolean = false> = InsertionSort<
T,
Descent
>;
type InsertionSort<
T extends number[],
Descent extends boolean = false,
Result extends number[] = []
> = T extends [infer F extends number, ...infer R extends number[]]
? InsertionSort<R, Descent, Insert<Result, F, Descent>>
: Result;
type Insert<
T extends number[],
N extends number,
Descent extends boolean,
Result extends number[] = []
> = T extends [infer F extends number, ...infer R extends number[]]
? GreaterThan<N, F> extends true
? Descent extends true
? [...Result, N, ...T]
: Insert<R, N, Descent, [...Result, F]>
: Descent extends false
? [...Result, N, ...T]
: Insert<R, N, Descent, [...Result, F]>
: [...Result, N];
type Sort<T extends number[], Descent extends boolean = false> = MergeSort<
T,
Descent
>;
type MergeSort<
T extends number[],
Descent extends boolean = false
> = T['length'] extends 0 | 1
? T
: Split<T> extends [infer A extends number[], infer B extends number[]]
? Merge<MergeSort<A, Descent>, MergeSort<B, Descent>, Descent>
: never;
type Split<
T extends number[],
A extends number[] = [],
B extends number[] = [],
PickFromHead extends boolean = true
> = PickFromHead extends true
? T extends [infer F extends number, ...infer R extends number[]]
? Split<R, [...A, F], B, false>
: [A, B]
: T extends [...infer R extends number[], infer L extends number]
? Split<R, A, [L, ...B], true>
: [A, B];
type Merge<
A extends number[],
B extends number[],
Descent extends boolean,
Result extends number[] = []
> = A extends [infer FA extends number, ...infer RA extends number[]]
? B extends [infer FB extends number, ...infer RB extends number[]]
? GreaterThan<FA, FB> extends true
? Descent extends true
? Merge<RA, B, Descent, [...Result, FA]>
: Merge<A, RB, Descent, [...Result, FB]>
: Descent extends false
? Merge<RA, B, Descent, [...Result, FA]>
: Merge<A, RB, Descent, [...Result, FB]>
: [...Result, ...A]
: B extends [infer _, ...infer __]
? [...Result, ...B]
: Result;
type Sort<T extends number[], Descent extends boolean = false> = QuickSort<
T,
Descent
>;
type QuickSort<
T extends number[],
Descent extends boolean = false
> = T extends [infer F extends number, ...infer R extends number[]]
? Partition<R, F> extends [
infer Lower extends number[],
infer Higher extends number[]
]
? Descent extends true
? [...QuickSort<Higher, Descent>, F, ...QuickSort<Lower, Descent>]
: [...QuickSort<Lower, Descent>, F, ...QuickSort<Higher, Descent>]
: never
: T;
type Partition<
T extends number[],
Pivot extends number,
Lower extends number[] = [],
Higher extends number[] = []
> = T extends [infer F extends number, ...infer R extends number[]]
? GreaterThan<F, Pivot> extends true
? Partition<R, Pivot, Lower, [...Higher, F]>
: Partition<R, Pivot, [...Lower, F], Higher>
: [Lower, Higher];
Expect<
Equal<
Sort<[9007199254740992, 9007199254740991]>,
[9007199254740991, 9007199254740992]
>
>,
Expect<Equal<Sort<[1.2345, 1.234]>, [1.234, 1.2345]>>,
Expect<
Equal<
Sort<
[1.2345, 1.236, 0, 2.0, -1, 2, 9007199254740992, -9007199254740991.3]
>,
[-9007199254740991.3, -1, 0, 1.2345, 1.236, 2, 2.0, 9007199254740992]
>
>,
Expect<
Equal<
Sort<[9007199254740991, 9007199254740992], true>,
[9007199254740992, 9007199254740991]
>
>,
Expect<Equal<Sort<[1.236, 1.2345], true>, [1.236, 1.2345]>>,
Expect<Equal<Sort<[1.2, 2], true>, [2, 1.2]>>,
Expect<Equal<Sort<[2, 123.1], true>, [123.1, 2]>>,
Expect<
Equal<
Sort<
[1.2345, 1.236, 0, 2.0, -1, 2, 9007199254740992, -9007199254740991.3],
true
>,
[9007199254740992, 2.0, 2, 1.236, 1.2345, 0, -1, -9007199254740991.3]
>
>
Solution by JohnLi1999 #29282
type ParseNumber<
S extends string
> =
S extends `${infer I}.${infer D}`?
[I,D]
:[S,'']
// l -> -1 e->0 g->1
type CompareLength<
A extends string,
B extends string,
> =
A extends `${string}${infer AR}`?
B extends `${string}${infer BR}`?
CompareLength<AR,BR>
:1
:
B extends A?
0:-1
type GreatConfig = {
"0": '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8'| '9'
"1": '2' | '3' | '4' | '5' | '6' | '7' | '8'| '9',
'2': '3' | '4' | '5' | '6' | '7' | '8'| '9',
"3": '4' | '5' | '6' | '7' | '8'| '9',
"4": '5' | '6' | '7' | '8'| '9',
"5": '6' | '7' | '8'| '9',
'6': '7' | '8'| '9',
"7": '8'| '9'
"8": '9',
'9': never,
}
type CompareDigit<
A extends string,
B extends string,
> =
A extends B?
0:
A extends keyof GreatConfig?
B extends GreatConfig[A]?
-1:1
:never
type CompareDigits<
A extends string,
B extends string,
> =
A extends `${infer AF}${infer AR}`?
B extends `${infer BF}${infer BR}`?
CompareDigit<AF, BF> extends infer CR?
CR extends 0?
CompareDigits<AR, BR>
:CR
:never
: 1
:
B extends A?
0:-1
type CompareNonNegetive<
T extends string,
U extends string,
TP extends [string,string] = ParseNumber<T>,
UP extends [string,string] = ParseNumber<U>,
ByLength extends (0 | 1 | -1) = CompareLength<TP[0],UP[0]>
> =
ByLength extends 0?
TP[0] extends UP[0]?
CompareDigits<TP[1],UP[1]>
:CompareDigits<TP[0],UP[0]>
:ByLength
type LTE<
A extends number,
B extends number,
> =
`${A}` extends `-${infer ABS_A}`?
`${B}` extends `-${infer ABS_B}`?
CompareNonNegetive<ABS_B,ABS_A> extends 1?false:true
: true
:
`${B}` extends `-${string}`?
false:
CompareNonNegetive<`${A}`,`${B}`> extends 1? false:true
type SplitArray<T extends number[],L extends number[] = [],R extends number[] = []> =
T extends [infer A extends number,...infer M extends number[],infer B extends number]?
SplitArray<M,[...L,A],[B,...R]>
: T['length'] extends 1?
[[...L,T[0]],R]
:[L,R]
type Merge<A extends number[],B extends number[],R extends number[] = [] > =
[A,B] extends [
[infer FA extends number,...infer RA extends number[]],
[infer FB extends number,...infer RB extends number[]]
]?
LTE<FA,FB> extends true?
Merge<RA,B,[...R,FA]>
:Merge<RB,A,[...R,FB]>
: [...R,...A,...B]
type MergeSort<
T extends number[],
H extends [number[],number[]]= SplitArray<T>,
> =
T['length'] extends (0 | 1)?
T:
[MergeSort<H[0]>,MergeSort<H[1]>] extends [infer A extends number[],infer B extends number[]]?
Merge<A,B>:T
type Reverse<T extends number[]> = T extends [infer F extends number,...infer M extends number[],infer R extends number] ?
[R,...Reverse<M>,F]:T
type Sort<T extends number[],Desc extends boolean = false ,R extends number[]= MergeSort<T>> = Desc extends true? Reverse<R>:R
Solution by jiangshanmeta #27764
/// tests
{
type t1 = Extends<Sort<[]>, []>;
type t6 = Extends<Sort<[1]>, [1]>
type t7 = Extends<Sort<[2, 4, 7, 6, 6, 6, 5, 8, 9]>, [2, 4, 5, 6, 6, 6, 7, 8, 9]>;
type t8 = Extends<Sort<[111_111_111_111_111, 555_555_555_555_555, 333_333_333_333_333]>, [111_111_111_111_111, 333_333_333_333_333, 555_555_555_555_555]>
type t9 = Extends<Sort<[2.53, 8, 4, 2.1, 2]>, [2, 2.1, 2.53, 4, 8]>
type t10 = Extends<Sort<[111_111_111_111_111.597, 111_111_111_111_111.5]>, [111_111_111_111_111.5, 111_111_111_111_111.597]>
}
{
type t1 = Extends<Sort<[3, 2, 1], true>, [3, 2, 1]>
type t2 = Extends<Sort<[3, 2, 0, 1, 0, 0, 0], true>, [3, 2, 1, 0, 0, 0, 0]>
type t3 = Extends<Sort<[111_111_111_111_111, 555_555_555_555_555, 333_333_333_333_333], true>, [555_555_555_555_555, 333_333_333_333_333, 111_111_111_111_111]>
type t4 = Extends<Sort<[3.58, 6, 3.3], true>, [6, 3.58, 3.3]>
type t5 = Extends<Sort<[111_111_111_111_111.44, 111_111_111_111_111.55], true>, [111_111_111_111_111.55, 111_111_111_111_111.44]>
}
////
type Shift<Arr extends any[]> = Arr extends [any, ...infer Rest] ? Rest : Arr;
type Cond<C extends boolean, Then, Else> = C extends true ? Then : Else;
type IsArrayLonger<Arr1 extends any[], Arr2 extends any[]> =
Arr1['length'] extends 0
? false
: Arr2['length'] extends 0
? true
: IsArrayLonger<Shift<Arr1>, Shift<Arr2>>
type IsArraysLengthEqual<Arr1 extends any[], Arr2 extends any[]> = Arr1['length'] extends Arr2['length']
? true
: false
type StrLength<Str extends string, Length extends any[] = []> = Str extends `${any}${infer RestStr}`
? StrLength<RestStr, [any, ...Length]>
: Length
type ArrFromLength<T extends string | number, Arr extends any[] = []> =
`${Arr['length']}` extends `${T}`
? Arr
: ArrFromLength<T, [any, ...Arr]>
type CompareNumbersWithSameDigits<T1 extends string, T2 extends string> =
T1 extends `${infer P1}${infer T1Rest}`
? T2 extends `${infer P2}${infer T2Rest}`
? Cond<
IsArraysLengthEqual<ArrFromLength<P1>, ArrFromLength<P2>>,
CompareNumbersWithSameDigits<T1Rest, T2Rest>,
IsArrayLonger<ArrFromLength<P1>, ArrFromLength<P2>>
>
: false
: false
type CompareFloat<F1 extends string, F2 extends string> =
F1 extends `${infer P1}${infer RestF1}`
? F2 extends `${infer P2}${infer RestF2}`
? P1 extends P2
? CompareFloat<RestF1, RestF2>
: IsArrayLonger<ArrFromLength<P1>, ArrFromLength<P2>>
: true
: false
type IsBiggerInt<
P1 extends string,
P2 extends string,
P1Length extends any[] = StrLength<P1>,
P2Length extends any[] = StrLength<P2>
> = Cond<
IsArraysLengthEqual<P1Length, P2Length>,
CompareNumbersWithSameDigits<P1, P2>,
IsArrayLonger<P1Length, P2Length>
>
type IsBiggerFloat<
P1 extends string,
P2 extends string,
IntP1 extends string = P1 extends `${infer Int}.${number}` ? Int : P1,
FloatP1 extends string = P1 extends `${number}.${infer Float}` ? Float : '0',
IntP2 extends string = P2 extends `${infer Int}.${number}` ? Int : P2,
FloatP2 extends string = P2 extends `${number}.${infer Float}` ? Float : '0',
> = IntP1 extends IntP2
? CompareFloat<FloatP1, FloatP2>
: IsBiggerInt<IntP1, IntP2>
type IsBigger<
T1 extends number,
T2 extends number,
P1 extends string = `${T1}`,
P2 extends string = `${T2}`,
> = P1 extends `${number}.${number}`
? IsBiggerFloat<P1, P2>
: P2 extends `${number}.${number}`
? IsBiggerFloat<P1, P2>
: IsBiggerInt<P1, P2>
type DevideArr<
Arr extends number[],
Pivot extends number,
Reverse extends boolean,
Left extends number[] = [],
Right extends number[] = []
> =
Arr extends [infer Elem extends number, ...infer RestArr extends number[]]
? Cond<
Cond<Reverse, IsBigger<Elem, Pivot>, IsBigger<Pivot, Elem>> ,
DevideArr<RestArr, Pivot, Reverse, [...Left, Elem], Right>,
DevideArr<RestArr, Pivot, Reverse, Left, [...Right, Elem]>
>
: [Left, Right];
type Mergesort<
Arr extends number[],
Reverse extends boolean,
Pivot extends number = Arr[0],
Parts extends [number[], number[]] = DevideArr<Shift<Arr>, Pivot, Reverse>
> = IsArrayLonger<Arr, [any]> extends true
? [...Mergesort<Parts[0], Reverse>, Pivot, ...Mergesort<Parts[1], Reverse>]
: Arr
type Sort<Arr extends number[], Reverse extends boolean = false> = Mergesort<Arr, Reverse>;
// test helpers
type Check<T, U> = [T] extends [U]
? [U] extends [T]
? any
: never
: never
type Extends<T extends Check<T, U>, U> = any;
Solution by AlexeyDuybo #26290
/**比较器部分 */
namespace Comparator {
type Digit = ToArray<`0123456789`>;
type ToArray<T extends string | number | bigint> = `${T}` extends `${infer F}${infer R}` ? [F, ...ToArray<R>] : [];
/**整数部分位数 */
type Length<T extends number | bigint | string> = ToArray<Integer<AbsString<T>>>["length"];
/**整数部分 */
type Integer<T extends number | bigint | string> = `${T}` extends `${infer I}.${any}` ? I : `${T}`;
/**小数部分 */
type Decimal<T extends number | bigint | string> = `${T}` extends `${any}.${infer D}` ? D : `0`;
/**最高位 */
type High<T extends string | number> = `${T}` extends `${infer F}${any}` ? F : ``;
/**更低位 */
type DigitLowerRest<T extends number | string> = `${T}` extends `${any}${infer R}` ? R : ``;
/**绝对值 */
type AbsString<T extends number | string | bigint> = `${T}` extends `-${infer N}` ? N : `${T}`;
/**是否负数 */
type IsNegative<T extends number | string | bigint> = `${T}` extends `-${any}` ? true : false;
/**固定小数位（补0） */
type DecimalFixed<T extends string, U extends number> = Compare<Length<T>, U> extends Comparison.Lower ? DecimalFixed<`${T}0`, U> : T;
/**比较单个位 */
type DigitComparator<T1 extends number | bigint | string, T2 extends number | bigint | string, IsNegative extends boolean = false, U extends string[] = Digit> =
(T1 extends T2 ?
Comparison.Equal :
(AbsString<T1> extends U[0] ?
(IsNegative extends false ? Comparison.Lower : Comparison.Greater) : //负值反转
(AbsString<T2> extends U[0] ?
(IsNegative extends false ? Comparison.Greater : Comparison.Lower) : //负值反转
(U extends [any, ...infer R extends string[]] ? DigitComparator<T1, T2, IsNegative, R> : false)
))
);
/**比较小数位 */
type CompareDecimal<A extends string, B extends string, _AIsNegative extends boolean = IsNegative<A>, _BIsNegative extends boolean = IsNegative<B>> =
[_AIsNegative & _BIsNegative] extends [never] ?
//一正一负
([0] extends [A & B] ? Comparison.Equal : //-0==0
_AIsNegative extends true ? Comparison.Lower : Comparison.Greater) //-X<Y
:
//正负相同
(Length<A> extends Length<B> ?
//位数相同，从高位开始比较
(`${A}${B}` extends `00` ? Comparison.Equal : //直到全部位都相同 return 相同
(High<A> extends High<B> ?
Compare<DigitLowerRest<A>, DigitLowerRest<B>, _AIsNegative, _BIsNegative> : //当前位相同，比较更低位
DigitComparator<High<A>, High<B>, _AIsNegative>) //当前位不同，retrun
)
:
//位数不同，补0再比较（作对齐）
CompareDecimal<DecimalFixed<A, Length<B>>, DecimalFixed<B, Length<A>>, _AIsNegative, _BIsNegative>);
export enum Comparison {
/**大于 */
Greater,
/**等于 */
Equal,
/**小于 */
Lower,
}
export type Compare<A extends number | string, B extends number | string, _AIsNegative extends boolean = IsNegative<A>, _BIsNegative extends boolean = IsNegative<B>> =
[_AIsNegative & _BIsNegative] extends [never] ?
//一正一负
([0] extends [A & B] ? Comparison.Equal : //-0==0
_AIsNegative extends true ? Comparison.Lower : Comparison.Greater) //-X<Y
:
//正负相同
(Length<A> extends Length<B> ?
//整数部分位数相同，从高位开始比较
(`${Integer<A>}${Integer<B>}` extends `` ? CompareDecimal<Decimal<A>, Decimal<B>, _AIsNegative, _BIsNegative> : //直到全部位都相同后，比较小数部分
(High<A> extends High<B> ?
Compare<DigitLowerRest<A>, DigitLowerRest<B>, _AIsNegative, _BIsNegative> : //当前位相同，比较更低位
DigitComparator<High<A>, High<B>, _AIsNegative>) //当前位不同，retrun
)
:
//整数部分位数不同，比较位数大的
Compare<Length<A>, Length<B>, _AIsNegative, _BIsNegative>);
}
//这里使用冒泡排序
/**冒泡一次 */
type BubbleOnce<A extends number[], Reverse extends boolean = false, _Result extends number[] = []> = A extends [infer F extends number, infer S extends number, ...infer R extends number[]] ?
(Comparator.Compare<F, S> extends (Reverse extends true ? Comparator.Comparison.Lower : Comparator.Comparison.Greater) ?
BubbleOnce<[F, ...R], Reverse, [..._Result, S]> : //交换
BubbleOnce<[S, ...R], Reverse, [..._Result, F]>) :
[..._Result, ...A]; //return
type Sort<A extends number[], Reverse extends boolean = false, _Result extends number[] = []> =
BubbleOnce<A, Reverse> extends [...infer R extends number[], infer L extends number] ? Sort<R, Reverse, [L, ..._Result]> : _Result
type test_real_number = Sort<[1234567890123456, -8, -7.5, -0, -1234567890123456, 0, -.0012, -1234567890123455, 1.100001, 123.456, 1234567890123455, 45632, -1.000001, 1.000001, 5423165456, 0.000001, -.1012, 0.100001], true>;
Solution by E-uler #25693
type IsEqual<X, Y> = (<T>() => T extends X ? 1 : 2) extends (<T>() => T extends Y ? 1 : 2) ? true : false
type Includes<T extends readonly any[], U> = { [P in T[number]]: true }[U] extends true ? true : false
type Maximum<
T extends number[],
N extends number[] = [],
U extends number = T[number]
> = T extends []
? T
: IsEqual<U, N['length']> extends true
? U
: Maximum<T, [...N, 0], U extends N['length'] ? never : U>
type Sort<
T extends number[],
N extends number[] = [],
Result extends number[] = []
> = N['length'] extends Maximum<T>
? [...Result, N['length']]
: Sort<T, [...N, 0], Includes<T, N['length']> extends true ? [...Result, N['length']] : Result>
Solution by TKBnice #23947
type Tuple<T extends number, _TP extends unknown[] = []> =
_TP['length'] extends T
? _TP
: Tuple<T, [..._TP, unknown]>
type Max<A extends number, B extends number> =
Tuple<A> extends [...Tuple<B>, ...any]
? A
: B
type MaxN<T extends number[], _Max extends number = 0> =
T extends [infer First extends number, ...infer Rest extends number[]]
? Rest extends []
? Max<First, _Max>
: MaxN<Rest, Max<First, _Max>>
: never
type Reverse<T extends unknown[]> =
T extends [infer First, ...infer Rest]
? [...Reverse<Rest>, First]
: []
type SortAsc<T extends number[]> =
T extends [infer First extends number, ...infer Rest extends number[]]
? First extends MaxN<T>
? [...Sort<Rest>, First]
: Sort<[...Rest, First]>
: []
type Sort<T extends number[], Desc extends boolean = false> =
Desc extends true
? Reverse<SortAsc<T>>
: SortAsc<T>
enum Comparison {
Greater,
Equal,
Lower,
}
type CompareDigits<A extends string, B extends string> =
A extends B
? Comparison.Equal
: '0123456789' extends `${any}${A}${any}${B}${any}`
? Comparison.Lower
: Comparison.Greater
type ReverseString<S extends string> = S extends `${infer F}${infer Rest}` ? `${ReverseString<Rest>}${F}` : ''
type CompareNumbers<A extends string, B extends string> =
ReverseString<A> extends `${infer ALast}${infer ARest}`
? ReverseString<B> extends `${infer BLast}${infer BRest}`
? CompareNumbers<ReverseString<ARest>, ReverseString<BRest>> extends Comparison.Equal
? CompareDigits<ALast, BLast>
: CompareNumbers<ReverseString<ARest>, ReverseString<BRest>>
: Comparison.Greater
: B extends ''
? Comparison.Equal
: Comparison.Lower
type Max<A extends number, B extends number> =
CompareNumbers<`${A}`, `${B}`> extends Comparison.Lower
? B
: A
type MaxN<T extends number[], _Max extends number = 0> =
T extends [infer First extends number, ...infer Rest extends number[]]
? Rest extends []
? Max<First, _Max>
: MaxN<Rest, Max<First, _Max>>
: never
type ReverseTuple<T extends unknown[]> =
T extends [infer First, ...infer Rest]
? [...ReverseTuple<Rest>, First]
: []
type SortAsc<T extends number[]> =
T extends [infer First extends number, ...infer Rest extends number[]]
? First extends MaxN<T>
? [...Sort<Rest>, First]
: Sort<[...Rest, First]>
: []
type Sort<T extends number[], Desc extends boolean = false> =
Desc extends true
? ReverseTuple<SortAsc<T>>
: SortAsc<T>
extra test cases
Expect<Equal<Sort<[3, 12345678901234567890, 2]>, [2, 3, 12345678901234567890]>>,
Expect<Equal<Sort<[3, 12345678901234567890, 2], true>, [12345678901234567890, 3, 2]>>,
Just update the Max utility type and leverage the code from the Integers Comparator problem
enum Comparison {
Greater,
Equal,
Lower,
}
type CompareDigits<A extends string, B extends string> =
A extends B
? Comparison.Equal
: '0123456789' extends `${any}${A}${any}${B}${any}`
? Comparison.Lower
: Comparison.Greater
type ReverseString<S extends string> = S extends `${infer F}${infer Rest}` ? `${ReverseString<Rest>}${F}` : ''
type CompareNumbers<A extends string, B extends string> =
ReverseString<A> extends `${infer ALast}${infer ARest}`
? ReverseString<B> extends `${infer BLast}${infer BRest}`
? CompareNumbers<ReverseString<ARest>, ReverseString<BRest>> extends Comparison.Equal
? CompareDigits<ALast, BLast>
: CompareNumbers<ReverseString<ARest>, ReverseString<BRest>>
: Comparison.Greater
: B extends ''
? Comparison.Equal
: Comparison.Lower
/**
* NumberString => [IntegerPartString, FractionPartString]
* e.g. '3.1415' => ['3', '1415']
* e.g. '15' => ['15', '0']
*/
type ParseFloatNumber<A extends string> =
A extends `${infer Integer}.${infer Fraction}`
? [Integer, Fraction]
: [A, `0`]
type CompareFloatNumbers<A extends string, B extends string> =
ParseFloatNumber<A> extends [infer AI extends string, infer AF extends string] ?
ParseFloatNumber<B> extends [infer BI extends string, infer BF extends string] ?
CompareNumbers<AI, BI> extends Comparison.Equal
? CompareNumbers<AF, BF>
: CompareNumbers<AI, BI>
: never
: never
type Max<A extends number, B extends number> =
CompareFloatNumbers<`${A}`, `${B}`> extends Comparison.Lower
? B
: A
type MaxN<T extends number[], _Max extends number = 0> =
T extends [infer First extends number, ...infer Rest extends number[]]
? Rest extends []
? Max<First, _Max>
: MaxN<Rest, Max<First, _Max>>
: never
type ReverseTuple<T extends unknown[]> =
T extends [infer First, ...infer Rest]
? [...ReverseTuple<Rest>, First]
: []
type SortAsc<T extends number[]> =
T extends [infer First extends number, ...infer Rest extends number[]]
? First extends MaxN<T>
? [...Sort<Rest>, First]
: Sort<[...Rest, First]>
: []
type Sort<T extends number[], Desc extends boolean = false> =
Desc extends true
? ReverseTuple<SortAsc<T>>
: SortAsc<T>
extra test cases:
Expect<Equal<Sort<[3, 12345678901234567890, 2]>, [2, 3, 12345678901234567890]>>,
Expect<Equal<Sort<[3, 12345678901234567890, 2], true>, [12345678901234567890, 3, 2]>>,
Expect<Equal<Sort<[3, 3.14159, 1.414, 2]>, [1.414, 2, 3, 3.14159]>>,
Compared to version 2, we add ParseFloatNumber and CompareFloatNumbers utility types, and just update Max to use CompareFloatNumbers instead of CompareNumbers.
Not shortest, but try to be clean and easy to understand, and solve extra problem increamentally with as small step as possible.
Solution by zhaoyao91 #22985
// 冒泡排序
type Bubble<T extends number[], M extends boolean = false> // true最小数到末尾.false最大数到末尾.
= T extends [infer A extends number, infer B extends number, ... infer R extends number[]]
? IsLower<A, B> extends M
? [B, ...Bubble<[A, ...R], M>]
: [A, ...Bubble<[B, ...R], M>]
: T
type Sort<T extends number[], M extends boolean = false>
= Bubble<T, M> extends [... infer R extends number[], infer L]
? [...(Sort<R, M>), L]
: T
type IsLower<A extends number, B extends number> = _Comparator<A, B> extends 'Lower' ? true : false
// 冒泡排序
// Utils
type _GetInteger<N extends string> = `${ N }` extends `${ infer Integer }.${ string }` ? Integer : N
type _GetFloat<N extends string> = `${ N }` extends `${ string }.${ infer Float }` ? Float : '0'
// Utils
// 正负浮点数比较
type _Comparator<A extends number, B extends number>
= `${ A }` extends `-${ infer AbsA }`
? `${ B }` extends `-${ infer AbsB }`
? ComparePositives<AbsB, AbsA>
: 'Lower'
: `${ B }` extends `-${ number }`
? 'Greater'
: ComparePositives<`${ A }`, `${ B }`>
// 正浮点数比较
type ComparePositives<
A extends string,
B extends string,
_IntegerA extends string = _GetInteger<A>,
_IntegerB extends string = _GetInteger<B>,
_FloatA extends string = _GetFloat<A>,
_FloatB extends string = _GetFloat<B>,
_ByIntegerLength = _CompareByLength<_IntegerA, _IntegerB>,
_ByIntegerDigits = _CompareByIntegerDigits<_IntegerA, _IntegerB>,
> = _ByIntegerLength extends 'Equal'
? _ByIntegerDigits extends 'Equal'
? _CompareByFloatDigits<_FloatA, _FloatB>
: _ByIntegerDigits
: _ByIntegerLength
// 字符串长度比较
type _CompareByLength<A extends string, B extends string>
= A extends `${ string }${ infer AR }`
? B extends `${ string }${ infer BR }`
? _CompareByLength<AR, BR>
: 'Greater'
: B extends `${ string }${ infer BR }`
? 'Lower'
: 'Equal'
// 浮点部分比较
type _CompareByFloatDigits<A extends string, B extends string> =
A extends `${ infer AF }${ infer AR }`
? B extends `${ infer BF }${ infer BR }`
? _CompareDigits<AF, BF> extends 'Equal'
? _CompareByFloatDigits<AR, BR>
: _CompareDigits<AF, BF>
: 'Greater'
: B extends ''
? 'Equal'
: 'Lower'
// 比较长度相等的数值
type _CompareByIntegerDigits<A extends string, B extends string>
= `${ A }|${ B }` extends `${ infer AF }${ infer AR }|${ infer BF }${ infer BR }`
? _CompareDigits<AF, BF> extends 'Equal'
? _CompareByIntegerDigits<AR, BR>
: _CompareDigits<AF, BF>
: 'Equal'
// 比较个位数值
type _CompareDigits<A extends string, B extends string>
= A extends B
? 'Equal'
: '0123456789' extends `${ string }${ A }${ string }${ B }${ string }`
? 'Lower'
: 'Greater'
Solution by lvjiaxuan #22863
namespace TupleMath {
type NTuple<N extends number, C extends unknown[] = []> = C['length'] extends N ? C : NTuple<N, [...C, 0]>;
export type Min<A extends number[], C extends unknown[]=NTuple<999>> = A extends [infer F extends number, ...infer Rest extends number[]] ?
Min<Rest, C extends [...NTuple<F>, ...infer AR] ? AR['length'] extends 0 ? C : NTuple<F> : C> : C;
export type Max<A extends number[], C extends unknown[]=[]> = A extends [infer F extends number, ...infer Rest extends number[]] ?
Max<Rest, NTuple<F> extends [...C, ...infer AR] ? AR['length'] extends 0 ? C : NTuple<F> : C> : C;
export type Add<T extends unknown[], U extends unknown[]> = [...T, ...U];
export type Half<T extends unknown[], C extends unknown[]=[]> = T extends [...C, ...C, ...infer Rest] ?
Rest['length'] extends 0|1 ? C : Half<T, Add<C,[0]>> : never;
export type Median<T extends unknown[], U extends unknown[]> = Half<Add<T,U>>;
export type FilterSmallerEqual<T extends number[], U extends unknown[]> = T extends [infer F extends number, ...infer Rest extends number[]] ?
[ ...(U extends [...NTuple<F>, ...infer _] ? [F] : []) , ...FilterSmallerEqual<Rest, U>] : [];
export type FilterGreater<T extends number[], U extends unknown[]> = T extends [infer F extends number, ...infer Rest extends number[]] ?
[ ...(NTuple<F> extends [...U, 0, ...infer _] ? [F] : []) , ...FilterGreater<Rest, U>] : [];
}
type MergeSort<
A extends number[],
D extends boolean = false,
M extends unknown[] = TupleMath.Median<TupleMath.Min<A>, TupleMath.Max<A>>,
L extends number[]= TupleMath.FilterSmallerEqual<A, M>,
R extends number[]= TupleMath.FilterGreater<A, M>
>
= A['length'] extends 1|0 ? A :
R extends [] ? L :
[...MergeSort<D extends false ? L : R, D>, ...MergeSort<D extends false ? R : L, D>];
type Sort<A extends number[], D extends boolean = false> = MergeSort<A, D>;
Solution by Karamuto #22391
// your answers
type Compara<A extends number, B extends number> = A extends B ? 0 : "0123456789" extends `${string}${A}${string}${B}${string}` ? -1 : 1;
type GetNumberMax<Arr extends number[], MaxV extends number = Arr[0]> = Arr extends [infer F extends number, ...infer R extends number[]] ?
Compara<F, MaxV> extends 1 ?
GetNumberMax<R, F>
: GetNumberMax<R, MaxV>
: MaxV;
type EarseNumber<Arr extends number[], Target extends number> =
Arr extends [infer F, ...infer R extends number[]] ?
F extends Target ? [...R]
: [F, ...EarseNumber<R, Target>]
: [];
type Sort<T extends number[], IsGreater extends boolean = false, Res extends number[] = [], MaxV extends number = GetNumberMax<T>> =
T extends [] ?
Res
: IsGreater extends false ?
Sort<EarseNumber<T, MaxV>, IsGreater, [MaxV, ...Res]>
: Sort<EarseNumber<T, MaxV>, IsGreater, [...Res, MaxV]>;
;
Solution by Seann0824 #22235
// your answers
type Less<A extends number, B extends number, N extends number[] = []> //是否 A < B
= '0123456789' extends `${string}${A}${string}${B}${string}` ? true : false
type Bubble<T extends number[], M extends boolean = false> //true最小数到末尾.false最大数到末尾.
= T extends [infer A extends number, infer B extends number, ... infer R extends number[]]
? Less<A, B> extends M
? [B, ...Bubble<[A, ...R], M>]
: [A, ...Bubble<[B, ...R], M>]
: T
type Sort<T extends number[], M extends boolean = false>
= Bubble<T, M> extends [... infer R extends number[], infer L]
? [...(Sort<R, M>), L]
: T
Solution by goddnsgit #22194
type Reverse<Arr extends readonly any[]> = Arr extends [infer TFirst, ...infer TRest] ? [...Reverse<TRest>, TFirst] : Arr;
type Greater<N1 extends number, N2 extends number, arr extends number[] = []> =
arr['length'] extends N1 ? false
: arr['length'] extends N2 ? true
: Greater<N1, N2, [...arr, arr['length']]>;
type PushRight<Arr extends readonly any[]> = Arr extends [infer T1 extends number, infer T2 extends number, ...infer TRest]
? (Greater<T1, T2> extends true ? [T2, ...PushRight<[T1, ...TRest]>] : [T1, ...PushRight<[T2, ...TRest]>])
: Arr;
type SortAscending<Arr extends readonly any[], PushedRight = PushRight<Arr>> = PushedRight extends [...infer TRest, infer TLast]
? [...SortAscending<TRest>, TLast]
: PushedRight;
type Sort<Arr extends readonly any[], reverse extends boolean = false> = reverse extends true ? Reverse<SortAscending<Arr>> : SortAscending<Arr>;
Solution by mdakram28 #20653
// Works for natural numbers with 15+ digits.
type GreaterThan<T extends number, U extends number, K extends any[] = []> = K['length'] extends T
? false
: K['length'] extends U
? true
: GreaterThan<T, U, [...K, any]>
type GetBiggest<Arr extends number[], Res extends number = 0> = Arr extends [infer R extends number, ...infer Tail extends number[]]
? GreaterThan<R, Res> extends true
? GetBiggest<Tail, R> : GetBiggest<Tail, Res>
: Res
type RemoveNumber<Arr extends number[], Number extends number> = Arr extends [infer N extends number, ...infer Tail extends number[]]
? [
...N extends Number? [] : [N],
...N extends Number ? Tail : RemoveNumber<Tail, Number>
]
: []
type Reverse<T extends any[]> = T extends [infer F, ...infer R] ? [...Reverse<R>, F] : []
type Sort<
Arr extends number[],
Rev extends boolean = false,
Res extends any[] = [],
ArrLeng extends number = Arr['length'],
Biggest extends number = GetBiggest<Arr>
> = Arr['length'] extends 0
? Rev extends true
? Reverse<Res> : Res
: Res['length'] extends ArrLeng
? never : Sort<RemoveNumber<Arr, Biggest>, Rev, [Biggest, ...Res], ArrLeng>
Solution by Zhukov87 #20066
type TenTimesNumber<T extends unknown[]> = [
...T,
...T,
...T,
...T,
...T,
...T,
...T,
...T,
...T,
...T
]
type NumberWithinTen<
T extends string | number,
R extends unknown[] = []
> = `${R['length']}` extends `${T}` ? R : NumberWithinTen<T, [unknown, ...R]>
type ToNumber<
T extends string | number,
R extends unknown[] = []
> = `${T}` extends `${infer A}${infer B}`
? ToNumber<B, [...TenTimesNumber<R>, ...NumberWithinTen<A>]>
: R
type GreaterThan<
A extends string | number,
B extends string | number
> = ToNumber<A> extends [...ToNumber<B>, ...infer R]
? R['length'] extends 0
? false
: true
: false
type Bubble<T extends number[], N extends boolean = false> = T extends [
infer A,
infer B,
...infer C
]
? A extends number
? B extends number
? GreaterThan<A, B> extends (N extends true ? false : true)
? [A, ...C] extends number[]
? [B, ...Bubble<[A, ...C], N>]
: never
: [B, ...C] extends number[]
? [A, ...Bubble<[B, ...C], N>]
: never
: never
: never
: T
type Sort<T extends number[], N extends boolean = false> = Bubble<
T,
N
> extends [...infer A, infer B]
? A extends number[]
? [...Sort<A, N>, B]
: never
: []
Solution by mossgowild #20047
// 实现小于等于工具函数 A <= B
type LessThanOrEqual<A extends number, B extends number, Count extends unknown[] = []> = Count['length'] extends A
? true // Count === A <= B
: Count['length'] extends B
? false // Count === B < A
: LessThanOrEqual<A, B, [unknown, ...Count]> // Count < A and Count < B
// 过滤得到小于等于 N 的数
type FilterLessThanOrEqual<N extends number, A extends number[] = [], Res extends number[] = []> = A extends [infer F extends number, ...infer rest extends number[]]
? LessThanOrEqual<F, N> extends true
? FilterLessThanOrEqual<N, rest, [...Res, F]>
: FilterLessThanOrEqual<N, rest, Res>
: Res
// 实现大于工具函数 A > B
type GreaterThan<A extends number, B extends number, Count extends unknown[] = []> = Count['length'] extends A
? false // Count === A < B
: Count['length'] extends B
? true // Count === B < A
: GreaterThan<A, B, [unknown, ...Count]>
// 过滤得到大于 N 的数
type FilterGreaterThan<N extends number, A extends number[] = [], Res extends number[] = []> = A extends [infer F extends number, ...infer rest extends number[]]
? GreaterThan<F, N> extends true
? FilterGreaterThan<N, rest, [...Res, F]>
: FilterGreaterThan<N, rest, Res>
: Res
/**
* 快排思想:跟分治思想很相似
* 第一轮，取一个基准值，小于等于基准值放在左边，大于基准值放在右边
* 第二轮，对于左边和右边的集合，分别进行第一轮的操作，也就是Sort操作
* ....
*/
type Sort<A extends number[] = [], B extends Boolean = false> = A extends [infer F extends number, ...infer rest extends number[]]
? B extends true
? [...Sort<FilterGreaterThan<F, rest>, B>, F, ...Sort<FilterLessThanOrEqual<F, rest>, B>]
: [...Sort<FilterLessThanOrEqual<F, rest>, B>, F, ...Sort<FilterGreaterThan<F, rest>, B>]
: []
Solution by wzp-coding #17287
// your answers
type Digit=
{
'0':never,
'1':'0',
'2':'0'|'1',
'3':'0'|'1'|'2',
'4':'0'|'1'|'2'|'3',
'5':'0'|'1'|'2'|'3'|'4',
'6':'0'|'1'|'2'|'3'|'4'|'5',
'7':'0'|'1'|'2'|'3'|'4'|'5'|'6',
'8':'0'|'1'|'2'|'3'|'4'|'5'|'6'|'7',
'9':'0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8',
} ;
type GreaterThan<
A extends keyof Digit,
B extends keyof Digit > =
B extends Digit[A]
? true
: false ;
type StringToTuple<
Str extends string > =
Str extends `${infer R extends string}${infer U extends string}`
? [R,...StringToTuple<U>]
: [] ;
type ReverseTuple<
Tuple extends readonly any[]> =
Tuple extends readonly [infer R,...infer U extends readonly any[] ]
? [...ReverseTuple<U>,R]
: [] ;
type NumberParts<
Num extends number> =
`${Num}` extends `-${infer R extends string}.${infer U extends string}`
? [['-'],StringToTuple<R>,StringToTuple<U>]
: `${Num}` extends `${infer R extends string}.${infer U extends string}`
? [['+'],StringToTuple<R>,StringToTuple<U>]
: `${Num}` extends `-${infer R extends string}`
? [['-'],StringToTuple<R>,[]]
: [['+'],StringToTuple<`${Num}`>,[]] ;
type DummyArrayCopy<
A extends readonly any[],
DummyElement = any > =
A extends readonly [infer R,...infer U extends readonly any[]]
? [DummyElement,...DummyArrayCopy<U,DummyElement>]
: [] ;
type NumberPartsToSameForm<
A extends number,
B extends number,
PartsA extends readonly any[] = NumberParts<A>,
PartsB extends readonly any[] = NumberParts<B>,
DummyPartsA extends readonly any[] =
PartsA extends
[
infer R extends readonly any[],
infer U extends readonly any[],
infer V extends readonly any[]
]
? [R,DummyArrayCopy<U>,DummyArrayCopy<V>]
: never,
DummyPartsB extends readonly any[] =
PartsB extends
[
infer R extends readonly any[],
infer U extends readonly any[],
infer V extends readonly any[]
]
? [R,DummyArrayCopy<U>,DummyArrayCopy<V>]
: never,
> =
[
[
PartsA[0],
PartsA[1] extends [...DummyPartsB[1],...infer R extends readonly any[]]
? PartsA[1]
: PartsB[1] extends [...DummyPartsA[1],...infer R extends readonly any[]]
? [...DummyArrayCopy<R,'0'>,...PartsA[1]]
: [never] ,
PartsA[2] extends [...DummyPartsB[2],...infer R extends readonly any[]]
? PartsA[2]
: PartsB[2] extends [...DummyPartsA[2],...infer R extends readonly any[]]
? [...PartsA[2],...DummyArrayCopy<R,'0'>]
: never
] ,
[
PartsB[0],
PartsB[1] extends [...DummyPartsA[1],...infer R extends readonly any[]]
? PartsB[1]
: PartsA[1] extends [...DummyPartsB[1],...infer R extends readonly any[]]
? [...DummyArrayCopy<R,'0'>,...PartsB[1]]
: [never] ,
PartsB[2] extends [...DummyPartsA[2],...infer R extends readonly any[]]
? PartsB[2]
: PartsA[2] extends [...DummyPartsB[2],...infer R extends readonly any[]]
? [...PartsB[2],...DummyArrayCopy<R,'0'>]
: never
]
] ;
type CompareState ='greater'|'less'|'equal' ;
type SignCompare<
Parts extends readonly any[],
PartsA extends readonly any[] = Parts[0],
PartsB extends readonly any[] = Parts[1]> =
PartsA[0] extends ['+']
? PartsB[0] extends ['+']
? [PartsA,PartsB]
: 'greater'
: PartsB[0] extends ['+']
? 'less'
: [PartsA,PartsB] ;
type PartsToEffectiveParts<
Parts extends readonly any[],
PartsA extends readonly any[] = Parts[0],
PartsB extends readonly any[] = Parts[1],
EffectivePartsA extends readonly any[] = [...PartsA[1],...PartsA[2]],
EffectivePartsB extends readonly any[]= [...PartsB[1],...PartsB[2]]
> =
[EffectivePartsA,EffectivePartsB] ;
type ModuleCompare<
EffectiveParts extends readonly any[],
EffectivePartsA extends readonly any[] = EffectiveParts[0],
EffectivePartsB extends readonly any[] = EffectiveParts[1]> =
EffectivePartsA extends readonly [infer R extends keyof Digit,...infer U extends (keyof Digit)[]]
? EffectivePartsB extends readonly [infer V extends keyof Digit,...infer W extends (keyof Digit)[]]
? GreaterThan<R,V> extends true
? 'greater'
: GreaterThan<V,R> extends true
? 'less'
: ModuleCompare<[U,W]>
: 'equal'
: 'equal'
type Compare<
A extends number,
B extends number,
CompareByModule=ModuleCompare<PartsToEffectiveParts<NumberPartsToSameForm<A,B>>>,
CompareBySign=SignCompare<NumberPartsToSameForm<A,B>> > =
CompareBySign extends CompareState
? CompareBySign
: CompareByModule extends 'less'
? `${A}` extends `-${number}`
? 'greater'
: 'less'
: CompareByModule extends 'greater'
? `${A}` extends `-${number}`
? 'less'
: 'greater'
: CompareByModule ;
type ArrayToParts<
A extends readonly any[],
PartA extends readonly any[]=[],
PartB extends readonly any[]=[]> =
A extends readonly [infer R,infer U,...infer V]
? ArrayToParts<V,[...PartA,R],[...PartB,U]>
: A extends readonly [infer R,...infer V]
? ArrayToParts<V,[...PartA,R],[...PartB]>
: [PartA,PartB];
type PartSort<
Part extends readonly number[],
Etalon extends number,
OutputA extends readonly number[]=[],
OutputB extends readonly number[]=[]> =
Part extends [infer R extends number,...infer V extends number[]]
? Compare<R,Etalon> extends 'greater'
? PartSort<V,Etalon,OutputA,[...OutputB,R]>
: PartSort<V,Etalon,[...OutputA,R],OutputB>
: [OutputA,OutputB] ;
type Sort<
Input extends readonly number[],
Flag extends boolean = false,
InputParts extends readonly (number[])[] = ArrayToParts<Input>,
InputPartA extends readonly number[] = InputParts[0],
InputPartB extends readonly number[] = InputParts[1],
Etalon extends number = InputPartA extends [] ? InputPartB extends [] ? never : InputPartB[0] :InputPartA[0],
InputPartASorted extends readonly (readonly number[])[] = InputPartA extends [] ? [] : PartSort<InputPartA,Etalon>,
InputPartBSorted extends readonly (readonly number[])[] = InputPartB extends [] ? [] : PartSort<InputPartB,Etalon>,
> =
Input extends readonly (Input[0])[]
? Input
: [[...InputPartASorted[0],...InputPartBSorted[0]],[...InputPartASorted[1],...InputPartBSorted[1]]] extends
readonly [infer R extends readonly number[],infer U extends readonly number[]]
? Flag extends false
? [...(R extends [] ? R :Sort<ReverseTuple<R>,Flag>),...(U extends [] ? U :Sort<ReverseTuple<U>,Flag>)]
:[...(U extends [] ? U :Sort<ReverseTuple<U>,Flag>),...(R extends [] ? R :Sort<ReverseTuple<R>,Flag>)]
: never ;
Solution by justBadProgrammer #16719
// your answers
type NumberToTuple<T extends number, Result extends 0[] = []> = Result['length'] extends T
? Result
: NumberToTuple<T, [0, ...Result]>
type MinusOne<T extends number, Result extends 0[] = NumberToTuple<T>> = Result extends [infer F, ...infer R]
? R['length']
: 0
type GT<A extends number, B extends number> = A extends B
? false
: A extends 0
? false
: B extends 0
? true
: GT<MinusOne<A>, MinusOne<B>>
type SingleSort<
T extends number,
Source extends unknown[] = [],
Desc extends boolean = false,
Result extends number[] = []
> = Source extends [infer F extends number, ...infer R]
? Equal<T, F> extends true
? [...Result, T, F, ...R]
: GT<T, F> extends true
? Desc extends true
? [...Result, T, F, ...R]
: SingleSort<T, R, Desc, [...Result, F]>
: Desc extends true
? SingleSort<T, R, Desc, [...Result, F]>
: [...Result, T, F, ...R]
: [...Result, T]
type Sort<
T extends unknown[],
Desc extends boolean = false,
Result extends number[] = []
> = T extends [infer F extends number, ...infer R]
? Sort<R, Desc, SingleSort<F, Result, Desc>>
: Result
Solution by humandetail #16698
type NumberSet<T, U extends number = 0, R extends number[] = []> = U extends T ? [...R, U][number] : NumberSet<T, R["length"], [...R, U]>;
type GreaterThan<T, U> = [Exclude<NumberSet<T>, NumberSet<U>>] extends [never] ? false : true;
type Min<T extends any[], R extends any = T[0]> =
T extends [infer F, ...infer Rest]
? GreaterThan<F, R> extends true ? Min<Rest, R> : Min<Rest, F>
: R;
type Max<T extends any[], R extends any = T[0]> =
T extends [infer F, ...infer Rest]
? GreaterThan<F, R> extends true ? Max<Rest, F> : Max<Rest, R>
: R;
type Remove<Tuple, Item, R extends any[] = []> =
Tuple extends [infer F, ...infer Rest]
? F extends Item
? Remove<Rest, never, R>
: Remove<Rest, Item, [...R, F]>
: R;
type Sort<T extends number[], Reverse = false, R extends number[] = []> =
T extends []
? R
: Reverse extends true
? Sort<Remove<T, Max<T>>, Reverse, [...R, Max<T>]>
: Sort<Remove<T, Min<T>>, Reverse, [...R, Min<T>]>;
Solution by softoika #15178
// your answers
enum Comparison {
Greater,
Equal,
Lower,
}
type Comparator<X extends number, Y extends number, A extends 1[] = []> = A['length'] extends Y
? A['length'] extends X
? Comparison.Equal
: Comparison.Greater
: A['length'] extends X
? Comparison.Lower
: Comparator<X, Y, [...A, 1]>
type IsMaxOrMin<
T extends number,
A extends number[],
End extends Comparison.Lower | Comparison.Greater // true时降序，T < F结束判断，T不可能是最大的
> = A extends [infer F extends number, ...infer R extends number[]]
? Comparator<T, F> extends End ? false : IsMaxOrMin<T, R, End> // 两数相等或者不是结束条件继续递归
: true
type Sort<T extends number[], D extends boolean = false, Res extends number[] = []> = T extends [infer F extends number, ...infer R extends number[]]
? (
// 如果是升序排序D为false，Comparator比较剩下的元素时只要有一个比他小，返回Greater，那么就不是最小的，把这个元素放到数组末尾，继续找最小值
// 如果是降序排序D为true，Comparator比较剩下的元素时只要有一个比他大，返回Lower，那么就不是最大的，把这个元素放到数组末尾，继续找最大值
IsMaxOrMin<F, R, D extends true ? Comparison.Lower : Comparison.Greater> extends true
? Sort<R, D, [...Res, F]>
: Sort<[...R, F], D, Res>
)
: Res
Solution by fengchunqi #14947
Do not consider extra challenges.
import type { Equal, Expect } from "@type-challenges/utils";
type cases = [
Expect<Equal<Sort<[]>, []>>,
Expect<Equal<Sort<[1]>, [1]>>,
Expect<Equal<Sort<[2, 1]>, [1, 2]>>,
Expect<Equal<Sort<[0, 0, 0]>, [0, 0, 0]>>,
Expect<Equal<Sort<[1, 2, 3]>, [1, 2, 3]>>,
Expect<Equal<Sort<[3, 2, 1]>, [1, 2, 3]>>,
Expect<Equal<Sort<[3, 2, 1, 2]>, [1, 2, 2, 3]>>,
Expect<Equal<Sort<[3, 2, 0, 1, 0, 0, 0]>, [0, 0, 0, 0, 1, 2, 3]>>,
Expect<Equal<Sort<[2, 4, 7, 6, 6, 6, 5, 8, 9]>, [2, 4, 5, 6, 6, 6, 7, 8, 9]>>,
Expect<Equal<Sort<[1, 1, 2, 1, 1, 1, 1, 1, 1]>, [1, 1, 1, 1, 1, 1, 1, 1, 2]>>,
Expect<Equal<Sort<[], true>, []>>,
Expect<Equal<Sort<[1], true>, [1]>>,
Expect<Equal<Sort<[2, 1], true>, [2, 1]>>,
Expect<Equal<Sort<[0, 0, 0], true>, [0, 0, 0]>>,
Expect<Equal<Sort<[1, 2, 3], true>, [3, 2, 1]>>,
Expect<Equal<Sort<[3, 2, 1], true>, [3, 2, 1]>>,
Expect<Equal<Sort<[3, 2, 1, 2], true>, [3, 2, 2, 1]>>,
Expect<Equal<Sort<[3, 2, 0, 1, 0, 0, 0], true>, [3, 2, 1, 0, 0, 0, 0]>>,
Expect<
Equal<Sort<[2, 4, 7, 6, 6, 6, 5, 8, 9], true>, [9, 8, 7, 6, 6, 6, 5, 4, 2]>
>
];
type MakeTuple<U extends number, T extends any[] = []> = T["length"] extends U
? T
: MakeTuple<U, [any, ...T]>;
type IsGe<T extends number, U extends number> = T extends U
? false
: Reduce<U, MakeTuple<T>>;
type Reduce<U extends number, T extends any[] = []> = T["length"] extends U
? true
: T["length"] extends 0
? false
: T extends [infer Alpha, ...infer Rest]
? Reduce<U, Rest>
: never;
type Compare<T extends number, U extends number> = T extends U
? 0
: IsGe<T, U> extends true
? 1
: -1;
type PickSmall<T extends any[]> = T extends [infer Alpha, ...infer Rest]
? Rest extends []
? Alpha
: Compare<Alpha & number, PickSmall<Rest>> extends -1 | 0
? Alpha & number
: PickSmall<Rest>
: never;
type Split<T extends any[], U extends any> = T extends [
infer Alpha,
...infer Rest
]
? Rest extends []
? U extends Alpha
? []
: [Alpha]
: U extends Alpha
? Rest
: [Alpha, ...Split<Rest, U>]
: [];
type Reverse<T extends any[]> = T extends [...infer Rest, infer Last]
? Rest extends []
? [Last]
: [Last, ...Reverse<Rest>]
: T;
type SortAsc<T extends any[]> = T extends [infer Alpha, ...infer Rest]
? Rest extends []
? [Alpha]
: Compare<Alpha & number, PickSmall<Rest>> extends 0 | -1
? [Alpha, ...SortAsc<Rest>]
: [PickSmall<Rest>, ...SortAsc<[Alpha, ...Split<Rest, PickSmall<Rest>>]>]
: T;
type SortDes<T extends number[]> = Reverse<T>;
type Sort<T extends any[], U extends boolean = false> = U extends true
? SortDes<SortAsc<T>>
: SortAsc<T>;
Solution by wbcs #11893
The shortest solution - quick sort
type Sort<A extends number[], D extends boolean = false>
= A extends [infer A0 extends number, infer A1 extends number, ...infer AR extends number[]]
? Split<[A1, ...AR], A0> extends [infer Lower extends number[], infer Higher extends number[]]
? D extends true
? [...Sort<Higher, D>, A0, ...Sort<Lower, D>]
: [...Sort<Lower, D>, A0, ...Sort<Higher, D>]
: never
: A
// <[5, 1, 4, 2, 3], 3> -> [[1, 2], [5, 4, 3]]; <[1, 2, 3], 4> -> [[1, 2, 3], []]
type Split<A extends number[], M extends number, Lower extends number[] = [], Higher extends number[] = []>
= A extends [infer H extends number, ...infer T extends number[]]
? IsLower<H, M> extends true
? Split<T, M, [...Lower, H], Higher>
: Split<T, M, Lower, [...Higher, H]>
: [Lower, Higher]
// <2, 4> -> true; <4, 2> -> false; <2, 2> -> false
type IsLower<A extends number, B extends number>
= '0123456789' extends `${string}${A}${string}${B}${string}` ? true : false
Extra: solution for big & negative numbers
All it needs to start working on big and negative numbers is just to replace IsLower with a more fancy implementation from the 274 - Integers Comparator problem
type IsLower<A extends number, B extends number> = Comparator<A, B> extends 'Lower' ? true : false
type Comparator<A extends number, B extends number>
= `${A}` extends `-${infer AbsA}`
? `${B}` extends `-${infer AbsB}`
? ComparePositives<AbsB, AbsA>
: 'Lower'
: `${B}` extends `-${number}`
? 'Greater'
: ComparePositives<`${A}`, `${B}`>
type ComparePositives<A extends string, B extends string, ByLength = CompareByLength<A, B>>
= ByLength extends 'Equal'
? CompareByDigits<A, B>
: ByLength
type CompareByLength<A extends string, B extends string>
= A extends `${infer AF}${infer AR}`
? B extends `${infer BF}${infer BR}`
? CompareByLength<AR, BR>
: 'Greater'
: B extends `${infer BF}${infer BR}`
? 'Lower'
: 'Equal'
type CompareByDigits<A extends string, B extends string>
= `${A}|${B}` extends `${infer AF}${infer AR}|${infer BF}${infer BR}`
? CompareDigits<AF, BF> extends 'Equal'
? CompareByDigits<AR, BR>
: CompareDigits<AF, BF>
: 'Equal'
type CompareDigits<A extends string, B extends string>
= A extends B
? 'Equal'
: '0123456789' extends `${string}${A}${string}${B}${string}`
? 'Lower'
: 'Greater'
Solution by Alexsey #11688
// bubble sort, goal is to support a larger tuple
type Sort<T extends readonly number[], D extends boolean = false> = ReturnType<<
K extends keyof T & `${number}`,
T1 extends {[I in keyof T]:
[IsOdd<I>, MinusOne<I>] extends [true, infer Isub1 extends K] ? CompareAndSwap<T[Isub1], T[I], D>[1] // ..., 2, 3(i), ...
: [I, PlusOne<I>] extends [`${number}`, infer Iadd1 extends K] ? CompareAndSwap<T[I], T[Iadd1], D>[0] // ..., 2(i), 3, ...
: T[I]},
K1 extends keyof T1 & `${number}`,
T2 extends {[I in keyof T1]:
[IsOdd<I>, PlusOne<I>] extends [true, infer Iadd1 extends K1] ? CompareAndSwap<T1[I], T1[Iadd1], D>[0] // ..., 1(i), 2, ...
: [I, MinusOne<I>] extends [`${number}`, infer Isub1 extends K1] ? CompareAndSwap<T1[Isub1], T1[I], D>[1] // ..., 1, 2(i), ...
: T1[I]},
>() => T2> extends infer T2 extends readonly number[]
? T extends T2 ? T : Sort<T2, D> : never
type CompareAndSwap<A extends number, B extends number, D extends boolean = false>
= IsGreater<B, A> extends D ? [B, A] : [A, B]
type IsOdd<N extends keyof any> = N extends `${any}${1 | 3 | 5 | 7 | 9}` ? true : false
type PlusOne<N>
= N extends `${infer L}0` ? `${L}1` : N extends `${infer L}1` ? `${L}2` : N extends `${infer L}2` ? `${L}3`
: N extends `${infer L}3` ? `${L}4` : N extends `${infer L}4` ? `${L}5` : N extends `${infer L}5` ? `${L}6`
: N extends `${infer L}6` ? `${L}7` : N extends `${infer L}7` ? `${L}8` : N extends `${infer L}8` ? `${L}9`
: N extends '9' ? '10' : N extends `${infer L}9` ? `${PlusOne<L>}0` : never
type MinusOne<N>
= N extends `${infer L}9` ? `${L}8` : N extends `${infer L}8` ? `${L}7` : N extends `${infer L}7` ? `${L}6`
: N extends `${infer L}6` ? `${L}5` : N extends `${infer L}5` ? `${L}4` : N extends `${infer L}4` ? `${L}3`
: N extends `${infer L}3` ? `${L}2` : N extends `${infer L}2` ? `${L}1` : N extends `${infer L}1` ? `${L}0`
: N extends '0' ? '-1' : N extends '10' ? '9' : N extends `${infer L}0` ? `${MinusOne<L>}9` : never
// Comapre Numbers
type IsGreater<A extends number, B extends number>
= A extends B ? false
: [`${A}`, `${B}`] extends [`${infer A1}${infer A2}`, `${infer B1}${infer B2}`]
? '-' extends A1 ? ('-' extends B1 ? IsGreaterNumber<B2, A2> : false)
: '-' extends B1 ? true
: A1 extends B1 ? IsGreaterNumber<A2, B2>
: '0123456789' extends `${any}${A1}${any}${B1}${any}` ? IsLonger<A2, B2>
: IsLonger<B2, A2> extends true ? false : true
: never
type IsGreaterNumber<A extends string, B extends string>
= A extends B ? false
: [A, B] extends [`${infer A1}${infer A2}`, `${infer B1}${infer B2}`]
? '.' extends A1 ? ('.' extends B1 ? IsGreaterFractional<A2, B2> : false)
: '.' extends B1 ? true
: A1 extends B1 ? IsGreaterNumber<A2, B2>
: '0123456789' extends `${any}${A1}${any}${B1}${any}` ? IsLonger<A2, B2>
: IsLonger<B2, A2> extends true ? false : true
: '' extends A ? false : true
type IsLonger<A extends string, B extends string>
= A extends B ? false
: [A, B] extends [`${infer A1}${infer A2}`, `${infer B1}${infer B2}`]
? '.' extends A1 ? false
: '.' extends B1 ? true
: IsLonger<A2, B2>
: '' extends A ? false : true
type IsGreaterFractional<A extends string, B extends string>
= A extends B ? false
: [A, B] extends [`${infer A1}${infer A2}`, `${infer B1}${infer B2}`]
? A1 extends B1 ? IsGreaterFractional<A2, B2>
: '0123456789' extends `${any}${A1}${any}${B1}${any}` ? false : true
: '' extends A ? false : true
// Testing
type Any9999 = Replicate<9999>
type N9999 = Any9999 extends [...infer T] ? {[I in keyof T]: I extends `${infer N extends number}` ? N : never} : []
type Sorted9999 = Sort<N9999> // best case
// ^?
type Any300 = Replicate<300>
type N300 = Any300 extends [...infer T] ? {[I in keyof T]: I extends `${infer N extends number}` ? N : never} : []
type Sorted300 = Sort<N300, true> // worst case
// ^?
type Replicate<N extends number | string, T extends any[] = []>
= `${N}` extends `${infer L extends number}${infer R}` ? Replicate<R, [...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...[[], [any], [any, any], [any, any, any], [any, any, any, any], [any, any, any, any, any], [any, any, any, any, any, any], [any, any, any, any, any, any, any], [any, any, any, any, any, any, any, any], [any, any, any, any, any, any, any, any, any]][L]]>
: T
Solution by teamchong #11490