Проблемът с N-дама е една от класическите главоблъсканици, перфектна възможност да изтупате праха от старата шахматна дъска за няколко ръце на проба и грешка. Но също така често се използва като пример при изучаване на нов език за програмиране и в този текст ще разгледаме как можем да го решим със сравнително нова функция на javascript — генератори. Въпреки че има много начини за решаване на този проблем, използването на ES6-генератори е особено елегантен метод и показва защо генераторите са полезна техника.
Проблемът с N-дама е лесен за формулиране, но по-труден за решаване: На N*N квадратна шахматна дъска поставете N дами по начин, така че никоя дама да не застрашава някоя от другите, т.е. споделя колона, ред или диагонал. За N = 4 решението може да изглежда така:
Сега към генераторите. И така, какво е? Е, генераторът е нещо, което създава нещо итерируемо. Итерируемото е нещо, което можете да поискате да направи крачка напред и да достави стойност и евентуално сигнал, че няма повече стойности за доставяне. В javascript генераторът изглежда почти като обикновена функция, но връща не само веднъж, а много, вероятно безкрайно много пъти. Прост пример, който преминава през първите N цели числа, изглежда така:
const range = function*(n) {
let c = 0;
while (c++ < n) {
yield n;
}
}
Обърнете внимание на * вдясно от ключовата дума на функцията и израза за доходност. Всеки път, когато генераторът достигне този ред, той ще върне тази стойност и ще вземе почивка, докато някой не извика неговата next() функция.
Можете да итерирате върху всичко, което може да бъде итерирано, с for…of конструкция като тази
for(const val of range(5)) {
console.log(val)
}
// Outputs:
// 0
// 1
// 2
// 3
// 4
Или като го разпространите в масив с оператора за разпространение (...):
console.log([...range(5)]) //[0,1,2,3,4]
Прочетете повече за генераторите тук…
Една употреба на генератори е мързеливо оценяване, домакинска техника във функционални езици като Haskell и Scala, и ви позволява да пишете код, сякаш използва големи масиви от данни с огромни масиви, без всъщност да ги държи в паметта. Това работи, ако имате нужда само от един елемент наведнъж и ако случаят е такъв, можете да итерирате върху генератор, а не върху масив. Това е ключовият момент в нашата програма за решаване на N-дама. Стъпките са както следва:
- Генерирайте всички възможни позиции за дами на дъската
- Филтрирайте позициите, които са решения
- Разпечатайте решенията
Вместо да генерираме всички възможни позиции, ще направим нещо малко по-умно, а именно генериране на всички позиции, където дамите са на различни редове и колони. Един от начините да направите това е да започнете с поставянето на всички дами на главния диагонал и след това да пренаредите или разместите редовете по всички възможни начини. Това ще доведе до всички позиции, където дамите са на различни редове и колони. В код това изглежда така (повярвайте ми или проверете сами):
const permutations = function* (elements) {
if (elements.length === 1) {
yield elements;
} else {
let [first, ...rest] = elements;
for (let perm of permutations(rest)) {
for (let i = 0; i < elements.length; i++) {
let start = perm.slice(0, i);
let rest = perm.slice(i);
yield [...start, first, ...rest];
}
}
}
}
Следващата стъпка е да се намери функция, която заема позиция и проверява дали тя е решение или не. Тъй като знаем, че дамите са на различни редове и колони, трябва само да проверим диагоналите. Тук можем да повторим всички двойки дами и да проверим дали са на един и същи диагонал. Но първо някои помощни програми:
const pairs = function*(iterable) {
const asArray = [...iterable];
for(const val1 of asArray) {
for (const val2 of asArray) {
if(val1 === val2) {
break;
}
yield [val1, val2];
}
}
}
const some = function(iterable, pred) {
for(const val of iterable) {
if(pred(val)){
return true;
}
}
return false;
}
const filter = function*(iterable, predicate) {
for(let val of iterable) {
if (predicate(val)) {
yield val;
}
}
}
const withIndex = function*(iterable) {
let c = 0;
for (const val of iterable) {
yield [val, c++];
}
}
Двойките итератори с индекс и филтър са това, което може да се нарече генератори от втори ред, тъй като те вземат итератор и връщат друг. Надяваме се, че всички тези функции са донякъде ясни. withIndex взема генератор и връща нов, който итерира дадения итерируем, заедно с индекса на стойностите. Имаме нужда от това, тъй като пермутациите наистина са само позицията на колоната на дамите; позицията на реда ще бъде дадена от индекса (или обратното, ако искате).
Последното нещо, от което се нуждаем, преди да съберем тези неща, е функцията за проверка дали две дами са на един и същи диагонал:
([[x1,y1], [x2,y2]]) => Math.abs(x1-x2) == Math.abs(y1-y2)
Помислете за секунда и мисля, че ще разберете защо това работи по предназначение.
const solutions = function(N) {
return filter(
permutations([...range(N)]),
(p) => !some(
pairs(withIndex(p)),
([[x1,y1], [x2,y2]]) => Math.abs(x1-x2) == Math.abs(y1-y2))
)
)
}
Така! Да тръгваме!
*Натиска бягане*
Аааа...Нищо не се случва...това е разочарование.
Работата е там, че ние само връщаме итератор и той няма да направи нищо, преди да го повторим, например чрез for…of цикъл. Като този:
for(const val of solutions(8)) {
const n = val.length;
let str = "";
for (let i = 0; i < n; i++) {
str += val == i ? '♛ ': '▢ ';
}
console.log(str);
}
Това е по-добре! Сега получаваме резултат!
▢ ▢ ♛ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ♛ ▢ ▢ ▢ ♛ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ♛ ▢ ♛ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ♛ ▢ ▢ ▢ ♛ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ♛ ▢ ▢ ▢ ... ...
Ако искахме само едно решение, можехме да направим:
const solution = solutions.next().value;
Това изявление щеше да търси, докато намери едно решение и след това да спре. Нашият цикъл ще търси, докато намери всички решения, и ще ги отпечата.
И това приключва това въведение в генераторите, надявам се, че сте научили нещо полезно :)
