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

    Это как бы ответ на статью lxsmkv «Задача о переправе». Наиболее запоминающаяся часть той статьи — это огромная (в сопоставлении с сложностью задачи) таблица, в которой выражена модель задачи.

    Попробуем придумать что-то попроще.

    1. Условие


    У нас есть волк, коза и капуста. Их надо переправить на другой берег. Переправляет человек (перевозчик). Сложность в том, что волк съедает козу, а коза — капусту, если рядом нет человека. Кроме того, переправлять можно только по одному (в лодке только одно место для груза).

    2. Идея решения


    Теперь оцифруем задачу, то есть представим её в виде чисел и операций с ними. Мы должны описать распределения волка, козы и капусты по берегам (конфигурации) и действия с ними. Итак, у нас есть словесная формулировка условия задачи. Я хочу в модели совместить наглядность картинки с абстрактностью числа. То есть модель должна быть наглядна, чтобы быть понятной человеку, и абстрактной, чтобы быть понятной машине.

    Я хочу её представить в таком виде, чтобы она была легко понятна мне и чтобы она была легко программируема.

    Легче всего воспринимаются изображения (с одного взгляда). Легче всего программируются действия с числами. Таким образом, я хочу, чтобы моя модель совмещала в себе свойства как изображения, так и числа. Причём первично число, так как в перспективе предполагается программирование. То есть нам нужно не просто какое-то число, а такое, визуальный образ которого будет отражать задачу (и ход её решения). Изобразим условие задачи в виде картинки. Действие «съедает» изобразим стрелкой.

    image

    Кто-то увидит в этой картинке пищевую цепочку, кто-то ориентированный граф. Но всё это не имеет значения. Для нас важно, что некоторые пары запрещены. И какие именно пары, определяется их положением на картинке.

    image

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

    Теперь нам надо показать распределение участников по берегам.

    image

    Нетрудно заметить, что информация, содержащаяся в правой части схемы, дублируется в левой части. Действительно, участники не исчезают из задачи и не появляются вновь. Каждый из них находится или на левом, или на правом берегу. Следовательно, достаточно одной правой части схемы.

    image

    В такой схеме содержится вся информация о любом распределении объектов, возникающем в ходе решения задачи. Что это за объект определяется местом (позицией), занимаемым им на схеме, а на каком он берегу определяется тем, занято место или пусто.

    Теперь возьмёмся за числа. Все современные системы счисления позиционные, то есть функция цифры в числе определяется её положением в этом числе. То есть разрядом. И каждый разряд может иметь несколько значений.

    Теперь с каждым разрядом свяжем объект задачи. А значений каждого разряда нам понадобится два. Пусть первый разряд – это капуста, второй – коза, а третий – волк. В каждом разряде нам понадобятся два значения: 1 – стартовый берег, 0 – финишный берег.

    Получается, что для описания любой конфигуации нам нужно трёхзначное двоичное число. Например, 111 – стартовая конфигуация, 000 – финишная.

    То же самое можно сказать и о кодировании хода числом. Тоже необходимо трёхзначное двоичное число, в котором разряд – это участник, а значение разряда кодирует действие (1 – перевезти, 0 – нет).

    Остаётся описать переход от одной конфигурации к другой. Для этого надо найти математическую операцию о. Тогда этот переход можно описать так:

    К1 о Д = К2

    Что же это за операция? Рассмотрим один из разрядов конфигурации и тот же разряд действия. Если в этом разряде действия единица, то в разряде конфигурации единица должна смениться на нуль и наоборот. Если в разряде действия нуль, то разряд конфигурации остаётся без изменения.

    Можно составить такую таблицу:
    К Д К о Д
    1 1 0
    1 0 1
    0 1 1
    0 0 0

    Очевидно, что это xor. То есть разряды конфигурации К инвертируются по маске Д.

    В конечном итоге мы должны конфигурацию 111 инвертировать по маске 111:

    111 xor 111 = 000

    Ну вот, собственно темообразующая часть статьи на этом закончена – идея найдена. Остальное – следствия.

    3. Правила


    В предыдущей части сформулирована идея, на которой может быть построена цифровая модель задачи. Однако в задаче есть ещё и правила ходов. Сформулировав их с использованнием найденной идеи, мы и получим модель задачи и её решения.

    Правила – это запреты, то есть они определяют, что нельзя делать. В нашем случае запреты можно преобразовать в разрешения. Действительно, для кодирования позиций (конфигуаций) и ходов мы можем использовать трёхзначные двоичные числа:

    1. Исходный список конфигураций (ходов): 000, 100, 010, 001, 110, 101, 011, 111.
    2. Исходный список масок (действий) такой же: 000, 100, 010, 001, 110, 101, 011, 111.

    Запреты означают, что часть из этих чисел использовать нельзя. Следовательно, можно использовать только какие-то подмножества чисел из этих списков. Выясним, какие.
    Для этого сначала надо понять роль перевозчика в нашей модели.

    Пока он на берегу, всё спокойно, никто никого не ест. Но как только он уплывает на другой берег, волк съедает козу или коза капусту. Следовательно, допусимость пары проверяется в конце хода (или после хода) на том берегу, с которого делается ход.

    Следовательно, нам в числах, кодирующих конфигуации и ходы, надо закодировать ещё и перевозчика. Для этого добавим ещё один разряд. Пусть единица в этом разряде кодирует перевозчика на стартовом берегу, а нуль – на финишном. Причём очевидно, что у числа, кодирующего ход, в старшем (четвёртом) разряде всегда 1. То есть не бывает ходов без участия перевозчика. Тогда исходые списки чисел станут такими:

    1. Исходный список конфигураций: 1000, 1100, 1010, 1001, 1110, 1101, 1011, 1111, 0000, 0100, 0010, 0001, 0110, 0101, 0011, 0111.
    2. Исходный список масок: 1000, 1100, 1010, 1001, 1110, 1101, 1011, 1111.

    Теперь используем этот же принцип для кодирования разрешённости/запрещённости хода или конфигурации (позиции). Добавим ещё один разряд, пятый – 1 ход или конфигуация разрешены, 0 – запрещены.

    Сформируем теперь списки разрешённых ходов.

    Инвертировать можно только или один разряд, или ни одного (перевозить можно только одного пассажира или плыть порожняком). Следовательно, маски могут быть только 1000, 1100, 1010, 1001 (это список разрешённых ходов).

    Сформируем теперь списки разрешённых позиций.
    Запрещена исходная конфигурация 1111 (первый ход не может быть порожняком).
    Запрещаются единицы или нули в соседних разрядах (на берегу не могут быть пары волк–коза и коза–капуста).
    То есть запрещаются конфигурации 1111, 1110, 1011, 1001, 1100. Следовательно, разрешаются 1000, 1101 и 1010.

    После нечётного хода проверяется конфигурация единиц, а после чётного — нулей (единицы – это объекты на этом берегу, нули – на том; нечётный ход – переезд с этого берега на тот, чётный – с того на этот).

    Если мы хотим, чтобы игра заканчивалась и быстро, то надо ограничить количество ходов. Поэтому запретим повторение позиций.

    Это правило требует, чтобы позиция, из которой делается очередной ход, становилась запрещённой. То есть одна и та же позиция может быть разрешена, а может быть и запрещена. Следовательно, надо кодировать запрещённость/разрешённость позиции. Снова вводим дополнительный разряд – пятый: позиция разрешена – 1, позиция запрещена – 0.
    Очевидно, что код хода в этом разряде должен всегда содержать 0, потому что разрешённая позиция не запрещается автоматически, а только если в результате хода получается тоже допустимая позиция.

    Код исходной позиции сначала, естественно, содержит в пятом разряде единицу – она, раз мы в ней находимся, разрешена.

    Окончательно получается список допустимых позиций 11000, 11101, 11010 и список допустимых ходов 01000, 01100, 01010, 01001.

    4. Вычисление ходов.


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

    Аргументы этой функции:

     исхПоз – исходная позиция,
     списЗапрещПоз – список запрещённых позиций,
     списДопустХод – список допустимых ходов.

    Вернуть функция должна резПоз – рузультирующую позицию.

    Итак, функция вычислХод должна:

    для каждого элемента Х списка допустимых ходов списДопустХод
     вычислить резПоз = исхПоз xor Х
      для каждой позиции П из списЗапрещПоз
      если резПоз and П ≠ 0
       добавить резПоз xor 10000 к списЗапрещПоз
       вернуть резПоз

    5. Конец


    Ну вот, осталось спроектировать главную функцию, которая будет вызывать функцию вычислХод с нужными аргументами и складывать полученные результаты в какую-нибудь удобную структуру данных, из которой в конце концов можно будет вывести результат на экран в удобном для восприятия человеком виде. Ну и собственно написать код.

    На этом месте можно начинать мыслить, как программист. Желающие могут заняться этим в качестве домашнего задания.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 19

      +3

      Чтобы мыслить, как программист, сначала желательно научиться мыслить хотя бы чуть-чуть как математик.
      Вот пример: сейчас на https://www.codingame.com идёт контест: https://www.codingame.com/contests/mean-max. Один из ключевых моментов: освоить законы движения объектов с учётом сопротивления среды (трение), в условиях дискретного движения (по шагам/тикам). Можно просчитывать некоторое дерево вариантов движения с различными векторами ускорения — но это вариант не очень, т.к. процессорное время сильно ограничено. А можно состаить математическую модель и вывести ряд математических формул, описывающих данное движение в различных вариантах: один юнит (дестроер) должен просто достигнуть некоторой точки (разрушить танкер тараном), другой юнит (лутер) должен достигнуть этой же точки, но с нулевой скоростью в конце пути — задачка посложнее, третий юнит должен просто нарезать круги на максимально возможной скорости (генерировать ресурс "ярости", нужный для абилок) избегая столкновений (диаграмма Вороного в помощь? хотя можно и наоборот: преграждать дорогу вражеским лутерам, просчитывая траекторию их движения, но это уже детали выбора стратегии)… Да, несколько лет назад mail.ru group проводил контест "Russian AI cup", связанный с гоночной тематикой — там данная тема тоже рулила...

        0
        Да, несколько лет назад mail.ru group проводил контест «Russian AI cup», связанный с гоночной тематикой — там данная тема тоже рулила...

        Вот только тогда все кто был в топе пользовались перебором возможных стратегий, а не рассчётом одной оптимальной.
          0

          Ага, я тоже читал публикации топов на хабре :)
          Там не настолько жёсткие были ограничения по ЦП, поэтому можно было уделить больше внимания другим аспектам стратегии… Но тем интереснее сейчас влезать в codingame.com :)

          0
          Чтобы мыслить, как программист, сначала желательно научиться мыслить хотя бы чуть-чуть как математик.

          Вот и ответ на вопрос, почему программистам нужно ВУЗовское образование и математика в частности.

            0
            В котором в (абстрактный большой процент вузов) (абстрактный большой процент тем) нужной математики не дается, либо дается настолько отвратительно что она забывается сразу после сдачи экзамена ибо студенту никто не объясняет ни где ни как она применяется
            • UFO just landed and posted this here
          0
          Почему-то при решении задачи большинство оставляют козу с волком\капустой на другом берегу без присмотра крестьянина.
            +1
            Разве? Откуда статистика?
              0
              Студентов опрашивал. Интервьюеров озадачивал на собеседованиях (да, я слышал про репрезентативность выборки, но кроме личного опыта предложить ничего, увы, не могу).
                0
                Спасибо. У меня лично вообще никакой выборки. А знакомые решили её правильно.
            0

            Я не программист, но мне до этого очень далеко, интересно к кому я тогда вообще отношусь;-)

              +3

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


              Полагаю, порядок ходов должен быть такой?
              11111 — начальная позиция
              10101 — перевезли козу туда
              11101 — приехали обратно
              10001 — перевезли волка туда
              11011 — привезли козу обратно
              10010 — увезли капусту
              11010 — приехали обратно
              10000 — увезли козу


              При этом "допустимые позиции" — это
              11000, 11101, 11010. Явно не хватает 11011 (когда коза, капуста и перевозчик на стартовом берегу, никто никого не съест) или 11110, по выбору.


              На лицо баг в рассуждениях.

                0

                И ход рассуждений, и использования битов и даже примеры напоминают книгу к языку который был создан в МВТУ им. Баумана. Там в качестве задач рассматривались обработки очереди к парикмахеру, работа порта с танкерами и распиловка бревен. Фишка была в том, что этот язык был "заточен" под решения подобных задач. Книгу прочитал с удовольствием, а языком пользоваться не пришлось и названия не помню. Это было в конце 90-х.
                Мне рассказали что за решение оптимизационной задачи по распиловки бревен немцы создателю выплачивали вознаграждение.
                Может кто из выпускников Бауманки вспомнит об этом.

                  +4
                  Простите, где в этой статье мышление «не как у программиста»?
                    0
                    Задался тем же вопросом. Зашел почитать о логике мышления программистов, а увидел решение задачки. Мне кажется заголовок не подходящий посту.
                    +1

                    Я, конечно, извиняюсь, но если Вы читали комментарии к статье, на которую отвечаете, то не могли не заметить изящного решения Dr_Dash, а также скрипт vaniacer, которые делают именно то, для чего предназначены машины — автоматизируют решение задачи, снижая нагрузку на человека. Конечно, полезен любой опыт, но иногда лишь как пример "как не надо". Приведенное решение не экономит ни время, ни ресурсы, и притом даже не упрощает его поддержку/сопровождение по сравнению с указанными выше.

                      +1
                      Ради простой задачи городить такое? А как же главный принцип программиста — не усложняй?
                        0
                        Я может глупый человек, но мне кажется, что основная сложность этой задачи это понять, что с другого берега можно вернуть один/несколько объектов назад. Причем, что в первой, что во второй статье, я не нашел ни математического, ни программистского, ни философского способа до этого дойти.
                        Если озвучить данную подсказку в самом начале то задача решается тупым перебором. Благо дело «летальных» исходов всего два: коза и капуста, коза и волк.
                          0
                          Да, неудачная статья получилась — отрывок из верновика дедовского курсовика. Что-ж, буду тренироваться.

                          Only users with full accounts can post comments. Log in, please.