Commits

Shlomi Fish committed a23af10

Reached the solution.

It was generated by the not-a-opt-proto.pl and is documented in notes.txt.

  • Participants
  • Parent commits 77bd532

Comments (0)

Files changed (4)

File not-a-not-b-not-c.txt

 ----------------------------+---+---+---+---+---+---+---+---|
 ~A~B+~A~C+A~B~C             | 1   1   1   0   1   0   0   0 |
 ----------------------------+---+---+---+---+---+---+---+---|
+~(AB+AC+BC)                 | 1   1   1   0   1   0   0   0 |
+----------------------------+---+---+---+---+---+---+---+---|
+~(A XOR B XOR C)            | 1   0   0   1   0   1   1   0 |
+----------------------------+---+---+---+---+---+---+---+---|
+
 ~A~B + A = A + ~B
 
 A~B = A~B

File not-a-opt-proto.pl

 # @p is the population of the positions.
 my @p = (map { undef() } (0 .. $limit));
 
-sub lim
+sub neg
 {
-    return (shift() & $limit);
+    return ((~(shift())) & $limit);
 }
 
 my %initial;
 my $B = $initial{B} = 0b11001100;
 my $C = $initial{C} = 0b10101010;
 
-my $NOT_A = lim(~$A);
-my $NOT_B = lim(~$B);
-my $NOT_C = lim(~$C);
+my $NOT_A = neg($A);
+my $NOT_B = neg($B);
+my $NOT_C = neg($C);
 
 # $initial{NOT_AND} = ((~($initial{A} & $initial{B} & $initial{C})) & $limit);
 # $initial{NOT_OR2} = ((~($initial{A} | $initial{B} | $initial{C})) & $limit);
 
 my @start_p = @p;
 
-my @keys = (grep { $not_def->($_) } (0 .. $limit));
+foreach my $i (grep { $get->($_) } 0 .. $limit)
+{
+    print "Checking $i\n";
+    
+    my $neg = neg($i);
 
-for my $k_i (0 .. $#keys-1)
-{
-    print "Checking $k_i\n";
-    for my $k_j ($k_i+1 .. $#keys)
+    if ($not_def->($neg))
     {
         @p = @start_p;
 
-        $set->($keys[$k_i], ['i', 'k_i']);
-        $set->($keys[$k_j], ['i', 'k_j']);
+        $set->($neg, ['~', $i]);
+        
+        find();
 
-        if (find())
+        my @i_p = @p;
+
+        foreach my $j (grep { $get->($_) } (0 .. $limit))
         {
-            print sprintf("Found for 0b%.8b , 0b%.8b.\n", $keys[$k_i], $keys[$k_j]);
+            my $neg_j = neg($j);
+
+            @p = @i_p;
+
+            if ($not_def->($neg_j))
+            {
+                $set->($neg_j, ['~', $j]);
+                
+                if (find())
+                {
+                    foreach my $signal (qw(A B C))
+                    {
+                        my $n = neg($initial{$signal});
+                        print "~$signal = ", disp($n), "\n";
+                    }
+                }
+            }
         }
-
     }
 }
 
+sub disp
+{
+    my $n = shift;
 
+    my $e = $p[$n];
+
+    my $proto_ret = sub { 
+    if ($e->[0] eq "i")
+    {
+        return $e->[1];
+    }
+    elsif (($e->[0] eq "&") || ($e->[0] eq "|"))
+    {
+        return "(" . disp($e->[1]) . ")$e->[0](" . disp($e->[2]) . ")";
+    }
+    elsif ($e->[0] eq "~")
+    {
+        return "~(". disp($e->[1]) . ")";
+    }
+    else
+    {
+        die "Unknown e->[0] $e->[0]!";
+    }
+    }->();
+
+    $proto_ret =~ s{\(([ABC])\)}{$1}g;
+    $proto_ret =~ s{\(([ABC])&([ABC])\)}/
+        join("",sort { $a cmp $b } ($1,$2))
+        /eg;
+    $proto_ret =~ s/\(([ABC]{2})\|\(([ABC]{2})\|([ABC]{2})\)\)/
+        "(" . join("|", sort { $a cmp $b} ($1,$2,$3)) . ")"
+        /eg;
+
+    return $proto_ret;
+}
+
+Mort = ~(AB|AC|BC)
+Gang = ~((Mort&A)|(Mort&B)|(Mort&C)|(ABC))
+
+# Gang == NOT ( A XOR B XOR C )
+
+~A = (Mort&Gang)|(Mort&C)|(Mort&B)|(Gang&BC)
+~B = (Mort&Gang)|(Mort&C)|(Mort&A)|(Gang&AC)
+~C = (Mort&Gang)|(Mort&B)|(Mort&A)|(Gang&AB)
+

File process-proto.pl

     s/\$get->\(\$_\)/\$p[\$_]/;
     s/\$not_def->\(([^\)]+)\)/(!defined(\$p[$1]))/;
     s/\$set->\(([^,]+),([^\)]+)\)/\$p[$1] = $2/;
+    s/neg\(([^\)]+)\)/((~($1))&\$limit)/;
 
     return $_;
 }