Generate a Universal-binary-function Lookup Table

Question

_{This is tangentially related to my quest to invent an esoteric programming language.}

A table of the binary numbers 0 .. 15 can be used to implement a Universal Binary Function using indexing operations. Given two 1-bit inputs X and Y, all 16 possible functions can be encoded in a 4-bit opcode.

X Y  F|0 1 2 3 4 5 6 7 8 9 A B C D E F
- -    - - - - - - - - - - - - - - - -  
0 0    0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1    0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 0    0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 1    0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
       -     -   - -   -   -   -   - -
       0    ~X  ~Y ^   &   Y   X   | 1
      ZERO    NOT-Y   AND         OR
          NOT-X   XOR              ONE

So this set of 16 functions can be applied to binary inputs as the function

U(f,x,y): (f >> ((x<<1) | y)) & 1,

or

U(f,x,y): (f / 2^(x×2 + y)) % 2,

or with indexing or matrix partitioning.

It will be useful to know the most compact way to represent or generate such a table of values for any possible languages to be built upon this type of binary operation.

The goal:

Generate this exact text output:

0101010101010101
0011001100110011
0000111100001111
0000000011111111

That's it! Shortest-code wins.

Answer 1

J, 10 (13?) characters

|.|:#:i.16

Number list:

   i.16
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15`

to binary:

   #:i.16
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

Transpose:

   |:#:i.16
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Reverse:

   |.|:#:i.16
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

Do we need to remove the spaces? Looking at the other J answer it seems we do so we'll need to add 3 characters and borrow the 1": from Jan's answer.

Answer 2

Python 2, 40

for n in 1,2,4,8:print 8/n*('0'*n+'1'*n)

Answer 3

APL (14)

Assuming ⎕IO=0 (that's a setting):

⎕D[⊖(4⍴2)⊤⍳16]

Explanation:

• ⍳16: numbers [0,16)
• (4⍴2)⊤: encode each number in base 2 using 4 digits
• ⊖: horizontal reverse (so the MSB ends up on top)
• ⎕D[...]: select these values from ⎕D which is the string 0123456789. (A numeric matrix is displayed with spaces between the values, a character matrix is not. So this converts each numerical bit to one of the chars '0' '1').

Answer 4

Jelly, 42 7 bytes

⁴ḶBUz0Y

Try it online!

Thanks to Dennis for his help. Here is the first message, here is the last (other discussions also occured). With his help, I apparently (almost) square-rooted the score.

Answer 5

///, 51 bytes

Try it online

/a/0101/aaaa
/b/0011/bbbb
/z/0000//o/1111/zozo
zzoo

Answer 6

GolfScript (18 17 15 chars)

(With thanks to Howard)

16,zip{','-~n}%

I don't understand why the 10-char

16,zip{n}/

doesn't work; I suspect that a bug in the standard interpreter is resulting in unsupported types on the stack.

An alternative at 18 characters which I understand fully is:

4,{2\?.2,*$8@/*n}%

A more mathematical approach is a bit longer, at 28 chars:

4,{2.@??)2.4??.@/+2base(;n}/

A lot of that is for the base conversion and zero-padding. Without those, it drops to 19 chars,

4,{2.@??)2.4??\/n}/

with output

21845
13107
3855
255

Answer 7

Postscript 108 177 126 77 74 70

[43690 52428 61680 65280]
{16{dup 2 mod =only 2 idiv}repeat<>=}forall

Reversed the values for a simpler mod- off method.

151 131 119

Applying a more APL-ish approach. edit: replaced string chopping and array zipping with indexing and for-loops.

[[0 1 15{}for]{16 add 2 5 string cvrs}forall]4 
-1 1{0 1 15{2 index exch get 1 index 1
getinterval =only}for pop<>=}for

Indented:

[[0 1 15{}for]{16 add 2 5 string cvrs}forall]
4 -1 1{ % [] i
    0 1 15{ % [] i j
        2 index exch get % [] i [](j)
        1 index 1  % [] i [](j) i 
        getinterval  % [] i [](j)<i>
        =only  % [] i
    }for 
    pop<>= % []
}for

Reimplementing the functions used in the winning J answer leads to this (with a lot of support code).

-1 16 i + #: |: |.{{==only}forall()=}forall

i here is 1-based vector described in Iverson's Elementary Functions, hence the -1 ... + to produce 0 .. 15.

Answer 8

CJam - 16

4,{G,f{\m>2%}N}/

Equivalent java code (as explanation):

public class Lookup {
    public static void main(final String... args) {
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 16; ++j) {
                System.out.print((j >> i) % 2);
            }
            System.out.println();
        }
    }
}

Answer 9

Javascript (ECMA6), 67

s=(k,n)=>n-.5?s((k<<n/2)^k,n/2)+"0".repeat(n)+k.toString(2)+"\n":"" 

To use this, call

s(255,8)

Bitshift!
And also XOR and a bit of recursion.

The first thing to notice is that if we take any line and you shift it (# of continuous 0's) / 2 left, we get a nice XOR to get the next line up.

For example,

0000000011111111 //line 4
0000111111110000 //shifted 4 to the left

XOR these bitwise give us

0000111100001111 //XOR'ed. This is line 3!

which is the next line up (line 3).
Applying the same process for line 3, shift 2 left and we get...

0000111100001111
0011110000111100

XOR'ed gives

0011001100110011

which is line 2.
Notice that the amount we shift halves each time.
Now we simply call this function recursively, with 2 arguments. The integer value of this line, and N, which is how much we need to shift. When we do recursing just pass in the shifted XOR'ed value and n/2.

"0".repeat(n)

is to pad 0's to the beginning of each line because toString takes out leading 0's.

Answer 10

J, 21 characters

1":<.2|(2^i.4)%~/i.16

• i.16 is a list of 0..15
• 2^i.4 is a list (1,2,4,8)
• %~/ produces the table of divisions where the left argument forms rows but is the right argument to division
• 2| calculates the remainder after dividing [each cell] by two
• <. floors that value to 0 or 1
• 1": formats the table with one character per cell

Answer 11

GolfScript, 19 chars

Another GolfScript approach

4,{2\?{&!!}+16,%n}%

Answer 12

Ruby (44)

Boring and long: Just printing the 0-padded binary representations of the numbers.

[21845,13107,3855,255].map{|i|puts"%016b"%i}

Answer 13

Perl (36+1)

+1 for say, as usual. the double 0 is not a typo :)

map say((00x$_,1x$_)x(8/$_)),1,2,4,8

Answer 14

JavaScript (ECMA6), 108

Trying a different approach here. Even though it was encouraged to use binary operators, I allowed myself to submit this solution since the challange is also kolmogorov-complexity and I was thinking - how can I reduce the amount of code representing those values...? Bases.

['gut','a43','2z3','73'].forEach(n=>{a=parseInt(n,36).toString(2);
alert(('00000000'+a).substr(a.length-8))})

(Line break for convenience).

It's a shame I had to mess with padding with leading zeros, but the point of this code is simply representing the target binary result in Base 36, which are exactly those gut, a43, 2z3, 73 values.

Note: I realize it won't be anywhere near the winning answer, but just for the sake of the idea...

Answer 15

Sprects, 44 bytes

 aaaa
bbbb
zozo
zzoo o1111 z0000 b0011 a0101

Cedric's answer ported to Sprects.

Answer 16

JavaScript (ES6), 58 52 bytes

Builds the string recursively.

f=(n=64)=>n--?f(n)+(!n|n&15?'':`
`)+(n>>(n>>4)&1):''

How it works

This recursion is based on the fact that the pattern is made of the vertical binary representation of nibbles 0x0 to 0xF:

  0101010101010101 bit #0 <- Y = 0
  0011001100110011 bit #1
  0000111100001111 bit #2
  0000000011111111 bit #3 <- Y = 3
  ----------------
  0123456789ABCDEF
  ^              ^
X = 0          X = 15

Therefore, each position (X,Y) in this pattern can be expressed as the Y-th bit of X: X & (1 << Y). We can also isolate this bit with: (X >> Y) & 1. Rather than keeping track of X and Y, we iterate on a single variable n ranging from 0 to 63. So, the formula becomes: (n >> (n >> 4)) & 1. It's actually easier to iterate from 63 to 0, so the string is built in reverse order. In other words, character n-1 is appended to the left of character n.

As a side note, recursion doesn't bring anything here except shorter code.

Without the linebreaks, the code is 35 bytes long:

f=(n=64)=>n--?f(n)+(n>>(n>>4)&1):''

We need 17 more bytes to insert the linebreaks. This could be shortened to 14 bytes if a leading linebreak is acceptable.

Demo

f=(n=64)=>n--?f(n)+(!n|n&15?'':`
`)+(n>>(n>>4)&1):''

console.log(f());

Answer 17

Bash + coreutils, 65 bytes

Not the shortest, but not the longest either:

for i in {1,2,4,8};{ eval echo \$\[\({0..15}\&$i\)/$i];}|tr -d \ 

(The last character is a space)

Try it online.

Answer 18

MATL, 8 bytes

16:qYB!P

Try it online!

Explanation

16:    % Generate range [1 2 ... 16]
q      % Subtract 1, element-wise
YB     % Convert to binary. Gives a 16×4 char array. Each original number is a row
!      % Transpose
P      % Reverse vertically. Implicitly display

Answer 19

CJam, 10 9 bytes

Thanks to @Dennis for 1 byte off!

Y4m*zW%N*

Try it online!

Explanation

Y     e# Push 2
4     e# Push 4
m*    e# Cartesian power of 2 (interpreted as [0 1]) with exponent 4
z     e# Zip
W%    e# Reverse the order of rows
N*    e# Join with newlines. Implicitly display

Answer 20

NARS2000 APL, 22

"01"[⊖1+(4⍴2)⊤(⍳16)-1]

Derived from marinus's APL answer, which doesn't seem to work on NARS2000.

Generate vector

      ⍳16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Change to zero-based

      (⍳16)-1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Generate shape for encode

      (4⍴2)
2 2 2 2

Encode

      (4⍴2)⊤(⍳16)-1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Adjust for 1-based indexing

      1+(4⍴2)⊤(⍳16)-1
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2
1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2
1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2

Reverse primary axis

      ⊖1+(4⍴2)⊤(⍳16)-1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2
1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2

Index

      "01"[⊖1+(4⍴2)⊤(⍳16)-1]
0101010101010101
0011001100110011
0000111100001111
0000000011111111

Answer 21

C, 73 chars

i;main(){for(;i<64;)i&15||puts(""),putchar(48|1&~0xFF0F0F33335555>>i++);}

This is just a general solution for outputting 64 bits in four 16-bit blocks; you just need to change the number 0xFF0F0F33335555 to output an other bit sequence.

simplified & ungolfed:

int main() {
    int i;
    for(i = 0; i < 64; i++) {
        if(i % 16 == 0) {
            puts("");
        }
        int bit = ~0xFF0F0F33335555 >> i;
        bit &= 1;
        putchar('0' + bit);
    }
}

Answer 22

Haskell, 73

Yikes, 73 chars! I can't for the love of god get this any smaller though.

r=replicate
f n=r(div 8n)("01">>=r n)>>=id
main=mapM(putStrLn.f)[1,2,4,8]

The real sad part about this is that if you were to echo the output using bash, you'd only need 74 characters.

Answer 23

JavaScript (ES5) 69

for(x="";4>x;x++){z="";for(n=0;16>n;)z+=1-!(n++&1<<x);console.log(z)}

Answer 24

inca2, 33 27 24

4 16#(,`2|(~16)%.2^~4){D

This is based on Jan Dvorak's answer. inca2 is able to execute this as of yesterday's bugfixes. Technically invalid since the language was invented after the question, but invention of a language was part of my goal in posing the question. So here's some payback in gratitude to the other answers. :)

Explanation:

4 16#(,`2|(~16)%.2^~4){D
          (~16)               integers 0 .. 15 
                 2^~4         first 4 powers of 2: 1 2 4 8
          (~16)%.2^~4         division table
        2|                    mod 2 (and floor)
       `                      transpose
      ,                       ravel
     (               ){D      map to chars '0'..'9'
4 16#                         reshape to 4x16

Some of the parentheses should be unnecessary, but apparently there are some remaining issues with my interpretation of the grammar. And "ravel => map => reshape" is really clumsy: map needs to be smarter. Edit: bugfixes allow elimination of parens.

---

Factoring the base conversion into a separate function N:x|y%.x^~1+[]/x.y yields this 19 16 char version.

4 16#(,`2N~16){D

---

And while I'm cheating anyway here, I've gone ahead and made this a built-in function. But, even though it's a niladic function (not requiring an argument), there is no support for niladic functions, and it must be supplied with a dummy argument.

inca2, 2

U0

Answer 25

Pyth 24 / 26

The shortest method was grc's answer translated to Pyth which I felt was cheap so I did my own method:

Mine: 26 characters

 mpbjk*/8dS*d[0 1)[1 2 4 8

grc's: 24 characters

Fd[1 2 4 8)*/8d+*\0d*\1d

Answer 26

C++ 130

Converts hex to binary

#define B std::bitset<16>
#define C(x) cout<<x<<endl;
void main(){
B a(0xFF),b(0xF0F),c(0x3333),d(0x5555);
C(d)C(c)C(b)C(a)
}

Answer 27

Haskell (Lambdabot), 47 bytes

unlines$reverse$transpose$replicateM 4['1','0']

Kinda cheaty because it uses transpose from Data.List and replicateM from Control.Monad, however both are loaded by default from Lambdabot.

Also, I'm sure there is room for improvement, just wanted to share the idea

Answer 28

Julia (39 Bytes)

Second script I've ever written in Julia, gotta admit I'm liking Julia, she's a pretty beast.

hcat(map(x->collect(bin(x,4)),0:15)...)

Returns

[0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 
 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 
 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]  

Explanation:

• bin(x,4) - Convert int to binary integer with padding to 4 characters.
• collect(_) - Split string into char array.
• map(x->_,0:15) - Do this for the first 16 digits in the range.
• hcat(_...) - Splat and horizontally concatenate into a matrix.

Answer 29

C 83 77 76 74 71

x;f(n){for(;x<4;x++,puts(""))for(n=0;n<16;)putchar(49-!(n++&(1<<x)));}

Pretty straightforward.

x;
f(n){
    for(;x<4;x++,puts(""))
        for(n=0;n<16;)
            putchar(49-!(n++&(1<<x)));
}

Answer 30

R, 53 41 bytes

A translation of @grc's python answer. Shaved off 12 bytes from the original translation through use of rep()'s each and length arguments (and partial argument matching), and by remembering that 0:1 is equivalent to c(0,1).

for(n in 2^(0:3))print(rep(0:1,e=n,l=16))

for(n in 2^(0:3))print(rep(c(rep(0,n),rep(1,n)),8/n))

You can also attempt a translation of @Gareth's J answer, something like this (34 bytes):

t(e1071::bincombinations(4))[4:1,]

However, it uses a function that's not part of base R, and outputs a matrix which is hard to format into exact printed text like in the specification.