14
\$\begingroup\$

Introduction

Logic gates! Everyone knows them, everyone loves them (unless you're starting to learn them). Take two booleans, compare them, get a single boolean in return. AND, NAND, OR, NOR, XOR, XNOR. Fun! But, what if you only had the inputs and output, but not the operator?

Logic Gates

Challenge

Given a three digit number, xyz, where x and y are inputs to the unknown gate(s) and z is the output, list all the possible gates. The output order doesn't matter but it must be all caps and separated by a space. This is , so the shortest answer wins!

Example Inputs and Outputs

Inputs:

001

101

111

Outputs:

NAND NOR XNOR

NAND OR XOR

AND OR XNOR

\$\endgroup\$
7
  • 3
    \$\begingroup\$ Is it possible we are given the NOT gate? (10 or 01) \$\endgroup\$
    – Sisyphus
    Sep 29, 2020 at 1:14
  • 14
    \$\begingroup\$ Welcome to the site! This is an interesting first question, but currently is missing a few key things we require. While this has the code golf tag, we do ask that you specify in the question exactly what the winning criteria is. Furthermore, we generally have pretty lax rules on input, and so restricting the input to a three digit number (rather than a string, list, etc.) is frowned upon (as is requiring a strict output format). I believe that, with little editing, your question can meet our standards more or less as is though. Next time however, I‘d recommend checking out the (cont.) \$\endgroup\$ Sep 29, 2020 at 1:16
  • 5
    \$\begingroup\$ (cont.) Sandbox in order to get feedback and clarifications on your potential challenges, which can help avoid issues when posting challenges. Finally, I‘d recommend you check out our Meta, where you‘ll find posts detailing what to do/avoid when creating a challenge (sort questions by votes to properly explore our policies/consensus) \$\endgroup\$ Sep 29, 2020 at 1:21
  • 10
    \$\begingroup\$ This is pretty similar to the earlier challenge Evaluating Logic Gates, where you are given two inputs and must list all gates that make the result evaluate to True. The difference here is that the required result may be True or False, and I'm not sure whether that's different enough to avoid this being a duplicate. \$\endgroup\$
    – xnor
    Sep 29, 2020 at 1:48
  • 3
    \$\begingroup\$ can we take the inputs spearately/ as an array? \$\endgroup\$
    – Razetime
    Sep 29, 2020 at 3:44

9 Answers 9

10
\$\begingroup\$

JavaScript (ES6),  58  56 bytes

n=>`25AND 41OR X37OR`.replace(/\d+/g,m=>m>>n%6&1?'':'N')

Try it online!

How?

Given the input \$n\$, we compute \$n\bmod 6\$ to get an index into 3 small lookup bit masks.

It's worth noting that all operations are commutative, i.e. \$(X \operatorname{op} Y)=(Y \operatorname{op} X)\$ even when \$X=\lnot Y\$. So the collisions between 011 and 101 and between 010 and 100 are actually very welcome.

 n (decimal) | n mod 6 | NAND | NOR | XNOR
-------------+---------+------+-----+------
  011 or 101 |    5    |   0  |  1  |  1
  010 or 100 |    4    |   1  |  0  |  0
         111 |    3    |   1  |  1  |  0
         110 |    2    |   0  |  0  |  1
         001 |    1    |   0  |  0  |  0
         000 |    0    |   1  |  1  |  1
                           |     |     |
                           |     |     +--> 0b100101 = 37
                           |     +--------> 0b101001 = 41
                           +--------------> 0b011001 = 25

We look for the bit masks in the string "25AND 41OR X37OR" and replace them with either "N" or an empty string.

\$\endgroup\$
1
  • \$\begingroup\$ Impressive, attacking the problem via logic instead of any particular language \$\endgroup\$
    – jimfan
    Sep 29, 2020 at 15:28
4
\$\begingroup\$

Jelly, 33 bytes

V€Ḅ“n|ḃ’b⁹¤æ»ị“N“”ż“AND “OR X“OR”

Try it online!

Explanation

V€Ḅ“n|ḃ’b⁹¤æ»ị“N“”ż“AND “OR X“OR”  Main Link
 €                                 For each character
V                                    evaluate it (into 0 or 1)
  Ḅ                                  convert the input string to binary
   “n|ḃ’b⁹¤                        [106, 86, 150]:
   “n|ḃ’                             6968982
        b                            in base
         ⁹                           256
           æ»                      Right shift each number by the input (those three numbers encode whether or not the N needs to be present)
              ị                      and index into
               “N“”                  ["N", ""] (odd = N, even = "", since Jelly lists wrap)
                   ż                 interleave it with
                    “AND “OR X“OR”   "AND ", "OR X", "OR"
                                    Final result is [N]AND [N]OR X[N]OR
\$\endgroup\$
2
  • \$\begingroup\$ Converting the input to binary is the same as taking it as a number and reducing it modulo 8, if that helps. \$\endgroup\$
    – Neil
    Sep 29, 2020 at 9:00
  • \$\begingroup\$ You can save a byte by removing the final \$\endgroup\$ Sep 29, 2020 at 10:05
3
\$\begingroup\$

Python 3, 98 88 78 bytes

lambda s:'%sAND %sOR X%sOR'%(*[eval(s[0]+o+s[1]+'!='+s[2])*'N'for o in'&|^'],)

Try it online!

Thanks to ovs for -20 bytes

\$\endgroup\$
0
2
\$\begingroup\$

Charcoal, 33 bytes

Nθ⭆vAND jOR XiOR⎇‹ι_ι×NΣ§◧⍘℅ι01⁸θ

Try it online! Link is to verbose version of code. Explanation: The lowercase letters' ASCII codes encode the binary patterns for where the Ns appear. This algorithm actually depends on the input being an integer and the output being in upper case. Although the input is taken in base 10, the cyclic indexing means that the values are equivalent to base 2.

Nθ                                  Input the 3-digit number
   vAND jOR XiOR                    Literal string `vAND jOR XiOR`
  ⭆                                 Map over characters and join
                  ι                 Current character
                 ‹                  Is less than
                   _                Literal `_`
                ⎇                   If true then
                    ι               Current character else
                      N             Literal `N`
                     ×              Repeated by
                       Σ            Extract decimal value of
                            ι       Current character
                           ℅        ASCII code
                          ⍘  01     Converted to base 2
                         ◧     ⁸    Left padded to length 8
                        §           Cyclically indexed by
                                θ   Input number
\$\endgroup\$
2
\$\begingroup\$

Python 3.8, 72 59 bytes

lambda n:f'{n%15%2*"N"}AND {n*3%17%2*"N"}OR X{n%9%2*"N"}OR'

Try it online!

Expects input as a decimal number.

-13 bytes thanks to ovs' modular dark magic

I squinted at the numbers very hard until I found these three formulae ovs chained all the modulos:

  • n&1!=n//110 <=> "the last digit is 1 and n is not 111; or n == 110"
  • n%2!=(n>2) <=> "the last digit is 0 and n is nonzero; or n == 001"
  • n%9%2 <=> "the number of 1 in the digits of n is odd"
\$\endgroup\$
5
  • \$\begingroup\$ Two minor golfs: Both != can be replaced by XOR and by rearranging the last expression the brackets can be avoided: tio.run/… \$\endgroup\$
    – ovs
    Sep 30, 2020 at 9:23
  • \$\begingroup\$ Thanks! I thought about xor but I was persuaded it would require more parentheses than !=. \$\endgroup\$
    – Stef
    Sep 30, 2020 at 9:30
  • \$\begingroup\$ It turns out you can do all 3 expressions with modulo chains: tio.run/##K6gsycjPM7YoKPqfZhvzPycxNyklUSHPKk29Ok/… \$\endgroup\$
    – ovs
    Sep 30, 2020 at 9:44
  • \$\begingroup\$ Hahahaha okay but you'll have to explain to me how you came up with n*3%17%2 \$\endgroup\$
    – Stef
    Sep 30, 2020 at 9:48
  • 1
    \$\begingroup\$ I've used a bruteforce program to search for expression of the form n*a%b%c. This has been helpful for quite a few challenges on this site ;). \$\endgroup\$
    – ovs
    Sep 30, 2020 at 10:02
2
\$\begingroup\$

Pyth, 53 bytes

%"%sAND %sOR X%sOR"[*\Nn&=vz1/z110*\Nn%z2>z2*\N%%z9 2

Try it online!

Port of a previous version of Stef's Python 3.8 answer.

Pyth, 64 61 bytes

-3 bytes by using string formatting.

A,shzs@z1=Tsez%"%sAND %sOR X%sOR"[?x&GHT\Nk?x|GHT\Nk?xxGHT\Nk

Try it online!

First time golfing in Pyth!

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

05AB1E, 35 bytes

’n€ƒxš¯š¯’4ôuεI`Š…*+~Nè.VQi'Nõ.;]ðý

Try it online or verify all test cases.

Explanation:

’n€ƒxš¯š¯’                 # Push dictionary string "nandxnornor"
  4ô                       # Split it into parts of size 4: ["nand","xnor","nor"]
    u                      # Uppercase each string: ["NAND","XNOR","NOR"]
     ε                     # Map over each string:
      I                    #  Push the input
       `                   #  Pop and push its digits separated to the stack
        Š                  #  Triple-swap the values on the stack: a,b,c → c,a,b
         …*+~              #  Push string "*+~"
             Nè            #  Index the map-index into this string
               .V          #  Execute it as 05AB1E code:
                           #   *: Multiply the top two values on the stack
                           #   +: Add the top two values on the stack
                           #   ~: Bitwise-OR the top two values on the stack
                 Qi        #  If this is equal to the third value that was on the stack:
                   'Nõ.;  '#   Remove the first "N" in the string
     ]                     # Close the if-statement and map
      ðý                   # And join the list with space delimiter
                           # (after which the result is output implicitly)

See this 05AB1E tip of mine (section How to use the dictionary?) to understand why ’n€ƒxš¯š¯’ is "nandxnornor".
The ’n€ƒxš¯š¯’4ôu could alternatively also have been .•UNœTǨ₆~•# for the same byte-count.

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

C (gcc), 78 73 bytes

Saved 5 bytes thanks to ceilingcat!!!

f(n){n=1<<n%6;printf("NAND %sOR X%sOR"+!(n&38),"N"+!(n&22),"N"+!(n&26));}

Try it online!

Inputs a three digit decimal number representing the two boolean arguments and the result of a boolean operator and outputs all possible operators to stdout.

Uses that super-handy lookup table from Arnauld's JavaScript answer.

\$\endgroup\$
0
0
\$\begingroup\$

Java (OpenJDK 8), 143 bytes

void A(int a){for(int i=-1;i++<5;)if((7+21*((a+2)/4)>>i&1)==a%2)System.out.print(new String[]{"AND","OR","XOR","NAND","NOR","XNOR"}[5-i]+" ");}

Try it online! (More details inside)

Input is a single 3 digit number, interpreted as binary. Example input: "A(0b101);"

Explanation:

 (...)
 if((7+21*((a+2)/4)>>i&1)==a%2)
     7+21*(       )                 // The shortest interpolation equation (see bottom of tio.) I could find, for the "x" values of
                                    //   0, 1, 2, representing 00_, 01_ / 10_, 11_ respectively.
           (a+2)/4                  // The sum of the second and third bit, found this equation with brute force,
                                    //   alternative: (a|1)/3, needs parentheses because of bit operation order.
                   >>i&1            // The bit at i, delete all bits except the first to compare it with:
                        )==a%2)     // The first digit of a. (like "number % 10", except for binary)

And, I'm pretty sure you can print the answer when asked to return it.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Suggest a+2>>2 instead of (a+2)/4 \$\endgroup\$
    – ceilingcat
    Dec 2, 2020 at 5:58

Your Answer

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

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