06141-hard-binary-to-decimal

Back

思路：

  1. 实现数字类型两数相加
  2. 实现数字类型乘以2
type BinaryToDecimal<
  S extends string,
  Res extends number = 0
> = S extends `${infer N extends number}${infer Other}`
  ? BinaryToDecimal<Other, NumAdd<MulplyTwo<Res> & number, N> & number>
  : Res;

// 数字转数组
type NumberToArray<N extends number, Count extends 1[] = []> = number extends N
  ? []
  : [N] extends [Count["length"]]
  ? Count
  : NumberToArray<N, [...Count, 1]>;
// 实现一个数乘以2的结果
type MulplyTwo<N extends number> = [
  ...NumberToArray<N>,
  ...NumberToArray<N>
]["length"];
// 实现两数相加
type NumAdd<N extends number, M extends number> = [
  ...NumberToArray<N>,
  ...NumberToArray<M>
]["length"];

Solution by Vampirelee #32647 

// 解答をここに記入
type BinaryToDecimal<S extends string, Counter extends never[] = [never], Ans extends never[] = []> = S extends `${infer Rest}1` ? BinaryToDecimal<Rest, [...Counter, ...Counter], [...Ans, ...Counter]> : S extends `${infer Rest}0` ? BinaryToDecimal<Rest, [...Counter, ...Counter], Ans> : Ans["length"]

非常にシンプルな解答です。

2進数を下（2^0の方）から処理していく再帰で、Counter はその桁に対応する長さを持っています。

Ans は、解答となる数字を配列長で表現するための配列で、S の下一桁が 1 だったら Ans に Counter の要素を追加する（これはその桁の分をインクリメントする行為と同じ）ことで、10進数に変換していきます。

Solution by Kakeru-Miyazaki #30973 

// your answers
type ToTwo<T extends number[]> = [...T, ...T]

type BinaryToDecimal<S extends string, R extends number[] = []> = S extends `${infer Head}${infer Rest}` ? Head extends '1' ? BinaryToDecimal<Rest, [...ToTwo<R>, 0]> : BinaryToDecimal<Rest, ToTwo<R>> : R['length']

Solution by 437204933 #29717 

type PlusMap = {
  "0": {
    "0": [0, 0];
    "1": [1, 0];
    "2": [2, 0];
    "3": [3, 0];
    "4": [4, 0];
    "5": [5, 0];
    "6": [6, 0];
    "7": [7, 0];
    "8": [8, 0];
    "9": [9, 0];
  };
  "1": {
    "0": [1, 0];
    "1": [2, 0];
    "2": [3, 0];
    "3": [4, 0];
    "4": [5, 0];
    "5": [6, 0];
    "6": [7, 0];
    "7": [8, 0];
    "8": [9, 0];
    "9": [0, 1];
  };
  "2": {
    "0": [2, 0];
    "1": [3, 0];
    "2": [4, 0];
    "3": [5, 0];
    "4": [6, 0];
    "5": [7, 0];
    "6": [8, 0];
    "7": [9, 0];
    "8": [0, 1];
    "9": [1, 1];
  };
  "3": {
    "0": [3, 0];
    "1": [4, 0];
    "2": [5, 0];
    "3": [6, 0];
    "4": [7, 0];
    "5": [8, 0];
    "6": [9, 0];
    "7": [0, 1];
    "8": [1, 1];
    "9": [2, 1];
  };
  "4": {
    "0": [4, 0];
    "1": [5, 0];
    "2": [6, 0];
    "3": [7, 0];
    "4": [8, 0];
    "5": [9, 0];
    "6": [0, 1];
    "7": [1, 1];
    "8": [2, 1];
    "9": [3, 1];
  };
  "5": {
    "0": [5, 0];
    "1": [6, 0];
    "2": [7, 0];
    "3": [8, 0];
    "4": [9, 0];
    "5": [0, 1];
    "6": [1, 1];
    "7": [2, 1];
    "8": [3, 1];
    "9": [4, 1];
  };
  "6": {
    "0": [6, 0];
    "1": [7, 0];
    "2": [8, 0];
    "3": [9, 0];
    "4": [0, 1];
    "5": [1, 1];
    "6": [2, 1];
    "7": [3, 1];
    "8": [4, 1];
    "9": [5, 1];
  };
  "7": {
    "0": [7, 0];
    "1": [8, 0];
    "2": [9, 0];
    "3": [0, 1];
    "4": [1, 1];
    "5": [2, 1];
    "6": [3, 1];
    "7": [4, 1];
    "8": [5, 1];
    "9": [6, 1];
  };
  "8": {
    "0": [8, 0];
    "1": [9, 0];
    "2": [0, 1];
    "3": [1, 1];
    "4": [2, 1];
    "5": [3, 1];
    "6": [4, 1];
    "7": [5, 1];
    "8": [6, 1];
    "9": [7, 1];
  };
  "9": {
    "0": [9, 0];
    "1": [0, 1];
    "2": [1, 1];
    "3": [2, 1];
    "4": [3, 1];
    "5": [4, 1];
    "6": [5, 1];
    "7": [6, 1];
    "8": [7, 1];
    "9": [8, 1];
  };
};
type Digit = `${[0, 1, 2, 3, 4, 5, 6, 7, 8, 9][number]}`;

type ReverseJoin<S extends string[]> = S extends [
  infer Head extends string,
  ...infer Tail extends string[]
]
  ? `${ReverseJoin<Tail>}${Head}`
  : "";

type _Plus<
  A1 extends string[],
  A2 extends string[],
  R extends string = ""
> = A1 extends [infer A1H extends Digit, ...infer A1T extends any[] | []]
  ? A2 extends [infer A2H extends Digit, ...infer A2T extends any[] | []]
    ? PlusMap[A1H][A2H] extends [infer DigitResult extends number, infer Carry]
      ? _Plus<
          A1T,
          Carry extends 0 ? A2T : AsReverseArray<_Plus<A2T, ["1"]>>,
          `${DigitResult}${R}`
        >
      : never
    : `${ReverseJoin<A1>}${R}`
  : `${ReverseJoin<A2>}${R}`;

type Plus<A1 extends string, A2 extends string> = _Plus<
  AsReverseArray<A1>,
  AsReverseArray<A2>
>;

type Bit = "0" | "1";
type _BinaryToDecimal<
  LSB extends string[],
  P extends string = "1",
  R extends string = "0"
> = LSB extends [infer B extends Bit, ...infer Rest extends Bit[]]
  ? _BinaryToDecimal<Rest, Plus<P, P>, B extends "0" ? R : Plus<R, P>>
  : R;

type AsReverseArray<S extends string> = S extends ""
  ? []
  : S extends `${infer Head}${infer Tail}`
  ? [...AsReverseArray<Tail>, Head]
  : [S];

type BinaryToDecimal<S extends string> = _BinaryToDecimal<
  AsReverseArray<S>
> extends `${infer N extends number}`
  ? N
  : never;

Solution by dexmo007 #26247 

/**
 * 主要难点在于通过元组实现基础的加减乘法以及求幂
 */
type Num2Array<N extends number, Res extends unknown[] = []> = Res['length'] extends N ? Res : Num2Array<N, [...Res, unknown]>

type Subtract<M extends number, N extends number, L extends unknown[] = Num2Array<M>, R extends unknown[] = Num2Array<N>> =
    L extends [infer CurL, ...infer RestL] ? R extends [infer CurR, ...infer RestR] ? Subtract<M, N, RestL, RestR> : L['length'] :
    R extends [infer CurR, ...infer RestR] ? R['length'] : 0

type Add<M extends number, N extends number> = [...Num2Array<M>, ...Num2Array<N>]['length']

type Multiply<M extends number, N extends number, Arr extends unknown[] = Num2Array<N>, Res extends number = 0> =
    Arr extends [infer Cur, ...infer Rest] ? Multiply<M, N, Rest, Add<Res, M> & number> : Res

type Pow<M extends number, N extends number, Arr extends unknown[] = Num2Array<N>, Res extends number = 1> =
    Arr extends [infer Cyr, ...infer Rest] ? Pow<M, N, Rest, Multiply<Res, M>> : Res

type Str2Tuple<S extends string, T extends number[] = []> =
    S extends `${infer Cur extends number}${infer Rest}` ? Str2Tuple<Rest, [...T, Cur]> : T

type BinaryToDecimal<S extends string, Arr extends number[] = Str2Tuple<S>, Len extends number = Arr['length'], Index extends number = 0> =
    Arr extends [infer Cur extends number, ...infer Rest extends number[]] ?
    Add<Multiply<Cur, Pow<2, Subtract<Subtract<Len, 1>, Index>>>, BinaryToDecimal<S, Rest, Len, Add<Index, 1> & number>>
    : 0

type test = BinaryToDecimal<'0000001111'>

Solution by zhuizhui0429 #25913 

// your answers
// step1: 将字符串转换为tuple ，为了能够使用 ... 操作符控制 infer 的位置
type StringToTuple<S extends string> = S extends `${infer F}${infer R}`
  ? [F, ...StringToTuple<R>]
  : []

// 用 res 存储最终的计算结果， arr 存储 1，2，4，8，16，遇到1，则将 Arr 长度加入 res 
type Convert<T extends string[], Arr extends number[] = [1], Res extends number[] = []> =
  T extends [...infer F extends string[], infer L]
  ? L extends '1'
    ? Convert<F, [...Arr, ...Arr], [...Res, ...Arr]>
    : Convert<F, [...Arr, ...Arr], Res>
  : Res['length'];

type BinaryToDecimal<S extends string> = Convert<StringToTuple<S>>

Solution by yuzai #25878 

/**2的N次方 */
type BinSquareCounter<N extends number, _Counter extends 1[] = [], _Result extends 1[] = [1]> =
  _Counter[`length`] extends N ? _Result/*return*/ :
  BinSquareCounter<N, [..._Counter, 1], [..._Result, ..._Result]>;
type ReverseString<T extends string> = T extends `${infer F}${infer R}` ? `${ReverseString<R>}${F}` : ``;

type BinaryToDecimal<S extends string, _DecimalCounter extends 1[] = [], _Counter extends 1[] = [], _Reverse = ReverseString<S>> =
  _Reverse extends `${infer F}${infer R}` ? BinaryToDecimal<S, F extends `1` ? [..._DecimalCounter, ...BinSquareCounter<_Counter[`length`]>]/*Sum*/ : _DecimalCounter, [..._Counter, 1], R> :
  _DecimalCounter[`length`]/*return*/;

// old way
// /**制造数，最大999 */
// type MakeCounter<T extends number, _Result extends any[] = []> = _Result[`length`] extends (T | 999) ? _Result : MakeCounter<T, [..._Result, 1]>;
// /**加法 */
// type SimpleAdd<T extends number, U extends number> = [...MakeCounter<T>, ...MakeCounter<U>][`length`];
// /**2进制位值 */
// type Bin = [1, 2, 4, 8, 16, 32, 64, 128];
// /**转2进制位数组 */
// type ToBinArray<T extends string, _Result extends string[] = []> = _Result[`length`] extends 8 ?  //限制8位
//   _Result :
//   (T extends `${infer F}${infer R}` ?
//     ToBinArray<R, [..._Result, F]> :
//     ToBinArray<``, [`0`, ..._Result]>);   //补0
/**2进制位数组转位值数组 */
// type ParseToDecimal<T extends `${1 | 0}`[]> = T extends [infer F, ...infer R extends any[]] ? [F extends `1` ? Bin[R[`length`]/*index*/] : 0, ...ParseToDecimal<R>] : [];
// /**求和 */
// type Sum<T extends number[]> = T extends [infer F extends number, ...infer R extends number[]] ? SimpleAdd<F, Sum<R>> : 0;
// /**8位非空2进制 */
// type Bin8Bit = `${1 | 0 | ``}${1 | 0 | ``}${1 | 0 | ``}${1 | 0 | ``}${1 | 0 | ``}${1 | 0 | ``}${1 | 0 | ``}${1 | 0}`;

// type BinaryToDecimal<S extends Bin8Bit> = Sum<ParseToDecimal<ToBinArray<S>>>;    //10101010 ==> [1, 0, 1, 0, 1, 0, 1, 0] ==> [128, 0, 32, 0, 8, 0, 2, 0] ==> 128+32+8+2 = 170

Solution by E-uler #25010 

type BinaryToDecimal<S extends string, Acc extends unknown[] = []> = S extends `${infer First}${infer Rest}`
? First extends '1'
  ? BinaryToDecimal<Rest, [...Acc, ...Acc, '']>
  : BinaryToDecimal<Rest, [...Acc, ...Acc]>
: Acc['length']

Solution by NeylonR #24534 

// your answers
type BinaryToDecimal<S extends string, R extends number[] = []> =
  S extends `${infer F}${infer Rest}`
  ? BinaryToDecimal<Rest, [...(F extends '1' ? [1] : []),...R,...R]>
  : R['length']

Solution by jxhhdx #24382 

// your answers
type BinaryToDecimal<S extends string, R extends number[] = []> =
  S extends `${infer F}${infer Rest}`
  ? BinaryToDecimal<Rest, [...(F extends '1' ? [1] : []),...R,...R]>
  : R['length']

Solution by snakeUni #24033 

// Works up to 9999 -> '10011100001111' maximum tuple length.
namespace TupleMath {
  type Inc<T extends unknown[]> = Add<T, [0]>;
  type Subtract<T extends unknown[], U extends unknown[]> = T extends [...U, ...infer Rest] ? Rest : [];
  type Double<T extends unknown[]> = [...T, ...T];
  type StringLength<T extends string, C extends unknown[]=[]> = T extends `${any}${infer Rest}` ?
  StringLength<Rest, [...C, 0]> : C;
  type Add<T extends unknown[], U extends unknown[]> = [...T, ...U];
  type PowerOf2<T extends unknown[], C extends unknown[]=[],
   Sub extends unknown[]=Subtract<T,C>> = Sub['length'] extends 0 ? [0] : Sub['length'] extends 1 ?
  [0,0] : Double<PowerOf2<T, Inc<C>>>;
  export type BinaryToDecimal<S extends string> = S extends `${infer F}${infer Rest}` ? Add<F extends '1' ? 
  PowerOf2<StringLength<Rest>>
 : [], BinaryToDecimal<Rest>>: [];
}

type BinaryToDecimal<S extends string> = TupleMath.BinaryToDecimal<S>['length'];

Solution by Karamuto #22220 

type DoubleTuple<T extends unknown[]> = [...T, ...T]

type CalcPureBinary<R extends string> = 
  R extends `${any}${infer Rest}`
  ? DoubleTuple<CalcPureBinary<Rest>>
  : [unknown]

type BinaryToDecimalTupleResult<S extends string> = 
  S extends `${infer First}${infer Rest}`
  ? First extends '1'
    ? [...CalcPureBinary<Rest>, ...BinaryToDecimalTupleResult<Rest>]
    : BinaryToDecimalTupleResult<Rest>
  : []

type BinaryToDecimal<S extends string> = BinaryToDecimalTupleResult<S>['length']

playground

Solution by zhaoyao91 #21989 

// your answers
type BinaryToDecimal<S extends string, R extends number[] = []> =
  S extends `${infer F}${infer Rest}`
  ? BinaryToDecimal<Rest, [...(F extends '1' ? [1] : []),...R,...R]>
  : R['length']

Solution by YqxLzx #21735 

// your answers
type BinaryToDecimal<
  str,
  arr extends unknown[] = []
> = str extends `${infer f}${infer r}`
  ? f extends "1"
    ? BinaryToDecimal<r, [...arr, ...arr, 1]>
    : BinaryToDecimal<r, [...arr, ...arr]>
  : arr["length"];

Solution by fengjinlong #20364 

type BinaryToDecimal<
  S extends string,
  R extends unknown[] = []
> = S extends `${infer A}${infer B}`
  ? A extends '1'
    ? BinaryToDecimal<B, [...R, ...R, unknown]>
    : BinaryToDecimal<B, [...R, ...R]>
  : R['length']

Solution by theoolee #19754 

type NumberToArray<T extends number, R extends 1[] = []> = R['length'] extends T ? R : NumberToArray<T, [...R, 1]>;

type GetTwice<T extends unknown[]> = [...T, ...T];

type BinaryToDecimal<S extends string, Result extends unknown[] = []> = S extends `${infer F extends number}${infer R}`
  ? BinaryToDecimal<R, [...GetTwice<Result>, ...NumberToArray<F>]>
  : Result['length'];

Solution by CaoXueLiang #19489 

type Double<T extends any[], Inc> = Inc extends '0' ? [...T, ...T] : [...T, ...T, any];
type BinaryToDecimal<S extends string, Count extends any[] = []> =
  S extends `${infer F}${infer R}`
  ? BinaryToDecimal<R, Double<Count, F>>
  : Count['length'];

Solution by BulatDashiev #16960

type ArrayX2<T extends any[]> = T['length'] extends 1 ? [0] : T['length'] extends 2 ? [0, 0] : T extends [...infer Rest, infer L] ? [...ArrayX2, ...ArrayX2] : never;

type BinaryToDecimal<T extends string, N extends 0[] = [0], R extends 0[] = []> = ReverseString extends ${infer K}${infer Rest} ? K extends '1' ? BinaryToDecimal<ReverseString, [...N, 0], [...R, ...ArrayX2]> : BinaryToDecimal<ReverseString, [...N, 0], R> : R['length'];

Solution by my5201314zwl #16884 

// your answers

type NumberToArray<N extends number, Result extends 0[] = []> = Result['length'] extends N
  ? Result
  : NumberToArray<N, [...Result, 0]>

type GetTwice<T extends unknown[]> = [
  ...T, ...T
]

type BinaryToDecimal<S extends string, Result extends unknown[] = []> = S extends `${infer F extends number}${infer R}`
  ? BinaryToDecimal<R, [...GetTwice<Result>, ...NumberToArray<F>]>
  : Result['length']

Solution by humandetail #16497 

// your answers
type Dictionary =
{
  '0':[],
  '1':[0],
} ;
type _2=[0,0] ;

type ReverseString<
    S extends string > =
    S extends `${infer R extends string}${infer U extends string}`
    ? `${ReverseString<U>}${R}`
    : ''  ;

type Multyply<
    A extends any[],
    B extends any[]> =
    A extends [any,...infer U]
    ? [...B,...Multyply<U,B>]
    : []  ;

type ReverseStringToTuple
    <S extends string> =
    S extends `${infer R extends keyof Dictionary}${infer U extends string}`
    ? [...Dictionary[R],...Multyply<_2,ReverseStringToTuple<U>>]
    : []  ;

type BinaryToDecimal<
    S extends string> = 
    ReverseStringToTuple<ReverseString<S>>['length']  ;

Solution by justBadProgrammer #16003 

// your answers
type BinaryToDecimal<
    T extends string,
    U extends any[] = []
> = T extends `${infer K}${infer R}`
    ? K extends '1'
        ? BinaryToDecimal<R, [...U, ...U, unknown]>
        : BinaryToDecimal<R, [...U, ...U]>
    : U['length']

Solution by huangyuanjin #15336 

// your answers
type BinaryToDecimal<S extends string, Cur extends unknown[] = [unknown], Res extends unknown[] = []> = S extends `${infer R1}0`
  ? BinaryToDecimal<R1, [...Cur, ...Cur], Res>
  : S extends `${infer R2}1`
  ? BinaryToDecimal<R2, [...Cur, ...Cur], [...Res, ...Cur]>
  : Res['length']

Solution by fengchunqi #14574 

type Multiply2Add<T extends 1[]> = {
  '0': [...T, ...T]
  '1': [...T, ...T, 1]
}

type BinaryToDecimal<
  S extends string,
  Arr extends 1[] = []
> = S extends `${infer F}${infer R}`
  ? BinaryToDecimal<R, Multiply2Add<Arr>[F & ('0' | '1')]>
  : Arr['length']

Same way can be used in converting decimal string to number. Just rewrite Multiply2Add could work

Solution by yukinotech #14346 

// your answers
type BinaryToDecimal<S extends string, R extends unknown[] = []> =
  S extends `${infer First}${infer Rest}`
  ? BinaryToDecimal<Rest, [...(First extends '1' ? [unknown] : []),...R, ...R]>
  : R['length']

Solution by liuxing95 #13156 

type BinaryToDecimal<S extends string, Result extends number = 0> =
  S extends `${infer First extends 0 | 1}${infer Rest}`
    ? BinaryToDecimal<Rest, First extends 1 ? PlusOne<Double<Result>> : Double<Result>>
  : Result

type PlusOne<S extends number, Result extends string = '', Digits extends number[] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]>
  = `${S}` extends `${infer Lead extends number}9` ? PlusOne<Lead, `0${Result}`>
  : {[Digit in keyof Digits & `${number}`]: `${S}` extends `${infer Lead}${Digit}`
    ? `${Lead}${Digits[Digit]}${Result}` extends `${infer Num extends number}` ? Num : never : never
    }[keyof Digits & `${number}`]

type Double<S extends number, Carry extends number = 0, Result extends string = '', Digits extends number[] = Carry extends 1 ? [1, 3, 5, 7, 9, 1, 3, 5, 7, 9] : [0, 2, 4, 6, 8, 0, 2, 4, 6, 8], C extends number[] = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]>
  = {[Digit in keyof Digits & `${number}`]: `${S}` extends `${infer Lead extends number}${Digit}` ? Double<Lead, C[Digit & keyof C], `${Digits[Digit]}${Result}`>
    : `${C[S] extends 1 ? 1 : ''}${Digits[S]}${Result}` extends `${infer N extends number}` ? N : never
    }[keyof Digits & `${number}`]

Playground

Solution by teamchong #11754 

// your answers
type Helper<S, A extends number[]> =
  S extends '1' 
    ? [...A, ...A, 0]
    : [...A, ...A]

type BinaryToDecimal<S extends string, A extends number[] = []> = 
  S extends `${infer first}${infer rest}`
    ? BinaryToDecimal<rest, Helper<first, A>>
    : A['length']

Solution by TonyGoods #11627 

type BinaryToDecimal<S extends string, A extends any[] = []> = S extends `${infer F}${infer R}`
  ? BinaryToDecimal<R, [...A, ...A, ...F extends '0' ? [] : [1]]> : A['length']

Solution by wqs576222103 #11604 

type GetNum<N extends number, CurIndex extends any[] = [], Temp extends any[] = [0]>
    = N extends CurIndex['length']
    ? Temp['length']
    : GetNum<N, [...CurIndex, unknown], [...Temp, ...Temp]>

type CreateArr<T extends number, Res extends any[] = []>
    = `${T}` extends `${Res['length']}`
    ? Res
    : CreateArr<T, [...Res, unknown]>


type SplitString<S extends string, Res extends any[] = []>
    = S extends `${infer Start}${infer End}`
    ? SplitString<End, [...Res, Start]>
    : Res

type BinaryArr<S extends string, Res extends any[] = [], CurIndex extends any[] = [], Arr extends any[] = SplitString<S>>
    = Arr extends [...infer Start, infer End]
    ? End extends '1'
    ? BinaryArr<S, [...Res, GetNum<CurIndex['length']>], [...CurIndex, unknown], Start>
    : BinaryArr<S, [...Res], [...CurIndex, unknown], Start>
    : Res

type BinaryToDecimal<S extends string, Arr extends any[] = BinaryArr<S>, Res extends any[] = []> =
    Arr extends [infer Start, ...infer End]
    ? BinaryToDecimal<S, End, [...Res, ...CreateArr<Start & number>]>
    : Res['length']

Solution by EGyoung #8574 

// your answers
type BinaryToDecimal<S extends string, R extends any[] = []> = S extends `${infer F}${infer L}` ? BinaryToDecimal<L, [...R, ...R, ...(F extends '1' ? [any] : [])]> : R['length'];

Solution by venusliang #8135 

type ExpandTwo<T extends any[]> = [...T, ...T]

type BinaryToDecimal<S extends string, R extends any[] = []> = S extends `${infer L}${infer Rest}`
? L extends '0'
  ? BinaryToDecimal<Rest, ExpandTwo<R>>
  : BinaryToDecimal<Rest, [...ExpandTwo<R>, 0]>
: R['length']

Solution by ch3cknull #6985