Tough logic puzzle

[attofishpi]

boo boos

𝐴1 - (Grey, Canadian, Jazz, Oil Painter, White)

Oil painter live next door to grey hair...mmm

[attofishpi]

First contradiction found: you have 2 people listening to classical music.

Yeah - I'm not going to cross check - but clearly its screwed it.

[Flannel Jesus]

First contradiction found: you have 2 people listening to classical music.

Yeah - I'm not going to cross check - but clearly its screwed it.

My gpt keeps making the same mistake even when I tell it it's a mistake. It's hsowing me its steps in reasoning and I keep saying "you can't do that step, that doesn't make sense" and it says "okay, i'll do it again more careful this time" and then it makes the same mistake. 5 times in a row now.

[Flannel Jesus]

doesn't look like you can easily make a table in this forum software...

[Gary Childress]

Yeah, not Googling, I tried using a spreadsheet but there are so many moving parts that it would take me the rest of my life just to guess how to put them all together. That puzzle is beyond my capacity to solve or even fathom the way to solve it--assuming it is solvable. I'd go back to college to try to learn more about how to solve it, but it seems a little too late for that for me. I quit.

I'm going to leave the world to the experts and the young with more potential. I'm a sheep out to pasture. I'm not good for anything except to turn resources into waste products.

[Flannel Jesus]

Yeah, not Googling, I tried using a spreadsheet but there are so many moving parts that it would take me the rest of my life just to guess how to put them all together. That puzzle is beyond my capacity to solve or even fathom the way to solve it--assuming it is solvable. I'd go back to college to try to learn more about how to solve it, but it seems a little too late for that for me. I quit.

It's not as complicated as you think. You wanna do it together step by step?

[Gary Childress]

Yeah, not Googling, I tried using a spreadsheet but there are so many moving parts that it would take me the rest of my life just to guess how to put them all together. That puzzle is beyond my capacity to solve or even fathom the way to solve it--assuming it is solvable. I'd go back to college to try to learn more about how to solve it, but it seems a little too late for that for me. I quit.

It's not as complicated as you think. You wanna do it together step by step?

It's OK. I'm too spent to learn or retain anything. It's better that I stay humbled anyway.

[Flannel Jesus]

You shouldn't be so down on yourself brother.

[Gary Childress]

You shouldn't be so down on yourself brother.

If you knew me, you'd realize I should be. I've always been a loner, selfish and inconsiderate. And I usually end up screwing up everything and everyone. I deserve where I am mentally.

[godelian]

So, whose door is White? And what medium does the Kenyan use for his art?

This is deducible, but not easily. In fact all 5 properties of all 5 apartments are deducible.

$ ./doors-artists.js
final number of complete solutions:1
----
door_index hair_color nationality musical_style door_color profession

1 black Brazilian classical white oil_painter
2 grey Indian jazz pink sculptor
3 blonde Australian hiphop teal dig_painter
4 brunette Canadian reggae orange waterc_painter
5 red Kenyan elec_dance purple photographer

I wrote a JavaScript custom script to navigate through the solution space.

In my opinion, it can possibly not be solved using the standard ILP cut-and-branch algorithm, but not sure, because I didn't even try. The mapping onto ILP for use in a standard computation engine would be more complex to figure out anyway than just doing a custom script.

The custom script is based on the continuously filtered Cartesian multiplication of the permutation spaces of the five properties (door_index, hair_color, nationality, musical_style, door_color, profession).

The filtering continuously prevents a combinatorial explosion of the solution space, which would probably make the script run pretty much forever.

The script finishes its search in around 3 seconds.

If anyone is interested in the solution script, I will post it.

[Flannel Jesus]

Amazing.

I'm not only interested in the solution script, I'm interested in seeing a full breakdown video of your process of making the script and your reasoning about the code. Those are the correct answers.

[godelian]

Code: Select all

#!/usr/bin/env qjs

//The following is what the French would call "le référentiel"

var properties={
    "hair_color":["black","brunette","grey","red","blonde"],
    "nationality":["Indian","Brazilian","Canadian","Australian","Kenyan"],
    "musical_style":["classical","elec_dance","jazz","reggae","hiphop"],
    "door_color":["teal","pink","purple","orange","white"],
    "profession":["photographer","sculptor","oil_painter",
                    "dig_painter","waterc_painter"]
};

//constraints_type_1: 
//It specifies that a particular property value must always
//coexist with another property value

var constraints_type_1 = [
    {"cix":1,"property_needle_1":"hair_color","value_needle_1":"black",
        "property_needle_2":"musical_style","value_needle_2":"classical"},
    {"cix":2,"property_needle_1":"musical_style","value_needle_1":"elec_dance",
        "property_needle_2":"profession","value_needle_2":"photographer"},
    {"cix":4,"property_needle_1":"door_index","value_needle_1":3,
        "property_needle_2":"door_color","value_needle_2":"teal"},
    {"cix":5,"property_needle_1":"profession","value_needle_1":"sculptor",
        "property_needle_2":"door_color","value_needle_2":"pink"},
    {"cix":9,"property_needle_1":"hair_color","value_needle_1":"red",
        "property_needle_2":"door_color","value_needle_2":"purple"},
    {"cix":10,"property_needle_1":"profession","value_needle_1":"dig_painter",
        "property_needle_2":"hair_color","value_needle_2":"blonde"},
    {"cix":11,"property_needle_1":"profession","value_needle_1":"waterc_painter",
        "property_needle_2":"nationality","value_needle_2":"Canadian"},
    {"cix":12,"property_needle_1":"profession","value_needle_1":"oil_painter",
        "property_needle_2":"door_index","value_needle_2":1},
    {"cix":13,"property_needle_1":"door_color","value_needle_1":"orange",
        "property_needle_2":"musical_style","value_needle_2":"reggae"},
    {"cix":14,"property_needle_1":"nationality","value_needle_1":"Australian",
        "property_needle_2":"musical_style","value_needle_2":"hiphop"}
];

//check constraints of type 1

function isValidForType1(solution) {
    for(let assignment of solution) {
        for(let constraint of constraints_type_1) {
            let property_needle_1=constraint["property_needle_1"];
            let value_needle_1=constraint["value_needle_1"];
            let property_needle_2=constraint["property_needle_2"];
            let value_needle_2=constraint["value_needle_2"];
            //the assignment must have both properties assigned
            //for a constraint violation to even be possible
            if(!assignment.hasOwnProperty(property_needle_1)) continue;
            if(!assignment.hasOwnProperty(property_needle_2)) continue;
            //check for: value1 correct but value2 wrong
            if(assignment[property_needle_1]==value_needle_1 && 
                    assignment[property_needle_2]!==value_needle_2)
                return false;
            //check for: value2 correct but value1 wrong
            if(assignment[property_needle_2]==value_needle_2 && 
                    assignment[property_needle_1]!==value_needle_1)
                return false;
        }       
    }    
    return true;
}

//constraints_type_2
//It specifies that a particular property value must always coexist
//with a property value of a neigbor

var constraints_type_2 = [
    {"cix":3,"property_needle":"nationality","value_needle":"Indian",
            "property_neighbor":"musical_style","value_neighbor":"classical"},
    {"cix":7,"property_needle":"nationality","value_needle":"Brazilian",
            "property_neighbor":"musical_style","value_neighbor":"jazz"},
    {"cix":8,"property_needle":"hair_color","value_needle":"grey",
            "property_neighbor":"profession","value_neighbor":"oil_painter"}
];

// utility function: find neighbor of assignment by door index

function findNeighborByDoorIndex(solution,door_index) {
    for(let assignment of solution) {
        if(assignment["door_index"]==door_index)
            return assignment;
    }
    //not found
    //This should never happen. Maybe throw an exception of sorts?
    return null;
}

//check constraints of type 2

function isValidForType2(solution) {
    for(let constraint of constraints_type_2) {
        let property_needle=constraint["property_needle"];
        let value_needle=constraint["value_needle"];
        let property_neighbor=constraint["property_neighbor"];
        let value_neighbor=constraint["value_neighbor"];
        for(let assignment of solution) {
            //the assignment must have the property assigned
            if(!assignment.hasOwnProperty(property_needle)) continue;
            //the assignment must have the value assigned to the property
            if(assignment[property_needle]!==value_needle) continue;
            //retrieve door_index from assignment
            let door_index=assignment["door_index"];
            //we assume that we will not find a valid neighbor
            let foundValidNeighbor=false;
            //check left neighbor, if applicable
            if(door_index>1) {
                let assignmentLeftNeighbor=findNeighborByDoorIndex(solution,door_index-1);
                if(!assignmentLeftNeighbor.hasOwnProperty(property_neighbor)) continue;
                if(assignmentLeftNeighbor[property_neighbor]==value_neighbor) {
                    foundValidNeighbor=true;
                }
            }
            //check right neighbor, if applicable
            if(door_index<5) {
                let assignmentRightNeighbor=findNeighborByDoorIndex(solution,door_index+1);
                if(!assignmentRightNeighbor.hasOwnProperty(property_neighbor)) continue;
                if(assignmentRightNeighbor[property_neighbor]==value_neighbor) {
                    foundValidNeighbor=true;
                }
            }
            if(!foundValidNeighbor) {
                return false;
            }
        }        
    }
    return true;
}

//check constraints of type 3
//cix=6, Special case.
//this function only checks:
//"The red head is the right-hand neighbor of the Brunette."

function isValidForType3(solution) {
    for(let assignment of solution) {
        //the assignment must have the property assigned
        if(!assignment.hasOwnProperty("hair_color")) continue;
        //the assignment must have the value assigned to the property
        if(assignment["hair_color"]!=="brunette") continue;
        //we found the brunette
        //check that there is a right-hand neighbor
        var door_index=assignment["door_index"];
        //Brunette cannot be assigned to door 5
        if(door_index==5) return false;
        //find right-hand neighbor
        var assignmentRightNeighbor=findNeighborByDoorIndex(solution,door_index+1);
        //The right-hand neighbor must be the red head
        if(assignmentRightNeighbor["hair_color"]!=="red") return false;
    }
    return true;
}

//validate solution

function isValid(solution)
{
    let validForType1=isValidForType1(solution);
    if(!validForType1) return false;
    let validForType2=isValidForType2(solution);
    if(!validForType2) return false;
    let validForType3=isValidForType3(solution);
    if(!validForType3) return false;
    return true;
}

//permutator

const permutator = (inputArr) => {
  let result = [];

  const permute = (arr, m = []) => {
    if (arr.length === 0) {
      result.push(m)
    } else {
      for (let i = 0; i < arr.length; i++) {
        let curr = arr.slice();
        let next = curr.splice(i, 1);
        permute(curr.slice(), m.concat(next))
     }
   }
 }
 permute(inputArr)
 return result;
}

//for debugging purposes

function output(label,structure) {
    console.log(label+":"+JSON.stringify(structure));
}

//initial solution space

var solutionSpace=[
    [{"door_index":1},{"door_index":2},{"door_index":3},
               {"door_index":4},{"door_index":5}]
];

//iterate over the properties
for(let property of Object.keys(properties)) {
    let propertyValues=properties[property];
    let permutations=permutator(propertyValues);
    let newSolutionSpace=[];
    //iterate over the permutations of the property values
    for(let permutation of permutations) {
        //cartesian multiplication of existing solutions with
        //new permutations
        for(let solution of solutionSpace) {    
            let newSolution=[];
            for (let i = 0; i < solution.length; i++) {
                let assignment=solution[i];
                let newAssignment={...assignment};
                newAssignment[property]=permutation[i];
                newSolution.push(newAssignment);
            }
            //verify if the solution satisfies all constraints
            if(isValid(newSolution)){
                newSolutionSpace.push(newSolution);
            }
        }
    }
    //the new solution space now replaces the existing one
    solutionSpace=newSolutionSpace;
}

console.log("final number of complete solutions:"+solutionSpace.length);

//output the solutions

function pad(str){
    let pad=Array(15).join(' ');
    return (str + pad).substring(0, pad.length);
}
console.log("----");
let headerPrintedAlready=false;
for(let solution of solutionSpace) {
    for(let assignment of solution) {
        let line="";
        for(let key of Object.keys(assignment)) {
            line=line+pad(assignment[key]);
        }
        if(!headerPrintedAlready) {
            let header="";
            for(let key of Object.keys(assignment)) {
                header=header+pad(key);
            }
            console.log(header);
            console.log("");
            headerPrintedAlready=true;
        }
        console.log(line);
    }
    console.log("----");
}

[accelafine]

A human would do it in a far more interesting and charming way. Just saying.

[Flannel Jesus]

Are you iterating over all possible states and finding the one that matches (or that doesn't contradict, rather) all the given parameters?

[godelian]

I'm not only interested in the solution script, I'm interested in seeing a full breakdown video of your process of making the script and your reasoning about the code. Those are the correct answers.

In fact, the algorithm would at most investigate 5^6=15,625 potential solutions. So, I guess that even a brute search would work. But then again, locating the needle in the haystack requires filtering the solution space anyway. So, you could as well continuously filter.

Watching me make script amounts to watching me swimming in the pool or so. Typing it into the computer is the very last part of the design. Then it takes some debugging. Even that's not mostly done behind the screen. It's again on the bicycle or in the gym, pondering about "What did I do wrong?".