15
\$\begingroup\$

Description of the problem

Imagine a quarter of an infinite chessboard, as in a square grid, extending up and right, so that you can see the lower left corner. Place a 0 in there. Now for every other cell in position (x,y), you place the smallest non-negative integer that hasn't showed up in the column x or the row y.

It can be shown that the number in position (x, y) is x ^ y, if the rows and columns are 0-indexed and ^ represents bitwise xor.

Task

Given a position (x, y), return the sum of all elements below that position and to the left of that position, inside the square with vertices (0, 0) and (x, y).

The input

Two non-negative integers in any sensible format. Due to the symmetry of the puzzle, you can assume the input is ordered if it helps you in any way.

Output

The sum of all the elements in the square delimited by (0, 0) and (x, y).

Test cases

5, 46 -> 6501
0, 12 -> 78
25, 46 -> 30671
6, 11 -> 510
4, 23 -> 1380
17, 39 -> 14808
5, 27 -> 2300
32, 39 -> 29580
14, 49 -> 18571
0, 15 -> 120
11, 17 -> 1956
30, 49 -> 41755
8, 9 -> 501
7, 43 -> 7632
13, 33 -> 8022
\$\endgroup\$
  • \$\begingroup\$ vaguely related \$\endgroup\$ – RGS Feb 26 at 22:16
  • 2
    \$\begingroup\$ Interesting, I'm curious if there's a bitwise way to express this without summing everything. \$\endgroup\$ – xnor Feb 26 at 22:20
  • \$\begingroup\$ We'll see what you guys come up with :) \$\endgroup\$ – RGS Feb 26 at 22:21
  • 3
    \$\begingroup\$ The main diagonal is A224923. \$\endgroup\$ – Arnauld Feb 26 at 22:56

23 Answers 23

8
\$\begingroup\$

Perl 6, 19 bytes

{sum [X+^] 0 X..@_}

Try it online!

The sum of the bitwise xor between all numbers in the range 0 to all inputs.

|improve this answer|||||
\$\endgroup\$
7
\$\begingroup\$

Python 2, 49 bytes

lambda x,y:sum(k/-~x^k%-~x for k in range(~x*~y))

Try it online!

The usual div-mod trick for iterating over two ranges. Unfortunately, since we want inclusive ranges, we need to raise each input by 1, which we do with -~. Thanks to Bubbler for saving 2 bytes by cancelling the minuses on -~x*-~y.

Python 3 would be a byte longer using //. I tried to use the 3.8 walrus operator to cut down on the -~x repetition, without success.

55 bytes

f=lambda m,n:m|n>0and(m^n)+f(m-1,n)+f(m,n-1)-f(m-1,n-1)

Try it online!

A cute recursion, but unfortunately longer. This doesn't use anything particular about XOR -- this same method can be used to add up any two-variable function over a rectangle. The base case m|n>0 terminates with zero when either m or n becomes negative, or (harmlessly) when both are zero.

This will time out on larger test cases due to the huge degree of recursive branching.

52 bytes

f=lambda m,n,b=1:m|n>0and(m^n)+f(m,n-1)*b+f(m-1,n,0)

Try it online!

A similar shorter recursion. The idea is that we can recursively travel left or down, but once we've gone left, we set to flag b to zero and ignore the results of any further travel down. The result is that we travel to each cell in the rectangle exactly one, like this:

O < O < O < O
            v
O < O < O < O
            v
O < O < O < O

Other ideas

Here are some partial ideas that didn't lead to decent golfs, but maybe someone can make use of them.

The one-dimensional summation (on a half-open range)

w=lambda i,n:sum(i^j for j in range(n))

can be expressed recursively as

w=lambda i,n:i+n and 4*w(i/2,n/2)+n%2*(n^i^1)+n/2

(Python 2 used for floor division.)

We also have an efficient formula

$$f(m-1,n-1) = \sum_{i=0}^{\infty} {\frac{m n - |m \odot 2^{i}||n \odot 2^{i}|}{2} 2^i}$$

where \$ \odot k\$ is the symmetric modulo-\$(2k)\$ operator mapping to the range from \$-k\$ to \$k\$. This summation can be truncated where \$2^i\$ is bigger than the inputs, since further terms will be zero.

|improve this answer|||||
\$\endgroup\$
  • 2
    \$\begingroup\$ -~x*-~y can be ~x*~y. \$\endgroup\$ – Bubbler Feb 27 at 2:51
  • \$\begingroup\$ Also, an attempt to remove some -~s turned out to be 53 bytes. \$\endgroup\$ – Bubbler Feb 27 at 2:53
  • \$\begingroup\$ Good work here! +1 \$\endgroup\$ – RGS Feb 27 at 19:18
4
\$\begingroup\$

Wolfram Language (Mathematica), 28 bytes

Array[BitXor,{##}+1,0,Plus]&

Try it online!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Nice use of the fourth argument! \$\endgroup\$ – Greg Martin Feb 27 at 10:52
  • \$\begingroup\$ Wow, this is incredibly short for a Mathematica submission! +1 \$\endgroup\$ – RGS Feb 27 at 19:20
  • \$\begingroup\$ You can save three bytes by taking a list as input \$\endgroup\$ – Lukas Lang Feb 28 at 14:47
4
\$\begingroup\$

Ruby, 36 bytes

->x,y{(0..y+x*y+=1).sum{|r|r/y^r%y}}

Try it online!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ What is the |r| doing? \$\endgroup\$ – RGS Feb 27 at 19:25
  • 1
    \$\begingroup\$ @RGS It defines the name of the variable which is used inside the block, iterating over every value between 0 and y+x*y+=1. Kind of like for( r = 0; r <= y+x*(y+1); r = r + 1 ){ \$\endgroup\$ – Eric Duminil Feb 28 at 11:26
3
\$\begingroup\$

APL (Dyalog Extended), 15 bytes

+/,{⊥≠/⊤⍵}¨⍳1+⎕

Try it online!

Full program.

How it works

+/,{⊥≠/⊤⍵}¨⍳1+⎕
              ⎕  ⍝ Take a pair [x y] from stdin
           ⍳1+   ⍝ Generate indices from [0 0] to [x y] inclusive
   {     }¨      ⍝ For each pair,
       ⊤⍵        ⍝   Convert two numbers into two-column bit matrix
                 ⍝   (each column is binary representation of each number)
     ≠/          ⍝   Reduce each row with not-equals (XOR)
    ⊥            ⍝   Convert the resulting binary representation back to integer
+/,              ⍝ Sum all elements and implicit print
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Nice APL submission +1 \$\endgroup\$ – RGS Feb 27 at 19:19
3
\$\begingroup\$

05AB1E, 6 bytes

Ý`δ^˜O

Try it online or verify all test cases.

Explanation:

Ý       # Push a list in the range [0,value] for each value in the (implicit) input-pair
 `      # Push both these lists separated to the stack
  δ     # Apply double-vectorized:
   ^    #  XOR them together
    ˜O  # And then take the flattened sum
        # (after which the result is output implicitly)
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks for your submission! Was it after or before the morning meetings? ;) \$\endgroup\$ – RGS Feb 27 at 19:19
  • 1
    \$\begingroup\$ @RGS Uhh, dunno anymore haha. I think slightly before based on that '13 hours ago'. ;) \$\endgroup\$ – Kevin Cruijssen Feb 27 at 21:13
  • \$\begingroup\$ Alright! I see you like golfing :D \$\endgroup\$ – RGS Feb 27 at 21:55
  • 2
    \$\begingroup\$ @RGS What makes you think that, haha. Is it my multiple answers a day? My 65k+ rep? My 7+ gold badges? Me joining 3.5 years ago, but still active today? xD But yes, I indeed like golfing while I'm waiting for things to compile/build at work. \$\endgroup\$ – Kevin Cruijssen Feb 28 at 7:30
  • \$\begingroup\$ Oh man, I wish I was coding in a compiled language :P I am gonna propose that back at work, so that I can enjoy some code golf while everything builds... \$\endgroup\$ – RGS Feb 28 at 8:20
3
\$\begingroup\$

J, 23 17 bytes

-6 bytes thanks to Bubbler!

1#.1#.XOR/&(i.,])

Try it online!

K (oK), 25 bytes

{+/2/'~=/'(64#2)\''+!1+x}

Try it online!

Most probably can be golfed further.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ J, 17 bytes using outer product instead of catalogue. \$\endgroup\$ – Bubbler Feb 27 at 9:27
  • \$\begingroup\$ @Bubbler Of course! That's much, much better! \$\endgroup\$ – Galen Ivanov Feb 27 at 9:29
  • \$\begingroup\$ Thanks for your two solutions +1 Why don't you have two different answers? \$\endgroup\$ – RGS Feb 27 at 19:23
  • 1
    \$\begingroup\$ @RGS Well, I'm not sure... They turned out to be quite different. \$\endgroup\$ – Galen Ivanov Feb 28 at 7:29
2
\$\begingroup\$

Jelly, 7 bytes

^þ/;RSS

Try it online!

A monadic link taking a pair of integers and returning an integer.

A couple of alternative 7-byters:

Ż€^þ/SS ‘Ḷ^þ/SS

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ So short! Thanks for the alternatives +1 \$\endgroup\$ – RGS Feb 26 at 23:48
2
\$\begingroup\$

Burlesque, 18 bytes

psqrzMPcp{q$$r[}ms

Try it online!

ps   # Parse to arr of ints
qrz  # Boxed range [0,N]
MP   # Map push
cp   # Cartesian product
{
 q$$ # Boxed xor
 r[  # Reduce by
}ms  # Map sum
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Nice solution +1 Do the several letters together represent a single function name? \$\endgroup\$ – RGS Feb 27 at 19:23
  • 1
    \$\begingroup\$ @RGS there's no such things as a function, it's all stack. The q is shorthand for putting it in a block. e.g. qrz = {rz}. Operations are elements of the stack too, and most operations are 2 chars. Some, like maps and reduce, take blocks of operations as an argument and apply them. \$\endgroup\$ – DeathIncarnate Feb 27 at 19:33
  • \$\begingroup\$ I understand, thanks for the explanation! \$\endgroup\$ – RGS Feb 27 at 19:37
2
\$\begingroup\$

C (gcc), 48 bytes

R;f(x,y){R=++x*++y;for(y=0;--R;y+=R%x^R/x);x=y;}

Try it online!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks for your C submission +1 \$\endgroup\$ – RGS Feb 27 at 19:20
  • \$\begingroup\$ Nice! How does this work? \$\endgroup\$ – S.S. Anne Mar 1 at 2:49
  • \$\begingroup\$ @S.S.Anne xnor has used the same algorithm for his python solution and written a good explanation. \$\endgroup\$ – xibu Mar 2 at 16:22
2
\$\begingroup\$

Java 8, 58 bytes

(x,y)->{int t=++x*-~y;for(y=0;--t>0;)y+=t%x^t/x;return y;}

Port of @xibu's C answer, so make sure to upvote him!

Try it online.

Explanation:

(x,y)->{        // Method with two integer parameters and integer return-type
  int t=++x     //  Increase `x` by 1 first with `++x`
        *-~y;   //  Create a temp integer `t`, with value `x*(y+1)`
  for(y=0;      //  Reset `y` to 0 to reuse as result-sum
      --t>0;)   //  Loop as long as `t-1` is larger than 0,
                //  decreasing it before every iteration with `--t`
    y+=         //   Increase the result-sum by:
       t%x      //    `t` modulo-`x`
          ^     //    Bitwise XOR-ed with:
           t/x; //    `t` integer-divided by `x`
  return y;}    //  And then return the result-sum `y`
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Straightforward! Thanks +1 \$\endgroup\$ – RGS Feb 27 at 19:25
2
\$\begingroup\$

Clojure, 72 bytes

(defn s[x y](apply +(for[a(range(inc x))b(range(inc y))](bit-xor a b))))

Ungolfed:

(defn sumxy[x y]
  (apply + (for [a (range (inc x))
                 b (range (inc y)) ]
              (bit-xor a b))))

Tests:

(println (s  5 46) " <-> "  6501)
(println (s  0 12) " <-> "    78)
(println (s 25 46) " <-> " 30671)
(println (s  6 11) " <-> "   510)
(println (s  4 23) " <-> "  1380)
(println (s 17 39) " <-> " 14808)
(println (s  5 27) " <-> "  2300)
(println (s 32 39) " <-> " 29580)
(println (s 14 49) " <-> " 18571)
(println (s  0 15) " <-> "   120)
(println (s 11 17) " <-> "  1956)
(println (s 30 49) " <-> " 41755)
(println (s  8  9) " <-> "   501)
(println (s  7 43) " <-> "  7632)
(println (s 13 33) " <-> "  8022)

Try it online!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ So many parenthesis :p +1 \$\endgroup\$ – RGS Feb 27 at 19:26
  • 1
    \$\begingroup\$ Lisp (of which Clojure is a variant) was one of the earliest high-level languages. It probably would have been more widely adopted were it not for the high costs incurred by the untimely post-war depletion of the Strategic Parenthesis Reserve. However, despite such setbacks, Lisp and its derivatives have been influential in key algorithmic techniques such as recursion and condescension. See the "...History of Programming Languages" page. :-) \$\endgroup\$ – Bob Jarvis - Reinstate Monica Feb 27 at 22:52
  • 1
    \$\begingroup\$ I don't think I even understand all the jokes and references, but that blog post is making me laugh so much :D thanks for this! \$\endgroup\$ – RGS Feb 27 at 22:56
2
\$\begingroup\$

Japt -x, 6 bytes

ô ï^Vô

Try it

ô ï^Vô     :Implicit input of integers U & V
ô          :Range [0,U]
  ï        :Cartesian product with
    Vô     :Range [0,V]
   ^       :Reduce each pair by XORing
           :Implicit output of sum of resulting array
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I like the two eyes ô at the ends of the code +1 \$\endgroup\$ – RGS Feb 27 at 19:21
1
\$\begingroup\$

JavaScript (ES6), 41 bytes

Takes input as (x)(y) (or the other way around). Computes the sum recursively, the obvious way.

x=>g=(y,Y=y)=>~x&&(x^y)+g(y?y-1:x--&&Y,Y)

Try it online!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Good answer! I thought you were going to find some weird formula with the bits of x and y! Nothing came to mind? \$\endgroup\$ – RGS Feb 26 at 23:47
  • 1
    \$\begingroup\$ @RGS The carries implied by a sum usually doesn't mix well with bitwise operations. So I doubt a magic formula exists. (But I'd love to see one.) \$\endgroup\$ – Arnauld Feb 26 at 23:56
  • \$\begingroup\$ If time efficiency were the goal, there are some simple formulas that come quite close (and can then be corrected by brute-forcing a much shorter list). \$\endgroup\$ – Brilliand Feb 27 at 21:24
1
\$\begingroup\$

Python 3, 59 58 bytes

Saved a byte thanks to Neil and HyperNeutrino!!!

lambda x,y:sum(a^b for a in range(x+1)for b in range(y+1))

Try it online!

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ You have an extra space that you can remove after the ) in range(x+1) \$\endgroup\$ – HyperNeutrino Feb 26 at 22:43
1
\$\begingroup\$

C (gcc), 61 52 bytes

Saved 9 bytes thanks to Arnauld!!!

b;s;f(x,y){for(s=b=y;~x;b--||(b=y,x--))s+=x^b;s-=y;}

Try it online!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Do you really have to have the three variables before the f? Can't you stuff them somewhere else or something? :/ \$\endgroup\$ – RGS Feb 26 at 23:50
  • \$\begingroup\$ @RGS Tried several variations and they had either more or the same byte count. :( \$\endgroup\$ – Noodle9 Feb 26 at 23:51
  • \$\begingroup\$ 52 bytes \$\endgroup\$ – Arnauld Feb 26 at 23:51
  • \$\begingroup\$ @Arnauld That's diabolical - thanks! :-) \$\endgroup\$ – Noodle9 Feb 26 at 23:57
1
\$\begingroup\$

Wolfram Language (Mathematica), 33 bytes

Sum[i~BitXor~j,{i,0,#},{j,0,#2}]&

Try it online!

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Zsh, 31 bytes

eval '<<<$[' +{0..$1}^{0..$2} ]

Try it online!

Uses eval to expand the <<<$[ ] after expanding the lists. The TIO link adds set -x so you can see what the brace expansion looks like.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks for your zsh submission! \$\endgroup\$ – RGS Feb 27 at 19:24
1
\$\begingroup\$

Perl 5 -pa, 36 bytes

map{//;map$\+=$_^$',0..$F[0]}0..<>}{

Try it online!

Takes in inputs on separate lines.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks for your Perl 5 submission! Why did you go for Perl 5 and not any other version? Like a more recent version? \$\endgroup\$ – RGS Feb 27 at 21:29
  • \$\begingroup\$ @RGS Perl 5 is very different from Perl 6, so much so that the latter has been renamed to Raku to prevent confusion. Perl 5 is what most people refer to as just Perl \$\endgroup\$ – Jo King Feb 28 at 2:09
1
\$\begingroup\$

Oracle SQL, 126 bytes

This isn't a golfing language and it doesn't have a bitwise XOR operator but:

SELECT SUM(x+y-2*BITAND(x,y))FROM(SELECT LEVEL-1 x FROM T CONNECT BY LEVEL<x+2),(SELECT LEVEL-1 y FROM T CONNECT BY LEVEL<y+2)

Assumes that there is a table T with columns X and Y containing one row that has the input values.

So for the inputs:

CREATE TABLE t(x,y) AS SELECT 5,46 FROM DUAL;

This outputs:

| SUM(X+Y-2*BITAND(X,Y)) |
| ---------------------: |
|                   6501 |

db<>fiddle here


As an aside, its only 81 characters in PostgreSQL:

SELECT sum(a#b)FROM t,generate_series(0,t.x)AS x(a),generate_series(0,t.y)AS y(b)

db<>fiddle here

But its less fun as that has a built-in XOR operator and series generation.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Really cool solution! thanks for it +1 \$\endgroup\$ – RGS Feb 27 at 21:29
1
\$\begingroup\$

Japt -x, 8 bytes

ò@Vò^XÃc

Try it

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 8 bytes: ò@Vò^XÃc. \$\endgroup\$ – Shaggy Feb 27 at 7:30
  • \$\begingroup\$ I also like the eyes and nose here: ò@ò \$\endgroup\$ – RGS Feb 27 at 19:25
1
\$\begingroup\$

Julia 1.0, 33 bytes

(x,y)->sum(i⊻j for i=0:x,j=0:y)

Try it online!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ This Julia answer is really short +1 good job \$\endgroup\$ – RGS Mar 1 at 9:26
1
\$\begingroup\$

C (gcc), 51 bytes

d,r;f(x,y){for(d=y;~d||(x--,d=y),~x;)r+=x^d--;d=r;}

Try it online!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Nice answer! +1 keep up the good work \$\endgroup\$ – RGS Mar 1 at 9:26

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.