<commit_before>/** @author <NAME> */

/** B представляет пустую клетку
  * @type {CellState}
  */
var B = false;

/** Q представляет клетку с ферзем
  * @type {CellState}
  */
var Q = true;

/** Пустая доска с размерностью n=4
  * @type {Board}
  */
var n4emptBrd = [B, B, B, B,
                 B, B, B, B,
                 B, B, B, B,
                 B, B, B, B];

/** Решение для доски с размерностью 4
  * @type {Board}
  */
var n4solBrd = [B, Q, B, B,
                B, B, B, Q,
                Q, B, B, B,
                B, B, Q, B];

/** Создает пустую доску n*n элементов
  * @param  {Natural} n Размерность доски
  * @return {Board}
  */
function createEmptyBoard(n){
  var b = [];
  for(var i=0;i<n*n;i++){ b.push(B); }
  return b;
}

// Тесты для функции createEmptyBoard
(function(){
  console.log("Тест1:", createEmptyBoard(4).length==16);
})();

/** Решает проблему n-ферзей
  * @param  {Board} b Доска
  * @return {Board | false} Если задача имеет решение - доску, иначе false
  */
// function solve(b){return false; } // заглушка
function solve(b){
   // Ищет решение для данной доски
   // @param {Board} b
   // @return {Board | false}
  function solveBrd(b){
    if(isSolved(b)){
      return b;
    }else{
      return solveChilds(nextBoards(b));
    }
  }

  // Ищет решения для списка потомков
  // @param {array.<Board>} lob
  // @return {Board | false}
  function solveChilds(lob){
    if(lob.length==0){
      return false; // базовый случай
    }else{
      // рекурсивный случай
      var first = lob[0];
      var rest  = lob.slice(1,lob.length);
      var tryBrd = solveBrd(first);
      if(tryBrd!=false){
        return tryBrd;
      }else{
        return solveChilds(rest);
      }
    }
  }

  return solveBrd(b);
}

(function(){
  console.log("Тест2:", solve(createEmptyBoard(1)).toString()==[Q].toString());
  console.log("Тест3:", solve(createEmptyBoard(2))==false);
  console.log("Тест4:", solve(createEmptyBoard(4)).toString()==n4solBrd.toString());
})();

/** Является ли данная доска решением?
  * @param  {Board} b
  * @return {Boolean}
  */
//function isSolved(b){ return false; } // Заглушка
function isSolved(b){
  return isValid(b) && getFiguresPos(0, b).length==getBoardSize(b);
}

(function(){
  console.log("Тест23:", isSolved(n4emptBrd)==false);
  console.log("Тест24:", isSolved(n4solBrd)==true);
})();

/** Создает массив потомков данной доски
  * Все несостоятельные доски вырезаются
  * @param  {Board} b
  * @return {array.<Board>}
  */
// function nextBoards(b){ return []; } // Заглушка
function nextBoards(b){
  return keepOnlyValid(fillBlanks(b));
}

// Тесты для nextBoards
(function(){
  console.log("Тест5:", nextBoards(createEmptyBoard(1)).toString()==keepOnlyValid(fillBlanks(createEmptyBoard(1))).toString());
})();

/** Создает массив досок в которых в каждой пустой клетке
    исходной доски стоит фигурка
  * @param  {Board} b Исходная доска
  * @return {array.<Board>}
  */
// function fillBlanks(b){ return []; } // заглушка
function fillBlanks(b){
  // @param {Board}   brd Итерируемая доска
  // @param {Natural} pos Позиция
  function iter(brd, pos){
    if(brd.length==0){
      return []; // базовый случай
    }else{
      var first = brd[0];
      var rest  = brd.slice(1,brd.length);
      if(first!=Q){
        return [fillSquare(b, pos, Q)].concat(iter(rest, pos+1));
      }else{
        return iter(rest, pos+1);
      }
    }
  }

  var clone = b.slice(0, b.length); // Клонируем доску
  return iter(clone, 0);
}

// Тесты для fillBlanks
(function(){
  console.log(
    "Тест6:",
    (function(){
      var x = fillBlanks(createEmptyBoard(1));
      return x.length==1 && x[0][0]==Q;
    })());
  console.log("Тест7:", fillBlanks([Q]).length==0);
  console.log(
    "Тест8:",
    (function(){
      var x = fillBlanks(createEmptyBoard(2));
      return x.length==4 &&
        x[0].toString()==[Q,B,B,B].toString() &&
        x[1].toString()==[B,Q,B,B].toString() &&
        x[2].toString()==[B,B,Q,B].toString() &&
        x[3].toString()==[B,B,B,Q].toString()
    })());
})();

/** Ставит на доску в данную позицию данное значение (ферзь или пустая)
  * @param {Board}   b Доска
  * @param {Natural} p Позиция
  * @param {Q | B}   v Ферзь или пустая?
  */
function fillSquare(b,p,v){
  var clone = b.slice(0, b.length);
  clone[p]=v;
  return clone;
}

// Тесты для функции fillSquare
(function(){
  console.log("Тест9:", fillSquare([B],0,Q).toString()==[Q].toString());
})();

/** Фильтрует массив досок оставляя только те доски
    в которых ни одна фигурка не атакует другую
  * @param  {array.<Board>} lob
  * @return {array.<Board>}
  */
//function keepOnlyValid(lob){ return []; } // заглушка
function keepOnlyValid(lob){
  return lob.filter(function(b){ return isValid(b); });
}

(function(){
  console.log("Тест10:", keepOnlyValid([[B]]).toString()==[[B]].toString());
  console.log("Тест11:", keepOnlyValid([[Q]]).toString()==[[Q]].toString());
  console.log("Тест12:", function(){
    var lob = [
      [Q,Q,B,B],
      [B,Q,Q,B],
      [B,Q,B,Q]
    ];
    return keepOnlyValid(lob).length==0;
  }());
})();

/** Проверяет валидна ли доска
  * @param {Board} b Доска
  * @return {Boolean} true - доска валидна, иначе false
  */
//function isValid(b){ return false; }
function isValid(b){
  // Не атакует по горизонтали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByHorizontal(pos1, pos2){
    return !(posToRow(pos1, b)==posToRow(pos2, b));
  }

  // Не атакует по вертикали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByVertical(pos1, pos2){
    return !(posToCol(pos1, b)==posToCol(pos2, b));
  }

  // Не атакует ли первая фигурка вторую по диагонали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByDiagonal(pos1, pos2){
    var rowDiff = posToRow(pos1, b) - posToRow(pos2, b);
    var colDiff = posToCol(pos1, b) - posToCol(pos2, b);
    return !(Math.abs(rowDiff/colDiff)==1);
  }

  // Не атакует ли эта фигурка другую фигурку?
  // @param  {Integer} thisPos   Позиция этой фигурки
  // @param  {Integer} othersPos Позиция остальных фигурок
  // @return {Boolean} true если атакует
  function notAttackOthers(thisPos, othersPos){
    if(othersPos.length==0){
      return true;
    }else{
      var othersFirst = othersPos[0];
      var othersRest  = othersPos.slice(1, othersPos.length);
      return notAttackByHorizontal(thisPos, othersFirst) &&
        notAttackByVertical(thisPos, othersFirst) &&
        notAttackByDiagonal(thisPos, othersFirst) &&
        notAttackOthers(thisPos, othersRest);
    }
  }

  // Проверяет не атакуют ли фигурки друг друга
  // @param  {array.<Integer>} Массив позиций фигурок на доске
  // @return {Boolean} true если фигурки не атакуют друг-друга
  function checkFigures(positions){
    if(positions.length==0){
      return true; // базовый случай
    }else{
      var first = positions[0];
      var rest  = positions.slice(1, positions.length);
      return notAttackOthers(first, rest) && checkFigures(rest);
    }
  }

  return checkFigures(getFiguresPos(0, b));
}

// Тесты для функции isValid
(function(){
  // Не валидна если фигурки на одной горизонтали
  console.log("Тест13:", isValid([Q,Q,
                                  B,B])==false);
  // Не валидна если фигурки на одной вертикали
  console.log("Тест14:", isValid([Q,B,
                                  Q,B])==false);
  // Не валидна если фигурки на одной диагонали
  console.log("Тест15:", isValid([Q,B,
                                  B,Q])==false);
  console.log("Тест16:", isValid([B,Q,
                                  Q,B])==false);
  // Валидные доски
  console.log("Тест17:", isValid([Q])==true);
  console.log("Тест18:", isValid(n4emptBrd)==true);
  console.log("Тест19:", isValid(n4solBrd)==true);
})();

/** Возвращает массив со всеми позициями фигурок на доске
  * @param  {Integer} curPos Текущая позиция
  * @param  {Board}  board  Доска
  * @return {array.<Integer>}
  */
function getFiguresPos(curPos, board){
  if(board.length==0){
    return [];
  }else{
    var first = board[0];
    var rest  = board.slice(1, board.length);
    if(first==Q){
      return [curPos].concat(getFiguresPos(curPos+1, rest));
    }else{
      return getFiguresPos(curPos+1, rest);
    }
  }
}

/** Считает размерность доски исходя из количества элементов
  * @param  {Board}   Доска
  * @return {Natural} Размерность доски
  */
function getBoardSize(board){
  return Math.sqrt(board.length);
}

// Тесты для функции getBoardSize
(function(){
  console.log("Тест20:", getBoardSize(n4emptBrd)==4);
})();

/** Переводит позицию фигурки в строку
  * @param  {Integer} Позиция доски
  * @param  {Board}   Доска
  * @return {Integer} Строка на которой стоит фигурка. Zero-base
  */
function posToRow(pos, board){
  // Тут важно округлить в меньшую сторону
  return Math.floor(pos/getBoardSize(board));
}

// Тесты для функции posToRow
(function(){
  console.log("Тест21:", posToRow(1, n4emptBrd)==0);
})();

/** Переводит позицию фигурки в столбец
  * @param  {Integer} Позиция доски
  * @param  {Board}   Доска
  * @return {Integer} Колонка на которой стоит фигурка. Zero-base
  */
function posToCol(pos, board){
  return pos%getBoardSize(board);
}

// Тесты для функции posToCol
(function(){
  console.log("Тест22:", posToCol(5, n4emptBrd)==1);
})();

/** Тест производительности.
  * Передайте начальный размер доски и конечный размер доски, тест посчитает сколько занимает поиск решения для каждой доски в этом интервале
  * @param {Natural} startSizeOfBoard Начальный размер доски
  * @param {Natural} endSizeOfBoard   Конечный размер доски
  * @return {true} Тест закончился
  */
function benchmark(startSizeOfBoard, maxSizeOfBoard){
  if(startSizeOfBoard>maxSizeOfBoard){
    return true;
  }else{
    console.log("Считаем для доски с размерностью:", startSizeOfBoard);
    var startTime = Date.now();
    var solution  = solve(createEmptyBoard(startSizeOfBoard));
    var endTime   = Date.now();
    console.log("Решение:", solution.toString());
    console.log("Затраченное время:", endTime - startTime, "миллисекунд");
    return benchmark(startSizeOfBoard+1, maxSizeOfBoard);
  }
}
<commit_msg>Правка<commit_after>/** @author <NAME> */

/** B представляет пустую клетку
  * @type {CellState}
  */
var B = false;

/** Q представляет клетку с ферзем
  * @type {CellState}
  */
var Q = true;

/** Пустая доска с размерностью n=4
  * @type {Board}
  */
var n4emptBrd = [B, B, B, B,
                 B, B, B, B,
                 B, B, B, B,
                 B, B, B, B];

/** Решение для доски с размерностью 4
  * @type {Board}
  */
var n4solBrd = [B, Q, B, B,
                B, B, B, Q,
                Q, B, B, B,
                B, B, Q, B];

/** Создает пустую доску n*n элементов
  * @param  {Natural} n Размерность доски
  * @return {Board}
  */
function createEmptyBoard(n){
  var b = [];
  for(var i=0;i<n*n;i++){ b.push(B); }
  return b;
}

// Тесты для функции createEmptyBoard
(function(){
  console.log("Тест1:", createEmptyBoard(4).length==16);
})();

/** Решает проблему n-ферзей
  * @param  {Board} b Доска
  * @return {Board | false} Если задача имеет решение - доску, иначе false
  */
// function solve(b){return false; } // заглушка
function solve(b){
   // Ищет решение для данной доски
   // @param {Board} b
   // @return {Board | false}
  function solveBrd(b){
    if(isSolved(b)){
      return b;
    }else{
      return solveChilds(nextBoards(b));
    }
  }

  // Ищет решения для списка потомков
  // @param {array.<Board>} lob
  // @return {Board | false}
  function solveChilds(lob){
    if(lob.length==0){
      return false; // базовый случай
    }else{
      // рекурсивный случай
      var first = lob[0];
      var rest  = lob.slice(1,lob.length);
      var tryBrd = solveBrd(first);
      if(tryBrd!=false){
        return tryBrd;
      }else{
        return solveChilds(rest);
      }
    }
  }

  return solveBrd(b);
}

(function(){
  console.log("Тест2:", solve(createEmptyBoard(1)).toString()==[Q].toString());
  console.log("Тест3:", solve(createEmptyBoard(2))==false);
  console.log("Тест4:", solve(createEmptyBoard(4)).toString()==n4solBrd.toString());
})();

/** Является ли данная доска решением?
  * @param  {Board} b
  * @return {Boolean}
  */
//function isSolved(b){ return false; } // Заглушка
function isSolved(b){
  return isValid(b) && getFiguresPos(0, b).length==getBoardSize(b);
}

(function(){
  console.log("Тест23:", isSolved(n4emptBrd)==false);
  console.log("Тест24:", isSolved(n4solBrd)==true);
})();

/** Создает массив потомков данной доски
  * Все не валидные доски вырезаются
  * @param  {Board} b
  * @return {array.<Board>}
  */
// function nextBoards(b){ return []; } // Заглушка
function nextBoards(b){
  return keepOnlyValid(fillBlanks(b));
}

// Тесты для nextBoards
(function(){
  console.log("Тест5:", nextBoards(createEmptyBoard(1)).toString()==keepOnlyValid(fillBlanks(createEmptyBoard(1))).toString());
})();

/** Создает массив досок в которых в каждой пустой клетке
    исходной доски стоит фигурка
  * @param  {Board} b Исходная доска
  * @return {array.<Board>}
  */
// function fillBlanks(b){ return []; } // заглушка
function fillBlanks(b){
  // @param {Board}   brd Итерируемая доска
  // @param {Natural} pos Позиция
  function iter(brd, pos){
    if(brd.length==0){
      return []; // базовый случай
    }else{
      var first = brd[0];
      var rest  = brd.slice(1,brd.length);
      if(first!=Q){
        return [fillSquare(b, pos, Q)].concat(iter(rest, pos+1));
      }else{
        return iter(rest, pos+1);
      }
    }
  }

  var clone = b.slice(0, b.length); // Клонируем доску
  return iter(clone, 0);
}

// Тесты для fillBlanks
(function(){
  console.log(
    "Тест6:",
    (function(){
      var x = fillBlanks(createEmptyBoard(1));
      return x.length==1 && x[0][0]==Q;
    })());
  console.log("Тест7:", fillBlanks([Q]).length==0);
  console.log(
    "Тест8:",
    (function(){
      var x = fillBlanks(createEmptyBoard(2));
      return x.length==4 &&
        x[0].toString()==[Q,B,B,B].toString() &&
        x[1].toString()==[B,Q,B,B].toString() &&
        x[2].toString()==[B,B,Q,B].toString() &&
        x[3].toString()==[B,B,B,Q].toString()
    })());
})();

/** Ставит на доску в данную позицию данное значение (ферзь или пустая)
  * @param {Board}   b Доска
  * @param {Natural} p Позиция
  * @param {Q | B}   v Ферзь или пустая?
  */
function fillSquare(b,p,v){
  var clone = b.slice(0, b.length);
  clone[p]=v;
  return clone;
}

// Тесты для функции fillSquare
(function(){
  console.log("Тест9:", fillSquare([B],0,Q).toString()==[Q].toString());
})();

/** Фильтрует массив досок оставляя только те доски
    в которых ни одна фигурка не атакует другую
  * @param  {array.<Board>} lob
  * @return {array.<Board>}
  */
//function keepOnlyValid(lob){ return []; } // заглушка
function keepOnlyValid(lob){
  return lob.filter(function(b){ return isValid(b); });
}

(function(){
  console.log("Тест10:", keepOnlyValid([[B]]).toString()==[[B]].toString());
  console.log("Тест11:", keepOnlyValid([[Q]]).toString()==[[Q]].toString());
  console.log("Тест12:", function(){
    var lob = [
      [Q,Q,B,B],
      [B,Q,Q,B],
      [B,Q,B,Q]
    ];
    return keepOnlyValid(lob).length==0;
  }());
})();

/** Проверяет валидна ли доска
  * @param {Board} b Доска
  * @return {Boolean} true - доска валидна, иначе false
  */
//function isValid(b){ return false; }
function isValid(b){
  // Не атакует по горизонтали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByHorizontal(pos1, pos2){
    return !(posToRow(pos1, b)==posToRow(pos2, b));
  }

  // Не атакует по вертикали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByVertical(pos1, pos2){
    return !(posToCol(pos1, b)==posToCol(pos2, b));
  }

  // Не атакует ли первая фигурка вторую по диагонали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByDiagonal(pos1, pos2){
    var rowDiff = posToRow(pos1, b) - posToRow(pos2, b);
    var colDiff = posToCol(pos1, b) - posToCol(pos2, b);
    return !(Math.abs(rowDiff/colDiff)==1);
  }

  // Не атакует ли эта фигурка другую фигурку?
  // @param  {Integer} thisPos   Позиция этой фигурки
  // @param  {Integer} othersPos Позиция остальных фигурок
  // @return {Boolean} true если атакует
  function notAttackOthers(thisPos, othersPos){
    if(othersPos.length==0){
      return true;
    }else{
      var othersFirst = othersPos[0];
      var othersRest  = othersPos.slice(1, othersPos.length);
      return notAttackByHorizontal(thisPos, othersFirst) &&
        notAttackByVertical(thisPos, othersFirst) &&
        notAttackByDiagonal(thisPos, othersFirst) &&
        notAttackOthers(thisPos, othersRest);
    }
  }

  // Проверяет не атакуют ли фигурки друг друга
  // @param  {array.<Integer>} Массив позиций фигурок на доске
  // @return {Boolean} true если фигурки не атакуют друг-друга
  function checkFigures(positions){
    if(positions.length==0){
      return true; // базовый случай
    }else{
      var first = positions[0];
      var rest  = positions.slice(1, positions.length);
      return notAttackOthers(first, rest) && checkFigures(rest);
    }
  }

  return checkFigures(getFiguresPos(0, b));
}

// Тесты для функции isValid
(function(){
  // Не валидна если фигурки на одной горизонтали
  console.log("Тест13:", isValid([Q,Q,
                                  B,B])==false);
  // Не валидна если фигурки на одной вертикали
  console.log("Тест14:", isValid([Q,B,
                                  Q,B])==false);
  // Не валидна если фигурки на одной диагонали
  console.log("Тест15:", isValid([Q,B,
                                  B,Q])==false);
  console.log("Тест16:", isValid([B,Q,
                                  Q,B])==false);
  // Валидные доски
  console.log("Тест17:", isValid([Q])==true);
  console.log("Тест18:", isValid(n4emptBrd)==true);
  console.log("Тест19:", isValid(n4solBrd)==true);
})();

/** Возвращает массив со всеми позициями фигурок на доске
  * @param  {Integer} curPos Текущая позиция
  * @param  {Board}  board  Доска
  * @return {array.<Integer>}
  */
function getFiguresPos(curPos, board){
  if(board.length==0){
    return [];
  }else{
    var first = board[0];
    var rest  = board.slice(1, board.length);
    if(first==Q){
      return [curPos].concat(getFiguresPos(curPos+1, rest));
    }else{
      return getFiguresPos(curPos+1, rest);
    }
  }
}

/** Считает размерность доски исходя из количества элементов
  * @param  {Board}   Доска
  * @return {Natural} Размерность доски
  */
function getBoardSize(board){
  return Math.sqrt(board.length);
}

// Тесты для функции getBoardSize
(function(){
  console.log("Тест20:", getBoardSize(n4emptBrd)==4);
})();

/** Переводит позицию фигурки в строку
  * @param  {Integer} Позиция доски
  * @param  {Board}   Доска
  * @return {Integer} Строка на которой стоит фигурка. Zero-base
  */
function posToRow(pos, board){
  // Тут важно округлить в меньшую сторону
  return Math.floor(pos/getBoardSize(board));
}

// Тесты для функции posToRow
(function(){
  console.log("Тест21:", posToRow(1, n4emptBrd)==0);
})();

/** Переводит позицию фигурки в столбец
  * @param  {Integer} Позиция доски
  * @param  {Board}   Доска
  * @return {Integer} Колонка на которой стоит фигурка. Zero-base
  */
function posToCol(pos, board){
  return pos%getBoardSize(board);
}

// Тесты для функции posToCol
(function(){
  console.log("Тест22:", posToCol(5, n4emptBrd)==1);
})();

/** Тест производительности.
  * Передайте начальный размер доски и конечный размер доски, тест посчитает сколько занимает поиск решения для каждой доски в этом интервале
  * @param {Natural} startSizeOfBoard Начальный размер доски
  * @param {Natural} endSizeOfBoard   Конечный размер доски
  * @return {true} Тест закончился
  */
function benchmark(startSizeOfBoard, maxSizeOfBoard){
  if(startSizeOfBoard>maxSizeOfBoard){
    return true;
  }else{
    console.log("Считаем для доски с размерностью:", startSizeOfBoard);
    var startTime = Date.now();
    var solution  = solve(createEmptyBoard(startSizeOfBoard));
    var endTime   = Date.now();
    console.log("Решение:", solution.toString());
    console.log("Затраченное время:", endTime - startTime, "миллисекунд");
    return benchmark(startSizeOfBoard+1, maxSizeOfBoard);
  }
}

{'fraction_non_alphanumeric': 0.16012993837481487, 'fraction_numerical': 0.01184732240959251, 'mean_word_length': 3.2670199755401548, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1412226', 'n_tokens_mistral': 8035, 'n_tokens_neox': 8392, 'n_words': 1779}