type CountReversePairs<T extends number[]>
= CountUnion<{[I in Keys<T>]: {[J in Keys<T>]: GreaterThan<J, I> extends true ? GreaterThan<T[I], T[J]> extends true ? `${I}>${J}` : never : never}[Keys<T>]}[Keys<T>]>
type Keys<T extends unknown[]> = keyof T & `${number}`
type CountUnion<U extends string, C extends string = '0'> = [U] extends [never] ? C extends `${infer N extends number}` ? N : never : CountUnion<Exclude<U, Single<U>>, PlusOne<C>>
type Single<U> = (U extends U ? (_: Promise<U>) => void : never) extends (_: infer I extends Promise<U>) => void ? Awaited<I> : never
type PlusOne<N extends string>
= N extends `${infer L}9` ? `${PlusOne<L>}0`
: N extends `${infer L}8` ? `${L}9` : N extends `${infer L}7` ? `${L}8` : N extends `${infer L}6` ? `${L}7` : N extends `${infer L}5` ? `${L}6` : N extends `${infer L}4` ? `${L}` : N extends `${infer L}3` ? `${L}4` : N extends `${infer L}2` ? `${L}3` : N extends `${infer L}1` ? `${L}2` : N extends `${infer L}0` ? `${L}1`
: '1'
type GreaterThan<X extends string | number, Y extends string | number, Gt = undefined>
= X extends Y ? Gt extends true | false ? Gt : false
: `${X} ${Y}` extends `${infer A}${infer C} ${infer B}${infer D}`
? GreaterThan<C, D, Gt extends true | false ? Gt
: A extends B ? Gt
: '9876543210' extends `${any}${A}${any}${B}${any}` ? true : false>
: `${Y}` extends `` ? true : false
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