Type Challenges: 30575-hard-bitwisexor Solution

type BitwiseXOR<A extends string, B extends string, X extends string = ''>
  = `${A}^${B}` extends `${infer C}1^${infer D}0` | `${infer C}0^${infer D}1` ? BitwiseXOR<C, D, `1${X}`>
  : `${A}^${B}` extends `${infer C}1^${infer D}1` | `${infer C}0^${infer D}0` ? BitwiseXOR<C, D, `0${X}`>
  : `${A}${B}${X}`

Playground

Solution by teamchong #32992

type BitwiseXOR<S1 extends string, S2 extends string> = ReverseString<
  Xor<ReverseString<S1>, ReverseString<S2>>
>;

type ReverseString<S extends string> = S extends `${infer Char}${infer Others}`
  ? `${ReverseString<Others>}${Char}`
  : "";
  
type Xor<
  S1 extends string,
  S2 extends string
> = S1 extends `${infer L}${infer Others}`
  ? S2 extends `${infer L1}${infer Others1}`
    ? L extends L1
      ? `0${Xor<Others, Others1>}`
      : `1${Xor<Others, Others1>}`
    : `1${Xor<Others, "">}`
  : S2 extends `${infer L1}${infer Others1}`
  ? `1${Xor<"", Others1>}`
  : "";

Solution by Vampirelee #32716

type Reverse<S extends string> = S extends `${infer First}${infer Rest}` ? `${Reverse<Rest>}${First}` : ''

type GetLastAndRest<S extends string, _S extends string = Reverse<S>>
  = _S extends `${infer Last extends string}${infer Rest extends string}`
    ? { Last: Last, Rest: Reverse<Rest> }
    : { Last: '', Rest: '' }

type XOR<S1 extends string, S2 extends string> = S1 extends S2 ? '0' : '1'

type BitwiseXOR<
  S1 extends string,
  S2 extends string,
  _S1 extends { Last: string, Rest: string } = GetLastAndRest<S1>,
  _S2 extends { Last: string, Rest: string } = GetLastAndRest<S2>
> = `${ _S1['Rest'] }${ _S2['Rest'] }` extends ''
    ? `${XOR<_S1['Last'], _S2['Last']>}`
    : `${BitwiseXOR<_S1['Rest'], _S2['Rest']>}${XOR<_S1['Last'], _S2['Last']>}`

Solution by lvjiaxuan #32481

type ReverseString<S extends string> = S extends `${infer First}${infer Rest}`
  ? `${ReverseString<Rest>}${First}`
  : "";
type XOR<T extends string, U extends string> = T extends U ? "0" : "1";
type BitwiseXOR<
  S1 extends string,
  S2 extends string
> = ReverseString<S1> extends `${infer F1}${infer R1}`
  ? ReverseString<S2> extends `${infer F2}${infer R2}`
    ? `${BitwiseXOR<ReverseString<R1>, ReverseString<R2>>}${XOR<F1, F2>}`
    : S1
  : S2;

Solution by vangie #32338

type XORSingle<A extends string, B extends string> = A extends B ?  '0' : '1';
type Revert<S extends string> = S extends `${infer Start}${infer End}` ? `${Revert<End>}${Start}` : '';

type IterateXOR<S1 extends string, S2 extends string> = S1 extends `${infer Start1}${infer End1}` ? 
S2 extends `${infer Start2}${infer End2}` ? `${IterateXOR<End1, End2>}${XORSingle<Start1, Start2>}` : 
S1 : S2 extends `${infer Start2}${infer End2}` ? S2 : '';

type BitwiseXOR<S1 extends string, S2 extends string> = IterateXOR<Revert<S1>, Revert<S2>>;

Solution by Karamuto #31256

type BitwiseXOR<S1 extends string, S2 extends string> = [S1, S2] extends [
  `${infer S1Body}${'0' | '1'}`,
  `${infer S2Body}${'0' | '1'}`,
]
  ? `${BitwiseXOR<S1Body, S2Body>}${[S1, S2] extends
      | [`${string}0`, `${string}0`]
      | [`${string}1`, `${string}1`]
      ? '0'
      : '1'}`
  : `${S1}${S2}`;

Alternative:

type RevertString<S extends string> = S extends `${infer S0}${infer SRest}`
  ? `${RevertString<SRest>}${S0}`
  : '';

type BitwiseXOR<S1 extends string, S2 extends string> = BitwiseXOR.XORReverted<
  RevertString<S1>,
  RevertString<S2>
>;
namespace BitwiseXOR {
  export type XORReverted<S1 extends string, S2 extends string, R extends string = ''> = [
    S1,
    S2,
  ] extends [`${infer S10}${infer S1Rest}`, `${infer S20}${infer S2Rest}`]
    ? XORReverted<S1Rest, S2Rest, `${S10 extends S20 ? '0' : '1'}${R}`>
    : `${RevertString<`${S1}${S2}`>}${R}`;
}

Solution by BOCbMOU #31036

// 解答をここに記入

type ReversedStr<S> = S extends `${infer F}${infer Rest}` ? `${ReversedStr<Rest>}${F}` : ""

type XOR<X, Y> = [X, Y] extends ["0", "0"] | ["1", "1"] ? "0" : "1"

type InnerBitwiseXOR<S1 extends string, S2 extends string> = [S1, S2] extends [`${infer F1}${infer R1}`, `${infer F2}${infer R2}`] ? `${XOR<F1, F2>}${InnerBitwiseXOR<R1, R2>}` : `${S1}${S2}`

type BitwiseXOR<S1 extends string, S2 extends string> = ReversedStr<InnerBitwiseXOR<ReversedStr<S1>, ReversedStr<S2>>>

桁数が S1 と S2 で違う場合にも簡潔に処理をするため、一旦文字列を反転させてから XOR の処理をしていきます。そして、最終結果も反転させることで元に戻します。

type InnerBitwiseXOR<S1 extends string, S2 extends string> = [S1, S2] extends [`${infer F1}${infer R1}`, `${infer F2}${infer R2}`] ? `${XOR<F1, F2>}${InnerBitwiseXOR<R1, R2>}` : `${S1}${S2}`

において、再帰終了条件に単に [S1, S2] extends [${infer F1}${infer R1}, ${infer F2}${infer R2}] の失敗を設定し、 ${S1}${S2} を返すようにしているのは、

S1 の方が桁が少ない場合： [S1, S2] = ["", ("0" | "1" からなる string)]
S2 の方が桁が少ない場合： [S1, S2] = [("0" | "1" からなる string), ""]
両者の桁が同一の場合：[S1, S2] = ["", ""] となるため、残っている方をそのまま返したいだけの今回のケースは単に両者の結合を返せば良いためです。（※残っている方をそのまま返せばいいのは、XOR<X, 0> = X だからです。）

Solution by Kakeru-Miyazaki #30982

type FillZero<S1 extends string, S2 extends string, _Result1 extends string = ``, _Result2 extends string = ``> =
  `` extends S1 & S2 ? [_Result1, _Result2] /*return*/ :
  FillZero<
    S1 extends `${any}${infer R}` ? R : ``,
    S2 extends `${any}${infer R}` ? R : ``,
    S1 extends `${infer F}${any}` ? `${_Result1}${F}` : `0${_Result1}`,
    S2 extends `${infer F}${any}` ? `${_Result2}${F}` : `0${_Result2}`
  >;

type BitwiseXOR<S1 extends string, S2 extends string, _FZS extends [string, string] = FillZero<S1, S2>> =
  _FZS[0] extends `${infer F1}${infer R1}` ?
  _FZS[1] extends `${infer F2}${infer R2}` ?
  `${[F1 & F2] extends [never] ? 1 : 0}${BitwiseXOR<R1, R2, [R1, R2]>}` :
  `` :
  `` /*pop*/;

Solution by E-uler #30980

type BitwiseXOR<S1 extends string, S2 extends string> = 
  S1 extends '' ? S2 : S2 extends '' ? S1 
: S1 extends `${infer P1}0`
   ? S2 extends `${infer P2}0` 
      ? `${BitwiseXOR<P1,P2>}0` 
      : (S2 extends `${infer P2}1` ? `${BitwiseXOR<P1,P2>}1` : never)
: S1 extends `${infer P1}1` 
  ? S2 extends `${infer P2}0` 
    ? `${BitwiseXOR<P1,P2>}1` 
    : (S2 extends `${infer P2}1` ? `${BitwiseXOR<P1,P2>}0` : never)
: never

Solution by genaby #30696

type BitwiseXOR<S1 extends string, S2 extends string> = S1 extends ''
    ? S2
    : S2 extends ''
      ? S1
      : [S1, S2] extends [`${infer Rest1}${'0' | '1'}`, `${infer Rest2}${'0' | '1'}`]
        ? `${BitwiseXOR<Rest1, Rest2>}${XorLowestBit<S1, S2>}`
        : never
type XorLowestBit<S1 extends string, S2 extends string> = [S1, S2] extends [`${any}0`, `${any}1`] | [`${any}1`, `${any}0`] ? '1' : '0'

Solution by Sun79 #30589

type MakePrefix<
  S extends string, 
  P extends string = ''
> = 
  S extends `${string}${infer R}`?
    MakePrefix<R,`${P}0`>
    :P

type Pad<S1 extends string,S2 extends string> = 
  [S1,S2]extends [`${string}${infer RS1}`,`${string}${infer RS2}`]?
    Pad<RS1,RS2>: [MakePrefix<S2>,MakePrefix<S1>]

type _XOR<
  S1 extends string,
  S2 extends string,
  R extends string = ''
> =  
[S1,S2] extends [`${infer F1}${infer R1}`,`${infer F2}${infer R2}`]?
  _XOR<R1,R2,`${R}${F1 extends F2?'0':'1'}`>
  :R


type BitwiseXOR<
  S1 extends string,
  S2 extends string
> = 
  Pad<S1,S2> extends [infer P1 extends string,infer P2 extends string]?
    _XOR<`${P1}${S1}`,`${P2}${S2}`>
    :never

Solution by jiangshanmeta #30577