19
2
Syntax
~
not
/\
and
\/
or
t
true
f
false
P
, Q
, FISH
, etc: variables
(Operators are given in order of precedence)
Introduction
Some boolean formulae can be changed to different forms to make them shorter. For example, the formula
~(~P /\ ~Q)
can be changed to the shorter form
P\/Q
while the formula
P \/ ~P
can be changed to the shorter form
t
Challenge
In this challenge, you are required to write a program that, given any boolean formula using only /\
, \/
, ~
, t
, f
, parentheses, boolean variables (in uppercase), and whitespace, outputs a shortest form (since there may be more than one shortest form) in characters of that expression which is equivalent for all assignments of the variables. Shortest code (in any language) wins. I/O can be done in any reasonable manner.
Also, since answers are difficult to verify, it would be helpful (but isn't required) to include a brief explanation of how the code works.
In your "Challenge" section you do not mention any whitespace, but your examples have them. Should I handle them? – Victor Stafusa – 2014-03-10T01:53:51.927
@Victor Edited. – Lily Chung – 2014-03-10T01:56:08.993
What are you counting as the size of the expression: operators + variables + constants (i.e. ignoring parentheses), or characters (so that part of the solution is removing whitespace)? – Peter Taylor – 2014-03-10T08:23:42.717
@PeterTaylor Characters. – Lily Chung – 2014-03-10T15:24:29.350
Is it allowed to use third party lexer/parser library? – Florent – 2014-03-11T10:22:04.320
@Florent It is not. – Lily Chung – 2014-03-11T12:37:49.703
Do we have to handle
(P)
(which results inP
)? – Florent – 2014-03-11T16:39:50.283@Florent Yes, definitely. – Lily Chung – 2014-03-11T17:40:59.227
I'm not sure
code-golf
is the best tag for this challenge... – Florent – 2014-03-11T21:18:44.927@Florent Why not? Shortest code wins. – Lily Chung – 2014-03-11T21:49:36.600
4I think Florent's point is that it is a difficult problem to solve in general, let alone to golf. Among other things, the parser will need to be able to determine if two arbitrary formulae have the same truth conditions. Reducing p ^ ~p is easy enough if p is atomic, but how about ((A^B)v(A^C)) ^ ~(A^(BvC)) ? I think it is a cool problem and I am curious to see some responses. But if you want short solutions, the problem could be made more conducive to golfing by A. using prefix notation and B. providing a list of required reductions. – dfernig – 2014-03-12T02:34:34.947
@dfernig I briefly considered both of your suggestions (and regrettably bumped this question by editing and then rolling-back, oops...) , but I believe that (A) doesn't actually change the difficulty of the problem much, while (B) makes it much less interesting. – Lily Chung – 2014-03-12T04:18:15.380
1I have a valid (golfed) solution in more than 5000 characters. This is ridiculous... It is composed of a tokenizer, an AST-parser, an AST-rewriter and an expression generator. – Florent – 2014-03-12T13:27:20.280
1
Mathematica can do it in one function call (
– Florent – 2014-03-12T15:07:18.090BooleanMinimize
)@Florent I believe that Mathematica's
BooleanMinimize
will not always output the shortest form in characters - correct me if I'm wrong. – Lily Chung – 2014-03-12T15:25:15.790@IstvanChung Try it on Wolfram! It's unbeatable. – Florent – 2014-03-12T16:44:44.403
@Florent http://www.wolframalpha.com/input/?i=booleanminimize%28%28A+or+B%29+and+%28C+or+D%29+and+%28E+or+F%29%29
– Lily Chung – 2014-03-12T19:09:15.920@IstvanChung You have chosen a non-minimizable expression. Look at the DNF notation of this one
– Florent – 2014-03-12T20:01:52.020let us continue this discussion in chat
– Lily Chung – 2014-03-12T20:05:40.3601For the record, I have a 498-character solution now, whose sha256sum is
b9c98d088b78c30bb2108008a064a7b95722a4694d90ddad94a025c2eb4ed30a
. I'll post the actual code at a later date, as I don't want to stifle creativity. – Lily Chung – 2014-03-13T02:40:19.500