Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

import 
java.util.Random;
public class 
WordGrid {
public static class 
GridLocation {
public final int 
row, column;
public 
GridLocation(
int 
row, 
int 
column) {
this
.row = row;
this
.column = column;
}
// автоматическое создание Eclipse
@Override
public int 
hashCode() {
final int 
prime = 31;
int 
result = 1;
result = prime * result + column;
result = prime * result + row;
return 
result;
}
// автоматическое создание Eclipse
@Override
public boolean 
equals(Object obj) {
if 
(
this 
== obj) {
return true
;
}
if 
(obj == 
null
) {
return false
;
}
if 
(getClass() != obj.getClass()) {
return false
;
}
GridLocation other = (GridLocation) obj;
if 
(column != other.column) {
return false
;
}
if 
(row != other.row) {

---

98
Глава 3.
Задачи с ограничениями
return false
;
}
return true
;
}
}
Сначала.заполним.сетку.буквами.английского.алфавита.(
A-Z
),.генерируя.случай-
ные.символьные.коды.(целые.числа),.эквивалентные.буквам.кода.ASCII..Нам.
также.понадобится.метод.для.отметки.слова.в.сетке.с.учетом.списка.местополо-
жений.и.метод.отображения.сетки.(листинг.3.12).
Листинг 3.12. 
WordGrid.java (продолжение)
private final char 
ALPHABET_LENGTH = 26;
private final char 
FIRST_LETTER = 'A';
private final int 
rows, columns;
private char
[][] grid;
public 
WordGrid(
int 
rows, 
int 
columns) {
this
.rows = rows;
this
.columns = columns;
grid = 
new char
[rows][columns];
// инициализируем сетку случайными буквами
Random random = 
new 
Random();
for 
(
int 
row = 0; row < rows; row++) {
for 
(
int 
column = 0; column < columns; column++) {
char 
randomLetter = (
char
) (random.nextInt(ALPHABET_LENGTH)
+ FIRST_LETTER);
grid[row][column] = randomLetter;
}
}
}
public void 
mark(String word, List locations) {
for 
(
int 
i = 0; i < word.length(); i++) {
GridLocation location = locations.get(i);
grid[location.row][location.column] = word.charAt(i);
}
}
// получаем красивую печатную версию сетки
@Override
public 
String toString() {
StringBuilder sb = 
new 
StringBuilder();
for 
(
char
[] rowArray : grid) {
sb.append(rowArray);
sb.append(System.
lineSeparator
());
}
return 
sb.toString();
}

---

3.4. Поиск слова
99
Чтобы.выяснить,.где.можно.расположить.слова.в.сетке,.сгенерируем.их.области.
определения..Область.определения.слова.—.это.список.списков.возможных.по-
ложений.всех.его.букв.(
List>
)..Однако.слова.не.могут.рас-
полагаться.где.попало..Они.должны.находиться.в.пределах.строки,.столбца.или.
диагонали.в.пределах.сетки..Иначе.говоря,.они.не.должны.выходить.за.пределы.
сетки..Цель.функции.
generateDomain()
.—.создание.таких.списков.для.каждого.
слова.(листинг.3.13).
Листинг 3.13. 
WordGrid.java (продолжение)
public 
List> generateDomain(String word) {
List> domain = 
new 
ArrayList<>();
int 
length = word.length();
for 
(
int 
row = 0; row < rows; row++) {
for 
(
int 
column = 0; column < columns; column++) {
if 
(column + length <= columns) {
// слева направо
fillRight(domain, row, column, length);
// по диагонали снизу направо
if 
(row + length <= rows) {
fillDiagonalRight(domain, row, column, length);
}
}
if 
(row + length <= rows) {
// сверху вниз
fillDown(domain, row, column, length);
// по диагонали снизу налево
if 
(column — length >= 0) {
fillDiagonalLeft(domain, row, column, length);
}
}
}
}
return 
domain;
}
private void 
fillRight(List> domain,
int 
row, 
int 
column, 
int 
length) {
List locations = 
new 
ArrayList<>();
for 
(
int 
c = column; c < (column + length); c++) {
locations.add(
new 
GridLocation(row, c));
}
domain.add(locations);
}
private void 
fillDiagonalRight(List> domain,
int 
row, 
int 
column, 
int 
length) {
List locations = 
new 
ArrayList<>();
int 
r = row;
for 
(
int 
c = column; c < (column + length); c++) {
locations.add(
new 
GridLocation(r, c));

---

100
Глава 3.
Задачи с ограничениями
r++;
}
domain.add(locations);
}
private void 
fillDown(List> domain, 
int 
row,
int 
column, 
int 
length) {
List locations = 
new 
ArrayList<>();
for 
(
int 
r = row; r < (row + length); r++) {
locations.add(
new 
GridLocation(r, column));
}
domain.add(locations);
}
private void 
fillDiagonalLeft(List> domain,
int 
row, 
int 
column, 
int 
length) {
List locations = 
new 
ArrayList<>();
int 
c = column;
for 
(
int 
r = row; r < (row + length); r++) {
locations.add(
new 
GridLocation(r, c));
c--;
}
domain.add(locations);
}
}
Для.определения.диапазона.потенциальных.положений.слова.(вдоль.строки,.
столбца.или.по.диагонали).списочные.выражения.преобразуют.диапазон.в.спи-
сок.
GridLocation
.с.помощью.конструктора.этого.класса..Поскольку.для.каждого.
слова.
generateDomain()
.перебирает.все.ячейки.сетки.от.верхней.левой.до.нижней.
правой,.требуется.большое.количество.вычислений..Можете.ли.вы.придумать.
способ.сделать.это.более.эффективно?.Что,.если.одновременно.просматривать.
все.слова.одинаковой.длины.внутри.цикла?
Чтобы.проверить,.допустимо.ли.потенциальное.решение,.мы.должны.реали-
зовать.пользовательское.ограничение.для.поиска.слова..Метод.
satisfied()
.
в.
WordSearchConstraint
.просто.проверяет,.совпадают.ли.какие-то.положения,.
предложенные.для.одного.слова,.с.положением,.предложенным.для.другого.слова..
Это.делается.с.помощью.
set
..Преобразование.
list
.в.
set
.исключит.все.дубликаты..
Если.в.
set
,.преобразованном.из.
list
,.окажется.меньше.элементов,.чем.было.в.ис-
ходном.
list
,.это.означает,.что.исходный.
list
.содержал.несколько.дубликатов..
Чтобы.подготовить.данные.для.этой.проверки,.воспользуемся.
flatMap()
.для.
объединения.нескольких.подсписков.положений.каждого.слова.в.присваивании.
в.один.большой.список.положений.(листинг.3.14).
Наконец-то.мы.готовы.запустить.программу..Для.примера.есть.пять.слов.в.сетке.
9.
×
.9..Решение,.которое.получим,.должно.содержать.соответствия.между.каж-
дым.словом.и.местами,.где.составляющие.его.буквы.могут.поместиться.в.сетке.
(листинг.3.15).

---

3.4. Поиск слова
101
Листинг 3.14. 
WordSearchConstraint.java (продолжение)
package 
chapter3;
import 
java.util.Collection;
import 
java.util.Collections;
import 
java.util.HashMap;
import 
java.util.HashSet;
import 
java.util.List;
import 
java.util.Map;
import 
java.util.Map.Entry;
import 
java.util.Random;
import 
java.util.Set;
import 
java.util.stream.Collectors;
import 
chapter3.WordGrid.GridLocation;
public class 
WordSearchConstraint 
extends 
ConstraintList> {
public 
WordSearchConstraint(List words) {
super
(words);
}
@Override
public boolean 
satisfied(Map> assignment) {
// объединение всех GridLocations в один огромный список
List allLocations = assignment.values().stream()
.flatMap(Collection::stream).collect(Collectors.
toList
());
// наличие дубликатов положений сетки означает наличие совпадения
Set allLocationsSet = 
new 
HashSet<>(allLocations);
// если какие-либо повторяющиеся местоположения сетки найдены, 
// значит, есть перекрытие
return 
allLocations.size() == allLocationsSet.size();
}
Листинг 3.15. 
WordSearchConstraint.java (продолжение)
public static void 
main(String[] args) {
WordGrid grid = 
new 
WordGrid(9, 9);
List words = List.
of
("MATTHEW", "JOE", "MARY", "SARAH", "SALLY");
// генерация доменов для всех слов
Map>> domains = 
new 
HashMap<>();
for 
(String word : words) {
domains.put(word, grid.generateDomain(word));
}
CSP> csp = 
new 
CSP<>(words, domains);
csp.addConstraint(
new 
WordSearchConstraint(words));
Map> solution = csp.backtrackingSearch();
if 
(solution == 
null
) {
System.
out
.println("No solution found!");
} 
else 
{
Random random = 
new 
Random();
for 
(Entry> item : solution.entrySet()) {

---

102
Глава 3.
Задачи с ограничениями
String word = item.getKey();
List locations = item.getValue();
// в половине случаев случайным выбором — задом наперед
if 
(random.nextBoolean()) {
Collections.
reverse
(locations);
}
grid.mark(word, locations);
}
System.
out
.println(grid);
}
}
}
В.коде.есть.последний.штрих,.заполняющий.сетку.словами..Некоторые.слова,.
выбранные.случайным.образом,.располагаются.задом.наперед..Это.корректно,.
поскольку.данный.пример.не.допускает.наложения.слов..Конечный.результат.
должен.выглядеть.примерно.так..Сможете.ли.вы.найти.здесь.имена.Matthew,.
Joe,.Mary,.Sarah.и.Sally?
LWEHTTAMJ
MARYLISGO
DKOJYHAYE
IAJYHALAG
GYZJWRLGM
LLOTCAYIX
PEUTUSLKO
AJZYGIKDU
HSLZOFNNR
3.5. SEND + MORE = MONEY
SEND.+.MORE.=.MONEY.—.это.криптоарифметическая.головоломка,.где.нуж-
но.найти.такие.цифры,.которые,.будучи.подставленными.вместо.букв,.сделают.
математическое.утверждение.верным..Каждая.буква.в.задаче.представляет.одну.
цифру.от.0.до.9..Никакие.две.разные.буквы.не.могут.представлять.одну.и.ту.
же.цифру..Если.буква.повторяется,.это.означает,.что.цифра.в.решении.также.
повторяется.
Чтобы.проще.было.решить.эту.задачку.вручную,.стоит.выстроить.слова.в.столбик:
SEND
+MORE
=MONEY
Задача.легко.решается.вручную,.потребуется.лишь.немного.алгебры.и.интуиции..
Но.довольно.простая.компьютерная.программа.поможет.сделать.это.быстрее,.ис-
пользуя.множество.возможных.решений..Представим.SEND.+.MORE.=.MONEY.
как.задачу.с.ограничениями.(листинг.3.16).

---

3.5. SEND + MORE = MONEY