9
\$\begingroup\$

Your mission, if you choose to accept it, is to construct a simple truth evaluator for the following logical operators:

----------------------------------------------------------------------------------
  Logical Name          |  Gate Name   |  Symbol  |  Symbol Name  |  Truth Table
----------------------------------------------------------------------------------
  Identity              |  is          |          |  (none)       |  10
  Negation              |  not         |    ~     |  tilde        |  01
  Conjunction           |  and         |    &     |  ampersand    |  1000
  Disjunction           |  or          |    |     |  pipe         |  1110
  Negative Conjunction  |  nand        |    ^     |  caret        |  0111
  Joint Denial          |  nor         |    v     |  "vee"        |  0001
  Exclusive Disjunction |  xor         |    x     |  "ecks"       |  0110
  Equivalence           |  equals/xnor |    =     |  equals       |  1001
  Implication           |  implies     |    >     |  greater than |  1011

Truth tables are in the following order:

  1. 1 1
  2. 1 0
  3. 0 1
  4. 0 0

Input will come as a simple string of 0, 1, and the symbol. You can either accept input as a parameter or read it from the user on stdin. Here are some sample input/output pairs:

Input: 1
Output: 1

Input: ~1
Output: 0

Input: 0|1
Output: 1

Input: 1>0
Output: 0

The unary operator (negation) will always appear before the boolean value, while the binary operators will always appear between the two boolean values. You can assume that all input will be valid. Strings are regular ASCII strings.

If you prefer, you can use T and F rather than 1 and 0. -6 to your character count if you support both.

This is : shortest code in any language wins!

\$\endgroup\$
  • 3
    \$\begingroup\$ I believe ^'s symbol name should say caret. \$\endgroup\$ – FireFly Oct 7 '13 at 15:23
  • 3
    \$\begingroup\$ @FireFly Haha, you're right. Too close to lunch! Thanks. \$\endgroup\$ – asteri Oct 7 '13 at 15:25
6
\$\begingroup\$

APL (45 - 6 = 39)

⍎(1+9≠L)⌷¨↓⍉Z⍪⍉⍪'10∧∨⍲⍱≠≤*'[L←'TF&|^vx>'⍳Z←⍞]

Supports T and F as input but will always output 0 or 1.

Explanation:

  • Z←⍞: read a line and store it in Z
  • L←'TF&|^vx>'⍳Z: get the index in 'TF&|^vx>' for each character in Z, giving 9 if the character is not in 'TF&|^vx>'.
  • '10∧∨⍲⍱≠≤*'[...]: find the corresponding character in '10∧∨⍲⍱≠≤*'. (So characters that weren't in the first list become *).
  • ↓⍉Z⍪⍉⍪: make this into a matrix, put the original (Z) on top of it, and split it into a list of strings, where the first character is the original and the second character is its translation, if any.
  • (1+9≠L)⌷¨: for each of these strings, get the first character if there was no translation (if L=9 in that place) and the second character if there was.
  • Example: if the input had been T|0, we would have 1∨0 by now which is the corresponding APL expression
  • : eval

Note: ~ and = already do the right thing so they don't need to be replaced by anything.

\$\endgroup\$
  • \$\begingroup\$ Very nice! This is a translate-to-APL-and-eval approach, right? I was pondering a gerund-based approach in J, but I don't know how to cleverly split up the operands. :\ \$\endgroup\$ – FireFly Oct 8 '13 at 7:17
  • \$\begingroup\$ Why do matrix manipulation when you can simply add translation rules for no-change characters like ⍎'1010~∧∨⍲⍱≠=≤'['10TF~&|^vx=>'⍳⍞]? (Score 33-6=27) \$\endgroup\$ – TwiNight Oct 14 '13 at 22:53
8
\$\begingroup\$

C - 165 127

That was fun! Plain lookup table relying on a fixed offset for the lookup.

main(){
  char*s="100011001110110v& x = |^> /~",
       t[6]="0/xxx",
      *u= strchr((gets(t+2),t),0)-3;
  putchar(strchr(s,u[1])[*u*2+u[2]-159]);
}

For some reason gets doesn't get implicitly declared, so when I removed the include I had to change gets(t+2) to (gets(t+2),t) (or similarly elsewhere, costing as much).


Explanation

First of all, since the truth tables for the operators have plenty of overlapping characters we wish to store the lookup tables in a way so that we allow overlap. Here's how I chose to store them:

v    &    x    =    |    ^    >       ~     (operation)
1000 0001 0110 1001 0111 1110 1101 01 10    (truth table [order 00,01,10,11])
0    1    3    5    7    8    9    B  D     (offset in LUT below)

0123456789ABCDE   (offsets)
100011001110110   (values)

Next, we want to map operator symbols to these offsets. We do this by storing the operator symbols in the same string at a fixed offset from the LUT data (namely, 16 characters later, i.e. directly after the LUT data). The lookup process is "find operator in s, subtract 16, add left*2+right (left/right operand). For the lookup of the empty "identity operation", due to how the input is fetched the operator in this case will resolve to whatever t[1] is initialised to--in our case /. Thus, we use / as the lookup table key to represent the identity operation. When we process the unary ~ operation "left" (for the lookup calculation mentioned earlier) is always this same / . / happens to be one less than 0 ASCII-wise, meaning when we compensate for ASCII digits \ will represent -1. The slash in the lookup table key area (second-to-last character in s, that is) is positioned to compensate for this.

Next up, input handling. The input has dynamic length, but it'd be easier if we have specific static names for the left operand, operator and right operand, regardless of input. If we pretend that we could read the input right-to-left, this would basically happen automagically--the right operand is always the rightmost character, the operator (if present) is second-to-rightmost, the left operand (if present) is third-to-rightmost. In order to be able to index the string like this, we use strchr in order to locate the \0 terminator (- 3 to simplify indexing). This shows why t[0] and t[1] become the left operand/operator respectively when the input is 1 or 2 characters.

Putting it together, the output would be putchar(strchr(s,u[1])[(u[0] - '0')*2 + (u[2] - '0') - 15]), but some refactoring and constant folding instead gets us the shorter putchar(strchr(s,u[1])[u[0]*2+u[2]-159]).

\$\endgroup\$
  • \$\begingroup\$ Could you explain how that works? \$\endgroup\$ – Johannes Kuhn Oct 7 '13 at 17:14
  • \$\begingroup\$ The truth table overlap was a brilliant idea. Would've never thought of that myself. :) \$\endgroup\$ – asteri Oct 7 '13 at 18:53
  • \$\begingroup\$ Also the reading right-to-left. I knew the variable length input and positioning would pose a challenge, and that's a great way to solve it. Really excellent out-of-the-box thinking. Want to come work on my development team? Haha \$\endgroup\$ – asteri Oct 7 '13 at 19:01
  • 4
    \$\begingroup\$ I think more answers should have explanations like this. Helps those of us who are still learning a considerable bit! (And by those who are still learning pretty much means everyone) \$\endgroup\$ – agweber Oct 7 '13 at 20:12
  • \$\begingroup\$ @agweber: That's good to hear, I was a bit worried about my explanation. And yes, probably everyone here is in a "still learning" phase.. well, at least I know I am. \$\endgroup\$ – FireFly Oct 7 '13 at 20:29
4
\$\begingroup\$

Tcl, 212 208-6 = 202

proc o n\ e {proc $n a\ b expr\ $e}
o > {$a<=$b}
o v {!($a|$b)}
o x {$a^$b}
o ^ {!($a&$b)}
namespace pat tcl::mathop 
lmap o\ b [lassign [split [string map {~0 1 ~1 0} $argv] {}] a] {set a [$o $a $b]}
puts $a

Ungolfed:

# Defines an operator
proc operator {name expression} {
    proc $name {a b} "expr $expression"
}
operator > {$a<=$b}
operator v {!($a|$b)}
operator x {$a^$b}
operator ^ {!($a&$b)}
# Call the commands in ::tcl::mathop if the command is not in the global namespace
namespace path tcl::mathop
# lmap instead foreach
# assume that we only got 1 argument.
foreach {op b} [lassign [string map {{~ 0} 1 {~ 1} 0} [split $argv {}]] a] {
   set a [$op $a $b]
}
puts $a

I think the foreach line needs some explanation:

  • split $argv {} splits the input string (it is actually a list, but code-golf) into it's characters.
  • string map {{~ 0} 1 {~ 1} 0} ... takes a string and replaces ~ 0 with 1 and ~ 1 with 0
  • lassign ... a takes the first element of the list and assigns it to the variable a, returns the rest.
  • foreach {op b} ... {code} walks over the list and takes 2 elements each time: op and b
  • set a [$op $a $b] executes the command in the variable op, stores the result in a
\$\endgroup\$
3
\$\begingroup\$

JavaScript - 107 105 characters

alert((x=eval(prompt().replace(/v/,'|~').replace(/\^/,'&~').replace(/x/,'^').replace(/=/,'==')))!=-1?x:0)
\$\endgroup\$
  • \$\begingroup\$ Haha, nice. That's handy. Didn't even think of eval() when I made this up. Just give me a bit to get home and test it. \$\endgroup\$ – asteri Oct 7 '13 at 19:17
  • 1
    \$\begingroup\$ nand = &~ and nor = |~? \$\endgroup\$ – Johannes Kuhn Oct 8 '13 at 0:19
  • \$\begingroup\$ @Johannes: It is not really &~ and |~, but NAND is just the inverse of AND. So, inversing one of the bits does invert the result too. \$\endgroup\$ – ProgramFOX Oct 8 '13 at 16:51
3
\$\begingroup\$

Befunge-98 - 104 101 98-6 72

...because every task needs an esolang solution.. translation of my C implementation, but processing characters one at a time instead.

#v~
2_vp5a00+*2%2\p10\%
0:<+1_v#-g5\g1
1_|#:\</2\-
.@>2%
 v   ~x^&=.>  |

Fun fact: change the @ to a,$ and you get a fancy neverending REPL instead (though, if you do this you'll notice that identity is actually "repeat last command with lhs=0 and rhs=input", which just happens to default to identity). The REPL is no more.

Ungolfed (earlier version):

v10001100111011v& x = |^>~
  $       1111111111222222
 1234567890123456789012345

 [read input]
> ~ :a- #v_   $ 21g " "- + 0g , @

v p11:   <
   ↑save chr

0 ←lup   [traverse LUT]
> 1+  :11g  \0g -! #v_
 v                  <
    lup chr acc
v>  :3` #v_  $"0"-\2*+

               v>   . , a,
 v       <
v> 9+9+ 21p $

Edit: inspired by @jpjacobs' solution, I now rely on the position of characters in the LUT to represent truth tables. E.g., | is on position 11102 = 14 because this corresponds to the truth table for |.

\$\endgroup\$
  • \$\begingroup\$ That is crazy. Ok, every solution in befunge is crazy. \$\endgroup\$ – Johannes Kuhn Oct 8 '13 at 6:21
2
\$\begingroup\$

J - 6567-6=61

No more the b. Adverb. Without counting the assignment of the function: 67 characters for the TF version, 63 for the non-TF version:

lgcTF =:".@({&('*+-+-<*01',.3 6#'.:')"1@n^:(9>n=:'&|~xv>^FT'&i.)@{.&.>&.;:)
lgc   =:".@({&('*+-+-<*',.3 4#'.:')"1@n^:(7>n=:'&|~xv>^'&i.)@{.&.>&.;:)

LgcTF handles both 0 and 1 as well as T and F.

Supports all of J's syntax in terms of trains, parenthesis, and evaluates strictly right to left (no other precedence rules).

All characters not in the operator list + Z can not be used, others will act as in standard J (including variables).

Usage:

NB.Assign TF anyhow
T=:1 [ F=: 0
lgc 'T & F'
0
lgc ' T ~@& F' NB. negation after and = nand
NB. make a truth table
d=: 0 1
lgc 'd ~@|/ d'
1 0
0 0 
NB. and so on... 
\$\endgroup\$
1
\$\begingroup\$

Postscript 263

Firefly's idea translated to Postscript.

{(0/xxx)dup 2 3 getinterval(%lineedit)(r)file exch 
readstring pop length 1 sub 3
getinterval(100011001110110v& x = |^> /~)dup
2 index 1 1 getinterval search pop exch pop exch pop 
length 3 2 roll{}forall exch pop exch 2 mul add 159 sub add 
1 getinterval =}loop

Indented:

%!

{
    (0/xxx) dup 2 3 getinterval
    (%lineedit)(r)file exch % (0/xxx) file (xxx)
    readstring pop
    length % (0/xxx) len(x|xx|xxx)
    1 sub 3 getinterval % (0/x)|(/xx)|(xxx)
    (100011001110110v& x = |^> /~) dup
    2 index 1 1 getinterval search pop % (0/x)|(/xx)|(xxx) s post match pre
    exch pop exch pop % (xxx) s pre
    length 
    3 2 roll {} forall exch pop % s len(pre) u_0 u_2
    exch 2 mul add 159 sub add % s ind
    1 getinterval
    = flush
} loop
\$\endgroup\$
1
\$\begingroup\$

Befunge-93, 86 characters

Works by hashing the second symbol of the input (finding a function that was both compact and avoided collisions was some work) for a y coordinate, and taking the first and third symbols each modulo 2 as the two least significant bits of the x coordinate, then retrieving whatever value is at the indicated position. A better hash function or more compact method of storing/addressing the truth tables are just two possible ways one could cut down on the length.

~~~\:8/\5%:++00p2%\2%2*+00gg,@
0 1







1001
0001
1101
1

0
0110



1110
1000


0111
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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