4
\$\begingroup\$

The Walsh matrix is an interesting fractal matrix with the property that every single value in a Walsh matrix has a value of either -1 or 1. Additionally, the size of a Walsh matrix is always a power of 2.

Because each Walsh matrix is identical to the top-left quarter of the immediately higher-order Walsh matrix, we can create a generalized "infinite Walsh matrix" by considering the limit of the sequence of Walsh matrices of order N, as N goes to infinity. From here on, we will call this infinite generalization the Walsh matrix.

Your task is to build a program that takes the coordinates of a location in the Walsh matrix and returns the value that occurs there.

Your program will accept two integers x and y as input (in any form you choose), and output the value that appears in the x+1th row of the y+1th column of the Walsh matrix. For example, the input

2 5

will return 1, as the 3rd row in the 6th column of the Walsh matrix has a value of 1. The input

6 4

will return -1, as the 7th row in the 5th column of the Walsh matrix has a value of -1. The input

2834719 394802

will return -1, as the 2384720th row of the 394803rd column has a value of -1.

The shortest code to do this in any language wins.

\$\endgroup\$
  • 5
    \$\begingroup\$ I quickly figured out a procedure for determining the value of any cell. Problem is, it only gives the correct answer half of the time. :) \$\endgroup\$ – DavidC Feb 14 '14 at 20:26
  • 2
    \$\begingroup\$ print "0 ± 1" \$\endgroup\$ – Doorknob Feb 14 '14 at 22:05
  • \$\begingroup\$ @DavidCarraher, it seems that if you output 1 you'll do better than 50%. \$\endgroup\$ – Peter Taylor Feb 15 '14 at 9:27
  • 1
    \$\begingroup\$ @Peter Taylor, Great idea, and your solution even saves a few characters. \$\endgroup\$ – DavidC Feb 15 '14 at 13:56
  • 1
    \$\begingroup\$ Please add a minimal description of the matrix so that the problem makes sense when wikipedia is down. \$\endgroup\$ – Sparr Oct 15 at 4:37
4
\$\begingroup\$

GolfScript (18 15 14 bytes)

~&2base-1\0-,?

Takes input space-separated; outputs to stdout. Thanks to Howard for pointing out that the space in the 15-char solution was removable.

The way I reasoned to this solution is quite simple. Take the highest set bit of x|y: this tells you the size of the smallest Walsh matrix which contains the relevant index. Then clearing that bit in both x and y drops us down to the top-left quadrant, and we need to multiply by -1 if we were previously in the bottom-right quadrant: i.e. if the bit was set in both x and y. By induction down the bit sequence, we just need to count the number of bits set in x&y.

\$\endgroup\$
  • \$\begingroup\$ Of course it is much shorter to write ~&2base-1\0-,?. \$\endgroup\$ – Howard Feb 15 '14 at 11:11
2
\$\begingroup\$

Python 2 - 42 bytes

print(-1)**bin(input()&input()).count("1")

This takes the two coordinates as separate lines on standard input and writes the answer to standard output.

The algorithm is this:

  1. For coordinates X and Y, find X & Y, the bitwise AND of their values.
  2. Count the number of 1 bits in X & Y. This is the number of times the requested coordinate is in the bottom right quadrant of a level of the matrix.
  3. If the count is odd, the result is -1. If the count is even, the result is 1.

This should work for any positive integer coordinates (including large ones that need more than 32 bits).

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

Forth (gforth), 44 bytes

: f and 1e 63 for s>d 2* 1+ s>f f* 2* next ;

Try it online!

The function takes two word-sized unsigned integers (64 bits on TIO). It returns -1 or 1 on the floating-point stack and leaves a garbage 0 on the main stack.

The algorithm follows Blckknght's submission, but the task made me explore LOTS of possibilities for writing Forth programs - from bit shift, divmod, single-to-double conversion to abusing floating-point stack. (The TIO link has several alternative definitions of f which all work, but are longer than the main answer.)

How it works

: f ( u1 u2 -- -1e_or_1e )  \ Takes two integers and returns a float 1 or -1
  and 1e                    \ Bitwise and(=N), then put a 1(=R) on the FP stack
  63 for                    \ Repeat 64 times... (TIO gforth has 64-bit cells)
    s>d                       \ Sign-extend single N to double
                              \ In effect, 0 is pushed if MSB is zero, -1 otherwise
    2* 1+ s>f f*              \ Change 0_or_-1 to 1_or_-1, cast to float and multiply with R
    2*                        \ Shift N left once
  next                      \ End loop
  ;                         \ End function
\$\endgroup\$
0
\$\begingroup\$

x86_64 machine language for Linux, 17 bytes

0x00:  48 21 F7          and    rdi, rsi
0x03:  F3 48 0F B8 C7    popcnt rax, rdi
0x08:  FF C0             inc    eax
0x0a:  24 01             and    al, 1
0x0c:  01 C0             add    eax, eax
0x0e:  FF C8             dec    eax
0x10:  C3                ret    

Same algorithm as @Blckknght's answer.

Try it online!

\$\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.