Всем привет. Мы продолжаем решать задачи на JavaScript, на этот раз мы будем делать это на LeetCode. Сегодня у нас вот такая интересная задача
Называется задача Valid Sudoku. В ней нужно через JavaScript проверить, правильно ли указаны значения в полях Судоку.
Правила игры в Судоку
Правила Судоку такие: Есть поле любого размера, которое нужно полностью заполнить цифрами. Какие-то цифры на нём уже есть. Цифры не могут повторяться на одной строке или на одном столбце. Также поле разделено на квадраты, размером 3 на 3, внутри этих квадратов тоже повторений быть не может. И нужно это поле попытаться заполнить.
Например, вот эта клетка. В её столбце есть цифры 1, 2, 5, 6, в её строке есть цифры 1, 4, 7, 8, в её большом квадрате есть цифры 1, 4, 6, 8, 9. В итоге во всех этих клетках есть цифры 1, 2, 4, 5, 6, 7, 8, 9. Не хватает только тройки, которую мы можем смело поставить. Это интересная игра, далеко не во всех местах можно однозначно определить, какую цифру можно поставить, нужно выделить для себя возможные цифры (2 и 3 допустим), и придумывать для себя способы определить правильный ответ.
Кому интересно, можете ознакомиться с правилами и поиграть, лично я раньше обожал играть в эту игру и много нарешал таких судоку.
Приступим к самой задаче на JavaScript
Начинаем решать задачу
В нашей задаче значения должны поступать в виде такого массива. Многомерный массив 9 на 9, в котором вместо пустых ячеек передаются точки. Функция должна выводить либо true, либо false.
Я собираюсь сделать так, чтобы наш код работал в матрицах любого размера одинаково, для начала я получу ширину и высоту матрицы
Дальше я сделал переменную check, которая с самого начала будет равна true, но если будет найдена ошибка, она станет равна false, код функции остановится и эта переменная будет выведена из функции.
Дальше можно сделать цикл, который сравнивает одну ячейку со всеми остальными ячейками строки, потом перемещается на вторую ячейку, дальше он сравнивает её со всеми остальными, и так далее. Это будет долго и затратно, можно сделать это проще
Например, у нас 4 единицы, 0 двоек, 1 тройка, 2 четвёрки и 0 пятёрок.
Можно сделать объект, который будет в себя записывать количество каждой цифры в строке, и проверить строчку на правильность можно будет двумя циклами, один собирает этот объект, а другой проверяет его значения
Я создам дополнительную функцию, которая будет проверять каждый такой объект
После нашего цикла, где происходила запись значений строки в объект, мы отправляем этот объект в функцию для проверки. Если она выведет false, то есть неправильно, мы завершаем код.
Попробуем запустить то, что есть. Код не доделан, пока просто посмотрим
Я решил посмотреть, что же в первом случае. Оказывается точки тоже считаются за символы, а они повторяются везде. Надо это исправлять
Исправляем эту ошибку. Теперь у нас первый случай правильный, а второй нет. Там просто ответ должен получиться False, а наш код из за повторяющихся точек везде False выводил.
Приступаем к проверке столбцов и квадратов. Сделаю для них отдельные циклы.
Возможно, можно сделать это как-то попроще, но вот я сделал так...
Теперь осталось самое сложное, проверка на квадраты...
Я постараюсь придумать свой алгоритм. А я это делать очень люблю.
Думаем... Допустим, у нас есть вот такая таблица
Нужно сделать так, чтобы она проходилась не по отдельным строчкам, а по всем ячейкам большого квадрата. То есть по ячейкам с координатами (1, 1), (2, 1), (3, 1), (2, 1), (2, 2) и так далее... После завершения обхода по квадрату, код должен переходить по ячейкам следующего квадрата и тоже начать делать это с верхнего левого угла. Такой будет у нас механизм.
Проходить по строчкам не получится, у меня есть идея. Можно проходить по всем значениям матрицы от 0 до n (n - количество ячеек в таблице). То есть проходить от ячейки 0 до ячейки 80. Нам нужен цикл, который будет перебирать переменную i от 0 до 80, и эти i преобразовывать в реальные координаты. Допустим i=3 это у нас x=2, y=0.
Лучше с 0 считать их.
Нам нужно высчитать наш будущий X и Y. Попытаемся вывести формулу. Предупреждаю, это будет не просто, нужно будет напрячься.
Мы можем эту i % 3, это задаст нам стенку, за которую x не сможет выйти и будет начинаться сначала. И таким образом он будет проходить по всему квадрату
Дальше мы можем сделать x = i % 3 + Math.floor(i / 9) * 3, тогда этот x будет переходить в следующий квадрат, когда пройдёт через три ряда.
Тогда x = (i % 3 + Math.floor(i / 9) * 3) % 27, x должен переходить на четвёртый квадрат, когда пройдёт три квадрата и дойдёт до стенки.
Сейчас будем проверять наши формулы
Это всё можно посчитать в консоле прямо в браузере. Я перебираю все возможные i от ячеек от 0 до 80 и через формулу получаю наш X. Таким образом мы проходимся по всем квадратам.
Пока вроде правильно
Тоже верно. Посчитаем i = 28 (это 4 большой квадрат, y = 3, x = 1)
Нет, в формуле ошибка, "% 27" неправильно. Всё таки в части формулы "(i % 3 + Math.floor(i / 9) * 3)" уже наш i преобразуется в x, нам нужно написать "% 9"
Теперь наша формула работает, в 28-ой ячейке x = 1.
Посчитаем предпоследнюю 80-ую ячейку
Да, правильно. Ячейка, где i = 80 находится на x = 8.
Формула x = (i % 3 + Math.floor(i / 9) * 3) % 9
Теперь высчитываем y.
y = (Math.floor(i / 3)), Y будет идти до потолка квадрата
y = Math.floor(i / 3) - Math.floor(i / 9) * 3, Y будет переходить в другие квадраты, но он не остановится на правой стенке
y = Math.floor(i / 3) - Math.floor(i / 9) * 3 + Math.floor(i / 27) * 3, Y будет переходить в другие квадраты и подниматься на следующие
И правильно ведь считает.
Повторяю. Мы считаем ячейки в наших больших квадратах, для этого мы будет перебирать все i ячейки нашей таблицы от 0 до 80. Нам нужны эти координаты, и я выводил формулы:
x = (i % 3 + Math.floor(i / 9) * 3) % 9
y = Math.floor(i / 3) - Math.floor(i / 9) * 3 + Math.floor(i / 27) * 3
Но не забываем, мы хотим сделать код, который будет подстраиваться под разные размеры таблицы. Помним, наши переменные w - ширина таблицы, h - высота таблицы
x = (i % 3 + Math.floor(i / 9) * 3) % w
y = Math.floor(i / 3) - Math.floor(i / 9) * 3 + Math.floor(i / (w * 3)) * 3
И вот так наша статья потихонечку превращается в лекцию по математике
Попытаемся это всё вставить в код
И пишем вот такую жесть... Если честно, моё желание объяснять отпало... 😵
Хотя, я вроде что-то и объяснял до этого, но понять смогут только сообразительные и упорные.
Остаётся только запускать это и надеяться, что всё будет работать без багов
Даааааааааааааа!!!! Даааааааааааааааааааааааа!!! Ааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааа!!! Получилось!!! 😆🤩🤣
На первых двух массивах наша программа отработала корректно. А именно, она проверила правильный массив и неправильный массив.
Кроме этого, на LeetCode есть выборка из более большого объёма данных, на которых это всё можно проверять, вот здесь, думаю, начнётся жесть. Мы будем исправлять баги. Начинаем...
Начинается жесть. Исправление багов
Как вы поняли, полностью правильно это сделать у меня не получилось. Программа прошла 470 из 507 тестовых случаев. Я считаю, что это очень хорошо, но всё же, недостаточно.
А ошибка у нас конкретно в этом случае. Наша таблица правильная, но наша программа её откинула
Мои ставки на код с проверкой квадратов, но могут быть ошибки и в других местах.
Выровняем вот эту штуку для удобства
Я понял, что ничего не понял. Мы можем скопировать наш код и вот эту штуку к себе в редактор кода и посмотреть, что у нас не так.
Предлагаю такой способ. В каждой из трёх проверок (по строкам, по столбцам и по большим квадратам) мы будем выводить в консоль текст, если функция выдаёт False на этом месте. Так сказать, используем метод логирования.
Верно, проблема оказалась в квадратах. Я попробую ещё и вывести этот объект, на котором возникла ошибка
У нас произошла ошибка в квадрате, где есть две двойки и одна девятка.
В нашей матрице есть такой участок, но он не является полноценным квадратом. Наш квадрат по какой-то причине съехал
Хотя, чисто в теории, он и так мог съехать. Но эти цифры не находятся в одном квадрате.
Для более точного анализа, я хочу сделать массив с координатами элементов этого самого квадрата и вывести его на экран
Это очень странно. Получается, у нас вот такой квадрат?
С самим механизмом определения координат для i-ой ячейки всё в порядке, проблема с тем, как эти ячейки разбиваются на большие квадраты.
Проблема с этим местом в коде
Попробуем прибавить к i единицу, тогда должно заработать
Теперь наши координаты ячеек стали нормальными. Это видно сразу
Уберём лишнее, что мы написали для определения ошибки, всякие консоль.логи, и загрузим наш код на LeetCode
Дааааа, получилось
Подходим к концу
Я смог решить эту задачу. Только вот как показывает статистика, у других код работает быстрее...
Но нужно понимать, это статистика людей, которые вообще смогли решить эту задачу. Здесь не учитываются те, кто её просто провалил.
По времени выполнения я обошёл 12% программистов, которые её решили, это довольно хорошо.
Её решили 64% человек, которые её решали? Я чувствую себя немножечко глупенько. Но нужно понимать, 3.8 миллиона человек это те, кто вообще взялся за эту задачу, из тех, кто за неё взялся, то есть почувствовал свои силы, решили только 64%.
Ну ладно. Мне задача понравилась. Ну а если у вас есть какие-то комментарии, какие-то идеи насчёт оптимизации кода, пишите в комментариях
Не забывайте ставить лайки и подписываться