1. Shlomi Fish
  2. riddle-not-a-not-b-not-c

Commits

Shlomi Fish  committed 1cb67fd

Add the script and some other stuff.

  • Participants
  • Parent commits 50667e6
  • Branches default

Comments (0)

Files changed (2)

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

View file
  • Ignore whitespace
 
 A ( ~B + ~C + ~A (B + C) ) = A~B + A~C = A (~B + ~C)
 
+AB~C + ~A~B~C = ~C (AB + ~A~B)
+
+(~B + ~C + ~A (B + C) )*(B+C) = ~BC + ~CB + ~A(B + C) = ~BC + ~CB + ~AB + ~AC
+= B (~A + ~C) + C (~A + ~B)
+
+
 -------------------------
 
 Contemplating:
 Alternatives:
 -------------
 
-~(AB + BC + AC) = (~A + ~B)(~A + ~C)(~B + ~C) = (~A +~B~C)(~B + ~C) = 
+~(AB + BC + AC) = (~A + ~B)(~A + ~C)(~B + ~C) = (~A + ~B~C)(~B + ~C) = 
 
 ~[(A+B)(B+C)(A+C)] = ~(A+B) + ~(B+C) + ~(A+C) = ~A~B + ~B~C + ~A~C
 
 A (~A~B + ~B~C + ~A~C) = A~B~C
 
-~XY = ~X + ~Y
+A~B~C + ~AB~C = ~C(A XOR B)
+
+~A~B + ~B~C + ~A~C + A = A + ~B + ~C
+
+A~B~C + ~AB~C + C = (A XOR B) + C = C + A~B + ~AB
+
+B*(C + A~B + ~AB) = BC + ~AB = B (C + ~A)
+
+BC + ~AB + ~BA + AC = C(A + B) + (A XOR B)
+
+A~B~C + B  = B + A~C
+
+(B + A~C) + (~A~B + ~B~C + ~A~C) = ~A + ~C + B
+
+(A + ~B + ~C) * (~AB~C) = ~AB~C
 
 / ~A~B -> A + ~B ; B + ~A ; ~A~B~C ; A + ~C ; C + ~A ; ~A (~B + ~C)
 |      -> ~A~B + ~A~C

File not-a.pl

View file
  • Ignore whitespace
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use List::MoreUtils qw(all);
+
+my $limit = 0xFF;
+
+my $population =
+{ 
+    'p' => [map { undef() } (0 .. $limit)],
+};
+
+sub lim
+{
+    return (shift() & $limit);
+}
+
+my %initial;
+
+my $A = $initial{A} = 0b11110000;
+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);
+
+# $initial{NOT_AND} = ((~($initial{A} & $initial{B} & $initial{C})) & $limit);
+# $initial{NOT_OR2} = ((~($initial{A} | $initial{B} | $initial{C})) & $limit);
+# $initial{NOT_OR} = ((~(($A & $B) | ($A & $C) | ($B & $C))) & $limit);
+# $initial{B_NOT} = ((~$B) & $limit);
+# $initial{C_NOT} = ((~$C) & $limit);
+# $initial{NOT_AB} = ((~(($A | $B))) & $limit);
+# $initial{NOT_AC} = ((~(($A & $C))) & $limit);
+
+# $initial{NOT_OR} = ((~($B & ($A | $C))) & $limit);
+# $initial{NOT_AND2} = ((~($B)) & $limit);
+
+my $get = sub {
+    my $i = shift;
+
+    return $population->{p}[$i];
+};
+
+my $not_def = sub {
+    my $i = shift;
+
+    return !defined($get->($i));
+};
+
+my $set = sub {
+    my ($i, $val) = @_;
+
+    $population->{p}[$i] = $val;
+
+    return;
+};
+
+while (my ($key, $mask) = each(%initial))
+{
+    $set->($mask, ['i', $key]);
+}
+
+sub find
+{
+    my $found;
+    POP:
+    while (! ($found = all { $get->($_) } ($NOT_A, $NOT_B, $NOT_C)))
+    {
+        X_LOOP:
+        for my $x (0 .. ($limit-1))
+        {
+            if ($not_def->($x))
+            {
+                next X_LOOP;
+            }
+
+            Y_LOOP:
+            for my $y (($x+1) .. $limit)
+            {
+                if ($not_def->($y))
+                {
+                    next Y_LOOP;
+                }
+
+                my $new;
+                if ($not_def->($x & $y))
+                {
+                    $set->(($x & $y), ['&', $x, $y]);
+                    $new = 1;
+                }
+
+                if ($not_def->($x | $y))
+                {
+                    $set->(($x | $y), ['|', $x, $y]);
+                    $new = 1;
+                }
+                
+                if ($new)
+                {
+                    next POP;
+                }
+            }
+        }
+
+        last POP;
+    }
+    return $found;
+}
+
+find();
+
+my $init_population = { p => [ @{$population->{p}} ] };
+
+my @keys = (grep { $not_def->($_) } (0 .. $limit));
+
+for my $k_i (0 .. $#keys-1)
+{
+    for my $k_j ($k_i+1 .. $#keys)
+    {
+        print "Checking $k_i and $k_j\n";
+
+        $population = { p => [ @{$init_population->{p}} ] };
+
+        $set->($keys[$k_i], ['i', 'k_i']);
+        $set->($keys[$k_j], ['i', 'k_j']);
+
+        if (find())
+        {
+            print sprintf("Found for 0b%.8b , 0b%.8b.\n", $keys[$k_i], $keys[$k_j]);
+            exit(0);
+        }
+
+    }
+}
+
+