32
\$\begingroup\$

The goal of this challenge is to generalise the bitwise XOR function to other bases. Given two non-negative integers \$ x \$ and \$ y \$, and another integer \$ b \$ such that \$ b \geq 2 \$, write a program/function which computes the generalised XOR, described the following algorithm:

  1. First, find the base \$ b \$ representation of \$ x \$ and \$ y \$. For example, if \$ b = 30 \$ and \$ x = 2712 \$, then the digits for \$ x \$ would be \$ [3, 0, 12] \$. If \$ y = 403 \$, then the digits for \$ y \$ would be \$ [13, 13] \$.

  2. Next, pairwise match each digit in \$ x \$ with its corresponding digit in \$ y \$. Following on from the previous example, for \$ b^0 \$ we have \$ 12 \$ and \$ 13 \$, for \$ b^1 \$ we have \$ 0 \$ and \$ 13 \$, and for \$ b^2 \$ we have \$ 3 \$ and \$ 0 \$.

  3. Let \$ p \$ and \$ q \$ be one of the pairs of digits. The corresponding digit in the output will be equal to \$ -(p + q) \bmod b \$, where \$ \bmod \$ is the modulo function in the usual sense (so \$ -1 \bmod 4 = 3 \$). Accordingly, the output digit for \$ b^0 \$ is \$ 5 \$, the next digit is \$ 17 \$, and the final is \$ 27 \$. Combining the output digits and converting that back to an integer, the required output is \$ 5 \cdot 30^0 + 17 \cdot 30^1 + 27 \cdot 30^2 = 24815 \$.

This definition retains many of the familiar properties of XOR, including that \$ x \oplus_b y = y \oplus_b x \$ and \$ x \oplus_b y \oplus_b x = y \$, and when \$ b = 2 \$ the function behaves identically to the usual bitwise XOR.

This challenge is , so the shortest code in bytes wins. You may not accept/output digit arrays of base \$ b \$, and your code should work in theory for all bases, and not be limited by builtin base conversion which limit your program/function from working for say \$ b > 36 \$. However, assuming that your integer data type width is sufficiently large is fine.

Test cases

Formatted as x, y, b => output

2712, 403, 30   => 24815
24815, 2712, 30 => 403
27, 14, 2       => 21
415, 555, 10    => 140
0, 10, 10       => 90
10, 0, 10       => 90
52, 52, 10      => 6
42, 68, 10      => 0
1146, 660, 42   => 0
\$\endgroup\$
3
  • 6
    \$\begingroup\$ Welcome to Code Golf! (Usually I put links and stuff here but there's no need, looks like you did everything right :p) \$\endgroup\$ Jun 1 at 4:13
  • 4
    \$\begingroup\$ Also, the explanations were particularly clear and easy to read. \$\endgroup\$
    – Jonah
    Jun 1 at 5:25
  • 3
    \$\begingroup\$ Welcome to Code Golf and nice first question! For future reference, we recommend using the Sandbox to get feedback on challenge ideas before posting them to main. Otherwise, as other users have said, this is an excellent first challenge (these are just the "links and stuff" Redwolf mentioned :P)! \$\endgroup\$ Jun 1 at 13:27

15 Answers 15

8
\$\begingroup\$

Jelly, 7 bytes

bUSN%Uḅ

Try it online!

-3 byte thanks to Unrelated String

bUSN%Uḅ  Main link; take [x, y] on the left and b on the right
b        Convert x and y to base b
 U       Upend; reverse each of x and y's digits
  S      Sum; vectorizes
   N     Negate
    %    Modulo with b
     U   Upend; reverse the digits
      ḅ  Convert from base b

The double reverse is necessary such that the digits line up on the correct side should one digit list be shorter than the other.

Almost all ASCII!

\$\endgroup\$
6
  • \$\begingroup\$ I don't think you need the ¹ \$\endgroup\$ Jun 1 at 3:57
  • \$\begingroup\$ @UnrelatedString Oh yeah, I forgot to remove that when I inserted the reverse monad, which broke the 2,2 link. Thanks. \$\endgroup\$
    – hyper-neutrino
    Jun 1 at 3:57
  • 1
    \$\begingroup\$ @UnrelatedString Oh yeah, sum does that >_> \$\endgroup\$
    – hyper-neutrino
    Jun 1 at 3:58
  • 2
    \$\begingroup\$ So U was used (twice!) because we need to align the two numbers. Yet another reason to have a little-endian base conversion built-in. \$\endgroup\$
    – Bubbler
    Jun 1 at 4:04
  • 1
    \$\begingroup\$ haha jelly bUS goes brrr \$\endgroup\$
    – lyxal
    Jun 1 at 4:13
6
\$\begingroup\$

Vyxal, 14 13 11 bytes

vτR÷+N⁰%Ṙ⁰β

Try it Online!

Takes [x, y] and b and outputs the result.

-1 thanks to the power of vectorisation

and -2 thanks to porting Jelly

Explained (old)

vτR÷Zv∑N⁰%Ṙ⁰β
vτ             # Convert x and y to base b
  R            # reverse each result
   ÷Z          # zip the digits
               # to each pair of digits ([p, q]):
     v∑N       #     -(p + q)
        ⁰%     #     % b
          Ṙ    # reverse the result of the above map and
           ⁰β  # convert it from base b to base 10
\$\endgroup\$
1
  • \$\begingroup\$ Instead of zip and modified XOR each, could you use a similar trick to Unrelated String's golf on my Jelly answer and use vectorized sum and then negate and then mod? \$\endgroup\$
    – hyper-neutrino
    Jun 1 at 3:59
6
\$\begingroup\$

Python 2, 45 bytes

f=lambda b,x,y:x+y and-(x+y)%b+f(b,x/b,y/b)*b

Try it online!

The \$\text{div}\$ and \$\text{mod}\$ operator in Python 2 work much better than JavaScript in this challenge...

\$\endgroup\$
5
\$\begingroup\$

J, 16 bytes

[#.[|[:-@+/#.inv

Try it online!

Just a straight translation of the algorithm:

  • #.inv Convert to base b
  • [:-@+/ Negative of elementwise sum
  • [| Mod by b
  • [#. Convert back to decimal
\$\endgroup\$
5
\$\begingroup\$

C (gcc), 65 47 45 bytes

No bytes added or saved but thanks for a bug fix by Chris Bouchard!!!

f(x,y,b){x=x+y?~-b*(x+y)%b+b*f(x/b,y/b,b):0;}

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Does this work if (x%b+y%b) > b? E.g., if b is 4 and x and y are both 3? Because then you'd have (4 - 3 - 3) < 0. \$\endgroup\$ Jun 2 at 1:06
  • 2
    \$\begingroup\$ I think you could use (b-1)*(x+y)%b without gaining any bytes. \$\endgroup\$ Jun 2 at 1:21
  • \$\begingroup\$ @ChrisBouchard Well spotted and thanks for the fix! :D \$\endgroup\$
    – Noodle9
    Jun 2 at 22:17
4
\$\begingroup\$

Ruby, 42 bytes

f=->x,y,b{x+y<1?0:(-x-y)%b+b*f[x/b,y/b,b]}

Try it online!

\$\endgroup\$
4
\$\begingroup\$

R, 57 53 bytes

f=function(x,b)"if"(any(x),-sum(x)%%b+f(x%/%b,b)*b,0)

Try it online!

Using @tsh's recursive approach, taking input as [x, y], b.


Straightforward, taking input as [x, y], b:

R, 69 65 64 bytes

function(x,b,n=b^(0:max(0,log(x,b))))-(x[1]%/%n+x[2]%/%n)%%b%*%n

Try it online!

\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Extended), 10 bytes

Basically a translation of Jonah's J solution.

Tacit infix function. Takes \$b\$ as left argument and \$\{x,y\}\$ as right argument.

⊣⊥⊣|∘-+/⍤⊤

Try it online!

⍤⊤ convert \$\{x,y\}\$ to base \$b\$, one digit-value per row, padding with leading zeros if needed, then:

+/ sum each row

∘- negate those sums, then:

⊣| find the remainder when dividing by \$b\$

⊣⊥ evaluate in base \$b\$

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 11 bytes

Last 5 bytes very similar to the Vyxal answer ;)

вí0ζO(¹%R¹β

Try it online!

в            # convert [x, y] to base b; this results in a list of two lists of digits
 í           # reverse each digit list
  0ζ         # zip with 0 as filler
    O        # sum each pair of digits
     (       # negate all sums
      ¹%     # modulo b
        R    # reverse the resulting base-b digits
         ¹β  # convert from base b
\$\endgroup\$
3
\$\begingroup\$

Red, 78 bytes

f: func[x y b][either x + y = 0[0][(b * f x / b y / b b)-(x + y % b - b % b)]]

Try it online!

My first humble attempt at golfing in Red. This is is the common recursive approach to the problem, but involves a few extra steps in the calculation of the output "digit" because the operators behave quite inconveniently for this task: % is remainder, not modulus, while unary minus seems to work only in literals. So, we would need to use verbose function names negate and modulo, but the shown approach saves a few bytes over that.

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 44 bytes

  • -1 byte by applying a crazy bit-wise expression as suggested by Arnauld.
b=>g=(x,y)=>(s=~-x-~y)&&s*~-b%b+g(x/b,y/b)*b

Try it online!

\$\endgroup\$
1
1
\$\begingroup\$

Japt, 17 bytes

Ouch!

®ìV ÔÃÕ®xn uVÃÔìV

Try it

®ìV ÔÃÕ®xn uVÃÔìV     :Implicit input of array U=[x,y] and integer V=b
®                     :Map U
 ìV                   :  Convert to base V digit array
    Ô                 :  Reverse
     Ã                :End map
      Õ               :Transpose
       ®              :Map
        x             :  Reduce by addition
         n            :  After negating each
           uV         :  Mod V  
             Ã        :End map
              ìV      :Convert from base V digit array
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 18 bytes

I↨⮌E↨Σθη﹪±Σ÷θXηκηη

Try it online! Link is to verbose version of code. Takes input in the form [[x, y], b]. Explanation:

      θ             List `[x, y]`
     Σ              Take the sum
    ↨  η            Convert to base `b`
   E                Map over digits
            θ       List `[x, y]`
           ÷        Vectorised integer divide by
              η     `b`
             X      Raised to power
               κ    Current index
          Σ         Summed
         ±          Negated
        ﹪       η   Reduced modulo `b`
  ⮌                 Reversed
 ↨                η  Convert from base `b`
I                    Cast to string
                     Implicitly print
\$\endgroup\$
1
\$\begingroup\$

Core Maude, 155 bytes

mod X is pr INT . vars B X Y : Nat . op f : Nat Nat Nat -> Nat . eq f(0,0,B)=
0 . eq f(X,Y,B)= B * f(X quo B,Y quo B,B)+((B - 1)*(X + Y))rem B[owise]. endm

The answer is obtained by reducing the function f, which takes x, y, and b.

Example Session

             \||||||||||||||||||/
           --- Welcome to Maude ---
             /||||||||||||||||||\
         Maude 3.1 built: Oct 12 2020 20:12:31
         Copyright 1997-2020 SRI International
           Tue Jun  1 20:59:00 2021
Maude> mod X is pr INT . vars B X Y : Nat . op f : Nat Nat Nat -> Nat . eq f(0,0,B)=
> 0 . eq f(X,Y,B)= B * f(X quo B,Y quo B,B)+((B - 1)*(X + Y))rem B[owise]. endm
Maude> red f(2712, 403, 30) .
reduce in X : f(2712, 403, 30) .
rewrites: 28 in 0ms cpu (0ms real) (~ rewrites/second)
result NzNat: 24815
Maude> red f(24815, 2712, 30) .
reduce in X : f(24815, 2712, 30) .
rewrites: 28 in 0ms cpu (0ms real) (~ rewrites/second)
result NzNat: 403
Maude> red f(27, 14, 2) .
reduce in X : f(27, 14, 2) .
rewrites: 46 in 0ms cpu (0ms real) (~ rewrites/second)
result NzNat: 21
Maude> red f(415, 555, 10) .
reduce in X : f(415, 555, 10) .
rewrites: 28 in 0ms cpu (0ms real) (~ rewrites/second)
result NzNat: 140
Maude> red f(0, 10, 10) .
reduce in X : f(0, 10, 10) .
rewrites: 19 in 0ms cpu (0ms real) (~ rewrites/second)
result NzNat: 90
Maude> red f(10, 0, 10) .
reduce in X : f(10, 0, 10) .
rewrites: 19 in 0ms cpu (0ms real) (~ rewrites/second)
result NzNat: 90
Maude> red f(52, 52, 10) .
reduce in X : f(52, 52, 10) .
rewrites: 19 in 0ms cpu (0ms real) (~ rewrites/second)
result NzNat: 6
Maude> red f(42, 68, 10) .
reduce in X : f(42, 68, 10) .
rewrites: 19 in 0ms cpu (0ms real) (~ rewrites/second)
result Zero: 0
Maude> red f(1146, 660, 42) .
reduce in X : f(1146, 660, 42) .
rewrites: 19 in 0ms cpu (0ms real) (~ rewrites/second)
result Zero: 0

Ungolfed

mod X is
    pr INT .

    vars B X Y : Nat .

    op f : Nat Nat Nat -> Nat .
    eq f(0, 0, B) = 0 .
    eq f(X, Y, B) =
        B * f(X quo B, Y quo B, B)
            + ((B - 1) * (X + Y)) rem B [owise] .
endm
\$\endgroup\$
1
\$\begingroup\$

Pip, 29 23 bytes

{Y-$+ay&y%b+b*(fa//bb)}

Stretching the input format a bit, this submission is function that takes two arguments: a two-element list containing \$x\$ and \$y\$, and an integer \$b\$. Try it online!

Explanation

Recursive function idea borrowed from tsh's Python answer.

{                     }  A function:
  -$+a                    Negated sum of the first argument (the list of two numbers)
 Y                        Yank that value into y
      y&                  If y is 0 (falsey), return 0; otherwise, return:
        y%b                Negated sum modulo the second argument (the base)
           +               Plus
            b*             The base, times
              (f     )     A recursive call
                a//b       with the two numbers int-divided by the base
                    b      and the same base as before
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.