Njohnson7.github.io | Космический корабль | Кодовые войны

TL; DR: чтобы решить ката 1 кю в Ruby, все, что вам нужно сделать, это переопределить метод оператора равенства, чтобы все тесты проходили автоматически! (Шучу, пожалуйста, не делайте этого.)

На прошлой неделе я наткнулся на интересное ката (упражнение по программированию) на Codewars, которое называется Небоскребы 6 на 6. Поначалу оно выглядело обманчиво простым, потому что не содержало никаких сложных тем по информатике, как некоторые другие ката 1 кю. Однако это оказалось очень сложным, поэтому мне пришлось работать над этим в течение четырех дней, прежде чем окончательно решить эту проблему.

Иногда такие сложные проблемы могут расстраивать, но эта была очень приятной, потому что, хотя на это у меня ушло время, я все время добивался стабильного прогресса и никогда не застревал надолго. Больше всего помогло применение многих техник решения проблем, которым я научился в Школе запуска.

Я решил написать это сообщение в блоге, чтобы задокументировать свой опыт и показать другим, как даже проблемы, которые сначала кажутся очень пугающими, могут быть решены с помощью правильной стратегии и мышления. Я попытался структурировать этот пост как пошаговое руководство, показывая каждый шаг, который я сделал в процессе решения упражнения. Я постараюсь ничего не выдавать заранее, поэтому, если вы будете следовать указаниям, вы можете в любой момент сделать перерыв, чтобы попробовать это самостоятельно. (Лучшее время для перерыва - прямо перед любыми снимками.)

При правильной технике это ката может быть решено с использованием чистой логики, без необходимости полагаться на случайные догадки или применение грубой силы. Это делает его гораздо более приятным. В этом сообщении в блоге я покажу вам, как вы можете этого добиться.

Описание ката 6 на 6 небоскребов:

В сетке 6 на 6 квадратов вы хотите разместить небоскреб в каждом квадрате с некоторыми подсказками:

- Высота небоскребов от 1 до 6
- Никакие два небоскреба в ряду или столбце не могут иметь одинаковое количество этажей
- Подсказкой является количество небоскребов, которые вы видите в ряду. или колонна снаружи
- Более высокие небоскребы закрывают вид на расположенные за ними нижние небоскребы.

Сможете ли вы написать программу, которая решит каждую головоломку 6 на 6?

Пример:

Чтобы понять, как работает головоломка, это пример ряда с двумя подсказками. Слева видно 6 зданий, а с правой стороны только 1:

Есть только один способ размещения небоскребов. Слева направо все шесть зданий должны быть видны, и ни одно здание не может прятаться за другим зданием:

Пример головоломки 6 на 6 с решением:

Задача:

Напишите этот метод: solve_puzzle(clues)

Передайте подсказки в виде массива из 24 целых чисел. Подсказки находятся в массиве круглосуточно (по часовой стрелке). Показатель:

- Если подсказка недоступна, добавьте значение 0

- У каждой головоломки есть только одно возможное решение

- solve_puzzle возвращает массив 6x6 (6 строк, 6 столбцов). Первый индексатор предназначен для строки, второй индексатор - для столбца.

Понять проблему

В Launch School я узнал, что первым шагом в решении любого упражнения по кодированию является понимание проблемы. Для этого необходимо внимательно прочитать описание / подсказку и принять к сведению все требования и правила. Иногда это может показаться утомительным, поэтому я не всегда делаю это для каждой проблемы, даже если должен. Однако это определенно важно для более сложных проблем, подобных этой, и я не думаю, что смог бы решить ее, не предприняв сначала этого шага.

Я описал свой подход к решению этой проблемы в оставшейся части этого сообщения в блоге.

Определение ключевых терминов и изложение требований:

  • Высота небоскреба - целое число от 1 до 6.
  • Каждая строка и столбец должны содержать все числа от 1 до 6, поэтому не может быть одинаковых высот.
  • Входными данными является массив из 24 целых чисел, называемый clues, который передается методу solve_puzzle.
  • clue - это количество небоскребов, которые можно увидеть из ряда или столбца снаружи, по прямой линии, начинающейся от края сетки 6x6, смежной с этим clue. Подсказка - это точное число, поэтому количество видимых небоскребов должно быть точно равно подсказке, а не больше или меньше.
  • Небоскребы, расположенные выше, будут закрывать обзор нижним позади них. Например, 6 всегда будет блокировать каждый небоскреб за ним.
  • Каждая подсказка размещается вокруг сетки 6x6 по часовой стрелке по индексу появления в массиве clues, начиная с номера с индексом 0 над левым верхним квадратом и заканчивая номером с индексом 23 слева от верхнего левого угла. квадрат. (См. Картинку в подсказке.)
  • Неизвестные подсказки представлены в массиве clues как целое число 0.
  • Результатом будет двумерный массив массивов, содержащий 6 строк и 6 столбцов.
  • У каждого набора подсказок может быть только одно возможное решение.
  • Метод solve_puzzle должен уметь решать до 20 головоломок за 12 секунд или меньше.

Чтобы мне было легче понять и написать о чем, я начал использовать некоторые из моих собственных терминов для описания определенных аспектов проблемы:

  • grid или _15 _ = ›весь массив 6x6, содержащий 6 горизонтальных строк и 6 вертикальных столбцов.
  • line = ›строка или столбец сетки / доски (всего 12 строк).
  • _17 _ = ›отдельный элемент сетки или линии, который может содержать небоскреб (6 квадратов на линию, всего 36 квадратов).
  • sky = ›высота небоскреба, назначенного квадрату (по одному на квадрат).
  • nopes = ›набор высот небоскреба, который приведет к неверному решению, если будет назначен квадрату (в конечном итоге 5 на квадрат) (более подробно я объясню позже).

Решение проблемы вручную:

Сначала я сделал быструю попытку решить эту проблему с помощью грубой силы, что было не очень хорошей идеей, потому что я еще недостаточно хорошо разбирался в проблеме, даже после того, как изложил требования, которые я перечислил выше. Мое решение работало только с наборами подсказок без каких-либо неизвестных значений и было далеко не достаточно быстрым, чтобы соответствовать требованиям ограничения по времени. Я понял, что мне нужно потратить больше времени, чтобы разобраться в проблеме, поэтому решил решить ее вручную. Я не был уверен, что это можно будет решить без помощи компьютера, но я знал, что грубая сила не сработает, поэтому я решил, что, по крайней мере, попробую сделать это вручную в качестве следующего шага.

Сначала я нарисовал сетку 6х6 на листе бумаги. (У меня ужасный почерк, поэтому я собираюсь использовать несколько компьютерных изображений, чтобы представить каждый шаг, который я предпринял, чтобы нарисовать его. Мои навыки редактирования изображений тоже не так хороши, поэтому я прошу прощения за беспорядок.)

Хотя я думал, что набор подсказок без каких-либо неизвестных значений будет проще (на самом деле это оказалось сложнее), я решил начать с вариации набора подсказок, показанных в подсказке к упражнению:

clues = [ 0, 0, 0, 2, 2, 0,
          0, 0, 0, 6, 3, 0,
          0, 4, 0, 0, 0, 0,
          4, 4, 0, 3, 0, 0 ]

Подсказка со значением 6 на самом деле лучшее, на что мы можем надеяться. Он сообщает нам, какой будет весь ряд, потому что существует только одна допустимая строка, в которой можно увидеть все 6 небоскребов:

Другие подсказки не так полезны. Существует огромное количество возможных действительных строк, которые могли бы удовлетворить требованиям этих подсказок. Однако есть некоторые числа, которые, как мы можем знать наверняка, никогда не могут быть возможным значением высоты небоскреба на основе определенных подсказок, комбинации определенных подсказок или skys (высоты небоскребов), которые уже заполнены. Я буду называть эти недопустимые значения nopes.

Следующим моим шагом было перебрать все подсказки и составить таблицу, содержащую неточности и небеса для всех возможных подсказок или комбинаций подсказок. Это общие правила, которые можно успешно применять в любой ситуации; они не относятся к конкретному набору ключей. Любые закрашенные небеса были определены исключительно с использованием значений подсказок и неточностей.

Наличие набора конкретных правил, подобных этому, позволяет нам надежно вводить значение nope или sky только тогда, когда мы абсолютно уверены, что это правильное значение. Это сводит к минимуму вероятность ошибки и необходимости отступить. Использование этих правил, а также других техник, которые я объясню позже, позволит вам решить это упражнение без каких-либо догадок или грубой силы.

Вот таблица (прошу прощения за свой ужасный почерк; дайте мне знать, если вы хотите, чтобы я обновил ее с помощью компьютерной версии):

Здесь каждая строка представляет собой отдельную изолированную строку (строку / столбец), которая не зависит от остальной части таблицы. Подсказки находятся слева и справа в каждом ряду. Маленькие числа - нет. Большие числа в квадратах - это небеса, которые я смог заполнить, основываясь только на показанных здесь подсказках и неточностях. В верхних 6 строках есть одна известная подсказка слева и одна неизвестная подсказка (0) справа. В нижних рядах есть две известные подсказки, по одной с каждой стороны.

В этой таблице представлены все возможные комбинации подсказок, хотя иногда может потребоваться прочитать строку в обратном порядке, например, столбец 5 на изображении ниже, который необходимо читать снизу вверх, если вы вводите значения на основе таблица выше.

Давайте воспользуемся таблицей, приведенной выше, чтобы заполнить все квадраты, как можно больше:

(Я буду называть позиции квадратов, строк и столбцов числами от 1 до 6, а не от 0 до 5, как в массиве Ruby, чтобы упростить визуализацию. Они пронумерованы в порядке слева до справа для строк и сверху вниз для столбцов.) Нет - маленькие красные числа, а небеса - большие синие / белые числа.

Я смог заполнить одно небо на основе правил, а также довольно много нет. Я обычно даже заполняю пробелы для квадратов, в которых уже залито небо, что помогает мне лучше отслеживать все. Каждый раз, когда я заполняю небо, я обязательно добавляю нету со значением этого неба к каждому квадрату в строке и столбце этого неба, что в данном случае является нету со значением 6. Строка 4-3 подсказок (пятая строка) уже имела 6, включенную в каждый из квадратов, но я смог добавить 6 к нету квадратов 2-0 столбца подсказок (четвертый столбец). Это позволяет мне знать, что не может быть 6 ни в одном из квадратов ни в четвертой позиции любой строки, ни в пятой позиции любого столбца.

Других квадратов с пятью нету нет, поэтому мы не сможем заполнить больше неба, используя эту стратегию. Как вы думаете, каким должен быть наш следующий шаг?

Несмотря на то, что я решаю эту головоломку во второй раз прямо сейчас, мне потребовалось несколько минут, чтобы понять, каким должен быть следующий шаг. Сначала я начал пытаться получить представление о подсказках, но, поскольку их не так много, я понял, что будет намного легче смотреть на неточности. Несмотря на то, что мы уже заполнили небеса всех квадратов, содержащих пять нетов, мы все еще можем использовать их, чтобы определить следующее небо, которое мы можем заполнить, глядя на нету каждого line (строки / столбца) в целом:

Новые небеса и nopes имеют более темный оттенок синего. Я смог заполнить два неба, 5 и 6, посмотрев на набор нетов в пятом и шестом рядах соответственно. Если в строке (строке / столбце) есть пять квадратов, которые имеют одно значение nope, мы можем точно знать, что значение неба для оставшегося квадрата должно быть этим значением nope. В строке №5 нет значения со значением 5 в каждом квадрате (всего пять квадратов), за исключением третьего квадрата, поэтому мы знаем, что третий квадрат должен иметь значение неба 5. То же самое относится к 6 в шестой позиции строки №6 (нижний правый квадрат). Как и раньше, мы должны заполнить пробелы в строках, содержащих два квадрата, для которых мы только что залили небо.

После заполнения любых новых значений nope всегда лучше еще раз проверять любые квадраты, содержащие в общей сложности пять различных значений nope, а также любые строки с пятью одинаковыми значениями nope:

Увидев, что есть пять отклонений со значением 5 в строке №6, я смог заполнить одно небо значением 5 в четвертой позиции этой строки (зеленый), а также соответствующие сообщения в столбце № 4 и 5 ряд. Это позволило мне заполнить небо размером 4 во второй позиции того же ряда.

Теперь мы можем снова взглянуть на подсказки и попытаться увидеть, есть ли какие-либо возможные неточности, которые мы можем добавить к любому из квадратов, основываясь как на подсказке (-ах), так и на уже заполненных небесах.

Ниже я перечислил некоторые правила, которые я придумал, чтобы помочь определить, какие «нету» и «небеса» куда пойдут. Эти правила ни в коем случае не являются исчерпывающими, но они должны дать вам общее представление о том, как подойти к этой проблеме. Я объясню более подробно и приведу примеры по мере того, как мы работаем над этой проблемой, поэтому сейчас было бы неплохо просто просмотреть эти правила и вернуться к ним по мере необходимости.

Вот несколько общих правил для начала:

  • Напоминание: подсказка - это точное количество неба, которое видно со стороны ряда / столбца (линии), примыкающего к этой подсказке. Не может быть более или менее видимого неба, чем указано в подсказке.
  • Неизвестная подсказка означает, что количество видимых небес может быть любым числом от 1 до 6.
  • Небо с более высоким значением высоты (мы будем называть высоту «небом» или «значением неба») всегда будет блокировать любые следующие за ним небеса, которые имеют более низкое значение неба.
  • Первое небо в любой строке всегда будет видно с этой стороны. Поэтому первый квадрат всегда увеличивает общее количество видимых небес на 1, независимо от его значения неба.
  • Ничто не может заблокировать небо со значением 6. Следовательно, небеса, которые идут после 6 в строке, не видны. Кроме того, 6 всегда отображается в любой позиции строки, независимо от того, что находится перед ним.
  • Один из полезных способов сузить круг вопросов, которые могут быть заполнены для определенного квадрата, - это посмотреть на подсказки и уже заполненные значения неба для линии, содержащей этот квадрат, и посмотреть, можно ли использовать это, чтобы определить, начальные значения неба квадратов его линии должны быть в возрастающей или убывающей последовательности. Если это так, вы можете иногда использовать эти знания, чтобы заполнить «нет» или «небеса» в одном или нескольких квадратах этой линии (я объясню это подробнее позже).

Вот несколько более конкретных правил, которые также могут помочь:

  • Линия с подсказкой 2 никогда не может иметь первые три квадрата в виде возрастающей последовательности (например: 4, 5, 6). В противном случае вы могли бы увидеть более двух небес.
  • Если мы знаем значение неба в определенных линиях, мы можем определить, будет ли эта подсказка с этого момента бесполезной для нас. Например, линия с подсказкой 2 и небо 6 во втором квадрате может иметь действительное первое квадратное небо с любым числом от 1 до 5, поэтому эту подсказку больше нельзя использовать для определения чего-либо. Может быть полезно вычеркнуть бесполезную подсказку, чтобы мы знали, что мы должны пропустить ее, когда мы пытаемся найти наше следующее небо или значение нет.
  • Вот список, который я составил из некоторых конкретных правил, которым всегда можно следовать, если вы знаете комбинацию определенных значений подсказки и неба. (<-n-> указывает, что значение неба n может быть в квадрате в любом месте вокруг него, и правило будет по-прежнему применяться):

Теперь давайте посмотрим, сможем ли мы вычеркнуть какие-либо бесполезные подсказки или ответить на любые возражения на основе следующих правил:

Используя правила, я смог увидеть, что в пятой строке два начальных значения с обеих сторон должны быть возрастающей последовательностью (голубая стрелка вверх). Поэтому я знал, что квадраты во второй и пятой позициях никогда не могут быть 1, поэтому я добавил число 1 к вершинам этих двух квадратов. (A 5,6 находится в середине этой строки, что означает, что эти две подсказки больше не связаны напрямую. Я использовал правила для них по отдельности, и они оба просто увеличивались; просто потому, что одно увеличивается, не означает, что другой должен увеличиваться в свою очередь.)

Как вы думаете, какой шаг нам следует сделать дальше?

Как обычно, рекомендуется проверить, существуют ли какие-либо «наборы из пяти отклонений» (с этого момента я буду использовать этот термин для обозначения обоих квадратов с пятью полными отклонениями, а также строк с пятью одинаковыми нет). К сожалению, здесь нет никаких наборов из пяти «нет», поэтому давайте посмотрим, сможем ли мы заполнить какие-либо «нет» или «небеса», используя список правил, который мы рассмотрели выше:

Используя правило, которое гласит, что число 6 всегда будет блокировать все, что следует за ним, и увидев, что подсказка внизу столбца №5 - 4, я смог определить, что квадрат, расположенный в строке №3 столбца №5, может никогда не иметь значение неба 6, потому что в противном случае всего было бы меньше четырех видимых небес. Это связано с тем, что небо на 2 в позиции [5, 5] всегда будет заблокировано квадратом с более высоким небом, поскольку первые две строки должны иметь по крайней мере одно значение неба больше, чем 2. (Для краткости с этого момента я буду ссылаться на квадратные позиции в формате [row_number, column_number].)

Чтобы выяснить, что заполнять дальше, мы должны снова выполнить наш обычный шаг проверки наборов из пяти отклонений:

Как вы можете видеть, я проверил наборы из пяти отклонений и нашел одно в строке №1, а другое в строке №3, так что я смог заполнить два неба 6 в позициях [1, 2] и [3, 3]. Это дает нам в общей сложности шесть небес со значением 6, что позволяет нам знать, что каждое оставшееся небо должно иметь значение от 1 до 5. Возможно, вам будет полезно записать эту дополнительную информацию, но если вы следили и заполняли соответствующие отметки на каждом квадрате каждый раз, когда заполняете небо, в этом нет необходимости. Я также добавил стрелку вверх рядом с подсказкой в ​​левой части строки №3, чтобы обозначить, что первые два значения неба должны быть возрастающей последовательностью.

Вам может быть интересно, почему я поставил зеленые кресты на четырех уликах. Я сделал это, чтобы показать, что эти подсказки больше не говорят нам ничего ценного, потому что сторона линии, на которой они находятся, всегда будет действительной, независимо от того, какими значениями неба мы в конечном итоге заполняем квадраты. Например, в строке №5 всегда будут видны четыре неба, независимо от того, какое небо находится в квадрате в позиции [5, 2]. Вычеркивать подсказки не обязательно, но я предпочитаю это делать, потому что это позволяет мне сэкономить время позже, поскольку я знаю, что мне больше не придется проверять эту сторону линии на основе подсказки. (На самом деле я должен был сделать это некоторое время назад, каждый раз, когда у меня было достаточно неясностей и неясностей, чтобы знать, что подсказка будет бесполезной, но я забыл об этом до сих пор. Это скорее способ сэкономить время, чем что-то, что необходимо для решения проблемы, поэтому не беспокойтесь об этом слишком сильно.)

Вы, наверное, уже устали видеть, как я повторяю одни и те же шаги снова и снова, поэтому я перестану упоминать их так явно. Если у вас возникнут какие-либо трудности, пожалуйста, дайте мне знать, оставив комментарий ниже, и я дополню его более подробным объяснением.

Следующий может быть немного сложным, но если мы внимательно оглянемся на правила, у нас не должно возникнуть никаких проблем:

Я смог залить небо значением 4 в позиции [1, 4], увидев, что столбец № 4 имеет как подсказку 2 вверху, так и небо 6 в пятой позиции сверху (позиция [5, 4]) . Если бы небо 4 было размещено где-нибудь, кроме первой позиции, было бы видно более двух небес, что нарушило бы требования подсказки. Я вычеркнул подсказку в верхней части столбца №4, потому что, поскольку 1 и 2 являются единственными возможными значениями неба, оставшимися в этом столбце, размещение их в любом порядке в двух оставшихся квадратах будет действительным, поэтому эта подсказка больше не полезна нам. Теперь у нас осталось только три полезных подсказки.

Здесь может быть несколько возможных способов продолжения (как и в предыдущих примерах), но первое, что я замечаю, что мы можем что-то сделать, это строка №3:

Я залил небеса значениями 2 и 3 в первых двух квадратах строки №3, потому что я знал, что последовательность должна увеличиваться, и единственные возможные небеса во втором квадрате, которые удовлетворяют этому условию, - это 2 и 3. Глядя на нету, мы знаем, что первый квадрат не может иметь значение неба 1, а это означает, что второй квадрат не может быть 2, оставляя 2, 3 как единственную допустимую оставшуюся возможную последовательность.

Теперь мы в ударе! Следующие должны быть довольно простыми:

Вау, это оказалось даже проще, чем я ожидал! Я всегда немного волнуюсь в конце, потому что, если бы я где-то допустил ошибку, мне пришлось бы вернуться и все переделать. К счастью, на этот раз все прошло довольно гладко. Я смог заполнить все оставшиеся значения неба на основе одних только наборов из пяти небес. Обычно я заполнял бы возражения по ходу дела, но, поскольку квадратов больше не осталось, на этот раз в этом даже не было необходимости. Я определенно рекомендую всегда отвечать на возражения, так как вы никогда не знаете, действительно ли вы в конце или нет. Может быть легко забыть, какое небо вы только что заполнили, особенно если вы не кодируете цветом каждое новое добавление значений неба и nope, как мы это делали здесь.

Таким образом, это должно позаботиться о первом шаге в решении сложного упражнения по кодированию: понимании проблемы. На этом этапе вы можете перейти к следующим шагам, которые включают в себя написание тестовых примеров (Codewars позаботится об этой части за вас), принятие решения о том, какие структуры данных использовать, создание алгоритма и его перевод. все кодировать. Однако того, что мы здесь сделали, может быть недостаточно - мне на самом деле нужно было решить еще одну головоломку вручную, чтобы действительно все понять. Вот набор подсказок, которые я использовал для решения второй головоломки:

clues = [ 3, 2, 2, 3, 2, 1,  
          1, 2, 3, 3, 2, 2, 
          5, 1, 2, 2, 4, 3,             
          3, 2, 1, 2, 2, 4 ]

Нет неизвестных подсказок (нулей), поэтому кажется, что это должно быть проще, чем то, что мы только что сделали, но на самом деле это заняло у меня гораздо больше времени, вероятно, потому что не было никаких подсказок со значением 6. Тем не менее, это было довольно весело, поэтому я определенно рекомендую попробовать, если вы готовы принять вызов или думаете о решении этого ката на Codewars.

Я планировал также написать о процессе, через который я прошел, чтобы применить к этому упражнению остальные методы решения проблем, которые я изучил в Школе запуска, но это сообщение в блоге уже заняло у меня гораздо больше времени, чем я ожидал (более тринадцати часов до сих пор!), и читать тоже стало довольно долго. Я не уверен, что это действительно интересно кому-то еще, так что на этом я остановлюсь на этом.

Оставьте мне комментарий ниже, чтобы сообщить, хотите ли вы узнать об этом больше, и я постараюсь написать следующую статью, которая будет включать мой реальный код Ruby. Также не стесняйтесь оставлять комментарии с любыми мыслями, вопросами, предложениями, альтернативными подходами, которые вы придумали, или ошибками, которые вы, возможно, заметили, и я сделаю все возможное, чтобы ответить. Всем, кто добрался до конца, спасибо за чтение, и я надеюсь, вам понравилось!