Превед \о/
Как-то недели 4 тому назад, маясь бессонницей поздним ночером, я тупил в Фейсбуке. Смотрю — Facebook’s Coding Puzzle, оно же opportunity получить работу в солнечной Калифорнии. Ну, думаю, — если убивать время, так не просто же так. Один чёрт, всё равно не высплюсь, так хоть мозги напрягу олимпиадной задачкой…
Вообще, к подобным вещам я отношусь, мягко говоря, прохладно. Олимпиады всех разновидностей с детства недолюбливаю — а заядлых олимпиадников так и вовсе терпеть не могу.
Да, задачи из реальной жизни нередко необходимо решать за строго ограниченное время при строго ограниченном бюджете ресурсов, но они при этом обычно имеют намного более протяжённую границу эксплуатацонного поля, чем олимпиадные экзерсисы, и их контрпродуктивно решать в духе «шнеллер тяп-ляп, и отъебись». Обычно такое решение может служить временной заплаткой, а настоящее — долгоиграющее — по-всякому придётся разрабатывать в процессе, и это уже рутина. А олимпиадники на рутине очень быстро сдуваются, в отличие от посредственностей типа меня.
Из-за этого олимпиадная задача, с моей точки зрения, не может являться позитивной затравкой для начала диалога с кандидатом, с другой стороны, если Фейсбуку нужны мающиеся от бессонницы программисты, то это их, конечно же, дело.
Итак, задачка мне попалась такая:
Некий диалект Конвеевской игры в жизнь
- Есть квадратное игровое поле, полностью занятое чёрными и белыми фишками.
- Для каждой фишки производится просмотр квадрата 3х3, окружающего её.
- Если в квадрате больше чёрных фишек, чем белых, то она становится чёрной. Иначе — белой.
- Все фишки переворачиваются в конце хода одновременно.
- Фишки на границе поля никогда не переворачиваются
На стандартный вход программе передаётся текст, в первой строке которого — количество полей. Со второй строки — описания начальных состояний игровых полей в формате “<размер поля> <количество ходов>”, и далее состояние поля с буквами b и w для чёрных и белых фишек. Например,
1
4 5
bwbw
bbbw
wwwb
wbwb
На стандартный выход требуется выдать состояния всех полей после просчёта всех ходов, но уже без каких-либо циферок.
Также навешены какие-то дурацкие ограничения, типа максимальный размер квадрата — 32х32 и количество ходов не более 50.
На выбор предлагалось что-то около 10 ЯП, от PHP до C# (я, понятное дело, выбрал Java), и час времени.
Из этого часа у меня минут 10 ушло на установку жабы на мою «восьмёрку» — инсталлятором не поставилась ни фига, пришлось выцепить какой-то пыльный архив одного из старых проектов, в котором была JVM, и прописать всякое там окружение.
Впрочем, можно было и без этого обойтись, так как предлагается онлайновый редактор и компилятор, но, правда, очень уж тормознутые, так что локальным пользоваться намного удобней. А также проверяльшик — вот он, как раз, весьма помог, потому что про перевод строки в конце вывода в условии сказано не было. А без него не принималось.
Ну что ж, поехали!
1: import java.util.Scanner;
2:
3: public class Solution {
4: public static void main(String[] args) {
5: Scanner sc = new Scanner(System.in);
6: if (sc.hasNextLine()) {
7: Integer boardCount = new Integer(sc.nextLine());
8: for (int i = 0; i < boardCount; i++) {
9: solveBoard(sc);
10: }
11: }
12: System.out.println();
13: }
14: }
Ну, тут комментировать особо нечего. Тупо читаем количество полей, и вызываем в цикле решалку для каждого из них. Если нам скормили первой строкой какую-нибудь пакость заместо количества — мы упадём. Олимпиадная ведь задача, какая тут, нафиг, проверка на выход за границы эксплуатационного поля? Однако, пустой вход нас уронить не должен.
Для большей семантичностибугога решение одного игрового поля вынесем в отдельный метод:
1: private static void solveBoard(Scanner sc) {
2: String[] boardDefinition = sc.nextLine().split(" ");
3: Integer size = new Integer(boardDefinition[0]);
4: Integer iterations = new Integer(boardDefinition[1]);
5:
6: String[] board = new String[size];
7:
8: for (int n = 0; n < size; n++) {
9: board[n] = sc.nextLine();
10: }
11:
12: for (int i = 0; i < iterations; i++ {
13: }
14: }
Итак, сначала считаем определение поля. Размер складываем в переменную size, количество ходов в iterations. Затем заводим массив из size строк, и считываем в него начальное состояние поля.
Почем массив из size строк, а char[size][size]? Ну что вы как маленькие, право слово? Во-первых, в жабе нету двумерных массивов, только массивы массивов, поэтому память на больших размерностях жрётся как чёрт знает что. Во-вторых, строка в жабе — это уже и так вполне себе неплохо оптимизированный по всем параметрам одномерный массив с произвольным доступом (см. String.charAt(int)).
Поэтому, делаем так:
1: String[] nextBoard = new String[size];
2:
3: int reduced = size - 1;
4: for (int j = 0; j < size; j++) {
5: if ((j == 0) || (j == reduced)) {
6: nextBoard[j] = board[j];
7: } else {
8: StringBuilder sb = new StringBuilder();
9:
10: for (int k = 0; k < size; k++) {
11: if ((k == 0) || (k == reduced)) {
12: sb.append(board[j].charAt(k));
13: } else {
14: // выбрать цвет фишки
15: }
16: }
17:
18: nextBoard[j] = sb.toString();
19: }
20: }
21:
22: board = nextBoard;
Сначала заводим массив строк для состояния поля после совершения хода. Кроме того, нужна переменная для уменьшенной на единицу размерности поля, чтобы каждый раз его не вычислять.
Поначалу я забыл про последний пункт постановки задачи, и минут 7 потратил впустую, пока пытался дождаться проверки заведомо неправильного решения (уж больно фейсбуковский облачный компилятор тормозит), но на тот момент в запасе у меня несколько минут оставалось. Забегая вперёд, скажу, что уложился я в 55 минут из 60 :)
Итак, вспомнив про последний пункт постановки, и обходя игровое поле построчно, мы сразу копируем первую и последнюю строки в следующее состояние. Также, при обходе средних строк, мы, ничего не вычисляя, скопируем первый и последний символ в целевое состояние.
Осталось дело за малым: обойти квадрат 3х3 с центром в рассматриваемой ячейке и посчитать количество чёрных фишек (так как фишек всего 9, и принимаем решение мы исходя из того, что чёрных должно быть строго больше, то нас устроит любое количество больше 4 штук.)
Если бы я был труЪ-программистом, то я написал бы этот кусок примерно так:
1: int black = 0;
2: char c = 'w';
3: enough: for (int jj = j - 1; jj <= j + 1; jj++) {
4: for (int kk = k - 1; kk <= k + 1; kk++) {
5: if (board[jj].charAt(kk) == 'b') black++;
6:
7: if (black > 4) {
8: c = 'b';
9: break enough;
10: }
11: }
12: }
13: sb.append(c);
Но я не Ъ, и поэтому в моём решении обход выглядит так:
1: int black = 0;
2:
3: if (board[j - 1].charAt(k – 1) == 'b') black++;
4: if (board[j - 1].charAt(k) == 'b') black++;
5: if (board[j - 1].charAt(k + 1) == 'b') black++;
6: if (board[j].charAt(k – 1) == 'b') black++;
7: if (board[j].charAt(k) == 'b') black++;
8: if (board[j].charAt(k + 1) == 'b') black++;
9: if (board[j + 1].charAt(k – 1) == 'b') black++;
10: if (board[j + 1].charAt(k) == 'b') black++;
11: if (board[j + 1].charAt(k + 1) == 'b') black++;
12:
13: sb.append((b > 4) ? 'b' : 'w');
Вот только не надо сейчас делать такие O_O глаза.
Во-первых, вложенности циклов уже и без того более чем достаточно. Во-вторых, я не одобряю ниндзюцу ни в каком виде — а тут без него никак, ибо в жабе иначе из двух циклов наружу не выбраться, а подобные вещи в столь высокоуровневом языке очень трудно читать.
Так что делаем циклу unroll, и он (бонусом) начинает выглядеть ближе к пункту 3 постановки задачи. Да вообще, буквально его имплементирует.
Собственно, всё. Только вывод на экран осталось добавить за внешним циклом, но это вообще полная фигня:
1: for (int n = 0; n < size; n++) {
2: system.out.println(board[n]);
3: }
Теперь ещё разок окинем взглядом всё это безобразие целиком:
1: import java.util.Scanner;
2:
3: public class Solution {
4: private static void solveBoard(Scanner sc) {
5: String[] boardDefinition = sc.nextLine().split(" ");
6: Integer size = new Integer(boardDefinition[0]);
7: Integer iterations = new Integer(boardDefinition[1]);
8:
9: String[] board = new String[size];
10:
11: for (int n = 0; n < size; n++) {
12: board[n] = sc.nextLine();
13: }
14:
15: for (int i = 0; i < iterations; i++ {
16: String[] nextBoard = new String[size];
17: int reduced = size - 1;
18:
19: for (int j = 0; j < size; j++) {
20: if ((j == 0) || (j == reduced)) {
21: nextBoard[j] = board[j];
22: } else {
23: StringBuilder sb = new StringBuilder();
24:
25: for (int k = 0; k < size; k++) {
26: if ((k == 0) || (k == reduced)) {
27: sb.append(board[j].charAt(k));
28: } else {
29: int black = 0;
30:
31: if (board[j - 1].charAt(k – 1) == 'b') black++;
32: if (board[j - 1].charAt(k) == 'b') black++;
33: if (board[j - 1].charAt(k + 1) == 'b') black++;
34: if (board[j].charAt(k – 1) == 'b') black++;
35: if (board[j].charAt(k) == 'b') black++;
36: if (board[j].charAt(k + 1) == 'b') black++;
37: if (board[j + 1].charAt(k – 1) == 'b') black++;
38: if (board[j + 1].charAt(k) == 'b') black++;
39: if (board[j + 1].charAt(k + 1) == 'b') black++;
40:
41: sb.append((b > 4) ? 'b' : 'w');
42: }
43: }
44:
45: nextBoard[j] = sb.toString();
46: }
47: }
48:
49: board = nextBoard;
50: }
51:
52: for (int n = 0; n < size; n++) {
53: system.out.println(board[n]);
54: }
55: }
56:
57: public static void main(String[] args) {
58: Scanner sc = new Scanner(System.in);
59: if (sc.hasNextLine()) {
60: Integer boardCount = new Integer(sc.nextLine());
61: for (int i = 0; i < boardCount; i++) {
62: solveBoard(sc);
63: }
64: }
65: System.out.println();
66: }
67: }
Проверку на все кейсы программулина прошла со свистом, и я с чистой совестью отправился спать.
«А что же Фейсбук?» спросите вы.
Ну а чё Фейсбук. Ну, написала мне ихняя HR, назадавала кучу вопросов на тему профессионального развития, и после шестого моего письма с ответами (не вру, реально шестого) предложила позвонить скайпом и взять у меня пятнадцатиминутное ынтарвью. И тут я честно сознался, что в устном английском не силён, в ответ на что получил категорическое «We have a very open and communicative environment, so fluent spoken English is a must. If you don’t see yourself as a fluent speaker, unfortunately, we cannot move on at this time.»
Так что не светит мне солнечная Калифорния. По крайней мере, до тех пор, пока не подточу английский. А там — посмотрим.
