79
\$\begingroup\$

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.

Your functions/programs must be independent.

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.

Leaderboard

var QUESTION_ID=82938,OVERRIDE_USER=48934;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+(?:\.\d+)?)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

\$\endgroup\$
26
  • 2
    \$\begingroup\$ Your functions/programs may share code. What does this mean? Also, may the programs be in different languages? \$\endgroup\$
    – Lynn
    Jun 14, 2016 at 23:36
  • 2
    \$\begingroup\$ 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? \$\endgroup\$
    – DavidC
    Jun 14, 2016 at 23:50
  • 4
    \$\begingroup\$ The names you're missing are the AND-NOT gates (A AND NOT B and B AND NOT A). \$\endgroup\$
    – user45941
    Jun 15, 2016 at 1:33
  • 20
    \$\begingroup\$ 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! \$\endgroup\$
    – edc65
    Jun 15, 2016 at 17:25
  • 5
    \$\begingroup\$ @dorukayhan See: vacuous truth \$\endgroup\$
    – Sp3000
    Jun 15, 2016 at 21:19

94 Answers 94

121
+100
\$\begingroup\$

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

enter image description here

Gates

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

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
  • [17-03-04] Added link to workshop file
  • +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
  • [16-08-28] Added pictures
\$\endgroup\$
8
  • 46
    \$\begingroup\$ +1 We need more domino golfing on PPCG \$\endgroup\$
    – Beta Decay
    Aug 29, 2016 at 10:53
  • 8
    \$\begingroup\$ Related. \$\endgroup\$ Aug 29, 2016 at 11:58
  • 8
    \$\begingroup\$ Wow. This is one of the most original answers I have ever seen on this site. \$\endgroup\$
    – DJMcMayhem
    Aug 31, 2016 at 19:24
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – DJMcMayhem
    Sep 3, 2016 at 15:44
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Mar 9, 2017 at 13:19
49
+50
\$\begingroup\$

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 ?.|@!)
1110 ?$@#)!<
1111 1!@

All programs use 0 for false and 1 for true.

Try it online! This is not a test suite, you'll have to copy in the different programs and inputs yourself.

The above solution is within 2-bytes of optimality (unless we relax the truthy/falsy interpretation, I guess). I've let a brute force search run for close to two days over all programs that fit into side-length 2, i.e. up to 7 bytes (not quite all programs - I made a few assumptions on what every valid program needs and what no valid program could have). The search found solutions for 15 of the 16 possible gates - and often a lot more than just one. You can find a list of all the alternative solutions in this pastebin where I've also grouped them by equivalent behaviour. The ones I'm showing above I've selected because they are either the simplest or the most interesting solution, and I'll add explanations for them tomorrow.

As for the 16th gate: XOR is the only gate that can apparently not be implemented in 7 bytes. A brute force search over larger programs is unfortunately not feasible with the code I currently have. So XOR had to be written by hand. The shortest I've found so far is the above 10-byte program, which is based on a failed (but very close) attempt by FryAmTheEggman. It's possible that an 8-byte or 9-byte solution exists, but other than that, all the solutions should indeed be optimal.

Explanations

Warning: wall of text. On the off-chance anyone's interested how these highly compressed Hexagony programs actually work, I've included explanations for each of them below. I've tried to choose the simplest solution for each gate in cases where more than one optimal program exists, in order to keep the explanations reasonably short. However, some of them still boggle the mind, so I thought they deserve a bit more elaboration.

0000: False

I don't think we'll need a diagram for this one:

 ! @
. . .
 . .

Since the entire memory grid is initialised to zeros, ! simply prints a zero and @ terminates the program.

This is also the only 2-byte solution.

0001: And

 ? .
| @ !
 . .

This basically implements short-circuiting. The grey diagram below shows the beginning of the program, where the first input is read with ? and the instruction pointer (IP) wraps around to the the left corner where the | mirror reflects it. Now the corner acts as a conditional, such there are two different execution paths depending on the value of the first input. The red diagram shows the control flow for A = 0 and the green diagram for A = 1:

i i i

As you can see, when the A is 0, then we simply print it and terminate (remember that all . are no-ops). But when A is 1, then the IP traverses the first row again, reading B and printing that instead.

In total there are sixteen 5-byte solutions for this gate. Fourteen of those are essentially the same as the above, either using > instead of | or replacing the . with a command that's effectively a no-op, or putting ? in the second position:

?.|@!    .?|@!    ?=|@!    =?|@!    ?_|@!    _?|@!    ?0|@!
?.>@!    .?>@!    ?=>@!    =?>@!    ?_>@!    _?>@!    ?0>@!

And then there are two other solutions (which are equivalent to each other). These also implement the same short-circuiting logic, but the execution paths are a bit crazier (and left as an exercise to the reader):

?<!@|
?<!@<

0010: A and not B

 # ?
# ! )
 @ .

This also implements a form of short-circuiting, but due to the use of # the control flow is much trickier. # is a conditional IP switch. Hexagony actually comes with six IPs labelled 0 to 5, which start in the six corners of the grid, pointing along their clockwise edge (and the program always begins with IP 0). When a # is encountered, the current value is taken modulo 6, and control flow continues with the corresponding IP. I'm not sure what fit of madness made me add this feature, but it certainly allows for some surprising programs (like this one).

We will distinguish three cases. When A = 0, the program is fairly simple, because the value is always 0 when # is encountered such that no IP-switching takes place:

i

# does nothing, ? reads A (i.e. also does nothing), # still does nothing, ! prints the 0, ) increments it (this is important, otherwise the IP would not jump to the third line), @ terminates the program. Simple enough. Now let's consider the case (A, B) = (1, 0):

i

The red path still corresponds to IP 0, and I've added the green path for IP 1. We see that after ? reads A (1 this time), the # switches to the IP that starts in the top right corner. That means ? can read B (0). Now ) increments that to 1, such that the # in the top left corner does nothing and we remain with IP 1. The ! prints the 1 and the IP wraps around the left diagonal. # still does nothing and @ terminates the program.

Finally, the really weird case where both inputs are 1:

i

This time, the second input is also 1 and ) increments it to 2. That means the # in the top left corner causes another IP switch to IP 2, indicate in blue. On that path, we first increment it further to 3 (although that's irrelevant) and then pass the ? a third time. Since we've now hit EOF (i.e. the input is exhausted), ? returns 0, ! prints that, and @ terminates the program.

Notably, this is the only 6-byte solution for this gate.

0011: A

 ? !
@ . .
 . .

This is simple enough that we won't need a diagram: ? reads A, ! prints it, @ terminates.

This is the only 3-byte solution for this gate. (In principle, it would also be possible to do ,;@, but the search didn't include ;, because I don't think it can ever save bytes over ! for this task.)

0100: B and not A

 + ?
| @ !
 ? .

This one is a lot simpler than its "brother" 0010. The control flow is actually the same as we've seen above for 0001 (And). If A = 0, then the IP traverses the lower line, reading B and printing that before terminating. If A = 1 then the IP traverses the first line again, also reading B, but the + adds two unused memory edges so all it does is reset the current value to 0, so that ! always prints 0.

There are quite a lot of 6-byte alternatives to this (42 in total). First, there's a ton of solutions equivalent to the above. We can again choose freely between | and >, and + can be replaced with any other command that gives us an empty edge:

"?|@!?    &?|@!?    '?|@!?    *?|@!?    +?|@!?    -?|@!?    ^?|@!?    {?|@!?    }?|@!?
"?>@!?    &?>@!?    '?>@!?    *?>@!?    +?>@!?    -?>@!?    ^?>@!?    {?>@!?    }?>@!?

In addition, we can also use ] instead of ?. ] moves to the next IP (i.e. selects IP 1), so that this branch instead reuses the ? in the top right corner. That gives another 18 solutions:

"?|@!]    &?|@!]    '?|@!]    *?|@!]    +?|@!]    -?|@!]    ^?|@!]    {?|@!]    }?|@!]
"?>@!]    &?>@!]    '?>@!]    *?>@!]    +?>@!]    -?>@!]    ^?>@!]    {?>@!]    }?>@!]

And then there's six other solutions that all work differently with varying levels of craziness:

/[<@!?    ?(#!@]    ?(#>@!    ?/@#/!    [<<@!?    [@$\!?

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):

i

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.

i

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.

i i

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:

i

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

i

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?

i

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:

i

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.

i

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.

i

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:

enter image description here

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:

enter image description here

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:

enter image description here

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:

enter image description here

? 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:

enter image description here

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:

enter image description here

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.

\$\endgroup\$
4
  • 9
    \$\begingroup\$ Aaaaaand the tl;dr award goes to... (kidding obviously, great answer and very well written out, +1) \$\endgroup\$ Jul 22, 2016 at 15:15
  • 4
    \$\begingroup\$ This is the reason you are not active on chat anymore?? \$\endgroup\$
    – Optimizer
    Jul 30, 2016 at 6:32
  • \$\begingroup\$ Sort of late, but could you add a link to your brute force code? \$\endgroup\$
    – nedla2004
    Feb 3, 2017 at 21:48
  • \$\begingroup\$ @nedla2004 I usually don't keep them around, but it's always a modified version of this script. \$\endgroup\$ Feb 3, 2017 at 22:19
43
\$\begingroup\$

APL, 22 20 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.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ +1 Nice use of atops! You can save two bytes by making 0000 and 1111 into trad-fns 0 and 1. \$\endgroup\$
    – Adám
    Jun 15, 2016 at 8:11
  • \$\begingroup\$ 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. \$\endgroup\$
    – Adám
    Jun 15, 2016 at 10:24
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$
    – Adám
    Jun 15, 2016 at 10:32
  • 11
    \$\begingroup\$ Jelly: 19 bytes. This: 18 bytes. Doesn't this mean that you outgolfed Dennis? +1 for that. \$\endgroup\$ Jun 16, 2016 at 17:21
33
\$\begingroup\$

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:

False

AND, 4:

enter image description here

A and not B, 5 (I think I can get this down to three, but do not have board right now):

enter image description here

A, 4:

enter image description here

Not A and B,5 (I think I can get this down to three, but do not have board right now):

enter image description here

B, 4:

enter image description here

Xor,5 (I know a way to make it 4, but I don't have the board right now):

enter image description here

Or, 4:

enter image description here

Nor, 4:

enter image description here

Xnor, 5 (I know a way to make it 4, but I don't have the board right now):

enter image description here

Not B, 4:

enter image description here

B implies A, 5 (I think I can get this down to three, but do not have board right now):

enter image description here

Not A, 4:

enter image description here

A implies B, 5 (I think I can get this down to three, but do not have board right now):

enter image description here

Nand, 4:

enter image description here

True, 4:

enter image description here

\$\endgroup\$
6
  • 3
    \$\begingroup\$ Wow, I had no idea that programming in chess was possible... Could you post a video/simulation of a few of these in action? \$\endgroup\$
    – Beta Decay
    Sep 5, 2016 at 9:50
  • 3
    \$\begingroup\$ 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 \$\endgroup\$ Sep 5, 2016 at 9:58
  • \$\begingroup\$ 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? \$\endgroup\$ Sep 6, 2016 at 1:44
  • \$\begingroup\$ 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 :) \$\endgroup\$ Sep 6, 2016 at 2:18
  • \$\begingroup\$ On your "And" case, if you remove the right rook, what's stopping the king from moving down (to white)? \$\endgroup\$ Oct 18, 2016 at 15:01
27
\$\begingroup\$

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!

\$\endgroup\$
5
  • 14
    \$\begingroup\$ I love the use of Factorial to convert either 0 or 1 to 1. \$\endgroup\$
    – Neil
    Jun 15, 2016 at 8:33
  • \$\begingroup\$ Is Jelly UTF-8? If yes then ¤ and ¬ are 2 bytes, not 1. \$\endgroup\$
    – Vi.
    Sep 29, 2016 at 20:10
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Dennis
    Sep 29, 2016 at 20:12
  • \$\begingroup\$ 0 0 1 0 > 1 byte Greater than. wouldn't this fail if the second input was negative? \$\endgroup\$
    – MD XF
    Jun 17, 2017 at 21:28
  • 1
    \$\begingroup\$ @MFXF We can choose which truthy and which falsy value we support. \$\endgroup\$
    – Dennis
    Jun 17, 2017 at 21:31
26
+500
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ Is the trailing 1 on false required? \$\endgroup\$ Jun 18, 2017 at 15:48
  • \$\begingroup\$ @CalculatorFeline Yes, we need to append a 0 to the tape so it can be deleted last. \$\endgroup\$ Jun 18, 2017 at 18:51
  • \$\begingroup\$ Ah. Forgot about that+wrapping. Clever! \$\endgroup\$ Jun 18, 2017 at 21:34
25
\$\begingroup\$

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.

enter image description here

In each of these diagrams, the top input is A while the bottom input is B.

\$\endgroup\$
8
  • 6
    \$\begingroup\$ @xnor might be flattered to know that his logic gate is the one that requires the most NAND gates to make D: \$\endgroup\$
    – Joe Z.
    Jun 16, 2016 at 20:21
  • 1
    \$\begingroup\$ @mbomb007 I'll edit that in later. I'm not so experienced with Logisim, so it might take a while. \$\endgroup\$
    – Joe Z.
    Jun 16, 2016 at 20:25
  • 3
    \$\begingroup\$ But I like handwriting better. \$\endgroup\$
    – Leaky Nun
    Jun 16, 2016 at 20:31
  • 1
    \$\begingroup\$ For those wondering, "cex" is short for "counterexample", as in "counterexample to an implication". \$\endgroup\$
    – Joe Z.
    Jun 17, 2016 at 11:46
  • 2
    \$\begingroup\$ Alternatively you could switch to nor gate and format it using redstone... \$\endgroup\$
    – jimmy23013
    Jun 22, 2016 at 5:38
23
\$\begingroup\$

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]
\$\endgroup\$
7
  • \$\begingroup\$ 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 \$\endgroup\$ Jul 29, 2016 at 11:05
  • \$\begingroup\$ @GáborFekete Those don't exist in Python 2 because ints offload comparisons to cmp. I haven't tried this for Python 3. \$\endgroup\$
    – xnor
    Jul 29, 2016 at 11:11
  • \$\begingroup\$ Oh right now I see! \$\endgroup\$ Jul 29, 2016 at 11:24
  • \$\begingroup\$ Save 4 bytes by using the function not for 0001, False - ideone \$\endgroup\$ Sep 4, 2016 at 1:52
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – xnor
    Sep 4, 2016 at 22:35
23
\$\begingroup\$

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

\$\endgroup\$
3
  • 1
    \$\begingroup\$ What are your rules for suicide? Disallowed? And what happens when one side fills the entire board? Is that considered suicide? \$\endgroup\$ Sep 23, 2016 at 14:25
  • \$\begingroup\$ @MartinEnder Disallowed. And yes, that's considered suicide. \$\endgroup\$
    – jimmy23013
    Sep 23, 2016 at 16:43
  • \$\begingroup\$ The 1x7 solution seemed wrong. I'm trying to fix it... \$\endgroup\$
    – jimmy23013
    Oct 4, 2016 at 0:36
16
\$\begingroup\$

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.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – jimmy23013
    Jun 15, 2016 at 11:33
  • 2
    \$\begingroup\$ Math.min instead of a=>b=>a&b. Math.max instead of a=>b=>a|b. Math.pow instead of a=>b=>a>=b. \$\endgroup\$ Jun 16, 2016 at 0:37
  • 1
    \$\begingroup\$ Also, since NaN is falsey, you can do parseInt instead of a=>b=>a>b. \$\endgroup\$ Jun 16, 2016 at 21:11
  • 1
    \$\begingroup\$ @algmyr !NaN => true, !!NaN => false \$\endgroup\$ Jul 29, 2016 at 14:14
  • 1
    \$\begingroup\$ Now it is much more clear. Thank you! \$\endgroup\$
    – EzioMercer
    Jan 27, 2023 at 13:32
15
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ ^1|0$ should only match 1 character strings. What's going on here? \$\endgroup\$ Mar 2, 2017 at 15:44
  • \$\begingroup\$ @CalculatorFeline It matches [1 at beginning of input] OR [0 at end of input]. Took me a minute to get it too... \$\endgroup\$ Aug 18, 2017 at 3:46
  • \$\begingroup\$ Precedence, guys.... \$\endgroup\$
    – Leaky Nun
    Aug 18, 2017 at 4:07
  • \$\begingroup\$ I guess ^1|0$ is harder to read than 1.|.0. Seems to make reading harder in all \$\endgroup\$
    – l4m2
    Dec 7, 2017 at 5:25
11
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – cat
    Jun 15, 2016 at 22:32
  • \$\begingroup\$ @cat The flags cost 4 per program, as you have to count the space as well. \$\endgroup\$ Jun 16, 2016 at 0:55
  • \$\begingroup\$ @cat relevant meta post: meta.codegolf.stackexchange.com/questions/273/… \$\endgroup\$ Jun 16, 2016 at 5:23
  • \$\begingroup\$ It's been over a year. Do you have time yet? \$\endgroup\$ Jun 18, 2017 at 15:52
10
\$\begingroup\$

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

enter image description here

15. NAND gate - 1x2x3 = 6 blocks

enter image description here

14. A=>B - 1x2x3 = 6 blocksenter image description here

13. NOT A - 2 blocks enter image description here

12. B=>A - 1x2x3 = 6 blocksenter image description here

11. NOT B - 2 blocks enter image description here

10. XNOR - 1x3x4 = 12 blocks enter image description here

9. NOR - 1x2x3 = 6 blocksenter image description here

8. OR - 1 blocks enter image description here

7. XOR - 1x3x4 = 12 blocks enter image description here

6. B - 1 blocks enter image description here

5. !A&B - 1x2x5 = 10 blocks enter image description here

4. A - 1 blocks enter image description here

3. A&!B - 1x2x5 = 10 blocks enter image description here

2. AND - 2x2x3 = 12 blocks enter image description here

1. FALSE- 1 blocks enter image description here

\$\endgroup\$
1
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – Luca H
    Nov 23, 2017 at 11:12
9
\$\begingroup\$

Haskell, 78 76 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.

\$\endgroup\$
3
  • \$\begingroup\$ I was just about to comment "dude, _#_ isn't a standard operator!" And then I realised... Well done. \$\endgroup\$ Jun 16, 2016 at 14:09
  • \$\begingroup\$ 4 could be pure \$\endgroup\$
    – cole
    Jul 28, 2019 at 0:32
  • \$\begingroup\$ @cole: Thanks. Wow, pure was introduced into Prelude back in 2015, so it was available at the time of this challenge. \$\endgroup\$
    – nimi
    Jul 28, 2019 at 1:16
7
\$\begingroup\$

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
\$\endgroup\$
7
\$\begingroup\$

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 )

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You only have to provide snippets of code for each function. \$\endgroup\$ Jun 18, 2017 at 15:57
6
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ If integers aren't truthy/falsey, what happens when you put them in an if statement? \$\endgroup\$ Jun 22, 2016 at 16:33
  • 3
    \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ it remains unevaluated. \$\endgroup\$ Jun 22, 2016 at 16:39
6
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ How do you input the output? \$\endgroup\$
    – Leaky Nun
    Jun 15, 2016 at 6:59
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Fatalize
    Jun 15, 2016 at 7:01
  • 1
    \$\begingroup\$ This is the right tool for the job :P \$\endgroup\$ Jun 15, 2016 at 21:03
6
\$\begingroup\$

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)
\$\endgroup\$
9
  • 12
    \$\begingroup\$ Number six thinks it's funny. \$\endgroup\$ Jun 15, 2016 at 3:06
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ Number 6 is the best, I like number 12 too! xD! \$\endgroup\$
    – David
    Jun 15, 2016 at 3:19
  • \$\begingroup\$ Don't you have the "unequal" function? \$\endgroup\$
    – Leaky Nun
    Jun 15, 2016 at 5:27
  • \$\begingroup\$ No (I don't think so at least) \$\endgroup\$
    – David
    Jun 15, 2016 at 5:31
  • 2
    \$\begingroup\$ @David I think number 7 can be replaced by - \$\endgroup\$
    – Luis Mendo
    Jun 15, 2016 at 9:30
6
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Does it support a(2,2). for false? \$\endgroup\$
    – jimmy23013
    Jun 15, 2016 at 7:54
  • \$\begingroup\$ @jimmy23013 I guess it could if I assume that 2 is falsy. Not sure if that's acceptable. \$\endgroup\$
    – Fatalize
    Jun 15, 2016 at 7:55
  • \$\begingroup\$ @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. \$\endgroup\$
    – Fatalize
    Jun 15, 2016 at 8:03
  • \$\begingroup\$ 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. \$\endgroup\$
    – DLosc
    Sep 3, 2022 at 17:04
6
\$\begingroup\$

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         #{:||
1100 not p              $:|
1101 not p or q         :||
1110 not p or not q     |
1111 true               #

Try it here! But read below first.

Input is implicit on stack. Result is let on stack. Add 16 bytes (one * to the end of each) if you want 0x00 or 0x01 to output representing 0 and 1. Add an additional 160 bytes if you want a 0 or a 1 printed. (Put ~~##~~~#{@ before each *.)

NTFJ's only binary operator is NAND, so each of these is written in NAND form.

Let's go through each of them.

0: false

~

~ represents a false bit. Simple enough. Since input is implicit at the bottom of the stack, this is left at the top of it.

1: p and q

|:|

NTFJ operates on a stack. : is the command for duplicate. Observe that p and qnot (p nand q) and that not q = q nand q.

Command | Stack
        | p q
   |    | (p nand q)
   :    | (p nand q) (p nand q)
   |    | (p nand q) nand (p nand q)
        | => not (p nand q)
        | => p and q

(Note, then, :|can be said to be negation and |:| can be said to be conjunction)

2: p and not q

:||:|

Observe that this just a negation, :| and a conjunction |:|.

Command | Stack
        | p q
  :|    | p (not q)
  |:|   | p and (not q)

3: p

$

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

10: not q

#{$:|

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.

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

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 1110 8D4411FE LEA EAX, [ECX+EDX-2] \$\endgroup\$
    – l4m2
    Dec 18, 2017 at 9:13
5
\$\begingroup\$

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.

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

Brainfuck, 184 178 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 +.
\$\endgroup\$
2
  • \$\begingroup\$ 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)? \$\endgroup\$ Jul 28, 2016 at 7:15
  • \$\begingroup\$ @MartinEnder I figured that I wouldn't just copy Dennis' answer here. \$\endgroup\$
    – Leaky Nun
    Jul 28, 2016 at 7:21
4
\$\begingroup\$

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.

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

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.

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

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
\$\endgroup\$
5
  • \$\begingroup\$ Isn't 0 falsy? \$\endgroup\$
    – Leaky Nun
    Jun 15, 2016 at 5:41
  • 2
    \$\begingroup\$ Not in ClojureScript. \$\endgroup\$
    – MattPutnam
    Jun 15, 2016 at 13:57
  • \$\begingroup\$ @LeakyNun Not in most LISPs or functional programming languages, which Clojure definitely is \$\endgroup\$
    – cat
    Jun 28, 2016 at 22:50
  • \$\begingroup\$ @cat Yes in most functional programming languages! Python, for example, evaluates not not(0) to False, which is the falsey value. \$\endgroup\$ Jul 17, 2016 at 16:55
  • 4
    \$\begingroup\$ @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. \$\endgroup\$
    – cat
    Jul 17, 2016 at 17:02
4
\$\begingroup\$

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).

false, 4 bytes (Courtesy of Leaky Nun)

(<>)

and, 36 bytes

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

A and not B, 40 bytes

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

A, 6 bytes

({}<>)

not A and B, 38 bytes

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

B, 2 bytes

{}

xor, 34 bytes

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

or, 6 bytes

({}{})

nor, 34 bytes

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

xnor, 10 bytes

({}{}[()])

not B, 34 bytes

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

B implies A, 14 bytes

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

not A, 34 bytes

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

A implies B, 16 bytes

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

nand, 12 bytes

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

true, 6 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.

\$\endgroup\$
13
  • \$\begingroup\$ (<>) is enough for false; also, (<{}{}>) is 8 bytes \$\endgroup\$
    – Leaky Nun
    Jul 28, 2016 at 1:20
  • \$\begingroup\$ Wow I had a much stricter definition of the challenge. Thank you. I will reduce this greatly \$\endgroup\$
    – Wheat Wizard
    Jul 28, 2016 at 1:35
  • \$\begingroup\$ What do you mean? \$\endgroup\$
    – Leaky Nun
    Jul 28, 2016 at 1:35
  • \$\begingroup\$ 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. \$\endgroup\$
    – Wheat Wizard
    Jul 28, 2016 at 1:36
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ Jun 18, 2017 at 16:04
4
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ I was just talking about that... \$\endgroup\$
    – Leaky Nun
    Jul 29, 2016 at 10:03
  • \$\begingroup\$ Is there actually a BLC interpreter that can deal with fractional bytes? \$\endgroup\$
    – Dennis
    Jul 29, 2016 at 16:50
  • \$\begingroup\$ @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. \$\endgroup\$ Jul 29, 2016 at 20:45
  • \$\begingroup\$ @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. \$\endgroup\$ Jul 29, 2016 at 20:50
4
\$\begingroup\$

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!

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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