type TupleOfLength<N extends number, Result extends 0[] = []> = Result["length"] extends N
? Result
: TupleOfLength<N, [...Result, 0]>;
// if L is greater than R, return true, else false
type Greater<L extends number, R extends number> = `${L}` extends `-${infer AbsL extends number}`
? `${R}` extends `-${infer AbsR extends number}`
? TupleOfLength<AbsL> extends [...TupleOfLength<AbsR>, ...unknown[]]
? false
: true
: false
: `${R}` extends `-${number}`
? true
: TupleOfLength<L> extends [...TupleOfLength<R>, unknown, ...unknown[]]
? true
: false;
type ExtractReversePairs<N extends number, T extends number[]> = T extends [
infer First extends number,
...infer Rest extends number[]
]
? Greater<N, First> extends true
? [[N, First], ...ExtractReversePairs<N, Rest>]
: ExtractReversePairs<N, Rest>
: [];
type CountReversePairs<T extends number[], U extends unknown[] = []> = T extends [
infer First extends number,
...infer Rest extends number[]
]
? CountReversePairs<Rest, [...U, ...ExtractReversePairs<First, Rest>]>
: U["length"];
Solution by yukicountry #34535
type CountReversePairs<T extends number[]>
= CountUnion<{[I in keyof T]:
{[J in keyof T]: `${IsGreater<J, I>}${IsGreater<T[I], T[J]>}` extends `truetrue` ? `${I},${J}` : never
}[number]}[number]>
type CountUnion<U, C extends number = 0>
= [U] extends [never] ? C
: (U extends U ? [Promise<U>] : never) extends {fill: (_: infer L) => any}
? CountUnion<Exclude<U, Awaited<L>>, PlusOne<C>> : never
type IsGreater<A extends string | number, B extends string | number, AB = `${A},${B}`>
= AB extends `-${infer A},-${infer B}` ? IsGreater<B, A>
: AB extends `-${any},${any}` ? false
: AB extends `${any},-${any}` ? true
: AB extends `${infer C}${infer A},${infer D}${infer B}`
? C extends D ? IsGreater<A, B>
: '0123456789' extends `${any}${C}${any}${D}${any}` ? IsLonger<A, B>
: IsLonger<B, A> extends true ? false : true
: AB extends `${any}${any},` ? true : false
type IsLonger<A extends string, B extends string, AB = `${A},${B}`>
= AB extends `${any}${infer A},${any}${infer B}` ? IsLonger<A, B>
: AB extends `${any}${any},` ? true : false
type PlusOne<N extends number, D extends number[] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]>
= (`${N}` extends `${infer L extends number}9` ? `${PlusOne<L>}0`
: {[I in keyof D]: `${N}` extends `${infer L}${I}` ? `${L}${D[I]}` : never}[number]
) extends `${infer N extends number}` ? N : never
Solution by teamchong #32983
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 FindGreater<T extends number[], N extends number> = T extends [infer L extends number, ...infer R extends number[]] ?
(Comparator<L, N> extends Comparison.Greater ?
[...FindGreater<R, N>, 1] : FindGreater<R, N>)
: []
// type FindGreaterCount<T extends number[], N extends number> = FindGreater<T, N>['length']
type CountReversePairsArray<T extends number[], C extends number[] = [] > = T extends [infer L extends number, ...infer R extends number[]] ? [...CountReversePairsArray<R, [...C, L]>, ...FindGreater<C, L>] : []
type CountReversePairs<T extends number[]> = CountReversePairsArray<T>['length']
First reuse the answer of Integers Comparator, FindGreater can count how many elements
in T is bigger than N, then in CountResversePairsArray just traverse the array and use FindGreater to get the count of each element.
Solution by Royce-DaDaDa #32966
type Pairs<T extends number[]> = T extends [ infer F extends number, ...infer Rest extends number[] ]
? `${string}${F}${string}${Rest[number]}${string}` | Pairs<Rest>
: never
type Filter<T extends string> = T extends unknown
? '9876543210' extends T
? T
: never
: never
// Previous challenge https://github.com/type-challenges/type-challenges/blob/main/questions/00730-hard-union-to-tuple/README.md
type UnionToIntersectionFn<U> = (U extends unknown ? (arg: () => U) => void : never) extends (arg: infer I) => void ? I : never
type GetUnionLast<U> = UnionToIntersectionFn<U> extends () => infer I ? I : never
type UnionToTuple<U, Last = GetUnionLast<U>> = [U] extends [never] ? [] : [...UnionToTuple<Exclude<U, Last>>, Last]
type CountReversePairs<
T extends number[],
P extends string = Pairs<T>,
F extends string = Filter<P>
> = UnionToTuple<F>['length']
Solution by lvjiaxuan #32945
type AbsReverses<X extends number, Y extends number, A extends 1[] = []> = A['length'] extends X
? 0
: A['length'] extends Y ? 1 : AbsReverses<X, Y, [...A, 1]>;
type Reverses<A extends number, B extends number> = `${A}` extends `-${infer X extends number}`
? `${B}` extends `-${infer Y extends number}` ? AbsReverses<Y, X> : 0
: `${B}` extends `-${number}` ? 1 : AbsReverses<A, B>;
type CountReverseWith<N extends number, A extends number[], R extends 1[] = []> = A extends [infer F extends number, ...infer T extends number[]]
? CountReverseWith<N, T, Reverses<N, F> extends 0 ? R : [...R, 1]>
: R;
type CountReversePairs<A extends number[], R extends 1[] = []> = A extends [infer F extends number, ...infer T extends number[]]
? CountReversePairs<T, [...R, ...CountReverseWith<F, T>]>
: R['length'];
Solution by alexandroppolus #31758
type SimpleGreaterThan<A extends number, B extends number, _StackA extends 1[] = [], _StackB extends 1[] = []> =
`${A}${B}` extends `-${infer NA extends number}-${infer NB extends number}` ?
SimpleGreaterThan<NB, NA> : //Negative
`${A}` extends `-${number}` ? false : //only A Negative
`${B}` extends `-${number}` ? true : //only B Negative
_StackA[`length`] extends A | 999 ? false :
_StackB[`length`] extends B | 999 ? true :
SimpleGreaterThan<A, B, [..._StackA, 1], [..._StackB, 1]>;
type CountReversePairsOnce<T extends number, U extends number[], _Recorder extends 1[] = []> =
U extends [infer F extends number, ...infer R extends number[]] ?
CountReversePairsOnce<T, R, SimpleGreaterThan<T, F> extends true ? [..._Recorder, 1] : _Recorder> :
_Recorder/*return*/;
type CountReversePairs<T extends number[], _Recorder extends 1[] = []> =
T extends [infer F extends number, ...infer R extends number[]] ?
CountReversePairs<R, [..._Recorder, ...CountReversePairsOnce<F, R>]> :
_Recorder[`length`]/*return*/;
Solution by E-uler #31605
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 LSorted extends number[],infer LC extends number[] ],
[infer RSorted extends number[],infer RC extends number[] ]
]?
[Merge<LSorted,RSorted>,[...LC,...RC,...CountSorted<LSorted,RSorted>]]:never
type CountSorted<
T extends number[],
U extends number[],
R extends number[] = []
> =
U extends [infer UF extends number,...infer UR extends number[]]?
T extends [infer TF extends number,...infer TR extends number[]]?
LTE<TF,UF> extends false?
CountSorted<T,UR,[...R,...T]>
:CountSorted<TR,U,R>
: R
: R
type CountReversePairs<T extends number[]> = MergeSort<T>[1]['length'];
Solution by jiangshanmeta #31454