Philosophy Now Forum

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("----");
}