Интервью с вопросами о кубах стека с использованием JavaScript

Question

У вас есть четыре цветных кубика.Каждая сторона каждого куба имеет один цвет, и есть четыре цвета: синий (B), красный (R), зеленый (G) и желтый (Y). Описание шести граней: передняя, ​​задняя, ​​левая, правая, верхняя,внизу, цвета куба:

Цель состоит в том, чтобы найти способы сложить четыре куба в виде вертикального столбца, чтобы каждая сторона столбца отображала все четыре цвета.

что я могу сделать,

спасибо

пс:

function init(){
    var a = [['R','B'],['G','Y'],['B','Y']],
        b = [['R','G'],['G','Y'],['B','B']],
        c = [['Y','B'],['R','G'],['Y','R']],
        d = [['Y','G'],['B','R'],['R','R']]
    var box = [a,b,c,d]
    return box;
}

Answer 1

Array.prototype.in_array = function(e) {
    for (i = 0; i < this.length; i++) {
        if (this[i] == e) return true;
    }
    return false;
}
Array.prototype.clone = function () {
    return this.slice();
} 

function deepcopy(obj) {
    var out = [],i = 0,len = obj.length;
    for (; i < len; i++) {
        if (obj[i] instanceof Array){
            out[i] = deepcopy(obj[i]);
        }
        else out[i] = obj[i];
    }
    return out;
}

function Cube (id, front, back, left, right, top, bottom) {
    var self = this;
    self.id=id;
    self.front = front;
    self.back = back;
    self.left = left;
    self.right = right;
    self.top = top;
    self.bottom = bottom;
    self.turnMethod1 = function(){//left-front-right-back
        var tmp=self.left;
        self.left=self.front;
        self.front=self.right;
        self.right=self.back;
        self.back=tmp;
    }
    self.turnMethod2 = function(){//left-top-right-bottom
        var tmp=self.left;
        self.left=self.top;
        self.top=self.right;
        self.right=self.bottom;
        self.bottom=tmp;
    }
    self.turnMethod3 = function(){//front-top-back-bottom
        var tmp=self.front;
        self.front=self.top;
        self.top=self.back;
        self.back=self.bottom;
        self.bottom=tmp;
    }

    self.fn = [
        self.turnMethod1,self.turnMethod2,self.turnMethod3
    ]

}

Cube.prototype.toString = function(){
    return this.id+"\t"+this.front+"\t"+this.back+"\t"+this.left+"\t"+this.right+"\t"+this.top+"\t"+this.bottom+"\n";
}


var cube1=new Cube(1,"R","B","G","Y","B","Y");
var cube2=new Cube(2,"R","G","G","Y","B","B");
var cube3=new Cube(3,"Y","B","R","G","Y","R");
var cube4=new Cube(4,"Y","G","B","R","R","R");

function count() {
    for (var i = 0; i < 3; i++) {
        for (var n = 0; n < 4; n++) {
            cube1.fn[i]()
            for (var a = 0; a < 3; a++) {
                for (var b = 0; b < 4; b++) {
                    cube2.fn[a]()
                    for (var c = 0; c < 3; c++) {
                        for (var d = 0; d < 4; d++) {
                            cube3.fn[c]()
                            for (var e = 0; e < 3; e++) {
                                for (var f = 0; f < 4; f++) {
                                    if(done()){
                                        printPermutation();
                                    }
                                    cube4.fn[e]()
                                };

                            };

                        };

                    };
                };

            };
        };

    };
}

function done() {
    var arr = []; /*front validation*/
    arr.push(cube1.front);
    if (arr.in_array(cube2.front)) {
        return false;
    } else {
        arr.push(cube2.front);
    }

    if (arr.in_array(cube3.front)) {
        return false;
    } else {
        arr.push(cube3.front);
    }
    if (arr.in_array(cube4.front)) {
        return false;
    } else {
        arr.push(cube4.front);
    } /*back validation*/
    var arr = [];
    arr.push(cube1.back);
    if (arr.in_array(cube2.back)) {
        return false;
    } else {
        arr.push(cube2.back);
    }
    if (arr.in_array(cube3.back)) {
        return false;
    } else {
        arr.push(cube3.back);
    }

    if (arr.in_array(cube4.back)) {
        return false;
    } else {
        arr.push(cube4.back);
    }
    /*left validation*/
    var arr = [];
    arr.push(cube1.left);
    if (arr.in_array(cube2.left)) {
        return false;
    } else {
        arr.push(cube2.left);
    }
    if (arr.in_array(cube3.left)) {
        return false;
    } else {
        arr.push(cube3.left);
    }
    if (arr.in_array(cube4.left)) {
        return false;
    } else {
        arr.push(cube4.left);
    } /*right validation*/
    var arr = [];
    arr.push(cube1.right);
    if (arr.in_array(cube2.right)) {
        return false;
    } else {
        arr.push(cube2.right);
    }
    if (arr.in_array(cube3.right)) {
        return false;
    } else {
        arr.push(cube3.right);
    }
    if (arr.in_array(cube4.right)) {
        return false;
    } else {
        arr.push(cube4.right);
    }

    return true;
}

function printPermutation(){
        console.log("----------------------------");
        var  arr = []
        arr.push("Cube\tFront\tBack\tLeft\tRight\tTop\tBottom\n");
        arr.push(cube1.toString());
        arr.push(cube2.toString());
        arr.push(cube3.toString());
        arr.push(cube4.toString());
        console.log(arr.join(""))
}


function main(){
    count()
}

main()

Answer 2

Поиск всех возможных состояний: их не так много (24 вращения на куб, большинство из которых вы можете отфильтровать). Псевдокод:

for cubeLevel0 in rotations(cubes[0]):
    var sidesMatch = function(cube) {
        return cube.N==cubeLevel0.N and cube.S==cubeLevel0.S and ...
    }
    for cubeLevel1 in rotations(cube[1]).filter(sidesMatch):
        for cubeLevel2 in rotations(cube[2]).filter(sidesMatch):
            for cubeLevel3 in rotations(cube[3]).filter(sidesMatch):
                console.log(cubeLevel0, cubeLevel1, cubeLevel2, cubeLevel3)

Вложенные циклы for ужасны, и вы можете удалить их, реализовав это как рекурсивную функцию. Я оставил это так для ясности.

Для реализации функции rotations(cube) у вас есть несколько вариантов. Наименее сложный способ - взять перед собой физический куб и обозначить каждую сторону {0,1,2,3,4,5} в произвольном порядке. Затем физически выполните одно из 24 вращений и запишите пермутированный порядок, затем отмените вращение, чтобы вернуться к исходному положению. Затем напишите функцию следующим образом:

// You HAVE to manually discover these with the physical method described above
var rotationPermutations = [[0,1,2,3,4,5,6], [3,4,2,1,5,0], ...(24 of these)...];

function rotations(cube) {  // representing a cube as a 6-tuple
    return rotationPermutations.map(function(permutation) {
        // return [cube[i] for i in permutation]
        return permutation.map(function(x){return cube[x]})
    });    
}

Вы можете быть умнее в вещах, если сможете найти способ определить, когда перестановка неверна; тогда вы можете сгенерировать все 48 перестановок осей (используя представление [[axis0top, axis0bottom], [axis1top, axis1bottom], [axis2top, axis2bottom]], переставляя ось 3! way, и переворачивая каждую ось 2 way, так что 2 ^ 3 = 8 возможностей переворота, 3! * 2 ^ 3 = 48 ) и отфильтровать половину из них с неправильной хиральностью. Однако обдумывание этого заняло бы больше времени, чем запись перестановок с использованием ручного метода, описанного выше.