# Golf all the 16 logic gates with 2 inputs and 1 output!

For example, the gate A and B is a logic gate with 2 inputs and 1 output.

There are exactly 16 of them, because:

• each logic gate takes two inputs, which can be truthy or falsey, giving us 4 possible inputs
• of the 4 possible inputs, each can have an output of truthy and falsey
• therefore, there are 2^4 possible logic gates, which is 16.

Your task is to write 16 programs/functions which implement all of them separately.

They are valid as long as they output truthy/falsey values, meaning that you can implement A or B in Python as lambda a,b:a+b, even if 2 is produced for A=True and B=True.

Score is total bytes used for each function/program.

## List of logic gates

1. 0,0,0,0 (false)
2. 0,0,0,1 (and)
3. 0,0,1,0 (A and not B)
4. 0,0,1,1 (A)
5. 0,1,0,0 (not A and B)
6. 0,1,0,1 (B)
7. 0,1,1,0 (xor)
8. 0,1,1,1 (or)
9. 1,0,0,0 (nor)
10. 1,0,0,1 (xnor)
11. 1,0,1,0 (not B)
12. 1,0,1,1 (B implies A)
13. 1,1,0,0 (not A)
14. 1,1,0,1 (A implies B)
15. 1,1,1,0 (nand)
16. 1,1,1,1 (true)

Where the first number is the output for A=false, B=false, the second number is the output for A=false, B=true, the third number is the output for A=true, B=false, the fourth number is the output for A=true, B=true.

• Your functions/programs may share code. What does this mean? Also, may the programs be in different languages?
– Lynn
Jun 14, 2016 at 23:36
• I find the explanation confusing: "of the 4 possible inputs each can have and output of truthy and falsy". Doesn't this imply 8 (4*2) states? Jun 14, 2016 at 23:50
• The names you're missing are the AND-NOT gates (A AND NOT B and B AND NOT A).
– user45941
Jun 15, 2016 at 1:33
• So it happened again. There are 18 answer, mostly simple and correct, then out of nowhere the question became "unclear what you're asking". I you don't like a challenge, go on, take another, do not close it! Jun 15, 2016 at 17:25
• @dorukayhan See: vacuous truth Jun 15, 2016 at 21:19

# Dominoes, 122,000 bytes or 72 tiles

The byte count is the size of the saved file which is 0.122 MB.

Domino computing was the inspiration. I have tested all of these up to symmetry (and beyond!) via a virtual-reality Steam game called Tabletop Simulator.

## Details

• I/O
• Start - This is included for clarity (not counted towards total) and is what 'calls' or 'executes' the function. Should be 'pressed' after input is given [Yellow].
• Input A - This is included for clarity (not counted towards total) and is 'pressed' to indicated a 1 and unpressed otherwise [Green].
• Input B - This is included for clarity (not counted towards total) and is 'pressed' to indicated a 1 and unpressed otherwise [Blue].
• Output - This is counted towards total. It is the domino that declares the result of the logic gate [Black].
• T/F
• A fallen output domino represents a result of True or 1
• A standing output domino represents a result of False or 0
• Pressing
• To give input or start the chain, spawn the metal marble
• Set the lift strength to 100%
• Lift the marble above the desired domino
• Drop the marble

## Gates

• false, 1
• and, 6 4
• A and not B, 4 3
• A, 1
• not A and B, 4 3
• B, 1
• xor, 15 11
• or, 1
• nor, 3 2
• xnor, 17 13
• not B, 2
• B implies A, 7 6
• not A, 2
• A implies B, 7 6
• nand, 16 15
• true, 1

## TL;DR

I had been waiting/wanting a domino-friendly challenge and when I saw this, I couldn't pass it up. The only problem was that apparently no one owns dominoes any more! So eventually I gave in and bought a Double Twelve. This set has 91 tiles, which gave me the idea of have a 'function call'/start domino instead of the normal (long) 'time delay' method. Credit for the 90 degree turn belongs to dominoesdouble07's channel.

After building these with physical dominoes, it was ruled on meta that valid solutions should be digital. So I recreated these gates in Tabletop Simulator. Sadly, TS and reality don't agree on domino physics. This required me adding 11 dominoes but I also saved 8. Overall, virtual dominoes are about x150 more effective in terms of building and testing (Ctrl+Z).

Update

• -9 [17-03-13] Shortened xor xnor nand
• +11 [17-03-03] Added digital xnor and xor
• -8 [17-03-03] Digitized all the gates (except xor and xnor). Blocking on Tabletop only requires 1 domino, instead of 2.
• [16-09-23] Shrunk images
• -11 [16-09-18] Nearly cut xor in half again. Thanks to @DJMcMayhem for xnor and Joe for xor.
• -31 [16-08-31] Updated some pics and shaved some tiles and cut xor in half
• +1 We need more domino golfing on PPCG Aug 29, 2016 at 10:53
• Related. Aug 29, 2016 at 11:58
• Wow. This is one of the most original answers I have ever seen on this site. Aug 31, 2016 at 19:24
• It looks like you could take one domino off if you squish the xnor together and have 4 across the top, rather than 5. Then again, I haven't tested it at all. Sep 3, 2016 at 15:44
• Thanks for taking the time to make this a valid answer. However, the link to the source file is a bit hard to find. Normally, the link in the header leads to the language itself. So I'd link that one to the steam game and then put the link to the actual "source file" in a separate, clearly labelled link somewhere in the body of the answer. Mar 9, 2017 at 13:19

## Hexagony, 89 bytes

Thanks to FryAmTheEggman for some necessary inspiration for the XOR solution.

0000 !@
0001 ?.|@!
0010 #?#!)@
0011 ?!@
0100 +?|@!?
0101 ??!@
0110 ?<@!!<_\~(
0111 ?<<@!
1000 )\!#?@{
1001 (~?/@#!
1010 ??|@!)
1011 \#??!1@
1100 ?(~!@
1101 ?.|@!)

### 0101: B

? ?
! @ .
. .

Woohoo, another simple one: read A, read B, print B, terminate. There are actually alternatives to this though. Since A is only a single character, we can also read it with ,:

,?!@

And there's also the option of using a single ? and using a mirror to run through it twice:

?|@!    ?>@!

### 0110: Xor

? < @
! ! < _
\ ~ ( . .
. . . .
. . .

Like I said above, this was the only gate that wouldn't fit in side-length 2, so this a handwritten solution by FryAmTheEggman and myself, and there's a good chance that it isn't optimal. There are two cases to distinguish. If A = 0 the control flow is fairly simple (because in that case we only need to print B):

We start on the red path. ? reads A, < is a branch which deflects the zero left. The IP wraps to the bottom, then _ is another mirror, and when the IP hits the corner, it wraps to the top left corner and continues on the blue path. ? reads B, ! prints it. Now ( decrements it. This is important because it ensures that the value is non-positive (it's either 0 or -1 now). That makes IP wrap to the to right corner, where @ terminates the program.

When A = 1 things get a bit trickier. In that case we want to print not B, which in itself isn't too difficult, but the execution path is a bit trippy.

This time, the < deflects the IP right and then next < just acts as a mirror. So the IP traverses the same path in reverse, reading B when it encounters ? again. The IP wraps around to the right corner and continues on the green path. It next encounters (~ which is "decrement, multiply by -1", which swaps 0 and 1 and therefore computes not B. \ is just a mirror and ! prints the desired result. Then ? tries to return another number but returns zero. The IP now continues in the bottom left corner on the blue path. ( decrements, < reflects, ( decrements again, so that the current value is negative when the IP hits the corner. It moves across the bottom right diagonal and then finally hits @ to terminate the program.

### 0111: Or

? <
< @ !
. .

More short-circuiting.

The A = 0 case (the red path) is a bit confusing here. The IP gets deflected left, wraps to the bottom left corner, gets immediately reflected by the < and returns to the ? to read B. It then wraps to the rigt corner, prints B with ! and terminates.

The A = 1 case (the green path) is a bit simpler. The < branch deflects the IP right, so we simply print the !, wrap back to the top left, and terminate at @.

There is only one other 5-byte solution:

\>?@!

It works essentially the same, but the actual execution paths are quite different and it uses a corner for branching instead of a <.

### 1000: Nor

) \
! # ?
@ {

This might be my favourite program found in this search. The coolest thing is that this implementation of nor actually works for up to 5 inputs. I'll have to get into the details of the memory model a bit to explain this one. So as a quick refresher, Hexagony's memory model is a separate hexagonal grid, where each edge holds an integer value (initially all zero). There's a memory pointer (MP) which indicates an edge and a direction along that edge (such that there's two neighboring edges in front of and behind the current edge, with meaningful left and right neighbours). Here is a diagram of the edges we'll be using, with the MP starting out as shown in red:

Let's first consider the case where both inputs are 0:

We start on the grey path, which simply increments edge A to 1 so that the # switches to IP 1 which is the blue path, starting in the top right corner. \ does nothing there and ? reads an input. We wrap to the top left corner where ) increments that input. Now as long as the input is zero, this will result in a 1, so that # doesn't do anything. Then { moves the MP to the left, i.e. on the first iteration from A to B. Since this edge still has its initial zero the IP wraps back to the top right corner and on a new memory edge. So this loop will continue as long as ? reads zeros, moving the MP around the hexagon from B to C to D and so on. It doesn't matter whether ? returns a zero because it was an input or because it was EOF.

After six iterations through this loop, { returns to A. This time, the edge already holds the value 1 from the very first iteration, so the IP wraps to the left corner and continues on the green path instead. ! simply prints that 1 and @ terminates the program.

Now what if any of the inputs is 1?

Then ? reads that 1 at some point and ) increments it to 2. That means # will now switch IPs again and we'll continue in the right corner on the red path. ? reads another input (if there is one), which doesn't really matter and { moves one edge further. This has to be an unused edge, hence this works for up to 5 inputs. The IP wraps to the top right where it's immediately reflected and wraps to the left corner. ! prints the 0 on the unused edge and # switches back to IP 0. That IP was still waiting around on the #, going southwest (grey path), so it immediately hits the @ and terminates the program.

In total there are seven 7-byte solutions for this gate. 5 of them work the same as this and simply use other commands to move to an unused edge (and may walk around a different hexagon or in a different direction):

)\!#?@"    )\!#?@'    )\!#?@^    )\!#?@{    )\!#?@}

And there is one other class of solutions which only works with two inputs, but whose execution paths are actually even messier:

?]!|<)@    ?]!|<1@

### 1001: Equality

( ~
? / @
# !

This also makes very clever use of conditional IP selection. We need to distinguish again between A = 0 and A = 1. In the first case we want to print not B, in the second we want to print B. For A = 0 we also distinguish the two cases for B. Let's start with A = B = 0:

We start on the grey path. (~ can be ignored, the IP wraps to the left corner (still on the grey path) and reads A with ?. ( decrements that, so we get -1 and IP wrap to the bottom left corner. Now like I said earlier, # takes the value modulo 6 before choosing he IP, so a value of -1 actually gets out IP 5, which starts in the left corner on the red path. ? reads B, ( decrements that as well so that we remain on IP 5 when we hit # again. ~ negates the -1 so that the IP wraps to the bottom right corner, prints the 1 and terminates.

Now if B is 1 instead, the current value will be 0 when we hit # the second time, so we switch back to IP 0 (now on the green path). That hits ? a third time, yielding 0, ! prints it and @ terminates.

Finally, the case where A = 1. This time the current value is already zero when we hit # for the first time, so this never switches to IP 5 in the first place. We simply continue immediately on the green path. ? now doesn't just give a zero but returns B instead. ! prints it and @ terminates again.

In total there are three 7-byte solutions for this gate. The other two work very differently (even from each other), and make even weirder use of #. In particular they read one or more values with , (reading a character code instead of an integer) and then use that value modulo 6 to pick an IP. It's pretty nuts.

),)#?@!

?~#,~!@

### 1010: Not B

? ?
| @ !
) .

This one is fairly simple. The execution path is the horizontal branch we already know from and earlier. ?? reads A and then immediately B. After reflecting at | and branching, for B = 0 we will execute the bottom branch, where ) increments the value to 1 which is then printed by !. On the top branch (if B = 1) the ? simply reset the edge to 0 which is then also printed by !.

There are eight 6-byte programs for this gate. Four of them are pretty much the same, using either > instead of | or 1 instead of ) (or both):

??>@!)    ??>@!1    ??|@!)    ??|@!1

Two use a single ? which is used twice due to a mirror. The negation then happens as we did for xor with either (~ or ~).

?>!)~@    ?>!~(@

And finally, two solutions use a conditional IP switch, because why use the simple way if the convoluted one also works:

??#)!@    ??#1!@

### 1011: B implies A

\ #
? ? !
1 @

This uses some rather elaborate IP switching. I'll start with the A = 1 case this time, because it's simpler:

We start on the grey path, which reads A with ? and then hits the #. Since A is 1 this switches to IP 1 (green path). The ! immediately prints that, the IP wraps to the top left, reads B (unnecessarily) and terminates.

When A = 0 things get a bit more interesting. First let's consider A = B = 0:

This time, the # does nothing and we remain on IP 0 (red path from that point onward). ? reads B and 1 turns it into a 1. After wrapping to the top left corner, we hit # again, so we end up on the green path after all, and print 1 as before, before terminating.

Finally, here is (A, B) = (0, 1), the false case:

Note that I've removed the initial grey path for clarity, but the program begins the same way, and we end up on the red path as before. So this time the second ? returns 1. Now we encounter the 1. At this point it's important to understand what digits actually do in Hexagony (so far we've only used them on zeros): when a digit is encountered, the current value is multiplied by 10 and then the digit is added. This is normally used to write decimal numbers verbatim into the source code, but it means that B = 1 is actually mapped to the value 11. So when we hit #, this is taken modulo 6 to give 5 and hence we switch to IP 5 (instead of 1 as before) and continue on the blue path. Hitting ? a third time returns a zero, so ! prints that, and after another two ?, the IP wraps to the bottom right where the program terminates.

There are four 7-byte solutions to this and they all work differently:

#)/!?@$<!?_@#1 \#??!1@ |/)#?@! ### 1100: Not A ? ( ~ ! @ . . Just a simple linear one: read A with ?, negate with (~, print with !, terminate with @. There's one alternative solution, and that's negating with ~) instead: ?~)!@ ### 1101: A implies B ? . | @ ! ) . This is a lot simpler than the opposite implication we just talked about. It's again one of those horizontal branch programs, like the one for and. If A is 0, it simply gets incremented to 1 on the bottom branch and printed. Otherwise, the top branch is executed again where ? reads B and then ! prints that instead. There's a ton of alternatives here (66 solutions in total), mostly due to free choice of effective no-ops. For a start we can vary the above solution in all the same ways we could for and and we can also choose between ) and 1: ?.|@!) .?|@!) ?=|@!) =?|@!) ?_|@!) _?|@!) ?0|@!) ?.|@!1 .?|@!1 ?=|@!1 =?|@!1 ?_|@!1 _?|@!1 ?0|@!1 ?.>@!) .?>@!) ?=>@!) =?>@!) ?_>@!) _?>@!) ?0>@!) ?.>@!1 .?>@!1 ?=>@!1 =?>@!1 ?_>@!1 _?>@!1 ?0>@!1 And then there's a different version using conditional IP selection, where the first command can be chosen almost arbitrarily, and there is also a choice between ) and 1 for some of those options: "?#1!@ &?#1!@ '?#1!@ )?#1!@ *?#1!@ +?#1!@ -?#1!@ .?#1!@ 0?#1!@ 1?#1!@ 2?#1!@ 3?#1!@ 4?#1!@ 5?#1!@ 6?#1!@ 7?#1!@ 8?#1!@ 9?#1!@ =?#1!@ ^?#1!@ _?#1!@ {?#1!@ }?#1!@ "?#)!@ &?#)!@ '?#)!@ *?#)!@ +?#)!@ -?#)!@ 0?#)!@ 2?#)!@ 4?#)!@ 6?#)!@ 8?#)!@ ^?#)!@ _?#)!@ {?#)!@ }?#)!@ ### 1110: Nand ?$
@ # )
! <

The last complicated one. If you're still reading, you've almost made it. :) Let's look at A = 0 first:

? reads A and then we hit $. This is a jump command (like Befunge's #) which skips the next instruction so that we don't terminate on the @. Instead the IP continues at #. However since A is 0, this doesn't do anything. ) increments it to 1 so that the IP continues on the bottom path where the 1 is printed. The < deflects the IP to the right where it wraps to the left corner and the program terminates. Next, when the input is (A, B) = (1, 0) we get this situation: It's essentially the same as before except that at the # we switch to IP 1 (green path), but since B is 0 we switch back to IP 0 when we hit # a second time (now blue path), where it prints 1 as before. Finally, the A = B = 1 case: This time, when we # the second time, the current value is still 1 so that we don't change the IP again. The < reflects it and the third time we hit ? we get a zero. Hence the IP wraps to the bottom left where ! prints the zero and the program ends. There are nine 7-byte solutions in total for this. The first alternative simply uses 1 instead of ): ?$@#1!<

Then there's two solutions that will do your head in with the amount of IP switching that's going on:

)?#_[!@    1?#_[!@

These actually blew my mind: the interesting part is that IP switching can be used as a deferred conditional. The language's IP-switching rules are such that the current IP makes another step before the switch happens. If that step happens to go through a corner, then the current value decides on which branch the IP will continue if we ever switch back to it. Exactly this happens when the input is A = B = 1. Although this is all consistent with how I designed the language, I was never aware of this implication of the spec, so it's nice when my language teaches me some new tricks :D.

Then there's a third solution whose amount of IP switching is even worse (although it doesn't make use of that deferred conditional effect):

>?1]#!@

And then there's another one:

?$@#)!< And then there's these four equivalent solutions, which do use some non-conditional IP switching and instead implement all the logic via branches and corners: ]<?<@!) ]<?<@!1 ]|?<@!) ]|?<@!1 ### 1111: True 1 ! @ . . . . You've earned yourself something simple for the end: set edge to 1, print with !, terminate with @. :) Of course, there's one alternative: )!@ As usual, all control flow diagrams created with Timwi's HexagonyColorer and the memory diagram with his EsotericIDE. • Aaaaaand the tl;dr award goes to... (kidding obviously, great answer and very well written out, +1) Jul 22, 2016 at 15:15 • This is the reason you are not active on chat anymore?? Jul 30, 2016 at 6:32 • Sort of late, but could you add a link to your brute force code? Feb 3, 2017 at 21:48 • @nedla2004 I usually don't keep them around, but it's always a modified version of this script. Feb 3, 2017 at 22:19 # APL, 2220 18 bytes The true and false entries are complete programs, and the other 14 are functions. (Thanks to Adám.) 0000 false 0 (complete program) 0001 p and q ∧ 0010 p and not q > 0011 p ⊣ 0100 not p and q < 0101 q ⊢ 0110 xor ≠ 0111 p or q ∨ 1000 not p and not q ⍱ 1001 eq = 1010 not q ~⊢ 1011 p or not q ≥ 1100 not p ~⊣ 1101 not p or q ≤ 1110 not p or not q ⍲ 1111 true 1 (complete program) Try it here. • +1 Nice use of atops! You can save two bytes by making 0000 and 1111 into trad-fns 0 and 1. – Adám Jun 15, 2016 at 8:11 • There is a consensus to allow tfns, but not to count the first line. This corresponds to not counting the filename in languages that use files as program containers with program name = filename. – Adám Jun 15, 2016 at 10:24 • – Adám Jun 15, 2016 at 10:32 • Jelly: 19 bytes. This: 18 bytes. Doesn't this mean that you outgolfed Dennis? +1 for that. Jun 16, 2016 at 17:21 # Chess/mediocre chess player in endgame, 70 pieces Inspired by that domino answer, I decided another game should have this honor. Note that I took a few rules for how the pieces move. Because I don't feel like studying the optimal moves for every situation, the rules for whites move is simple: Stay out of check, capture the highest ranking piece he can that turn, while losing as little material as possible, and stop a pawn from promoting, in that order of priority. If there are two spaces he can move to, with equal favourability, he can move to either (hence in these, if he can move to more than one square, they are the same colour). Note that white will capture with something even if it gets captured, if the piece it is attacking is higher value than the one lost. Values are here:pawn<knight=bishop<rook<queen The input is whether a rook is present or not. Note that rooks are only labelled with names A and B when it matters: if the gate behaves the same when the rooks are switched, they are not labelled. The output is the colour of the square white king ends on: White=1, black=0 Before the images, I want to apologise for poor images. I'm not much good at holding a camera steady. False, 4: AND, 4: A and not B, 5 (I think I can get this down to three, but do not have board right now): A, 4: Not A and B,5 (I think I can get this down to three, but do not have board right now): B, 4: Xor,5 (I know a way to make it 4, but I don't have the board right now): Or, 4: Nor, 4: Xnor, 5 (I know a way to make it 4, but I don't have the board right now): Not B, 4: B implies A, 5 (I think I can get this down to three, but do not have board right now): Not A, 4: A implies B, 5 (I think I can get this down to three, but do not have board right now): Nand, 4: True, 4: • Wow, I had no idea that programming in chess was possible... Could you post a video/simulation of a few of these in action? Sep 5, 2016 at 9:50 • hmmm, I currently don't have access to the chess board. I would probably say that the A implies B/B implies a/etc are hardest to understand due to the effect of pawns on the kings movement. I should probably add better explanation for those two Sep 5, 2016 at 9:58 • Glad to inspire :D If I am understanding correctly, the board and piece locations are equivalent to a program. The rooks are the input, so I can place them on any square as long as it is the right color? Sep 6, 2016 at 1:44 • No, the input of the rooks is whether they are present or absent from the board. They are labelled a and b when they are not symmetrical gates (when it matters the different a and b). Also I realised how I could golf off 2 pieces, but I don't have the board right now. Paintbrush must be utilised :) Sep 6, 2016 at 2:18 • On your "And" case, if you remove the right rook, what's stopping the king from moving down (to white)? Oct 18, 2016 at 15:01 # Jelly, 19 bytes 0 0 0 0 ¤ 1 byte Empty niladic chain. Returns default argument 0. 0 0 0 1 & 1 byte Bitwise AND. 0 0 1 0 > 1 byte Greater than. 0 0 1 1 0 bytes Empty link. Returns left argument. 0 1 0 0 < 1 byte Less than. 0 1 0 1 ị 1 byte At-index (x,y -> [y][x]). Returns right argument. 0 1 1 0 ^ 1 byte Bitwise XOR. 0 1 1 1 | 1 byte Bitwise OR. 1 0 0 0 |¬ 2 byte Logical NOT of bitwise OR. 1 0 0 1 = 1 byte Equals. 1 0 1 0 ¬} 2 bytes Logical NOT of right argument. 1 0 1 1 * 1 byte Exponentiation. 1 1 0 0 ¬ 1 byte Logical NOT of left argument. 1 1 0 1 >¬ 2 bytes Logical NOT of greater than. 1 1 1 0 &¬ 2 bytes Logical NOT of bitwise AND. 1 1 1 1 ! 1 byte Factorial. Try it online! • I love the use of Factorial to convert either 0 or 1 to 1. – Neil Jun 15, 2016 at 8:33 • Is Jelly UTF-8? If yes then ¤ and ¬ are 2 bytes, not 1. – Vi. Sep 29, 2016 at 20:10 • @Vi. Jelly supports UTF-8, but it also supports a custom code page that encodes each of the 256 characters it understands as a single byte each. The bytes link in the header points to it. Sep 29, 2016 at 20:12 • 0 0 1 0 > 1 byte Greater than. wouldn't this fail if the second input was negative? Jun 17, 2017 at 21:28 • @MFXF We can choose which truthy and which falsy value we support. Jun 17, 2017 at 21:31 # Bitwise Cyclic Tag, 118 bits = 14.75 bytes Bitwise Cyclic Tag is perhaps the simplest Turing-complete language ever devised. There is a program tape and a data tape, both consisting of a list of bits. The program tape is interpreted cyclically until the data tape is empty, as follows: • 0: delete the first bit from the data tape. • 1x: if the first bit of the data tape is 1, append the bit x to the data tape. We initialize the data tape with a 1 followed by the two input bits (the 1 is necessary because there is no way to create a 1 if the data tape consists entirely of 0s), and we use the final deleted data bit as the gate’s output. • 0,0,0,0 (false): 001 • 0,0,0,1 (and): 1001001 • 0,0,1,0 (A and not B): 0110100 • 0,0,1,1 (A): 1001 • 0,1,0,0 (not A and B): 0100 • 0,1,0,1 (B): 0 • 0,1,1,0 (xor): 0110110010 • 0,1,1,1 (or): 0110 • 1,0,0,0 (nor): 1101001000 • 1,0,0,1 (xnor): 110101001100 • 1,0,1,0 (not B): 1100100 • 1,0,1,1 (B implies A): 110101101000 • 1,1,0,0 (not A): 11010000 • 1,1,0,1 (A implies B): 11010011001 • 1,1,1,0 (nand): 10110100100010 • 1,1,1,1 (true): 1100 • Is the trailing 1 on false required? Jun 18, 2017 at 15:48 • @CalculatorFeline Yes, we need to append a 0 to the tape so it can be deleted last. Jun 18, 2017 at 18:51 • Ah. Forgot about that+wrapping. Clever! Jun 18, 2017 at 21:34 # NAND logic gates — 31 gates As the creator of the original series of NAND gate questions, I couldn't pass up the opportunity to use these gates to solve another logic gate problem. In each of these diagrams, the top input is A while the bottom input is B. • @xnor might be flattered to know that his logic gate is the one that requires the most NAND gates to make D: Jun 16, 2016 at 20:21 • @mbomb007 I'll edit that in later. I'm not so experienced with Logisim, so it might take a while. Jun 16, 2016 at 20:25 • But I like handwriting better. Jun 16, 2016 at 20:31 • For those wondering, "cex" is short for "counterexample", as in "counterexample to an implication". Jun 17, 2016 at 11:46 • Alternatively you could switch to nor gate and format it using redstone... Jun 22, 2016 at 5:38 ## Python 2, 137 bytes [].sort min int.__rshift__ round range {}.get cmp max lambda a,b:a<1>b lambda a,b:a==b lambda a,b:b<1 pow {0:1,1:0}.get {0:1}.get lambda a,b:a+b<2 slice Takes inputs like min(True,False) (or as min(1,0)). Takes heavy advantage of outputs only needing to have the right Truthy-Falsey value. Whenever possible, uses a built-in to avoid a costly lambda. I used code to search for built-ins that work. My favorite one is {0:1}.get, which I thought of by hand. The dictionary {0:1} maps the key 0 to the value 1. Its get method takes a key and a default, outputting the value matching the key, or the default if there's no such key. So, the only way to output a 0 is as {0:1}.get(1,0), with missing key 1 and default 0. One can get other variants with different dictionaries, but only this one was the shortest. built_in_names = list(__builtins__) object_names = ["int","(0)","(1)"] + \ ["True","False","0L","1L","0j","1j"] + \ ["str", "''", "'0'","'1'","'a'"] + \ ["list", "[]", "[0]", "[1]","['']","[[]]","[{}]"] + \ ["set","set()","{0}","{1}","{''}"] + \ ["dict","{}","{0:0}","{0:1}","{1:0}","{1:1}","{0:0,1:0}", "{0:0,1:1}","{0:1,1:0}","{0:1,1:1}"] + \ ["id"] object_method_names = [object_name+"."+method_name for object_name in object_names for method_name in dir(eval(object_name))] additional_func_names = [ "lambda a,b:0", "lambda a,b:1", "lambda a,b:a", "lambda a,b:b", "lambda a,b:b<1", "lambda a,b:a<1", "lambda a,b:a+b", "lambda a,b:a*b", "lambda a,b:a==b", "lambda a,b:a-b", "lambda a,b:a<=b", "lambda a,b:a>=b", "lambda a,b:a>b", "lambda a,b:a<b", "lambda a,b:a<1>b", "lambda a,b:a+b<2"] func_names = built_in_names + object_method_names + additional_func_names t=True f=False cases = [(f,f),(f,t),(t,f),(t,t)] def signature(func): table = [bool(func(x,y)) for x,y in cases] table_string = ''.join([str(int(val)) for val in table]) return table_string d={} for func_name in func_names: try: func = eval(func_name) result = signature(func) if result not in d or len(func_name)<len(d[result]): d[result]=func_name except: pass total_length = sum(len(func) for sig,func in d.items()) print total_length print for sig in sorted(d): print d[sig] • Can't you use methods of built-ins like int's __lt__ or __eq__? These will further decrease byte count: int.__gt__ instead of lambda a,b:b<1, int.__eq__ instead of lambda a,b:a==b and so on Jul 29, 2016 at 11:05 • @GáborFekete Those don't exist in Python 2 because ints offload comparisons to cmp. I haven't tried this for Python 3. – xnor Jul 29, 2016 at 11:11 • Oh right now I see! Jul 29, 2016 at 11:24 • Save 4 bytes by using the function not for 0001, False - ideone Sep 4, 2016 at 1:52 • @JonathanAllan That's clever, but I think that not doesn't meet the requirements of a function because you can't do f=not;f(3,4). The string not happens to work because the supposed function arguments look like a tuple, just as 3+ would work as 3+(4) even though 3+ as not a function that can take 4 as an input. – xnor Sep 4, 2016 at 22:35 # Go (game), 33 stones, 73 intersections If domino and chess are acceptable, then this. It can't be too golfy on a full 19x19 Go board. So I used small rectangular boards. The input is whether the stones marked 1 and 2 are present. The output is whether black wins. It uses area scoring, 0.5 komi, situational superko, no suicide. All black to play. Some are given multiple solutions. White wins (2, 1x5): ➊━━━➋ 1 and 2 (3, 2x3): ➊◯➋ ┗┷┛ 1 and not 2 (2, 1x5): ╺➊━➁╸ 1 (2, 1x5): ╺➊➁━╸ ╺➊━━➁ ➀━➁━╸ Not 1 and 2 (2, 1x5): ╺➋━➀╸ 2 (2, 1x5): ╺➋➀━╸ 1 xor 2 (2, 2x3): ➀┯➁ ┗┷┛ 1 or 2 (2, 1x5): ╺➊━➋╸ ➀━━━➁ 1 nor 2 (2, 1x4): ➊━━➋ ╺➀➁╸ 1 = 2 (2, 1x7): ╺━➀━➁━╸ Not 2 (2, 1x3): ➀➁╸ 1 or not 2 (2, 1x4): ➀➁━╸ ➀━➁╸ ╺➊➁╸ ➋➊━╸ ➋━➊╸ Not 1 (2, 1x3) ➁➀╸ Not 1 or 2 (2, 1x4): ➁➀━╸ 1 nand 2 (2, 1x3): ➊━➋ Black wins (2, 1x3): ➊➋╸ ➀━➁ ➊━➁ This page helped me a bit: http://www.mathpuzzle.com/go.html Maybe someone could find a 2 stone solution for 1 and 2 on a 1x9 board... • What are your rules for suicide? Disallowed? And what happens when one side fills the entire board? Is that considered suicide? Sep 23, 2016 at 14:25 • @MartinEnder Disallowed. And yes, that's considered suicide. Sep 23, 2016 at 16:43 • The 1x7 solution seemed wrong. I'm trying to fix it... Oct 4, 2016 at 0:36 # Javascript ES6, 124 bytes a=>0 Math.min parseInt a=>a a=>b=>a<b a=>b=>b a=>b=>a^b Math.max a=>b=>~a&~b a=>b=>a==b a=>b=>~b Math.pow a=>~a a=>b=>a<=b a=>b=>~a|~b a=>1 I seriously hate lambdas right now. • If I'm allowed to write some programs and some functions... I think you could change a=>b=>0 to a=>0 and say the grammar calling it is (a=>0)(a,b), only for those 4 entries. Jun 15, 2016 at 11:33 • Math.min instead of a=>b=>a&b. Math.max instead of a=>b=>a|b. Math.pow instead of a=>b=>a>=b. Jun 16, 2016 at 0:37 • Also, since NaN is falsey, you can do parseInt instead of a=>b=>a>b. Jun 16, 2016 at 21:11 • @algmyr !NaN => true, !!NaN => false Jul 29, 2016 at 14:14 • Now it is much more clear. Thank you! Jan 27 at 13:32 # Retina, 62 39 bytes 23 bytes thanks to @MartinEnder! 0000 false 1 byte : 2 0001 p and q 2 bytes: 11 0010 p and not q 2 bytes: 10 0011 p 2 bytes: ^1 0100 not p and q 2 bytes: 01 0101 q 2 bytes: 1$
0110 xor                5 bytes: 01|10
0111 p or q             1 byte : 1
1000 not p and not q    2 bytes: 00
1001 xnor               5 bytes: (.)\1
1010 not q              2 bytes: 0$1011 p or not q 5 bytes: ^1|0$
1100 not p              2 bytes: ^0
1101 not p or q         5 bytes: ^0|1$1110 not p or not q 1 byte : 0 1111 true 0 bytes: Takes input as PQ. Outputs an integer between 0 to 3. 0 is falsey, others are truthy. ## Explanation They are all just regexes. For example, 01|10 just matches 01 or 10. In 0000, 2 will never be in the input, so it never matches. In 1111, it matches the empty string, which there are 4. • ^1|0$ should only match 1 character strings. What's going on here? Mar 2, 2017 at 15:44
• @CalculatorFeline It matches [1 at beginning of input] OR [0 at end of input]. Took me a minute to get it too... Aug 18, 2017 at 3:46
• Precedence, guys.... Aug 18, 2017 at 4:07
• I guess ^1|0$is harder to read than 1.|.0. Seems to make reading harder in all – l4m2 Dec 7, 2017 at 5:25 ## Stack Cats, 67 + 64 = 131 bytes Note that the +64 is from applying the -nm flags to each program. -n indicates numeric I/O, and -m mirrors the source code across the last character - not all submissions need these flags technically, but for consistency and simplicity I'm scoring them all the same way. -2 -2 -3 -3 !I 0 0 0 0 <I!+ -4 -4 -4 1 |!T*I 0 0 0 1 [>I=I_ -4 -4 3 -2 *I*_ 0 0 1 0 :I*=I: -2 -2 3 3 T*I 0 0 1 1 [<!>X -2 1 -2 -2 _*T*I 0 1 0 0 *|!TI: -2 1 -3 1 !-|_I 0 1 0 1 <!I!>X -2 3 3 -2 ^T*I 0 1 1 0 ^:]<_I -2 3 3 3 -_T*I 0 1 1 1 *I<-I! 2 -3 -3 -3 -*|_I 1 0 0 0 ^{!:}I_ 2 -3 -3 2 _|*I 1 0 0 1 _|[<I!: 1 -2 1 -2 :]I*: 1 0 1 0 _!:|]X 1 -2 1 1 *I\<X 1 0 1 1 *>I>!I 2 2 -3 -3 -*I 1 1 0 0 I^:! 2 2 -3 2 _*I_ 1 1 0 1 |I|^:! 1 2 2 -1 |!:^I 1 1 1 0 -I*<*I 1 1 1 1 *<X 1 1 1 1 +I+ () in Stack Cats checks whether an element is positive or nonpositive (i.e. 0 or negative), so we're using that for truthy/falsy respectively. The second column is just for interest, and lists the best gates with 0/1s as outputs (with total score 90). Input is delimiter-separated bits via STDIN. Try it online! Stack Cats is a reversible esoteric language, where programs have reflective symmetry. Given a snippet f (e.g. >[[(!-)/), the mirror image (e.g. \(-!)]]<) computes the inverse f^-1. As such, even length programs do nothing (or get stuck in an infinite loop), and the only non-trivial programs have odd length, computing f g f^-1 where g is the centre operator. Since half the source code is always redundant, it can be left out, and running the code with the -m flag indicates that the source code should be mirrored over the last character to retrieve the actual source code. For example, the program *<X is actually *<X>*, which is symmetrical. Golfing in Stack Cats is highly unintuitive, so the above programs had to be found by brute force. Most of them are surprisingly complex, but I'll explain a few and add to this answer when I have time. For now, some explanations and alternative solutions for the 0/1 versions can be found on the Github repository here. • Note that the +64 is from applying the -nm flags to each program. 3 * 16 = 48 or 2 * 16 = 32, either way 64 is way hai – cat Jun 15, 2016 at 22:32 • @cat The flags cost 4 per program, as you have to count the space as well. Jun 16, 2016 at 0:55 • @cat relevant meta post: meta.codegolf.stackexchange.com/questions/273/… Jun 16, 2016 at 5:23 • It's been over a year. Do you have time yet? Jun 18, 2017 at 15:52 # Minecraft, 89 blocks In all of the following photos, blue blocks are for Input A and orange blocks are for Input B ## 16. TRUE gate - 1 blocks ## 15. NAND gate - 1x2x3 = 6 blocks ## 14. A=>B - 1x2x3 = 6 blocks ## 13. NOT A - 2 blocks ## 12. B=>A - 1x2x3 = 6 blocks ## 11. NOT B - 2 blocks ## 10. XNOR - 1x3x4 = 12 blocks ## 9. NOR - 1x2x3 = 6 blocks ## 8. OR - 1 blocks ## 7. XOR - 1x3x4 = 12 blocks ## 6. B - 1 blocks ## 5. !A&B - 1x2x5 = 10 blocks ## 4. A - 1 blocks ## 3. A&!B - 1x2x5 = 10 blocks ## 2. AND - 2x2x3 = 12 blocks ## 1. FALSE- 1 blocks • In the second to last image (AND) you could save 6 blocks by putting the torches on top to the back of the blocks, i.e. opposite to the levers. Swap the torch in the middle for a piece of dust and remove the dust at the top, bringing it down to 1x2x3=6 blocks. Nov 23, 2017 at 11:12 ## Haskell, 7876 75 bytes 1. _#_=2<1 2. && 3. > 4. pure 5. < 6. _#b=b 7. /= 8. || 9. (not.).max 10. == 11. _#b=not b 12. >= 13. a#_=not a 14. <= 15. (not.).min 16. _#_=1<2 Edit: -1 byte thanks to @cole. • I was just about to comment "dude, _#_ isn't a standard operator!" And then I realised... Well done. Jun 16, 2016 at 14:09 • 4 could be pure – cole Jul 28, 2019 at 0:32 • @cole: Thanks. Wow, pure was introduced into Prelude back in 2015, so it was available at the time of this challenge. – nimi Jul 28, 2019 at 1:16 # dc, 37 bytes dc ("desk calculator") is a standard unix command, a stack-based postfix calculator. It lacks bit operations, and comparison operators can only be used to execute macros (which is not worth the bytes). Integer division makes up for some of that. These scripts expect 0 and 1 values on the stack, and leave the result on the stack. 0,0,0,0 (false) 0 0,0,0,1 (and) * a*b 0,0,1,0 -1+2/ (a-b+1)/2 0,0,1,1 (A) r reverse a, b: a now on top 0,1,0,0 -1-2/ (a-b-1)/2 0,1,0,1 (B) (0 bytes) do nothing: b on top 0,1,1,0 (xor) - a-b 0,1,1,1 (or) + a+b 1,0,0,0 (nor) +v1- sqrt(a+b) -1 1,0,0,1 (xnor) +1- a+b-1 1,0,1,0 (not B) 1- b-1 1,0,1,1 (if B then A) -1+ a-b+1 1,1,0,0 (not A) r1- a-1 1,1,0,1 (if A then B) -1- a-b-1 1,1,1,0 (nand) *1- a*b - 1 1,1,1,1 (true) 1 ## Mathematica, 67 bytes 0>1& And #&&!#2& #& !#&&#2& #2& Xor Or Nor Xnor !#2& #||!#2& !#& !#||#2& Nand 1>0& Each of these evaluates to a function, so you can use them like #&&!#2&[True, False] Xor[True, False] Ah, if only integers were truthy/falsy in Mathematica, those four longer ones could have been shortened considerably. • If integers aren't truthy/falsey, what happens when you put them in an if statement? Jun 22, 2016 at 16:33 • @CᴏɴᴏʀO'Bʀɪᴇɴ it remains unevaluated. Jun 22, 2016 at 16:39 # Brachylog, 36 34 bytes 0000 false \ Backtrack (always false) 0001 p and q 1. Unify input and output with 1 0010 p and not q >. Input > Output 0011 p 1 Unify input with 1 0100 not p and q <. Input < Output 0101 q ,1. Unify output with 1 0110 xor '. Input and output cannot unify 0111 p or q 1;1. Unify input with 1 or unify output with 1 1000 not p and not q 0. Unify input and output with 0 1001 eq . Unify input with output 1010 not q ,0. Unify output with 0 1011 p or not q >=. Input >= Output 1100 not p 0 Unify input with 0 1101 not p or q <=. Input <= Output 1110 not p or not q 0;0. Unify input with 0 or unify output with 0 1111 true Empty program (always true) This expects 0 as falsy value and 1 as truthy value. Returns true or false. p is Input and q is Output. • How do you input the output? Jun 15, 2016 at 6:59 • @LeakyNun Just like the input. The main predicate you query has two arguments, called Input and Output by convention, but you can set values to both, or return values from both. Jun 15, 2016 at 7:01 • This is the right tool for the job :P Jun 15, 2016 at 21:03 # MATL, 34 23 bytes I hope I got the order all right! Zero is falsey, non-zero is truthy. Each function takes two implicit inputs (although it may ignore some inputs). The first input is A, and the second is B. You can input 0/1 for true/false, or T/F. Here is a TryItOnline example for test case 3. Saved 4 bytes by using * for and, and another 4 by using >/< instead of ~wY&/w~Y& after I saw Dennis' answer! 1. 0,0,0,0 0 (ignores input, just returns a zero) 2. 0,0,0,1 * (and) 3. 0,0,1,0 < (not-A and B) 4. 0,0,1,1 D (A) 5. 0,1,0,0 > (not-B and A) 6. 0,1,0,1 xD (discard A, display B) 7. 0,1,1,0 Y~ (xor) 8. 0,1,1,1 + (or) 9. 1,0,0,0 +~ (not-or) 10. 1,0,0,1 = (A=B) 11. 1,0,1,0 x~ (not-B) 12. 1,0,1,1 <~ (not-B or A) 13. 1,1,0,0 ~ (not-A) 14. 1,1,0,1 ~+ (not-A or B) 15. 1,1,1,0 *~ (not(A and B)) 16. 1,1,1,1 1 (just returns 1) • Number six thinks it's funny. Jun 15, 2016 at 3:06 • @CᴏɴᴏʀO'Bʀɪᴇɴ Number 6 is the best, I like number 12 too! xD! Jun 15, 2016 at 3:19 • Don't you have the "unequal" function? Jun 15, 2016 at 5:27 • No (I don't think so at least) Jun 15, 2016 at 5:31 • @David I think number 7 can be replaced by - Jun 15, 2016 at 9:30 # Prolog, 147 145 bytes Gained 2 bytes thanks to @SQB a(a,a). % 0000 false b(1,1). % 0001 P and Q c(1,0). % 0010 P and not Q d(1,_). % 0011 P e(0,1). % 0100 not P and Q f(_,1). % 0101 Q g(P,Q):-P\=Q. % 0110 P xor Q h(1,_). % 0111 P or Q h(0,1). i(0,0). % 1000 not P and not Q j(P,P). % 1001 P == Q k(_,0). % 1010 not Q m(P,Q):-P>=Q. % 1011 P or not Q n(0,_). % 1100 not P r(P,Q):-P=<Q. % 1101 not P or Q s(0,_). % 1110 not P or not Q s(1,0). t(_,_). % 1111 true Query x(P,Q). with x being the appropriate letter and P and Q set to either 0 or 1. Returns true or false. SWISH example including tests - enter runTest. to run. • Does it support a(2,2). for false? Jun 15, 2016 at 7:54 • @jimmy23013 I guess it could if I assume that 2 is falsy. Not sure if that's acceptable. Jun 15, 2016 at 7:55 • @jimmy23013 Actually, a(a,a). (or any other letter) works too and a is not an acceptable input for truthness, so that's good. Thanks for the suggestion. Jun 15, 2016 at 8:03 • You can save a couple more bytes by turning the multiline definitions into inequalities: h(P,Q):-P+Q>0. and s(P,Q):-P+Q<2. Sep 3, 2022 at 17:04 # NTFJ, 86 bytes 0000 false ~ 0001 p and q |:| 0010 p and not q :||:| 0011 p$
0100 not p and q        #{:||:|
0101 q                  #{$0110 xor :#{:#{:||#}:||| 0111 p or q :|#{:|| 1000 not p and not q :|#{:||:| 1001 eq :#{:#{:||#}:|||:| 1010 not q #{$:|
1011 p or not q         #{:||

$pops an item from the stack. So... yeah. ## 4: not p and q #{:||:| This is the same thing as 2, except with #{ at the beginning. # pushes 1 (the true bit) and { rotates the stack left once. Simple enough. ## 5: q #{$

Rotate left once, drop.

## 6: xor

:#{:#{:||#}:|||

Observe:

p xor q = (p and (not q)) or ((not p) and q)                ; by experimentation (trust me)
= (not ((not p) nand q)) or (not (p nand (not q)))  ; by definition of nand
= not (((not p) nand q) and (p nand (not q)))       ; by De Morgan's laws
= ((not p) nand q) nand (p nand (not q))            ; by definition of nand

However, there is no way to duplicate the stack entirely. So, we're going to have to bring each of p, q to the top and duplicate it.

Command | Stack
| p q
:    | p q q
#{    | q q p
:    | q q p p
#{    | q p p q
:|    | q p p (not q)
|    | q p (p nand (not q))
#}    | (p nand (not q)) q p
:|    | (p nand (not q)) q (not p)
|    | (p nand (not q)) (q nand (not p))
|    | (p nand (not q)) nand (q nand (not p))

And thus, we have our xor.

## 7: p or q

:|#{:||

Negate top, bring bottom to top, negate that, and nand them together. Basically, p or q = (not p) nand (not q).

## 8: not p and not q

:|#{:||:|

This is simply the negation of 7. Easy.

## 9: eq

:#{:#{:||#}:|||:|

This is just xnor, or not xor. Simple again.

#{$:| Negation of 5. ## 11: p or not q #{:|| Negate p, nand. (not p) nand q = not ((not p) and q) = p or (not q) (by De Morgan's laws). ## 12: not p$:|

Drop, stop, and negate.

## 13: not p or q

:||

De Morgan's laws to save the day, again! Same process as 11, just negating q instead of p.

## 14: not p or not q

|

This is just a mimic nand.

## 15: true

#

# is the true bit.

• just why... >_> Jun 15, 2016 at 21:36
• idk exactly how this works but it seems pretty cool +1 Jun 15, 2016 at 21:37
• Why isn't 5 just an empty program, and 10 just :|? Jul 29, 2016 at 14:09

# IA-32 machine code, 63 bytes

Hexdump of the code, with the disassembly:

0000  33 c0     xor eax, eax;
c3        ret;

0001  91        xchg eax, ecx;
23 c2     and eax, edx;
c3        ret;

0010  3b d1     cmp edx, ecx;
d6        _emit 0xd6;
c3        ret;

0011  91        xchg eax, ecx;
c3        ret;

0100  3b ca     cmp ecx, edx;
d6        _emit 0xd6;
c3        ret;

0101  92        xchg eax, edx;
c3        ret;

0110  91        xchg eax, ecx;
33 c2     xor eax, edx;
c3        ret;

0111  8d 04 11  lea eax, [ecx + edx];
c3        ret;

1000  91        xchg eax, ecx; // code provided by l4m2
09 d0     or eax, edx;
48        dec eax;
c3        ret;

1001  3b ca     cmp ecx, edx;
0f 94 c0  sete al;
c3        ret;

1010  92        xchg eax, edx;
48        dec eax;
c3        ret;

1011  39 d1     cmp ecx, edx; // code provided by l4m2
d6        _emit 0xd6;
40        inc aex;
c3        ret;

1100  91        xchg eax, ecx;
48        dec eax;
c3        ret;

1101  3b d1     cmp edx, ecx; // code inspired by l4m2
d6        _emit 0xd6;
40        inc aex;
c3        ret;

1110  8d 44 11 fe   lea eax, [ecx+edx-2] // code provided by l4m2
c3        ret;

1111  91        xchg eax, ecx;
40        inc eax;
c3        ret;

The code is longer than it could be, because it uses a standard coding convention: input in ecx and edx, and output in al. This may be expressed in C as

unsigned char __fastcall func(int, int);

It seems that MS Visual Studio doesn't understand the undocumented SALC opcode, so I had to use its code, instead of name.

Thanks you l4m2 for improving some of the code samples!

• 1110 8D4411FE LEA EAX, [ECX+EDX-2]
– l4m2
Dec 18, 2017 at 9:13

# C 34 bytes

#define g(n,a,b)((n-1)>>3-b-2*a)&1

Where n is the function number to use, but I think it would be refused so I propose this other one:

# C 244 bytes (using memory)

typedef int z[2][2];
z a={0,0,0,0};
z b={0,0,0,1};
z c={0,0,1,0};
z d={0,0,1,1};
z e={0,1,0,0};
z f={0,1,0,1};
z g={0,1,1,0};
z h={0,1,1,1};
z i={1,0,0,0};
z j={1,0,0,1};
z k={1,0,1,0};
z l={1,0,1,1};
z m={1,1,0,0};
z n={1,1,0,1};
z o={1,1,1,0};
z p={1,1,1,1};

it uses double indexed array. n[0][1] is (A implies B)(0,1)

# Forth 138 bytes

I just learned Forth. I suppose that's Ansi Forth compatible as it run also on gforth.

: z create dup , 1+ does> @ -rot 3 swap - swap 2* - rshift 1 and ;
0
z a z b z c z d z e z f z g z h z i z j z k z l z m z n z o z p
drop

Function z create a new function with the name provided then put the logic gate number from the top of stack to the new function address. It leaves the next (n+1) logic gate function in the stack for the next declaration.

you can test it :
And A B

0 0 b . cr
0 1 b . cr
1 0 b . cr
1 1 b . cr

( "." print top of stack "cr" is cariage return )

• You only have to provide snippets of code for each function. Jun 18, 2017 at 15:57

## Labyrinth, 85 bytes

Thanks to Sp3000 for saving 2 bytes.

!@
??&!@
??~&!@
?!@
?~?&!@
??!@
??$!@ ??|!@ ??|#$!@
??$#$!@
?#?$!@ ?#?$|!@
?#$!@ ?#$?|!@
??&#$!@ 1!@ All of these are full programs, reading two integers 0 or 1 from STDIN (using any non-digit separator), and printing the result as 0 or 1 to STDOUT. Try it online! (Not a test suite, so you'll have to try different programs and inputs manually.) As for explanations, these are all rather straightforward. All programs are linear, and the commands in use do the following: ? Read integer from STDIN and push. ! Pop integer and write to STDOUT. @ Terminate program. & Bitwise AND of top two stack items. | Bitwise OR of top two stack items.$   Bitwise XOR of top two stack items.
~   Bitwise NOT of top stack item.
#   Push stack depth (which is always 1 when I use it in the above programs).
1   On an empty stack, this pushes 1.

Note that I'm using # is always used to combine it with \$, i.e. to compute XOR 1, or in other words for logical negation. Only in a few cases was I able to use ~ instead, because the subsequent & discards all the unwanted bits from the resulting -1 or -2.

# Brainfuck, 184178 174 bytes

Input/output uses U+0000 and U+0001.

0000 .
0001 ,[,[->+<]]>.
0010 ,[,-[+>+<]]>.
0011 ,.
0100 ,-[,[->+<]]>.
0101 ,,.
0110 ,>,[-<->]<[>>+<]>.
0111 ,-[,-[+>-<]]>+.
1000 ,-[,-[+>+<]]>.
1001 ,>,[-<->]<[>>-<]>+.
1010 ,,-[+>+<]>.
1011 ,-[,[->-<]]>+.
1100 ,-[+>+<]>.
1101 ,[,-[+>-<]]>+.
1110 ,[,[->-<]]>+.
1111 +.
• Your reading a conditional second input looks expensive. E.g. for 0001 couldn't you just do ,[,>]<. (given an interpreter which allows you to go left of the starting cell)? Jul 28, 2016 at 7:15
• @MartinEnder I figured that I wouldn't just copy Dennis' answer here. Jul 28, 2016 at 7:21

# C, 268 bytes

#define c(a,b)0      // 0000
#define d(a,b)a&b    // 0001
#define e(a,b)a>b    // 0010
#define f(a,b)a      // 0011
#define g(a,b)a<b    // 0100
#define h(a,b)b      // 0101
#define i(a,b)a^b    // 0110
#define j(a,b)a|b    // 0111
#define k(a,b)!b>a   // 1000
#define l(a,b)a==b   // 1001
#define m(a,b)!b     // 1010
#define n(a,b)!b|a   // 1011
#define o(a,b)!a     // 1100
#define p(a,b)!a|b   // 1101
#define q(a,b)!b|!a  // 1110
#define r(a,b)1      // 1111

Macros seem shorter than functions.

## Brian & Chuck, 183 bytes

Thanks to Sp3000 for saving 4 bytes.

Some of the programs contain an unprintable character. In particular, every \x01 should be replaced with the <SOH> (0x01) control character:

0000
?
#>.
0001
,-?,-?>?\x01
#}>.
0010
,-?,?>?\x01
#}>.
0011
,?\x01+?
#>.
0100
,?,-?>?\x01
#}>.
0101
,,?\x01+?
#>.
0110
,?>},?>?_\x01
#}+{>?_}>.
0111
,\x01?,?>?
#{>.
1000
,?,?>?\x01
#}>.
1001
,-?>},?>?_\x01
#}+{>>?_}>.
1010
,,-?\x01+?
#>.
1011
,\x01?,-?>?
#{>.
1100
,-?\x01+?
#>.
1101
,\x01-?,?>?
#{>.
1110
,\x01-?,-?>?
#{>.
1111
?
#>+.

Input and output use byte values, so input should be two 0x00 or 0x01 bytes (without separator) and output will be one such byte. This is actually also the most sensible definition of truthy/falsy for B&C because the only control flow command ? regards zeros as falsy and everything else truthy.

### Explanations

First a quick B&C primer:

• Every program consists of two Brainfuck-like instances, each written on its own line. We call the first one Brian and the second one Chuck. Execution begins on Brian.
• Each program's tape is the other program's source code, and each program's instruction pointer is the other program's tape head.
• Only Brian can use the , (input byte) command and only Chuck can use the . (output byte) command.
• Brainfuck's [] loop does not exist. Instead, the only control flow you have is ? which switches control to the other instance iff the current value under the tape head is nonzero.
• In addition to > and <, there's { and } which are essentially equivalent to the Brainfuck snippets [<] and [>], that is, they move the tape head to the next zero position in that direction. The main difference is that { can also be stopped at the left end of the tape, regardless of what value it has.
• For convenience, any _s in the source code are replaced with null-bytes (as these are very useful in nontrivial programs in order to catch { and }).

Note that in all programs, Chuck's tape begins with a #. This could really be anything. ? works such that the tape head moves one cell before starting execution (so that the condition itself isn't executed if it happens to be a valid command). So we can't ever use the first cell of Chuck for code.

There are five classes of programs, which I'll explain in detail later. For now I'm listing them here in order of increasing complexity.

### 0000, 1111: Constant functions

?
#>.
?
#>+.

These are very simple. We switch to Chuck unconditionally. Chuck moves the tape head to the unused cell to the right and either prints it directly, or increments it first to print 1.

### 0011, 0101, 1010, 1100: Functions depending on only one input

,?\x01+?
#>.
,,?\x01+?
#>.
,,-?\x01+?
#>.
,-?\x01+?
#>.

Depending on whether we start with , or ,, we're working with A or B. Let's look at the first example 0011 (i.e. A). After reading the value, we use ? as a conditional on that value. If A = 1, then this switches to Chuck, who moves the tape head to the right and prints the literally embedded 1-byte. Otherwise, control remains on Brian. Here, the 1-byte is a no-op. Then we increment the input well with + to make sure it's non-zero and then switch to Chuck with ?. This time, > moves to an unused cell to the right which is then printed as 0.

In order to negated one of the values we simply decrement it with -. This turns 1 into 0 and 0 into -1, which is non-zero and hence truthy as far as ? is concerned.

### 0001, 0010, 0100, 1000: Binary functions with one truthy result

,-?,-?>?\x01
#}>.
,-?,?>?\x01
#}>.
,?,-?>?\x01
#}>.
,?,?>?\x01
#}>.

This is an extension of the previous idea in order to work with two inputs. Let's look at the example of 1000 (NOR). We (potentially) read both inputs with ,?. If either of those is 1, the ? switches to Chuck. He moves the tape head to the end with } (onto the empty cell after Brian's code), moves another cell with > (still zero) and prints it with ..

However, if both inputs are zero, then control is still with Brian. > then moves the tape head onto the } such that this command isn't executed when we switch to Chuck with ?. Now all that Chuck does is >. which only moves onto the 1-cell and prints that.

We can easily obtain the other three functions by negating one or both of the inputs as required.

### 0111, 1011, 1101, 1110: Binary functions with three truthy results

,\x01?,?>?
#{>.
,\x01?,-?>?
#{>.
,\x01-?,?>?
#{>.
,\x01-?,-?>?
#{>.

A minor modification of the previous idea in order to negated the result (i.e. print 0 when we've passed through all of Brian and 1 otherwise). Let's look at 0111 (OR) as an example. Note that the embedded 1-byte is a no-op, so this still starts with ,?,?. If either input is 1 we switch to Chuck, who moves the tape head back to the start with {. >. moves the tape head onto that 1-byte and prints it.

If both inputs are zero then we remain with Brian, move the tape head onto { to skip it and then switch to Chuck. When he executes >. this time he moves onto the empty cell after Brian's code and prints the 0.

Again, we easily obtain the other functions by negating one or both inputs.

### 0110, 1001: Binary functions with two truthy results

,?>},?>?_\x01
#}+{>?_}>.
,-?>},?>?_\x01
#}+{>>?_}>.

This one is a bit trickier. The previous functions were reasonably simple because they can be short-circuited - the value of the first input can decide the output, and if it doesn't then we look at the other input. For these two functions, we always need to look at both inputs.

The basic idea is to use the first input to decide whether the second input choose between 0 and 1 or between 1 and 0. Let's take 0110 (XOR) as an example:

Consider A = 0. In this case we want to output B as is. , reads A, ? does nothing. > moves onto the next (nonzero) cell so that } brings us to the _ on Chuck. Here, we read B with , and use ? again. If B was 0 as well, we're still on Brian. > skips the } on Chuck and ? switches so that the >. prints the 0 embedded in Brian's source code. If B was 1 on the other hand, Chuck does execute the } which moves into the _ in Brian's code already, so the >. then prints the 1-byte instead.

If A = 1, then we do switch to Chuck right away, who will execute }+{>?. What this does is move to the _ in Brian's source code, turns it into a 1 as well with +, then moves back to the start { and skips Brian's ? by moving one cell to the right with > before handing control back to him. This time, after Brian read's B, if B = 0, and Chuck uses >. the cell next to Brian's ? will be 1 instead of 0. Also, when B = 1, Chuck's } skips right over what to used to be a gap and moves all the way to the end of the tape, so that >. prints a zero instead. This way we're printing not B.

In order to implement equivalence, we simply negated A before using it as a condition. Note that due to this we also need to add another > to Chuck to skip that - as well when moving back to the start.

# ClojureScript, 88 84 76 74 bytes

nil and false are falsy, all other values are truthy. Booleans coerce to 0/1 for arithmetic and inequalities. Functions can take the wrong number of arguments.

0000   nil?            ; previously: (fn[]nil)
0001   and
0010   <
0011   true?           ; previously: (fn[x]x)
0100   >
0101   (fn[x y]y)
0110   not=
0111   or
1000   #(= 0(+ % %2))
1001   =
1010   #(not %2)
1011   <=
1100   not
1101   >=
1110   #(= 0(* % %2))
1111   /               ; previously: (fn[]4), inc
• Isn't 0 falsy? Jun 15, 2016 at 5:41
• Not in ClojureScript. Jun 15, 2016 at 13:57
• @LeakyNun Not in most LISPs or functional programming languages, which Clojure definitely is
– cat
Jun 28, 2016 at 22:50
• @cat Yes in most functional programming languages! Python, for example, evaluates not not(0) to False, which is the falsey value. Jul 17, 2016 at 16:55
• @EʀɪᴋᴛʜᴇGᴏʟғᴇʀ Er... Python is neither purely functional nor the type of functional language I'm talking about. Python is imperative, mostly, and with some smaller (poorly executed) functional aspects. Erlang, Haskell (I think), Common LISP, Clojure, Racket, Scheme, Factor, Standard ML, Objective CAML, etc 0 is just another value and is as a result truthy, and the symbol for false (#f, f, false, etc) is false. All other values are truthy in most functional languages.
– cat
Jul 17, 2016 at 17:02

# Brain-Flak, 418, 316 bytes

Try it online!

Let the inputs be the top two numbers on the stack at the start of the program (zero for false one for true) and the output be top of the stack at the end of the program (zero for false else for true).

(<>)

### and, 36 bytes

(({}{}[(())()])){{}{}(((<{}>)))}{}{}

### A and not B, 40 bytes

((({}){}{}[(())()])){{}{}(((<{}>)))}{}{}

({}<>)

### not A and B, 38 bytes

((({}){}{}[(())])){{}{}(((<{}>)))}{}{}

{}

### xor, 34 bytes

(({}{}[(())])){{}{}(((<{}>)))}{}{}

({}{})

### nor, 34 bytes

(({}{}<(())>)){{}{}(((<{}>)))}{}{}

({}{}[()])

### not B, 34 bytes

{}(({}<(())>)){{}{}(((<{}>)))}{}{}

(({}){}{}[()])

### not A, 34 bytes

(({}<{}(())>)){{}{}(((<{}>)))}{}{}

(({}){}{}[()()])

({}{}[()()])

<>(())

## Explanation

Since most of these are very similar I am not going to explain exactly how each of them works. I try my best to make it clear however how all of the sixteen work.

Firstly are the gates that return three of the same value (i.e. 2, 3, 5, 8, 9, 12, 14, and 15). These all follow the same pattern. First you convert the input into a two bit number with a as the twos place and B as the ones. This is done with this snippet (({}){}{}). You then subtract the value of the two bit input you want to isolate ({}[value]). (In the actual code the subtraction and the conversion are done in one step to save bytes). This can be combined with a not if needed: (({}<(())>)){{}{}(((<{}>)))}{}{}.

Next up: and, nor, or, xor, and xnor. These work similarly to the ones above. In fact some of these are included above, however this method is shorter. The trick I used here is that these each correspond to a sum of A B. e.g. xor evaluates to true if A+B = 1 and false otherwise. First you add A B and subtract the relevant amount. Expressed as ({}{}[0,1,2 or 3]). Then if necessary conduct a not

Next up: A, B, not A and not B. These are pretty much self explanatory. We start by removing the unnecessary value and then we either negate or finish.

Lastly are the two simpletons: true and false. For these we push the correct value to the off stack. The <> nilad returns zero so we can save two bytes by using the switch as the zero value.

Not the most efficient solution out there (perhaps the most efficient in Brain-Flak), but I had a good deal of fun writing these and I implore you to attempt to shorten these.

• (<>) is enough for false; also, (<{}{}>) is 8 bytes Jul 28, 2016 at 1:20
• Wow I had a much stricter definition of the challenge. Thank you. I will reduce this greatly Jul 28, 2016 at 1:35
• What do you mean? Jul 28, 2016 at 1:35
• I thought that I had to remove the existing inputs and place the result in its place. (<>) will leave the inputs and put the zero on the other stack. Jul 28, 2016 at 1:36
• Isn't <> enough for false due to implicit zeroes? Also, I think a can be the empty program. true can be <>[][] (doesn't save bytes, but looks cool :P). Jun 18, 2017 at 16:04

# Binary lambda calculus, 216 bits = 27 bytes

Uses the Church numerals 0 = λx. λy. y, 1 = λx. x as booleans.

• 0,0,0,0 (false): 0000000010 = λa. λb. λx. λy. y
• 0,0,0,1 (and): 000001011000111010 = λa. λb. b (λx. a) b
• 0,0,1,0 (A and not B): 0000010111010000010 = λa. λb. a b (λx. λy. y)
• 0,0,1,1 (A): 0000110 = λa. λb. a
• 0,1,0,0 (not A and B): 00011000001110 = λa. a (λx. λy. a)
• 0,1,0,1 (B): 000010 = λa. λb. b
• 0,1,1,0 (xor): 00011000011000110 = λa. a (λx. x (λy. x))
• 0,1,1,1 (or): 00011000110 = λa. a (λx. a)
• 1,0,0,0 (nor): 00000101011101010000010 = λa. λb. a b b (λx. λy. y)
• 1,0,0,1 (xnor): 0001011000110000110110 = λa. a (λx. a) (λb. b a)
• 1,0,1,0 (not B): 0000011000110 = λa. λb. b (λx. b)
• 1,0,1,1 (B implies A): 00000110110 = λa. λb. b a
• 1,1,0,0 (not A): 000001110001110 = λa. λb. a (λx. a)
• 1,1,0,1 (A implies B): 0010 = λa. a
• 1,1,1,0 (nand): 000001100111000110 = λa. λb. b (a (λx. b))
• 1,1,1,1 (true): 00000010 = λa. λb. λx. x

# Binary lambda calculus, 292 bits = 36.5 bytes

Uses the Church booleans true = λx. λy. x, false = λx. λy. y.

• 0,0,0,0 (false): 0000000010 = λa. λb. λx. λy. y
• 0,0,0,1 (and): 000001011011010 = λa. λb. b a b
• 0,0,1,0 (A and not B): 0000010110000010110 = λa. λb. b (λx. λy. y) a
• 0,0,1,1 (A): 0000110 = λa. λb. a
• 0,1,0,0 (not A and B): 000110000010 = λa. a (λx. λy. y)
• 0,1,0,1 (B): 000010 = λa. λb. b
• 0,1,1,0 (xor): 0000010111001011000001011010 = λa. λb. a (b (λx. λy. y) a) b
• 0,1,1,1 (or): 00011010 = λa. a a
• 1,0,0,0 (nor): 00000000010111101001011111010110 = λa. λb. b (λx. λy. y) (a b (λx. λy. x))
• 1,0,0,1 (xnor): 00000101110100101101100000110 = λa. λb. a b (b a (λx. λy. x))
• 1,0,1,0 (not B): 000000000101111010110 = λa. λb. λx. λy. b y x
• 1,0,1,1 (B implies A): 00000101101100000110 = λa. λb. b a (λx. λy. x)
• 1,1,0,0 (not A): 0000000001011111010110 = λa. λb. λx. λy. a y x
• 1,1,0,1 (A implies B): 00000101110100000110 = λa. λb. a b (λx. λy. x)
• 1,1,1,0 (nand): 000000000101111001011111010110110 = λa. λb. b (a (λx. λy. y) b) (λx. λy. x)
• 1,1,1,1 (true): 00000000110 = λa. λb. λx. λy. x
• I was just talking about that... Jul 29, 2016 at 10:03
• Is there actually a BLC interpreter that can deal with fractional bytes? Jul 29, 2016 at 16:50
• @Dennis The interpreters I linked to ignore padding bits in the last byte. For example, any one-byte program from '\x20' (00100000) to '\x2F' (00101111) is interpreted as the identity function 0010 = λa. a and behaves as cat. They know when the program ends because BLC is a prefix code. I think that counts as dealing with fractional bytes if anything does. Jul 29, 2016 at 20:45
• @Dennis Note also that these are functions, not programs (they do not communicate with the top-level I/O format, which is a Church list of bytes), and the effect of inserting these functions into a larger program is most accurately reflected by a fractional byte count. Jul 29, 2016 at 20:50

## ProgFk, 18.5 17.5 bytes

As ProgFk's instructions are specified in nibbles, the below code is given in hexadecimal, one logic gate per line and with spaces in between the bytes.

3
E1
DE 2D
<empty>
DE 1
1
E3
E2
E2 D
E3 D
1D
DE 2
D
DE 1D
E1 D
4

### Explanation

ProgFk is a tape-based esolang (similar to Brainfuck) where each cell is a bit and instructions are given as nibbles (4 bytes). Instructions operate on the cell pointed to by the instruction pointer. Input is given in the first and second cells (with A and B being the first and second cells respectively), and the instruction pointer starts at the first cell. Output is stored in the first cell.

Each instruction used is explained below.

1   Increment the instruction pointer.
2   Decrement the instruction pointer.
3   Set the current bit to 0.
4   Set the current bit to 1.
D   Perform a NOT on the current bit.
E   The next instruction is an extended instruction.

Extended instructions:
1   Set the current bit to the current bit AND the next bit.
2   Set the current bit to the current bit OR the next bit.
3   Set the current bit to the current bit XOR the next bit.
6   Swap the current bit and the next bit.

Saved a byte thanks to @LeakyNun!