import type { IsGreaterThan, IsLowerThan, Minus } from "flat-type-samurai";

type MaxProfit<
  Prices extends number[],
  Profit extends number = 0,
  MinPrice extends number = 10e4,
> =
  Prices extends [infer Head extends number, ...infer Tail extends number[]] ?
    IsLowerThan<Head, MinPrice> extends true ? MaxProfit<Tail, Profit, Head>
    : IsGreaterThan<Minus<Head, MinPrice>, Profit> extends true ?
      MaxProfit<Tail, Minus<Head, MinPrice>, MinPrice>
    : MaxProfit<Tail, Profit, MinPrice>
  : Profit;

type Result1 = MaxProfit<[7, 1, 5, 3, 6, 4]>;
       
type Result1 = 5

type Result2 = MaxProfit<[7, 6, 4, 3, 1]>;
       
type Result2 = 0

import type { IsGreaterThan, IsEmptyArray } from "flat-type-samurai";

type MergeArrays<
  A extends number[],
  B extends number[],
  R extends number[] = [],
> =
  A extends [infer A1 extends number, ...infer ARest extends number[]] ?
    B extends [infer B1 extends number, ...infer BRest extends number[]] ?
      IsGreaterThan<A1, B1> extends false ?
        MergeArrays<ARest, B, [...R, A1]>
      : MergeArrays<A, BRest, [...R, B1]>
    : IsEmptyArray<B> extends true ? [...R, A1, ...ARest]
    : []
  : IsEmptyArray<A> extends true ? [...R, ...B]
  : [];

type Result1 = MergeArrays<[1, 2, 3], [2, 5, 6]>;
       
type Result1 = [1, 2, 2, 3, 5, 6]

type Result2 = MergeArrays<[1], []>;
       
type Result2 = [1]

type Result3 = MergeArrays<[0], [1]>;
       
type Result3 = [0, 1]

type Result4 = MergeArrays<[4, 5, 6], [1, 2, 3]>;
       
type Result4 = [1, 2, 3, 4, 5, 6]

type RemoveElement<Arr extends number[], Ele extends number> =
  Arr extends [infer Head, ...infer Tail extends number[]] ?
    Head extends Ele ?
      RemoveElement<Tail, Ele>
    : [Head, ...RemoveElement<Tail, Ele>]
  : [];

type Result1 = RemoveElement<[3, 2, 2, 3], 3>;
       
type Result1 = [2, 2]

type Result2 = RemoveElement<[0, 1, 2, 2, 3, 0, 4, 2], 2>;
       
type Result2 = [0, 1, 3, 0, 4]

import type {
  Sum,
  Minus,
  IsLowerThan,
  Mult,
  LastCharacter,
} from "flat-type-samurai";
import type { LastCharacterWithRest } from "utils";

type LetterToInt<T extends string> =
  T extends "I" ? 1
  : T extends "V" ? 5
  : T extends "X" ? 10
  : T extends "L" ? 50
  : T extends "C" ? 100
  : T extends "D" ? 500
  : T extends "M" ? 1000
  : never;

type NewResult<
  Char extends string,
  R extends number,
  Num extends number = LetterToInt<Char>,
> = IsLowerThan<Mult<4, Num>, R> extends true ? Minus<R, Num> : Sum<R, Num>;

type RomanToInt<
  Roman extends string,
  R extends number = 0,
  L extends [string, string] = LastCharacterWithRest<Roman>,
> = Roman extends "" ? R : RomanToInt<L[1], NewResult<L[0], R>>;

type Result1 = RomanToInt<"III">;
       
type Result1 = 3

type Result2 = RomanToInt<"LV">;
       
type Result2 = 55

type Result3 = RomanToInt<"MCMXCIV">;
       
type Result3 = 1994

import type { Minus, Decrement, Increment, Max } from "flat-type-samurai";

/*
(-2, 3)-----(-1, 3)----( 0, 3)----( 1, 3)----( 2, 3)----( 3, 3)
    |                                                       |
    |                                                       |
(-2, 2)     (-1, 2)----( 0, 2)----( 1, 2)-----( 2, 2)       .
    |          |                                 |          .
    |          |                                 |          .
(-2, 1)     (-1, 1)    ( 0, 1)----( 1, 1)     ( 2, 1)
    |          |           |         |           |
    |          |           |         |           |
(-2, 0)     (-1, 0)    ( 0, 0)    ( 1, 0)     ( 2, 0)
    |          |                     |           |
    |          |                     |           |
(-2,-1)     (-1,-1)----( 0,-1)----( 1,-1)     ( 2,-1)
    |                                            |
    |                                            |
(-2,-2)-----(-1,-2)----( 0,-2)----( 1,-2)-----( 2,-2)

Given a positive integer N, return the N-th coordinate of the spiral above.
*/

type MovePos<
  Pos extends [number, number],
  Dir extends "up" | "right" | "down" | "left",
> =
  Dir extends "up" ? [Pos[0], Increment<Pos[1]>]
  : Dir extends "right" ? [Increment<Pos[0]>, Pos[1]]
  : Dir extends "down" ? [Pos[0], Decrement<Pos[1]>]
  : [Decrement<Pos[0]>, Pos[1]];

type NextDirection<Dir extends "up" | "right" | "down" | "left"> =
  Dir extends "up" ? "right"
  : Dir extends "right" ? "down"
  : Dir extends "down" ? "left"
  : "up";

type MoveForSteps<
  N extends number,
  Pos extends [number, number],
  Dir extends "up" | "right" | "down" | "left",
  StepCount extends number,
> =
  N extends 0 ? Pos
  : StepCount extends 0 ? Pos
  : MoveForSteps<Decrement<N>, MovePos<Pos, Dir>, Dir, Decrement<StepCount>>;

type Spiral<
  N extends number,
  Pos extends [number, number] = [0, 0],
  Dir extends "up" | "right" | "down" | "left" = "up",
  StepCount extends number = 1,
> =
  N extends 0 ? Pos
  : Spiral<
      Max<0, Minus<N, StepCount>>,
      MoveForSteps<N, Pos, Dir, StepCount>,
      NextDirection<Dir>,
      NextDirection<Dir> extends "up" | "down" ? Increment<StepCount>
      : StepCount
    >;

type Result1 = Spiral<0>;
       
type Result1 = [0, 0]

type Result2 = Spiral<1>;
       
type Result2 = [0, 1]

type Result3 = Spiral<2>;
       
type Result3 = [1, 1]

type Result4 = Spiral<3>;
       
type Result4 = [1, 0]

type Result5 = Spiral<4>;
       
type Result5 = [1, -1]

type Result6 = Spiral<5>;
       
type Result6 = [0, -1]

type Result7 = Spiral<6>;
       
type Result7 = [-1, -1]

type Result8 = Spiral<7>;
       
type Result8 = [-1, 0]

type Result9 = Spiral<8>;
       
type Result9 = [-1, 1]

type Result10 = Spiral<9>;
        
type Result10 = [-1, 2]

type Result11 = Spiral<10>;
        
type Result11 = [0, 2]

type Result12 = Spiral<11>;
        
type Result12 = [1, 2]

type Result13 = Spiral<12>;
        
type Result13 = [2, 2]

type Result14 = Spiral<13>;
        
type Result14 = [2, 1]

type Result15 = Spiral<14>;
        
type Result15 = [2, 0]

import type {
  IsLetter,
  ParseNumber,
  Or,
  And,
  IsEqual,
  Not,
  StringLength,
} from "flat-type-samurai";
import type { FirstCharacterWithRest, LastCharacterWithRest } from "utils";

type IsNumber<T extends string> = ParseNumber<T> extends never ? false : true;

type IsAlphaNumeric<T extends string> = And<
  Or<IsLetter<T>, IsNumber<T>>,
  Not<IsEqual<T, " ">>
>;

type ValidEndChars<
  T extends string,
  First extends [string, string] = FirstCharacterWithRest<T>,
  Last extends [string, string] = LastCharacterWithRest<First[1]>,
> =
  And<IsAlphaNumeric<First[0]>, IsAlphaNumeric<Last[0]>> extends true ?
    IsEqual<First[0], Last[0]>
  : false;

type TrimEnds<T extends string> =
  T extends `${string}${infer Rest}` ? LastCharacterWithRest<Rest>[1] : T;

type _IsPalindrome<T extends string> =
  T extends "" ? true
  : StringLength<T> extends 1 | 2 ? true
  : ValidEndChars<T> extends true ? _IsPalindrome<TrimEnds<T>>
  : false;

type Clean<T extends string> =
  T extends `${infer First}${infer Rest}` ?
    IsAlphaNumeric<First> extends true ?
      `${Lowercase<First>}${Clean<Rest>}`
    : Clean<Rest>
  : T;

type IsPalindrome<T extends string> = _IsPalindrome<Clean<T>>;

type Result1 = IsPalindrome<"A man, a plan, a canal: Panama">;
       
type Result1 = true

type Result2 = IsPalindrome<"race a car">;
       
type Result2 = true

type Result3 = IsPalindrome<" ">;
       
type Result3 = true

type Tail<T extends unknown[]> =
  T extends [...infer _, infer Last] ? Last : never;

type RemoveLast<T extends unknown[]> =
  T extends [...infer Rest, infer _] ? Rest : never;

type InvertOpen<T extends string> =
  T extends "(" ? ")"
  : T extends "[" ? "]"
  : T extends "{" ? "}"
  : never;

type ValidClose<Current extends string, Stack extends string[]> =
  Current extends ")" | "}" | "]" ?
    InvertOpen<Tail<Stack>> extends Current ?
      true
    : false
  : false;

type IsValidParentheses<S extends string, Stack extends string[] = []> =
  S extends `${infer F}${infer R}` ?
    F extends "(" | "{" | "[" ? IsValidParentheses<R, [...Stack, F]>
    : ValidClose<F, Stack> extends true ?
      IsValidParentheses<R, RemoveLast<Stack>>
    : false
  : Stack["length"] extends 0 ? true
  : false;

type Result1 = IsValidParentheses<"()">;
       
type Result1 = true

type Result2 = IsValidParentheses<"()[]{}">;
       
type Result2 = true

type Result3 = IsValidParentheses<"(]">;
       
type Result3 = false