Slimmeriken

Ook de “Slimmeriken” puzzel in het boek “Logic Puzzles for Really Smart People” (pagina 124-125) is voor Co-pilot een makkie. De eerste versie levert een brute-force programma op, die simpelweg alle 1,7 combinaties afsjouwt. Dat gaat wel zo snel dat je al tevreden zou kunnen zijn. Maar dat moet toch echt sneller mogelijk zijn.

In de stellingen liggen een aantal combinaties hard vast. Bijvoorbeeld “Emmy heeft het laagste IQ”, “Ada heeft als enige een leeftijd vaanvan het 1e cijfer de helft is van het 2e”, “Edwin heeft het hoogste IQ”, “Edwin is niet 27”, enz

Samen maakt dat er ‘nog’ maar 5761 combinaties over blijven.

Daarna kan nog verder geoptimaliseerd worden:

Stellingen direct verwerken in de permutatiefase
In plaats van alle combinaties te genereren en daarna te filteren met IsValid, kun je sommige stellingen tijdens het genereren al gebruiken om combinaties vroegtijdig uit te sluiten.

Stelling 1: De middelste leeftijd (qua volgorde) moet een IQ hebben dat ±1 is van die van de 64-jarige. Je kunt dit al checken tijdens het genereren van leeftijdscombinaties.
Stelling 3: De IQ van de deeltjesfysicus is 2 hoger dan die van de biochemicus. Dit kun je al checken tijdens het genereren van vakgebiedcombinaties.

Slimme filtering van vakgebieden
Je kunt ook regels toepassen op vakgebiedcombinaties vóór je ze gebruikt:
Stelling 3: Zoek alleen vakgebiedcombinaties waarin “Deeltjes” en “Biochemie” niet aan dezelfde persoon zijn gekoppeld én waarin het IQ-verschil tussen die twee personen precies 2 is.
Stelling 4: Zoek alleen combinaties waarin “Fotonica” en Emmy niet aan dezelfde persoon zijn gekoppeld, en het IQ van Fotonica is 1 hoger dan Emmy.

Dat levert op:

!

Het initiële VB programma is uitstekend, echter blijkt (ook de vorige puzzel) vooralsnog steeds de brute force methode gebruikt te worden.

Dit kan veel eleganter mbv Prolog:

% Mogelijke waarden
namen([isaac, benjamin, ada, emmy, edwin]).
leeftijden([27, 32, 48, 59, 64]).
iqs([150, 151, 152, 153, 154]).
vakgebieden([biochemie, nano, deeltjes, fotonia, kwantum]).

% Startpunt: een wetenschapper is een structuur van Naam, Leeftijd, IQ, Vakgebied
oplossing(Wetenschappers) :-
    namen(Namen),
    leeftijden(Leeftijden),
    iqs(IQs),
    vakgebieden(Vakken),

    % Maak 5 wetenschappers
    Wetenschappers = [
        wetenschapper(isaac, L1, IQ1, V1),
        wetenschapper(benjamin, L2, IQ2, V2),
        wetenschapper(ada, L3, IQ3, V3),
        wetenschapper(emmy, L4, IQ4, V4),
        wetenschapper(edwin, L5, IQ5, V5)
    ],

    % Alle leeftijden, IQs en vakgebieden zijn uniek
    permutation(Leeftijden, [L1, L2, L3, L4, L5]),
    permutation(IQs, [IQ1, IQ2, IQ3, IQ4, IQ5]),
    permutation(Vakken, [V1, V2, V3, V4, V5]),

    % Edwin heeft IQ 154
    member(wetenschapper(edwin, _, 154, _), Wetenschappers),

    % Benjamin heeft IQ 153
    member(wetenschapper(benjamin, _, 153, _), Wetenschappers),

    % Emmy heeft IQ 150
    member(wetenschapper(emmy, _, 150, _), Wetenschappers),

    % Ada heeft leeftijd 48
    member(wetenschapper(ada, 48, _, _), Wetenschappers),

    % Edwin is niet de jongste
    member(wetenschapper(edwin, L5, _, _), Wetenschappers),
    min_member(MinL, [L1, L2, L3, L4, L5]),
    L5 \= MinL,

    % IQ van deeltjesfysica is 2 hoger dan biochemie
    member(wetenschapper(_, _, IQd, deeltjes), Wetenschappers),
    member(wetenschapper(_, _, IQb, biochemie), Wetenschappers),
    IQd is IQb + 2,

    % Op een na jongste heeft IQ 2 hoger dan kwantum
    sort([L1, L2, L3, L4, L5], Gesorteerd),
    nth1(2, Gesorteerd, TweedeJongste),
    member(wetenschapper(_, TweedeJongste, IQtj, _), Wetenschappers),
    member(wetenschapper(_, _, IQk, kwantum), Wetenschappers),
    IQtj is IQk + 2,

    % IQ van fotonia is 1 hoger dan dat van Emmy
    member(wetenschapper(_, _, IQf, fotonia), Wetenschappers),
    member(wetenschapper(emmy, _, IQe, _), Wetenschappers),
    IQf is IQe + 1,

    % De wetenschapper die jonger is dan twee en ouder dan twee anderen
    % heeft IQ 1 hoger of lager dan die van de 64-jarige
    member(wetenschapper(_, 64, IQ64, _), Wetenschappers),
    member(wetenschapper(_, Lm, IQm, _), Wetenschappers),
    findall(L, member(wetenschapper(_, L, _, _), Wetenschappers), Lijst),
    include(<(Lm), Lijst, JongerDan),
    include(>(Lm), Lijst, OuderDan),
    length(JongerDan, 2),
    length(OuderDan, 2),
    (IQm is IQ64 + 1 ; IQm is IQ64 - 1).