Twelve statements: Difference between revisions
m →{{header|Prolog}}: Simplification of the code |
|||
Line 696: | Line 696: | ||
% 2. Exactly 3 of the last 6 statements are true. |
% 2. Exactly 3 of the last 6 statements are true. |
||
A2 |
A2 #<==> A7 + A8 + A9 + A10 + A11 + A12 #= 3, |
||
% 3. Exactly 2 of the even-numbered statements are true. |
% 3. Exactly 2 of the even-numbered statements are true. |
||
A3 |
A3 #<==> A2 + A4 + A6 + A8 + A10 + A12 #= 2, |
||
% 4. If statement 5 is true, then statements 6 and 7 are both true. |
% 4. If statement 5 is true, then statements 6 and 7 are both true. |
||
A4 |
A4 #<==> (A5 #==> (A6 #/\ A7)), |
||
% 5. The 3 preceding statements are all false. |
% 5. The 3 preceding statements are all false. |
||
A5 |
A5 #<==> A2 + A3 + A4 #= 0, |
||
% 6. Exactly 4 of the odd-numbered statements are true. |
% 6. Exactly 4 of the odd-numbered statements are true. |
||
A6 |
A6 #==> A1 + A3 + A5 + A7 + A9 + A11 #= 4, |
||
% 7. Either statement 2 or 3 is true, but not both. |
% 7. Either statement 2 or 3 is true, but not both. |
||
A7 |
A7 #<==> A2 #\/ A3 , |
||
% 8. If statement 7 is true, then 5 and 6 are both true. |
% 8. If statement 7 is true, then 5 and 6 are both true. |
||
A8 |
A8 #<==> (A7 #==> A5 #/\ A6), |
||
% 9. Exactly 3 of the first 6 statements are true. |
% 9. Exactly 3 of the first 6 statements are true. |
||
A9 |
A9 #<==> A1 + A2 + A3 + A4 + A5 + A6 #= 3, |
||
% 10. The next two statements are both true. |
% 10. The next two statements are both true. |
||
A10 |
A10 #<==> A11 #/\ A12, |
||
% 11. Exactly 1 of statements 7, 8 and 9 are true. |
% 11. Exactly 1 of statements 7, 8 and 9 are true. |
||
A11 |
A11 #<==> A7 + A8 + A9 #= 1, |
||
% 12. Exactly 4 of the preceding statements are true. |
% 12. Exactly 4 of the preceding statements are true. |
||
A12 |
A12 #<==> A1 + A2 + A3 + A4 + A5 + A6 + A7 +A8 + A9 + A10 + A11 #= 4, |
||
label(L), |
label(L), |
||
Line 745: | Line 745: | ||
Statements 1 3 4 6 7 11 are true |
Statements 1 3 4 6 7 11 are true |
||
true .</pre> |
true .</pre> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
Note: we choose to adapt the statement numbering to zero-based indexing in the constraintinfo lambda expressions but convert back to one-based on output. |
Note: we choose to adapt the statement numbering to zero-based indexing in the constraintinfo lambda expressions but convert back to one-based on output. |
Revision as of 23:59, 1 November 2012
You are encouraged to solve this task according to the task description, using any language you may know.
This puzzle is borrowed from here.
Given the following twelve statements, which of them are true?
1. This is a numbered list of twelve statements. 2. Exactly 3 of the last 6 statements are true. 3. Exactly 2 of the even-numbered statements are true. 4. If statement 5 is true, then statements 6 and 7 are both true. 5. The 3 preceding statements are all false. 6. Exactly 4 of the odd-numbered statements are true. 7. Either statement 2 or 3 is true, but not both. 8. If statement 7 is true, then 5 and 6 are both true. 9. Exactly 3 of the first 6 statements are true. 10. The next two statements are both true. 11. Exactly 1 of statements 7, 8 and 9 are true. 12. Exactly 4 of the preceding statements are true.
When you get tired of trying to figure it out in your head, write a program to solve it, and print the correct answer or answers.
Extra credit: also print out a table of near misses, that is, solutions that are contradicted by only a single statement.
Ada
Here is the main program, using a generic package Logic. The expression function introduced by the new standard Ada 2012 are very handy for this task.
<lang Ada>with Ada.Text_IO, Logic;
procedure Twelve_Statements is
package L is new Logic(Number_Of_Statements => 12); use L; -- formally define the 12 statements as expression function predicates function P01(T: Table) return Boolean is (T'Length = 12); -- list of 12 statements function P02(T: Table) return Boolean is (Sum(T(7 .. 12)) = 3); -- three of last six function P03(T: Table) return Boolean is (Sum(Half(T, Even)) = 2); -- two of the even function P04(T: Table) return Boolean is (if T(5) then T(6) and T(7)); -- if 5 is true, then ... function P05(T: Table) return Boolean is ( (not T(2)) and (not T(3)) and (not T(4)) ); -- none of preceding three function P06(T: Table) return Boolean is (Sum(Half(T, Odd)) = 4); -- four of the odd function P07(T: Table) return Boolean is (T(2) xor T(3)); -- either 2 or 3, not both function P08(T: Table) return Boolean is (if T(7) then T(5) and T(6)); -- if 7 is true, then ... function P09(T: Table) return Boolean is (Sum(T(1 .. 6)) = 3); -- three of first six function P10(T: Table) return Boolean is (T(11) and T(12)); -- next two function P11(T: Table) return Boolean is (Sum(T(7..9)) = 1); -- one of 7, 8, 9 function P12(T: Table) return Boolean is (Sum(T(1 .. 11)) = 4); -- four of the preding -- define a global list of statements Statement_List: constant Statements := (P01'Access, P02'Access, P03'Access, P04'Access, P05'Access, P06'Access, P07'Access, P08'Access, P09'Access, P10'Access, P11'Access, P12'Access); -- try out all 2^12 possible choices for the table procedure Try(T: Table; Fail: Natural; Idx: Indices'Base := Indices'First) is procedure Print_Table(T: Table) is
use Ada.Text_IO;
begin
Put(" "); if Fail > 0 then Put("(wrong at"); for J in T'Range loop if Statement_List(J)(T) /= T(J) then Put(Integer'Image(J) & (if J < 10 then ") " else ") ")); end if; end loop; end if; if T = (1..12 => False) then Put_Line("All false!"); else Put("True are"); for J in T'Range loop if T(J) then Put(Integer'Image(J)); end if; end loop; New_Line; end if;
end Print_Table; Wrong_Entries: Natural := 0;
begin if Idx <= T'Last then
Try(T(T'First .. Idx-1) & False & T(Idx+1 .. T'Last), Fail, Idx+1); Try(T(T'First .. Idx-1) & True & T(Idx+1 .. T'Last), Fail, Idx+1);
else -- now Index > T'Last and we have one of the 2^12 choices to test
for J in T'Range loop if Statement_List(J)(T) /= T(J) then Wrong_Entries := Wrong_Entries + 1; end if; end loop; if Wrong_Entries = Fail then Print_Table(T); end if;
end if; end Try;
begin
Ada.Text_IO.Put_Line("Exact hits:"); Try(T => (1..12 => False), Fail => 0); Ada.Text_IO.New_Line; Ada.Text_IO.Put_Line("Near Misses:"); Try(T => (1..12 => False), Fail => 1);
end Twelve_Statements;</lang>
- Output:
Exact hits: True are 1 3 4 6 7 11 Near Misses: (wrong at 1) True are 5 8 11 (wrong at 1) True are 5 8 10 11 12 (wrong at 1) True are 4 8 10 11 12 (wrong at 8) True are 1 5 (wrong at 11) True are 1 5 8 (wrong at 12) True are 1 5 8 11 (wrong at 12) True are 1 5 8 10 11 12 (wrong at 8) True are 1 5 6 9 11 (wrong at 8) True are 1 4 (wrong at 12) True are 1 4 8 10 11 12 (wrong at 6) True are 1 4 6 8 9 (wrong at 7) True are 1 3 4 8 9 (wrong at 9) True are 1 3 4 6 7 9 (wrong at 12) True are 1 2 4 7 9 12 (wrong at 10) True are 1 2 4 7 9 10 (wrong at 8) True are 1 2 4 7 8 9
Here is the definition the package Logic:
<lang Ada>generic
Number_Of_Statements: Positive;
package Logic is
--types subtype Indices is Natural range 1 .. Number_Of_Statements; type Table is array(Indices range <>) of Boolean; type Predicate is access function(T: Table) return Boolean; type Statements is array(Indices) of Predicate; type Even_Odd is (Even, Odd); -- convenience functions function Sum(T: Table) return Natural; function Half(T: Table; Which: Even_Odd) return Table;
end Logic;</lang>
And here is the implementation of the "convenience functions" in Logic:
<lang Ada>package body Logic is
function Sum(T: Table) return Natural is Result: Natural := 0; begin for I in T'Range loop if T(I) then Result := Result + 1; end if; end loop; return Result; end Sum; function Half(T: Table; Which: Even_Odd) return Table is Result: Table(T'Range); Last: Natural := Result'First - 1; begin for I in T'Range loop if I mod 2 = (if (Which=Odd) then 1 else 0) then Last := Last+1; Result(Last) := T(I); end if; end loop; return Result(Result'First .. Last); end Half;
end Logic;</lang>
BBC BASIC
<lang bbcbasic> nStatements% = 12
DIM Pass%(nStatements%), T%(nStatements%) FOR try% = 0 TO 2^nStatements%-1 REM Postulate answer: FOR stmt% = 1 TO 12 T%(stmt%) = (try% AND 2^(stmt%-1)) <> 0 NEXT REM Test consistency: Pass%(1) = T%(1) = (nStatements% = 12) Pass%(2) = T%(2) = ((T%(7)+T%(8)+T%(9)+T%(10)+T%(11)+T%(12)) = -3) Pass%(3) = T%(3) = ((T%(2)+T%(4)+T%(6)+T%(8)+T%(10)+T%(12)) = -2) Pass%(4) = T%(4) = ((NOT T%(5) OR (T%(6) AND T%(7)))) Pass%(5) = T%(5) = (NOT T%(2) AND NOT T%(3) AND NOT T%(4)) Pass%(6) = T%(6) = ((T%(1)+T%(3)+T%(5)+T%(7)+T%(9)+T%(11)) = -4) Pass%(7) = T%(7) = ((T%(2) EOR T%(3))) Pass%(8) = T%(8) = ((NOT T%(7) OR (T%(5) AND T%(6)))) Pass%(9) = T%(9) = ((T%(1)+T%(2)+T%(3)+T%(4)+T%(5)+T%(6)) = -3) Pass%(10) = T%(10) = (T%(11) AND T%(12)) Pass%(11) = T%(11) = ((T%(7)+T%(8)+T%(9)) = -1) Pass%(12) = T%(12) = ((T%(1)+T%(2)+T%(3)+T%(4)+T%(5)+T%(6) + \ \ T%(7)+T%(8)+T%(9)+T%(10)+T%(11)) = -4) CASE SUM(Pass%()) OF WHEN -11: PRINT "Near miss with statements "; FOR stmt% = 1 TO 12 IF T%(stmt%) PRINT ; stmt% " "; IF NOT Pass%(stmt%) miss% = stmt% NEXT PRINT "true (failed " ;miss% ")." WHEN -12: PRINT "Solution! with statements "; FOR stmt% = 1 TO 12 IF T%(stmt%) PRINT ; stmt% " "; NEXT PRINT "true." ENDCASE NEXT try% END</lang>
Output:
Near miss with statements 1 4 true (failed 8). Near miss with statements 1 5 true (failed 8). Near miss with statements 1 5 8 true (failed 11). Near miss with statements 1 3 4 6 7 9 true (failed 9). Near miss with statements 1 3 4 8 9 true (failed 7). Near miss with statements 1 4 6 8 9 true (failed 6). Near miss with statements 1 2 4 7 8 9 true (failed 8). Near miss with statements 1 2 4 7 9 10 true (failed 10). Solution! with statements 1 3 4 6 7 11 true. Near miss with statements 5 8 11 true (failed 1). Near miss with statements 1 5 8 11 true (failed 12). Near miss with statements 1 5 6 9 11 true (failed 8). Near miss with statements 1 2 4 7 9 12 true (failed 12). Near miss with statements 4 8 10 11 12 true (failed 1). Near miss with statements 1 4 8 10 11 12 true (failed 12). Near miss with statements 5 8 10 11 12 true (failed 1). Near miss with statements 1 5 8 10 11 12 true (failed 12).
D
<lang d>import std.stdio, std.typecons, std.algorithm,std.range,std.functional;
immutable texts = [
"this is a numbered list of twelve statements", "exactly 3 of the last 6 statements are true", "exactly 2 of the even-numbered statements are true", "if statement 5 is true, then statements 6 and 7 are both true", "the 3 preceding statements are all false", "exactly 4 of the odd-numbered statements are true", "either statement 2 or 3 is true, but not both", "if statement 7 is true, then 5 and 6 are both true", "exactly 3 of the first 6 statements are true", "the next two statements are both true", "exactly 1 of statements 7, 8 and 9 are true", "exactly 4 of the preceding statements are true"];
alias curry!(reduce!q{a + b}, 0) sumi;
immutable bool function(in bool[])[] funcs = [
s => s.length == 12, s => sumi(s[$-6 .. $]) == 3, s => sumi(s[1 .. $].stride(2)) == 2, s => s[4] ? (s[5] && s[6]) : true, s => sumi(s[1 .. 4]) == 0, s => sumi(s[0 .. $].stride(2)) == 4, s => sumi(s[1 .. 3]) == 1, s => s[6] ? (s[4] && s[5]) : true, s => sumi(s[0 .. 6]) == 3, s => s[10] && s[11], s => sumi(s[6 .. 9]) == 1, s => sumi(s[0 .. 11]) == 4];
void main() {
enum nStats = 12; Tuple!(const bool[], const bool[])[] full, partial;
foreach (n; 0 .. 2 ^^ nStats) { const st = iota(nStats).map!(i => !!(n & (2 ^^ i)))().array(); auto truths = funcs.map!(f => f(st))(); const matches = zip(st, truths) .map!(s_t => s_t[0] == s_t[1])() .array(); immutable mCount = matches.sumi(); if (mCount == nStats) full ~= tuple(st, matches); else if (mCount == nStats - 1) partial ~= tuple(st, matches); }
foreach (sols, isPartial; zip([full, partial], [false, true])) foreach (stm; sols) { if (isPartial) { immutable pos = stm[1].countUntil(false); writefln(`Missed by statement %d: "%s"`, pos + 1, texts[pos]); } else writeln("Solution:"); write(" "); foreach (i, t; stm[0]) writef("%d:%s ", i + 1, t ? "T" : "F"); writeln(); }
}</lang>
- Output:
Solution: 1:T 2:F 3:T 4:T 5:F 6:T 7:T 8:F 9:F 10:F 11:T 12:F Missed by statement 8: "if statement 7 is true, then 5 && 6 are both true" 1:T 2:F 3:F 4:T 5:F 6:F 7:F 8:F 9:F 10:F 11:F 12:F Missed by statement 8: "if statement 7 is true, then 5 && 6 are both true" 1:T 2:F 3:F 4:F 5:T 6:F 7:F 8:F 9:F 10:F 11:F 12:F Missed by statement 11: "exactly 1 of statements 7, 8 && 9 are true" 1:T 2:F 3:F 4:F 5:T 6:F 7:F 8:T 9:F 10:F 11:F 12:F Missed by statement 9: "exactly 3 of the first 6 statements are true" 1:T 2:F 3:T 4:T 5:F 6:T 7:T 8:F 9:T 10:F 11:F 12:F Missed by statement 7: "either statement 2 or 3 is true, but not both" 1:T 2:F 3:T 4:T 5:F 6:F 7:F 8:T 9:T 10:F 11:F 12:F Missed by statement 6: "exactly 4 of the odd-numbered statements are true" 1:T 2:F 3:F 4:T 5:F 6:T 7:F 8:T 9:T 10:F 11:F 12:F Missed by statement 8: "if statement 7 is true, then 5 && 6 are both true" 1:T 2:T 3:F 4:T 5:F 6:F 7:T 8:T 9:T 10:F 11:F 12:F Missed by statement 10: "the next two statements are both true" 1:T 2:T 3:F 4:T 5:F 6:F 7:T 8:F 9:T 10:T 11:F 12:F Missed by statement 1: "this is a numbered list of twelve statements" 1:F 2:F 3:F 4:F 5:T 6:F 7:F 8:T 9:F 10:F 11:T 12:F Missed by statement 12: "exactly 4 of the preceding statements are true" 1:T 2:F 3:F 4:F 5:T 6:F 7:F 8:T 9:F 10:F 11:T 12:F Missed by statement 8: "if statement 7 is true, then 5 && 6 are both true" 1:T 2:F 3:F 4:F 5:T 6:T 7:F 8:F 9:T 10:F 11:T 12:F Missed by statement 12: "exactly 4 of the preceding statements are true" 1:T 2:T 3:F 4:T 5:F 6:F 7:T 8:F 9:T 10:F 11:F 12:T Missed by statement 1: "this is a numbered list of twelve statements" 1:F 2:F 3:F 4:T 5:F 6:F 7:F 8:T 9:F 10:T 11:T 12:T Missed by statement 12: "exactly 4 of the preceding statements are true" 1:T 2:F 3:F 4:T 5:F 6:F 7:F 8:T 9:F 10:T 11:T 12:T Missed by statement 1: "this is a numbered list of twelve statements" 1:F 2:F 3:F 4:F 5:T 6:F 7:F 8:T 9:F 10:T 11:T 12:T Missed by statement 12: "exactly 4 of the preceding statements are true" 1:T 2:F 3:F 4:F 5:T 6:F 7:F 8:T 9:F 10:T 11:T 12:T
Go
<lang go>package main
import "fmt"
// its' not too much more work to check all the permutations concurrently var solution = make(chan int) var nearMiss = make(chan int) var done = make(chan bool)
func main() {
// iterate and use the bits as the permutation for i := 0; i < 4096; i++ { go checkPerm(i) } // collect the misses and list them after the complete solution(s) var ms []int for i := 0; i < 4096; { select { case <-done: i++ case s := <-solution: print12("solution", s) case m := <-nearMiss: ms = append(ms, m) } } for _, m := range ms { print12("near miss", m) }
}
func print12(label string, bits int) {
fmt.Print(label, ":") for i := 1; i <= 12; i++ { if bits&1 == 1 { fmt.Print(" ", i) } bits >>= 1 } fmt.Println()
}
func checkPerm(tz int) {
// closure returns true if tz bit corresponding to // 1-based statement number is 1. ts := func(n uint) bool { return tz>>(n-1)&1 == 1 } // variadic closure returns number of statements listed as arguments // which have corresponding tz bit == 1. ntrue := func(xs ...uint) int { nt := 0 for _, x := range xs { if ts(x) { nt++ } } return nt } // a flag used on repeated calls to test. // set to true when first contradiction is found. // if another is found, this function (checkPerm) can "short circuit" // and return immediately without checking additional statements. var con bool // closure called to test each statement test := func(statement uint, b bool) { switch { case ts(statement) == b: case con: panic("bail") default: con = true } } // short circuit mechanism defer func() { if x := recover(); x != nil { if msg, ok := x.(string); !ok && msg != "bail" { panic(x) } } done <- true }()
// 1. This is a numbered list of twelve statements. test(1, true)
// 2. Exactly 3 of the last 6 statements are true. test(2, ntrue(7, 8, 9, 10, 11, 12) == 3)
// 3. Exactly 2 of the even-numbered statements are true. test(3, ntrue(2, 4, 6, 8, 10, 12) == 2)
// 4. If statement 5 is true, then statements 6 and 7 are both true. test(4, !ts(5) || ts(6) && ts(7))
// 5. The 3 preceding statements are all false. test(5, !ts(4) && !ts(3) && !ts(2))
// 6. Exactly 4 of the odd-numbered statements are true. test(6, ntrue(1, 3, 5, 7, 9, 11) == 4)
// 7. Either statement 2 or 3 is true, but not both. test(7, ts(2) != ts(3))
// 8. If statement 7 is true, then 5 and 6 are both true. test(8, !ts(7) || ts(5) && ts(6))
// 9. Exactly 3 of the first 6 statements are true. test(9, ntrue(1, 2, 3, 4, 5, 6) == 3) // 10. The next two statements are both true. test(10, ts(11) && ts(12)) // 11. Exactly 1 of statements 7, 8 and 9 are true. test(11, ntrue(7, 8, 9) == 1) // 12. Exactly 4 of the preceding statements are true. test(12, ntrue(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) == 4)
// no short circuit? send permutation as either near miss or solution if con { nearMiss <- tz } else { solution <- tz }
}</lang>
- Output:
solution: 1 3 4 6 7 11 near miss: 1 4 near miss: 1 5 near miss: 1 5 8 near miss: 1 3 4 6 7 9 near miss: 1 3 4 8 9 near miss: 1 4 6 8 9 near miss: 1 2 4 7 8 9 near miss: 1 2 4 7 9 10 near miss: 5 8 11 near miss: 1 5 8 11 near miss: 1 5 6 9 11 near miss: 1 2 4 7 9 12 near miss: 1 4 8 10 11 12 near miss: 4 8 10 11 12 near miss: 5 8 10 11 12 near miss: 1 5 8 10 11 12
Haskell
Shows answers with 1 for true, followed by list of indices of contradicting elements in each set of 1/0s (index is 0-based).
<lang haskell>import Data.List (findIndices)
tf = mapM (\_ -> [1,0])
wrongness b = findIndices id . zipWith (/=) b . map (fromEnum . ($ b))
statements = [ (==12) . length, 3 ⊂ [length statements-6..], 2 ⊂ [1,3..], 4 → [4..6], 0 ⊂ [1..3], 4 ⊂ [0,2..], 1 ⊂ [1,2], 6 → [4..6], 3 ⊂ [0..5], 2 ⊂ [10,11], 1 ⊂ [6,7,8], 4 ⊂ [0..10] ] where (s ⊂ x) b = s == (sum . map (b!!) . takeWhile (< length b)) x (a → x) b = (b!!a == 0) || all ((==1).(b!!)) x
testall s n = [(b, w) | b <- tf s, w <- [wrongness b s], length w == n]
main = let t = testall statements in do putStrLn "Answer" mapM_ print $ t 0 putStrLn "Near misses" mapM_ print $ t 1</lang>
- Output:
Answer ([1,0,1,1,0,1,1,0,0,0,1,0],[]) Near misses ([1,1,0,1,0,0,1,1,1,0,0,0],[7]) ([1,1,0,1,0,0,1,0,1,1,0,0],[9]) ([1,1,0,1,0,0,1,0,1,0,0,1],[11]) ([1,0,1,1,0,1,1,0,1,0,0,0],[8]) ([1,0,1,1,0,0,0,1,1,0,0,0],[6]) ([1,0,0,1,0,1,0,1,1,0,0,0],[5]) ([1,0,0,1,0,0,0,1,0,1,1,1],[11]) ([1,0,0,1,0,0,0,0,0,0,0,0],[7]) ([1,0,0,0,1,1,0,0,1,0,1,0],[7]) ([1,0,0,0,1,0,0,1,0,1,1,1],[11]) ([1,0,0,0,1,0,0,1,0,0,1,0],[11]) ([1,0,0,0,1,0,0,1,0,0,0,0],[10]) ([1,0,0,0,1,0,0,0,0,0,0,0],[7]) ([0,0,0,1,0,0,0,1,0,1,1,1],[0]) ([0,0,0,0,1,0,0,1,0,1,1,1],[0]) ([0,0,0,0,1,0,0,1,0,0,1,0],[0])
J
In the following 'apply' is the foreign conjunction: <lang j> apply 128!:2
NB. example
'*:' apply 1 2 3
1 4 9</lang> This enables us to apply strings (left argument) being verbs to the right argument, mostly a noun. <lang j>S=: <;._2 (0 :0) 12&=@# 3=+/@:{.~&_6 2= +/@:{~&1 3 5 7 9 11 4&{=*./@:{~&4 5 6 0=+/@:{~&1 2 3 4=+/@:{~&0 2 4 6 8 10 1=+/@:{~&1 2 6&{=*./@:{~&4 5 6 3=+/@:{.~&6 2=+/@:{~&10 11 1=+/@:{~&6 7 8 4=+/@:{.~&11 )
testall=: (];"1 0<@I.@:(]~:(apply&><))"1) #:@i.@(2&^)@#</lang>
The output follows the Haskell convention: true/false bitstring followed by the index of a contradiction
All true <lang j> (#~0=#@{::~&_1"1) testall S ┌───────────────────────┬┐ │1 0 1 1 0 1 1 0 0 0 1 0││ └───────────────────────┴┘</lang> Near misses <lang j> (#~1=#@{::~&_1"1) testall S ┌───────────────────────┬──┐ │0 0 0 0 1 0 0 1 0 0 1 0│0 │ ├───────────────────────┼──┤ │0 0 0 0 1 0 0 1 0 1 1 1│0 │ ├───────────────────────┼──┤ │0 0 0 1 0 0 0 1 0 1 1 1│0 │ ├───────────────────────┼──┤ │1 0 0 0 1 0 0 0 0 0 0 0│7 │ ├───────────────────────┼──┤ │1 0 0 0 1 0 0 1 0 0 0 0│10│ ├───────────────────────┼──┤ │1 0 0 0 1 0 0 1 0 0 1 0│11│ ├───────────────────────┼──┤ │1 0 0 0 1 0 0 1 0 1 1 1│11│ ├───────────────────────┼──┤ │1 0 0 0 1 1 0 0 1 0 1 0│7 │ ├───────────────────────┼──┤ │1 0 0 1 0 0 0 0 0 0 0 0│7 │ ├───────────────────────┼──┤ │1 0 0 1 0 0 0 1 0 1 1 1│11│ ├───────────────────────┼──┤ │1 0 0 1 0 1 0 1 1 0 0 0│5 │ ├───────────────────────┼──┤ │1 0 1 1 0 0 0 1 1 0 0 0│6 │ ├───────────────────────┼──┤ │1 0 1 1 0 1 1 0 1 0 0 0│8 │ ├───────────────────────┼──┤ │1 1 0 1 0 0 1 0 1 0 0 1│11│ ├───────────────────────┼──┤ │1 1 0 1 0 0 1 0 1 1 0 0│9 │ ├───────────────────────┼──┤ │1 1 0 1 0 0 1 1 1 0 0 0│7 │ └───────────────────────┴──┘</lang>
Iterative for all true
In fact a repeat while true construction: x f^:(p)^:_ y
<lang j> (-N)&{. #: S <:@]^:((]-.@-:(apply&><)"1) (-N)&{.@#:@])^:(_) 2^N=.#S
1 0 1 1 0 1 1 0 0 0 1 0</lang>
Perl 6
<lang perl6>sub infix:<→> ($protasis,$apodosis) { !$protasis or $apodosis }
my @tests = { True }, # (there's no 0th statement)
{ all(.[1..12]) === any(True, False) }, { 3 == [+] .[7..12] }, { 2 == [+] .[2,4...12] }, { .[5] → all .[6,7] }, { none .[2,3,4] }, { 4 == [+] .[1,3...11] }, { one .[2,3] }, { .[7] → all .[5,6] }, { 3 == [+] .[1..6] }, { all .[11,12] }, { one .[7,8,9] }, { 4 == [+] .[1..11] };
my @good; my @bad; my @ugly;
for reverse 0 ..^ 2**12 -> $i {
my @b = $i.fmt("%012b").comb; my @assert = True, @b.map: { .so } my @result = @tests.map: { .(@assert).so } my @s = ( $_ if $_ and @assert[$_] for 1..12 ); if @result eqv @assert {
push @good, "<{@s}> is consistent.";
} else {
my @cons = gather for 1..12 { if @assert[$_] !eqv @result[$_] { take @result[$_] ?? $_ !! "¬$_"; } } my $mess = "<{@s}> implies {@cons}."; if @cons == 1 { push @bad, $mess } else { push @ugly, $mess }
}
}
.say for @good; say "\nNear misses:"; .say for @bad;</lang>
- Output:
<1 3 4 6 7 11> is consistent. Near misses: <1 2 4 7 8 9> implies ¬8. <1 2 4 7 9 10> implies ¬10. <1 2 4 7 9 12> implies ¬12. <1 3 4 6 7 9> implies ¬9. <1 3 4 8 9> implies 7. <1 4 6 8 9> implies ¬6. <1 4 8 10 11 12> implies ¬12. <1 4> implies 8. <1 5 6 9 11> implies 8. <1 5 8 10 11 12> implies ¬12. <1 5 8 11> implies 12. <1 5 8> implies 11. <1 5> implies 8. <4 8 10 11 12> implies 1. <5 8 10 11 12> implies 1. <5 8 11> implies 1.
Prolog
Works with SWI-Prolog and library(clpfd). <lang Prolog>puzzle :-
% 1. This is a numbered list of twelve statements.
L = [A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12], L ins 0..1, element(1, L, 1),
% 2. Exactly 3 of the last 6 statements are true.
A2 #<==> A7 + A8 + A9 + A10 + A11 + A12 #= 3,
% 3. Exactly 2 of the even-numbered statements are true.
A3 #<==> A2 + A4 + A6 + A8 + A10 + A12 #= 2,
% 4. If statement 5 is true, then statements 6 and 7 are both true.
A4 #<==> (A5 #==> (A6 #/\ A7)),
% 5. The 3 preceding statements are all false.
A5 #<==> A2 + A3 + A4 #= 0,
% 6. Exactly 4 of the odd-numbered statements are true.
A6 #==> A1 + A3 + A5 + A7 + A9 + A11 #= 4,
% 7. Either statement 2 or 3 is true, but not both.
A7 #<==> A2 #\/ A3 ,
% 8. If statement 7 is true, then 5 and 6 are both true.
A8 #<==> (A7 #==> A5 #/\ A6),
% 9. Exactly 3 of the first 6 statements are true.
A9 #<==> A1 + A2 + A3 + A4 + A5 + A6 #= 3,
% 10. The next two statements are both true.
A10 #<==> A11 #/\ A12,
% 11. Exactly 1 of statements 7, 8 and 9 are true.
A11 #<==> A7 + A8 + A9 #= 1,
% 12. Exactly 4 of the preceding statements are true.
A12 #<==> A1 + A2 + A3 + A4 + A5 + A6 + A7 +A8 + A9 + A10 + A11 #= 4,
label(L),
numlist(1, 12, NL),
write('Statements '), maplist(my_write, NL, L), writeln('are true').
my_write(N, 1) :-
format('~w ', [N]).
my_write(_N, 0). </lang> Output :
?- puzzle. Statements 1 3 4 6 7 11 are true true .
Python
Note: we choose to adapt the statement numbering to zero-based indexing in the constraintinfo lambda expressions but convert back to one-based on output.
The program uses brute force to generate all possible boolean values of the twelve statements then checks if the actual value of the statements matches the proposed or matches apart from exactly one deviation. Python's boolean type boolis a subclass of int, so boolean values True, False can be used as integers (1, 0, respectively) in numerical contexts. This fact is used in the lambda expressions that use function sum. <lang python> from itertools import product
- from pprint import pprint as pp
constraintinfo = (
(lambda st: len(st) == 12 ,(1, 'This is a numbered list of twelve statements')), (lambda st: sum(st[-6:]) == 3 ,(2, 'Exactly 3 of the last 6 statements are true')), (lambda st: sum(st[1::2]) == 2 ,(3, 'Exactly 2 of the even-numbered statements are true')), (lambda st: (st[5]&st[6]) if st[4] else 1 ,(4, 'If statement 5 is true, then statements 6 and 7 are both true')), (lambda st: sum(st[1:4]) == 0 ,(5, 'The 3 preceding statements are all false')), (lambda st: sum(st[0::2]) == 4 ,(6, 'Exactly 4 of the odd-numbered statements are true')), (lambda st: sum(st[1:3]) == 1 ,(7, 'Either statement 2 or 3 is true, but not both')), (lambda st: (st[4]&st[5]) if st[6] else 1 ,(8, 'If statement 7 is true, then 5 and 6 are both true')), (lambda st: sum(st[:6]) == 3 ,(9, 'Exactly 3 of the first 6 statements are true')), (lambda st: (st[10]&st[11]) ,(10, 'The next two statements are both true')), (lambda st: sum(st[6:9]) == 1 ,(11, 'Exactly 1 of statements 7, 8 and 9 are true')), (lambda st: sum(st[0:11]) == 4 ,(12, 'Exactly 4 of the preceding statements are true')),
)
def printer(st, matches):
if False in matches: print('Missed by one statement: %i, %s' % docs[matches.index(False)]) else: print('Full match:') print(' ' + ', '.join('%i:%s' % (i, 'T' if t else 'F') for i, t in enumerate(st, 1)))
funcs, docs = zip(*constraintinfo)
full, partial = [], []
for st in product( *([(False, True)] * 12) ):
truths = [bool(func(st)) for func in funcs] matches = [s == t for s,t in zip(st, truths)] mcount = sum(matches) if mcount == 12: full.append((st, matches)) elif mcount == 11: partial.append((st, matches))
for stm in full + partial:
printer(*stm)</lang>
- Output:
Full match: 1:T, 2:F, 3:T, 4:T, 5:F, 6:T, 7:T, 8:F, 9:F, 10:F, 11:T, 12:F Missed by one statement: 1, This is a numbered list of twelve statements: 1:F, 2:F, 3:F, 4:F, 5:T, 6:F, 7:F, 8:T, 9:F, 10:F, 11:T, 12:F Missed by one statement: 1, This is a numbered list of twelve statements: 1:F, 2:F, 3:F, 4:F, 5:T, 6:F, 7:F, 8:T, 9:F, 10:T, 11:T, 12:T Missed by one statement: 1, This is a numbered list of twelve statements: 1:F, 2:F, 3:F, 4:T, 5:F, 6:F, 7:F, 8:T, 9:F, 10:T, 11:T, 12:T Missed by one statement: 8, If statement 7 is true, then 5 and 6 are both true: 1:T, 2:F, 3:F, 4:F, 5:T, 6:F, 7:F, 8:F, 9:F, 10:F, 11:F, 12:F Missed by one statement: 11, Exactly 1 of statements 7, 8 and 9 are true: 1:T, 2:F, 3:F, 4:F, 5:T, 6:F, 7:F, 8:T, 9:F, 10:F, 11:F, 12:F Missed by one statement: 12, Exactly 4 of the preceding statements are true: 1:T, 2:F, 3:F, 4:F, 5:T, 6:F, 7:F, 8:T, 9:F, 10:F, 11:T, 12:F Missed by one statement: 12, Exactly 4 of the preceding statements are true: 1:T, 2:F, 3:F, 4:F, 5:T, 6:F, 7:F, 8:T, 9:F, 10:T, 11:T, 12:T Missed by one statement: 8, If statement 7 is true, then 5 and 6 are both true: 1:T, 2:F, 3:F, 4:F, 5:T, 6:T, 7:F, 8:F, 9:T, 10:F, 11:T, 12:F Missed by one statement: 8, If statement 7 is true, then 5 and 6 are both true: 1:T, 2:F, 3:F, 4:T, 5:F, 6:F, 7:F, 8:F, 9:F, 10:F, 11:F, 12:F Missed by one statement: 12, Exactly 4 of the preceding statements are true: 1:T, 2:F, 3:F, 4:T, 5:F, 6:F, 7:F, 8:T, 9:F, 10:T, 11:T, 12:T Missed by one statement: 6, Exactly 4 of the odd-numbered statements are true: 1:T, 2:F, 3:F, 4:T, 5:F, 6:T, 7:F, 8:T, 9:T, 10:F, 11:F, 12:F Missed by one statement: 7, Either statement 2 or 3 is true, but not both: 1:T, 2:F, 3:T, 4:T, 5:F, 6:F, 7:F, 8:T, 9:T, 10:F, 11:F, 12:F Missed by one statement: 9, Exactly 3 of the first 6 statements are true: 1:T, 2:F, 3:T, 4:T, 5:F, 6:T, 7:T, 8:F, 9:T, 10:F, 11:F, 12:F Missed by one statement: 12, Exactly 4 of the preceding statements are true: 1:T, 2:T, 3:F, 4:T, 5:F, 6:F, 7:T, 8:F, 9:T, 10:F, 11:F, 12:T Missed by one statement: 10, The next two statements are both true: 1:T, 2:T, 3:F, 4:T, 5:F, 6:F, 7:T, 8:F, 9:T, 10:T, 11:F, 12:F Missed by one statement: 8, If statement 7 is true, then 5 and 6 are both true: 1:T, 2:T, 3:F, 4:T, 5:F, 6:F, 7:T, 8:T, 9:T, 10:F, 11:F, 12:F
Java
The following Java code uses brute force. It tries to translate the logical statements as naturally as possible. The run time is almost zero. --Rene Grothmann 10:33, 28 October 2012 (UTC)
<lang Java> public class LogicPuzzle {
boolean S[] = new boolean[13]; int Count = 0;
public boolean check2 () { int count = 0; for (int k = 7; k <= 12; k++) if (S[k]) count++; return S[2] == (count == 3); }
public boolean check3 () { int count = 0; for (int k = 2; k <= 12; k += 2) if (S[k]) count++; return S[3] == (count == 2); }
public boolean check4 () { return S[4] == ( !S[5] || S[6] && S[7]); }
public boolean check5 () { return S[5] == ( !S[2] && !S[3] && !S[4]); }
public boolean check6 () { int count = 0; for (int k = 1; k <= 11; k += 2) if (S[k]) count++; return S[6] == (count == 4); }
public boolean check7 () { return S[7] == ((S[2] || S[3]) && !(S[2] && S[3])); }
public boolean check8 () { return S[8] == ( !S[7] || S[5] && S[6]); }
public boolean check9 () { int count = 0; for (int k = 1; k <= 6; k++) if (S[k]) count++; return S[9] == (count == 3); }
public boolean check10 () { return S[10] == (S[11] && S[12]); }
public boolean check11 () { int count = 0; for (int k = 7; k <= 9; k++) if (S[k]) count++; return S[11] == (count == 1); }
public boolean check12 () { int count = 0; for (int k = 1; k <= 11; k++) if (S[k]) count++; return S[12] == (count == 4); }
public void check () { if (check2() && check3() && check4() && check5() && check6() && check7() && check8() && check9() && check10() && check11() && check12()) { for (int k = 1; k <= 12; k++) if (S[k]) System.out.print(k + " "); System.out.println(); Count++; } }
public void recurseAll (int k) { if (k == 13) check(); else { S[k] = false; recurseAll(k + 1); S[k] = true; recurseAll(k + 1); } }
public static void main (String args[]) { LogicPuzzle P = new LogicPuzzle(); P.S[1] = true; P.recurseAll(2); System.out.println(); System.out.println(P.Count + " Solutions found."); }
} </lang>
- Output:
1 3 4 6 7 11 1 Solutions found.
Tcl
<lang tcl>package require Tcl 8.6
- Function to evaluate the truth of a statement
proc tcl::mathfunc::S {idx} {
upvar 1 state s apply [lindex $s [expr {$idx - 1}]] $s
}
- Procedure to count the number of statements which are true
proc S+ args {
upvar 1 state state tcl::mathop::+ {*}[lmap i $args {expr {S($i)}}]
}
- Turn a list of expressions into a list of lambda terms
proc lambdas items {lmap x $items {list state [list expr $x]}}
- Find the truth assignment that produces consistency. And those that are
- near misses too.
proc findTruthMatch {statements} {
set n [llength $statements] for {set i 0} {$i < 2**$n} {incr i} {
set state [split [format %0.*b $n $i] ""] set truths [lmap f $statements {apply $f [lambdas $state]}] set counteq [tcl::mathop::+ {*}[lmap s $state t $truths {expr { $s == $t }}]] if {$counteq == $n} { lappend exact $state } elseif {$counteq == $n-1} { set j 0 foreach s $state t $truths { incr j if {$s != $t} { lappend differ $state $j break } } }
} return [list $exact $differ]
}
- Rendering code
proc renderstate state {
return ([join [lmap s $state {
incr i expr {$s ? "S($i)" : "\u00acS($i)"}
}] "\u22c0"])
}
- The statements, encoded as expressions
set statements {
{[llength $state] == 12} {[S+ 7 8 9 10 11 12] == 3} {[S+ 2 4 6 8 10 12] == 2} {S(5) ? S(6) && S(7) : 1} {[S+ 2 3 4] == 0} {[S+ 1 3 5 7 9 11] == 4} {S(2) != S(3)} {S(7) ? S(5) && S(6) : 1} {[S+ 1 2 3 4 5 6] == 3} {S(11) && S(12)} {[S+ 7 8 9] == 1} {[S+ 1 2 3 4 5 6 7 8 9 10 11] == 4}
}
- Find the truth assignment(s) that give consistency
lassign [findTruthMatch [lambdas $statements]] exact differ
- Print the results
foreach state $exact {
puts "exact match\t[renderstate $state ]"
} foreach {state j} $differ {
puts "almost found\t[renderstate $state] \u21d2 [expr {[lindex $state $j-1]?"\u00ac":{}}]S($j)"
}</lang>
- Output:
exact match (S(1)⋀¬S(2)⋀S(3)⋀S(4)⋀¬S(5)⋀S(6)⋀S(7)⋀¬S(8)⋀¬S(9)⋀¬S(10)⋀S(11)⋀¬S(12)) almost found (¬S(1)⋀¬S(2)⋀¬S(3)⋀¬S(4)⋀S(5)⋀¬S(6)⋀¬S(7)⋀S(8)⋀¬S(9)⋀¬S(10)⋀S(11)⋀¬S(12)) ⇒ S(1) almost found (¬S(1)⋀¬S(2)⋀¬S(3)⋀¬S(4)⋀S(5)⋀¬S(6)⋀¬S(7)⋀S(8)⋀¬S(9)⋀S(10)⋀S(11)⋀S(12)) ⇒ S(1) almost found (¬S(1)⋀¬S(2)⋀¬S(3)⋀S(4)⋀¬S(5)⋀¬S(6)⋀¬S(7)⋀S(8)⋀¬S(9)⋀S(10)⋀S(11)⋀S(12)) ⇒ S(1) almost found (S(1)⋀¬S(2)⋀¬S(3)⋀¬S(4)⋀S(5)⋀¬S(6)⋀¬S(7)⋀¬S(8)⋀¬S(9)⋀¬S(10)⋀¬S(11)⋀¬S(12)) ⇒ S(8) almost found (S(1)⋀¬S(2)⋀¬S(3)⋀¬S(4)⋀S(5)⋀¬S(6)⋀¬S(7)⋀S(8)⋀¬S(9)⋀¬S(10)⋀¬S(11)⋀¬S(12)) ⇒ S(11) almost found (S(1)⋀¬S(2)⋀¬S(3)⋀¬S(4)⋀S(5)⋀¬S(6)⋀¬S(7)⋀S(8)⋀¬S(9)⋀¬S(10)⋀S(11)⋀¬S(12)) ⇒ S(12) almost found (S(1)⋀¬S(2)⋀¬S(3)⋀¬S(4)⋀S(5)⋀¬S(6)⋀¬S(7)⋀S(8)⋀¬S(9)⋀S(10)⋀S(11)⋀S(12)) ⇒ ¬S(12) almost found (S(1)⋀¬S(2)⋀¬S(3)⋀¬S(4)⋀S(5)⋀S(6)⋀¬S(7)⋀¬S(8)⋀S(9)⋀¬S(10)⋀S(11)⋀¬S(12)) ⇒ S(8) almost found (S(1)⋀¬S(2)⋀¬S(3)⋀S(4)⋀¬S(5)⋀¬S(6)⋀¬S(7)⋀¬S(8)⋀¬S(9)⋀¬S(10)⋀¬S(11)⋀¬S(12)) ⇒ S(8) almost found (S(1)⋀¬S(2)⋀¬S(3)⋀S(4)⋀¬S(5)⋀¬S(6)⋀¬S(7)⋀S(8)⋀¬S(9)⋀S(10)⋀S(11)⋀S(12)) ⇒ ¬S(12) almost found (S(1)⋀¬S(2)⋀¬S(3)⋀S(4)⋀¬S(5)⋀S(6)⋀¬S(7)⋀S(8)⋀S(9)⋀¬S(10)⋀¬S(11)⋀¬S(12)) ⇒ ¬S(6) almost found (S(1)⋀¬S(2)⋀S(3)⋀S(4)⋀¬S(5)⋀¬S(6)⋀¬S(7)⋀S(8)⋀S(9)⋀¬S(10)⋀¬S(11)⋀¬S(12)) ⇒ S(7) almost found (S(1)⋀¬S(2)⋀S(3)⋀S(4)⋀¬S(5)⋀S(6)⋀S(7)⋀¬S(8)⋀S(9)⋀¬S(10)⋀¬S(11)⋀¬S(12)) ⇒ ¬S(9) almost found (S(1)⋀S(2)⋀¬S(3)⋀S(4)⋀¬S(5)⋀¬S(6)⋀S(7)⋀¬S(8)⋀S(9)⋀¬S(10)⋀¬S(11)⋀S(12)) ⇒ ¬S(12) almost found (S(1)⋀S(2)⋀¬S(3)⋀S(4)⋀¬S(5)⋀¬S(6)⋀S(7)⋀¬S(8)⋀S(9)⋀S(10)⋀¬S(11)⋀¬S(12)) ⇒ ¬S(10) almost found (S(1)⋀S(2)⋀¬S(3)⋀S(4)⋀¬S(5)⋀¬S(6)⋀S(7)⋀S(8)⋀S(9)⋀¬S(10)⋀¬S(11)⋀¬S(12)) ⇒ ¬S(8)