Задача с водой программирование

Задача про воду, накапливающуюся между стенами

Эту задачу задавали на собеседовании в Twitter.

Рассмотрим следующую картинку:

На этой картинке изображены стены различной высоты в некотором плоском мире. Картинка представлена массивом целых чисел, где индекс — это точка на оси X, а значение каждого индекса — это высота стены (значение по оси Y). Картинке выше соответствует массив [2, 5, 1, 2, 3, 4, 7, 7, 6] .

Теперь представьте, что начался дождь, который не прекращается и поливает стены сверху равномерным потоком. Сколько воды соберется в «лужах» между стенами?

Единицей объема воды считаем квадратный блок 1×1. На картинке выше всё, что расположено слева от точки 1, выплескивается. Вода справа от точки 7 также прольется. У нас остается лужа между 1 и 6 — таким образом, получившийся объем воды равен 10.

Первый вариант решения (неверный)

Можно предположить, что нужно найти локальные максимумы и подсчитать пространство между ними, заполненное водой. Алгоритм будет довольно простой, но ответ на самом деле некорректен.

Решение будет таким:

Хотя на самом деле должно быть таким:

Правильный вариант решения

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

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

Решение в приведенном ниже коде работает в один проход, избегая поиска максимума проходом двух «указателей» навстречу друг другу с противоположных концов массива. Если наибольшее значение, найденное слева от левого указателя меньше, чем наибольшее значение найденное справа от правого указателя, то мы сдвигаем левый указатель на один индекс вправо. В противном случае, двигаем правый указатель на один индекс влево. Повторяем до тех пор, пока два указателя не пересекутся. (На словах звучит запутанно, код на самом деле очень простой).

Вариант реализации на Java

Для тех, кто предпочитает Gist.

Хинт для программистов: если зарегистрируетесь на соревнования Huawei Cup, то бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.

Перейти к регистрации

Источник

3 логические задачи для настоящего программиста

Компании любят проверять молодых специалистов на различные логические задачи. Мы подобрали три интересных задачи, которые заставят вас задуматься.

№1 – Как на счёт кофе?

Предположительная ситуация: в вашем офисе поставили 3 автомата, которые делают разнообразные напитки. Первый автомат изготавливает кофе, второй делает чай, а третий способен давать один из перечисленных напитков, но не предоставляет право выбора. Чтобы воспользоваться любым аппаратом требуется кинуть 1 монету. На автоматах присутствуют специальные наклейки, обозначающие тип выдаваемого напитка. Одна проблема – по техническим причинам завод перепутал все обозначения. Каждый автомат имеет неправильную наклейку. Вопрос, сколько потребуется монет, чтобы правильно определить тип автоматов?

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

1. Подходим к аппарату с пометкой «кофе-чай» и бросаем таксу в виде монетки. Помним, что все наклейки неправильные, соответственно здесь либо чай, либо кофе.
2. Предположим, что аппарат выдал чай, соответственно модель с надписью кофе не может выдавать кофе (все наклейки неправильные) и чай, так как ранее уже был найден аппарат с ним.
3. При помощи исключения возможных вариантов несложно определить, где выдаётся кофе.

Итог: 1 монеты достаточно.

#2 – Фальшивые монеты

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

Перед нами 12 монет, среди них 11 штук оригинальные, а одна из них фальшивая. Поддельная копия монеты имеет отличительный вес. Суть задания необходимо определить фальшивую монету за минимальное количество взвешиваний. В ходе процедуры применяются чашечные весы.

Ответ: Элементарная задача, но все равно не редко появляется путаница, половина отвечает 1 или 2. Для определения поддельной копии следует провести 3 взвешивания, так как у нас не получится узнать какая конкретно монета является поддельной за меньшее количество попыток. Соответственно, большая часть монет должна быть с одинаковым весом, так как они настоящие, а третья монета, из последнего взвешивания, будет поддельной.

Итог: потребуется 3 взвешивания.

#3 – Вода в бочке

Перед вами пустая и герметичная бочка. Задача заключается в том, чтобы наполнить ёмкость водой, а сложность – тара должна быть заполнена ровно на 50% . Важное условие! Использовать длинные предметы вроде палки и подобного запрещено.

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

1. Берём шланг и наливаем в бочку побольше воды, не обязательно заполнять полностью, но важно получить уверенность, что воды больше 50%.
2. Бочку следует постепенно наклонять до получения угла 45° по отношению к ровной поверхности. Все излишки воды просто вытекут, а необходимый объём останется.

Источник

Задача на переливания (сосуды). Оптимизация поиска

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

Задача: даны 2 сосуда, имеющие целочисленные объемы V1 и V2.
При этом V1 и V2 не имеют общих делителей, отличных от 1.
Имеется также «безразмерный» пруд, из которого можно черпать воду сосудами,
и в который можно выливать воду из сосудов. Определить последовательность переливаний,
необходимую для получения заданного (целочисленного) количества воды в одном из сосудов.

Подход к решению

Математически эта задача давно разобрана и доказано, что если V1 и V2 — взаимно-простые числа, то задача имеет решение.

Общий подход к решению такого рода задач на языке Prolog сводится к обходу пространства состояний задачи в ширину, либо в глубину. Под состоянием в данном случае имеется ввиду пара (Jar1, Jar2), содержащая текущее количество воды в сосудах. При этом, пространство состояний имеет древовидную структуру (можно назвать его деревом поиска решений).

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

На языке Prolog (я использую SWI Prolog) это может быть записано следующим образом:

Тут solve — функция, которую вызывает пользователь, передавая ей данные задачи (объемы кувшинов, их начальное содержимое и цель, которую надо достичь) для получения результата — набора действий (Actions). Эта функция вызывает функцию поиска в ширину (bsf), передавая ей данные в более для обработки удобном формате, а также начальное состояние. Состояние описывается содержимым кувшинов и набором действий, которые привели к этому: state(jars(A, B), actions([init])). В поиске в ширину состояния выстраиваются в очередь (добавление происходит в один конец, а выбор для обработки — с другого конца), для этого мы используем список, изначально содержащий единственный элемент.

Функция bfs проверяет не достигнуто ли конечное состояние (не оказалось ли в одном из кувшинов искомое количество литров). Если не достигнуто — выбирается первое состояние очереди и функцией genegate_states (показанной ниже) формируется новый набор состояний, которые добавляются в конец с помощью встроенной функции append. Новая очередь состояний передается на вход bfs рекурсивно.

Осталось разобрать генерацию состояний, код объемный, но очень простой, поэтому пояснения дам частично. Варианты перехода из текущего состояния опишем недетерминированным предикатом next_state. Недетерминированный — значит возвращает несколько решений, чтобы собрать их всех используем встроенный предикат findall:

Собственно next_state описывает все условия переходов, заданные в задаче, приведу его часть:

Т.е. если A не равно нулю (в первом кувшине что-от есть) — то следующим состоянием может быть такое, где A равно нулю (его содержимое можно вылить). Если B не полный — то его можно долить из пруда (зачерпнуть) и следующим состоянием будет такое, где он полный.

Оптимизация поиска решения

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

приводящие к уже рассмотренным состояниям, например:

На самом деле, возвращаться в состояние, которое было рассмотрено выше нет смысла. Если мы посмотрим на функцию поиска кратчайшего пути в графе (поиск в ширину) — то заметим, что все посещенные вершины могут помещаться в список и при переходе в следующее состояние (по дуге графа, edge) необходимо выполнить поиск нового узла (конца дуги) в списке посещенных:

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

Оператор \+ соответствует логическому НЕ, в Turbo/Visual Prolog соответствующая строка должна быть записана как NOT(jars(A, B)) . Предикат jars должен быть объявлен динамическим, а generate_states должен использовать next_unique_state вместо next_state. Перед началом работы базу данных необходимо очистить вызовом retractall (ведь запись в нее — это побочный эффект) и в этом она «хуже» чем список посещенных узлов. С другой стороны записи базы данных доступны в любой точке программы (к ней имеется глобальная точка доступа) и нам это удобно.

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

Итак, исходный код задачи целиком:

Другие оптимизации

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

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

Разберем решение этой же задачи на Visual Prolog.
Формулировка задачи:

Имеются три бочонка вместимостью 6 вёдер, 3 ведра и 7 вёдер.

В первом и третьем содержится соответственно 4 и 6 ведёр кваса. Требуется, пользуясь только этими тремя бочонками, разделить квас поровну.

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

Решение 1: (такой подход описан выше)

Опишем типы данных — нам потребуется кувшин ( jar ) имеющий емкость и текущее количество жидкости. Таких кувшина три — дальше нам будет удобно использовать список кувшинов.

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

В задаче описаны правила переливания, их нам надо запрограммировать. Возьмем только два кувшина, переливать будем из первого во второй:
jar(A, AVol), jar(B, BVol)

очевидно, мы может перелить не более чем A литров. Кроме того, в кувшин B не войдет более BVol — B литров. Запрограммировать такую логику переливания можно следующим образом:

Первые два аргумента функции — исходные кувшины, вторые два аргумента — их новые состояния (после переливания). Очень легко убедиться что эта функция работает верно.

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

Теперь, имея такую функцию легко запрограммировать переливания между тремя кувшинами:

Эта функция вызывает описанную выше функцию для каждой из пар — (a,b), (b,c), (a,c) . Кувшин, не участвующий в переливании остается неизменным.

Функция transfer берет 3 кувшина и возвращает нам следующие их состояния, так например:

transfer([jar(4, 6), jar(0, 3), jar(6, 7)], Next).

Вернет нам 3 возможных следующих состояний:

Теперь будем делать следующее — вызовем эту функцию, получим новое состояние, вызовем ее еще раз, … и еще много много раз. До тех пор, пока не придем к конечному состоянию. На языке Пролог это запишется так:

Функция состоит из двух правил — первое проверяет что мы оказались в конечном состоянии (в двух кувшинах одинаковый объем, а в третьем пусто). Если мы попали в конечное состоения — тор добавим его в путь (единственным элементом списка).

Второе правило генерирует следующее состояние с помощью предиката transfer и вызывает рекурсивно поиск из нового состояния. При этом этом к найденному пути ( Tail ) дописывается текущее состояние — получается [Jars|Tail] .

Такой перебор работает, но зацикливается, ведь мы можем вечно переливать: A→B, B→A, A→B, B→A, … Поэтой нашей программе надо хранить состояния в которых она уже находилась (чтобы не выполнять из них поиск повторно). Хранить все посещенные состояния будем в локальной базе данных. Опишем тип фактов:

Перед тем как выполнять из нового состосния рекурсивный поиск пути — проверять что оно действиетнльно новое (раньше в базе его не было):

Добавились строки 7 и 9, выполняющие вставку записи в базу и проверку отсутствия записи в базе соответственно.

Запустим поиск решения:

Получим «No Solution» .
Чтобы убедиться что программа перебирает решения перед нашим предикатом solve добавим еще одно правило:

Оно выводит текущее состояние кувшинов на экран и завершается неудачей ( fail ), что приводит к переходу к следующему правилу, однако на экране остается нужное нам состояние.

Запустим поиск еще раз — получим:

Программа перебирает все возможные состояния, но не может прийти к нужномук нам конечному.

Решение 2 (переливание из одного сосуда сразу в несколько других)

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

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

jar_d = jar(real, real)

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

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

Эта функция выполняет переливания из первого кувшина в два остальных. При этом, она может перелить не более чем A/2 литров, а также не более чем могут принять кувшины B и C (для этого ищется минимум). Переливание выполняется если мы льем более 100 грамм ( Delta > 0.1 ) — цифру можно уменьшать, если она будет меньше или равна нулю — программа будет зацикливаться (как это происходило в первом решении).

Изменилоась также функция генерации следующего состояния, теперь помимо transfer_between она вызывает transfer_a2bc , при этом на вход новой функции подаются все вомзожные комбинации из трех кувшинов (строки 9-14):

Если мы в функции solve запишем требование «во всех кувшинах должен быть один уровень жадкости» — программа не найдет решения. Это очевидно, т. к. средний увовень при заданных в условии параметрах равен 3.3, а средний кувшин имеет емкость равную трем. Зададим требование, что в кувшинах A и C по 5 литров, а в В — ноль:

Программа успешно найдет и выведет решение:
Path=[[jar(4,6),jar(0,3),jar(6,7)],[jar(1,6),jar(3,3),jar(6,7)],[jar(2,6),jar(1,3),jar(7,7)],[jar(6,6),jar(1,3),jar(3,7)],[jar(4,6),jar(3,3),jar(3,7)],[jar(5.5,6),jar(0,3),jar(4.5,7)],[jar(0.5,6),jar(2.5,3),jar(7,7)],[jar(6,6),jar(2.5,3),jar(1.5,7)],[jar(5.5,6),jar(3,3),jar(1.5,7)],[jar(6,6),jar(2,3),jar(2,7)],[jar(1,6),jar(2,3),jar(7,7)],[jar(2,6),jar(3,3),jar(5,7)],[jar(5,6),jar(0,3),jar(5,7)]]

1. Тут несколько реализаций.
2. Код целиком вы можете собрать из приведенных фрагментов. Тут есть все, надо лишь собрать их в одну программу.
3. Если сами делать не хотите — напишите вот этим ребятам. Укажите какую версию вам собрать и на каком прологе (Turbo/Visual/SWI/Arity/Gnu/D-)Prolog или еще что-то. Они все сделают.

Источник