javascript - 制作一个 "Perfect Classroom"

Question

这不是一个家庭作业问题，实际上我这样做是为了好玩。

问题是这样的:

我有一间具有指定“宽度”(椅子)的教室，我必须将所有学生安置好，这样教室里就不会发生对话。

如果一名学生与另一名学生相邻，就会发生对话。 (对 Angular 线计数)

对于这个例子，教室宽度是3。假设我们有一些学生:Matheus、Gabriel 和 Ravi，他们都互相交谈，现在我们有其他学生，A、B、C、D、E ，F。

上述问题的解决方案是:

|---------|--------|---------|
| Gabriel | A      | Matheus |
|---------|--------|---------|
| B       | C      | D       |
|---------|--------|---------|
| Ravi    | E      | F       |
|---------|--------|---------|

我的实际代码是这样的，但由于某种原因它使浏览器崩溃(无限循环):

/*
    Class Classroom
*/
function Classroom($width){
    $width=$width||6;
    var self=this;
    var alunos=[];
    self.addClassmate=function($classmate){
        alunos.push($classmate);
    }

    self.createClassroom=function(){
        var mapa=[];
        var width=$width;
        var height=Math.ceil(alunos.length/width);
        for(var i=0;i<width;++i){
            mapa[i]=[];
        }

        // Shuffle the array
        alunos.sort(function(a,b){
            return 0.5 - Math.random();
        });


        var i=0;
        var px=width;
        var py=height;


        // Fill the array
        while(px--){
            while(py--){
                if(i<alunos.length){
                    mapa[px][py]=alunos[i];
                }else{
                    mapa[px][py]=new Student('---');
                }

                ++i;
            }
            py=height;
        }

        function changePosition(px,py){
            var dx=Math.floor(Math.random()*width);
            var dy=Math.floor(Math.random()*height);
            var me=mapa[px][py];
            var other=mapa[dx][dy];
            mapa[dx][dy]=me;
            mapa[px][py]=other;
            alert('lol');
            checkChairs();
        }

        // DO IT

        function checkChairs(){
            for(var px=0;px<width;++px){
                for(var py=0;py<height;++py){
                    var me=mapa[px][py];
                    var leftCorner   = px==0;
                    var rightCorner  = px==width-1;
                    var topCorner    = py==0;
                    var bottomCorner = py==height-1;

                    if(!leftCorner){
                        if(mapa[px-1][py].hasRelationWith(me)){
                            changePosition(px,py);
                            return;
                        }
                        if(!topCorner){
                            if(mapa[px-1][py-1].hasRelationWith(me)){
                                changePosition(px,py);
                                return;
                            }
                        }
                        if(!bottomCorner){
                            if(mapa[px-1][py+1].hasRelationWith(me)){
                                return;
                            }
                        }
                    }

                    if(!rightCorner){
                        if(mapa[px+1][py].hasRelationWith(me)){
                            changePosition(px,py);
                            return;
                        }
                        if(!topCorner){
                            if(mapa[px+1][py-1].hasRelationWith(me)){
                                changePosition(px,py);
                                return;
                            }
                        }
                        if(!bottomCorner){
                            if(mapa[px+1][py+1].hasRelationWith(me)){
                                changePosition(px,py);
                                return;
                            }
                        }
                    }

                    if(!topCorner){
                        if(mapa[px][py-1].hasRelationWith(me)){
                            changePosition(px,py);
                            return;
                        }
                    }

                    if(!bottomCorner){
                        if(mapa[px][py+1].hasRelationWith(me)){
                            changePosition(px,py);
                            return;
                        }
                    }
                }
            }
        }

        checkChairs();

        return mapa;
    }
}


/*
    Class Student
*/
function Student($name){
    var self=this;
    var name=$name;
    var relation=[];

    self.addRelationWith=function($classmate,$mutual){
        $mutual=$mutual||true;
        if(self.hasRelationWith($classmate)) return;
        relation.push($classmate);
        if($mutual){
            $classmate.addRelationWith(self, false);
        }
    }

    self.hasRelationWith=function($classmate){
        var i=relation.length;
        while(i--){
            if(relation[i]==$classmate){
                return true;
            }
        }
        return false;
    }

    self.getName=function(){
        return name;
    }

    self.toString=function(){
        return '[Student '+self.getName()+']';
    }
}



var s=new Classroom(3);

var Matheus=new Student('Matheus');
var Gabriel=new Student('Gabriel');
var Ravi=new Student('Ravi');

Matheus.addRelationWith(Gabriel);
Matheus.addRelationWith(Ravi);
Gabriel.addRelationWith(Ravi);

s.addClassmate(Matheus);
s.addClassmate(Gabriel);
s.addClassmate(Ravi);
s.addClassmate('A');
s.addClassmate('B');
s.addClassmate('C');
s.addClassmate('D');
s.addClassmate('E');
s.addClassmate('F');

alert(s.createClassroom());

(我在这篇文章中给出的示例位于代码末尾)

Answer 1

哈哈!我简直不敢相信，我将字符串而不是 Students 传递给函数。

正确的代码如下:

/*
    Class Classroom
*/
function Classroom($width){
    $width=$width||6;
    var self=this;
    var alunos=[];
    self.addClassmate=function($classmate){
        alunos.push($classmate);
    }

    self.createClassroom=function(){
        var mapa=[];
        var width=$width;
        var height=Math.ceil(alunos.length/width);
        for(var i=0;i<width;++i){
            mapa[i]=[];
        }

        // Shuffle the array
        alunos.sort(function(a,b){
            return 0.5 - Math.random();
        });



        // Fill the array
        var i=0;
        for(var px=0;px<width;++px){
            for(var py=0;py<height;++py){
                if(i<alunos.length){
                    mapa[px][py]=alunos[i];
                    ++i;
                }else{
                    mapa[px][py]=new Student('---');
                }
            }
            py=height;
        }
        alert(mapa);
        function changePosition(px,py){
            var dx=Math.floor(Math.random()*width);
            var dy=Math.floor(Math.random()*height);
            var me=mapa[px][py];
            var other=mapa[dx][dy];
            mapa[dx][dy]=me;
            mapa[px][py]=other;
            checkChairs();
        }

        // DO IT

        function checkChairs(){
            for(var px=0;px<width;++px){
                for(var py=0;py<height;++py){
                    var me=mapa[px][py];
                    var leftCorner   = px==0;
                    var rightCorner  = px==width-1;
                    var topCorner    = py==0;
                    var bottomCorner = py==height-1;

                    if(!leftCorner){
                        if(mapa[px-1][py].hasRelationWith(me)){
                            changePosition(px,py);
                            return;
                        }
                        if(!topCorner){
                            if(mapa[px-1][py-1].hasRelationWith(me)){
                                changePosition(px,py);
                                return;
                            }
                        }
                        if(!bottomCorner){
                            if(mapa[px-1][py+1].hasRelationWith(me)){
                                return;
                            }
                        }
                    }

                    if(!rightCorner){
                        if(mapa[px+1][py].hasRelationWith(me)){
                            changePosition(px,py);
                            return;
                        }
                        if(!topCorner){
                            if(mapa[px+1][py-1].hasRelationWith(me)){
                                changePosition(px,py);
                                return;
                            }
                        }
                        if(!bottomCorner){
                            if(mapa[px+1][py+1].hasRelationWith(me)){
                                changePosition(px,py);
                                return;
                            }
                        }
                    }

                    if(!topCorner){
                        if(mapa[px][py-1].hasRelationWith(me)){
                            changePosition(px,py);
                            return;
                        }
                    }

                    if(!bottomCorner){
                        if(mapa[px][py+1].hasRelationWith(me)){
                            changePosition(px,py);
                            return;
                        }
                    }
                }
            }
        }

        checkChairs();

        return mapa;
    }
}


/*
    Class Student
*/
function Student($name){
    var self=this;
    var name=$name;
    var relation=[];

    self.addRelationWith=function($classmate,$mutual){
        $mutual=$mutual||true;
        if(self.hasRelationWith($classmate)) return;
        relation.push($classmate);
        if($mutual){
            $classmate.addRelationWith(self, false);
        }
    }

    self.hasRelationWith=function($classmate){
        var i=relation.length;
        while(i--){
            if(relation[i]==$classmate){
                return true;
            }
        }
        return false;
    }

    self.getName=function(){
        return name;
    }

    self.toString=function(){
        return self.getName();
    }
}



var s=new Classroom(3);

var Matheus=new Student('Matheus');
var Gabriel=new Student('Gabriel');
var Ravi=new Student('Ravi');

Matheus.addRelationWith(Gabriel);
Matheus.addRelationWith(Ravi);
Gabriel.addRelationWith(Ravi);
s.addClassmate(Matheus);
s.addClassmate(Gabriel);
s.addClassmate(Ravi);
s.addClassmate(new Student('A'));
s.addClassmate(new Student('B'));
s.addClassmate(new Student('C'));
s.addClassmate(new Student('D'));
s.addClassmate(new Student('E'));
s.addClassmate(new Student('F'));

alert(s.createClassroom());

我需要摩尔咖啡...