Задача про две ёмкости для жидкости

в 14:05, , рубрики: dot, FSM, GraphViz, svg, Графические оболочки, динамическое программирование, дискретная математика, интервью, комбинаторика, логические игры, математика, Программирование, собеседование в IT, собеседования

Существует классическая задача:

Есть 2 емкости: 5 литров и 3 литра. Как отмерить 4 литра жидкости используя только эти 2 емкости?

Понятное дело что тут важно не сколько знание правильного ответа, а знание метода решения таких задач. Ведь вместо целевых 4х литров могут спросить отсчитать и 1,2,6,7 литров.

В этом тексте я решу эту задачу в общем виде при помощи конечного автомата. Так как тут явно можно проследить состояния и входные воздействия. Также я упомяну про малоизвестный язык Front-End разметки Dot. Методика конечного автомата хорошо изучена и поставлена на рельсы. Состоит из 3 фаз.

Фаза №1: перечислить все возможные состояния (комбинаторика)

Задача про две ёмкости для жидкости - 1

Состояние определяется количеством жидкости в паре сосудов. Согласно комбинаторике по правилу умножения существует всего 24 состояния. Вот они все перечислены.

Фаза №2 перечислить все возможные входы. (из условий задачи)

Существует всего 5 легальных действий с бутылками. Вот их перечень.

№

Фаза №3 составить таблицу переходов

Этот пункт я пропущу так как таблица получится циклопических размеров. По правилу умножения 24*5=120 переходов

Фаза №4 отрисовать граф состояний (Helicopter view)

Как гласит английская народная пословица “Картинка стоит тысячи слов” (A picture is worth a thousand words). Также мой универский профессор часто говорил, что инженеры - это про схемы. Поэтому представляю блок-схему в виде ориентированного графа состояний для задачи про бутылки.

Задача про две ёмкости для жидкости - 3

Я накропал на языке С консольную утилиту, которая прокручивает конечный автомат и сохраняет в файл составленный код на языке dot. Далее бесплатная утилита dot.exe поедает файл *.dot и преобразует его во всем известный *.svg файл. Наконец  браузер Chrome.exe поедает *.svg и отрисовывает в окне на мониторе. Язык Dot хорош тем что он имеет простой синтаксис. Dot более высокоуровневый язык, чем спецификация *.svg файлов.

Глядя на этот ориентированный граф становится очевидным, что чтобы отмерить 4 литра надо выполнить следующую  процедуру из 6-ти инструкций:

возможные действия с бутылками
возможные действия с бутылками

есть еще одно синее решение

Задача про две ёмкости для жидкости - 5

Easy!
Вот код Dot графа для тех, кто захочет изучить граф внимательнее.

digraph G {
  b0_5__b0_3_T_0 [label="b0_5__b0_3_T_0" color=grey96 style=filled shape=box];
  b0_5__b0_3_T_0->b5_5__b0_3_T_5 [label="Top0" color=Red fontcolor=Red]
   b5_5__b0_3_T_5 [label="b5_5__b0_3_T_5" color=grey73 style=filled shape=box];
   b5_5__b0_3_T_5->b5_5__b0_3_T_5 [label="Top0" color=Red fontcolor=Red]
   b5_5__b0_3_T_5->b5_5__b3_3_T_8 [label="Top1" color=orange fontcolor=orange]
    b5_5__b3_3_T_8 [label="b5_5__b3_3_T_8" color=grey55 style=filled shape=box];
    b5_5__b3_3_T_8->b5_5__b3_3_T_8 [label="Top0" color=Red fontcolor=Red]
    b5_5__b3_3_T_8->b5_5__b3_3_T_8 [label="Top1" color=orange fontcolor=orange]
    b5_5__b3_3_T_8->b0_5__b3_3_T_3 [label="Empty0" color=royalblue fontcolor=royalblue]
    b0_5__b3_3_T_3 [label="b0_5__b3_3_T_3" color=grey82 style=filled shape=box];
    b0_5__b3_3_T_3->b5_5__b3_3_T_8 [label="Top0" color=Red fontcolor=Red]
    b0_5__b3_3_T_3->b0_5__b3_3_T_3 [label="Top1" color=orange fontcolor=orange]
    b0_5__b3_3_T_3->b0_5__b3_3_T_3 [label="Empty0" color=royalblue fontcolor=royalblue]
    b0_5__b3_3_T_3->b0_5__b0_3_T_0 [label="Empty1" color=aqua fontcolor=aqua]
    b0_5__b3_3_T_3->b0_5__b3_3_T_3 [label="0->1" color=green fontcolor=green]
    b0_5__b3_3_T_3->b3_5__b0_3_T_3 [label="0<-1" color=blue fontcolor=blue]
    b3_5__b0_3_T_3 [label="b3_5__b0_3_T_3" color=grey82 style=filled shape=box];
    b3_5__b0_3_T_3->b5_5__b0_3_T_5 [label="Top0" color=Red fontcolor=Red]
    b3_5__b0_3_T_3->b3_5__b3_3_T_6 [label="Top1" color=orange fontcolor=orange]
    b3_5__b3_3_T_6 [label="b3_5__b3_3_T_6" color=grey69 style=filled shape=box];
    b3_5__b3_3_T_6->b5_5__b3_3_T_8 [label="Top0" color=Red fontcolor=Red]
    b3_5__b3_3_T_6->b3_5__b3_3_T_6 [label="Top1" color=orange fontcolor=orange]
    b3_5__b3_3_T_6->b0_5__b3_3_T_3 [label="Empty0" color=royalblue fontcolor=royalblue]
    b3_5__b3_3_T_6->b3_5__b0_3_T_3 [label="Empty1" color=aqua fontcolor=aqua]
    b3_5__b3_3_T_6->b3_5__b3_3_T_6 [label="0->1" color=green fontcolor=green]
    b3_5__b3_3_T_6->b5_5__b1_3_T_6 [label="0<-1" color=blue fontcolor=blue]
    b5_5__b1_3_T_6 [label="b5_5__b1_3_T_6" color=grey69 style=filled shape=box];
    b5_5__b1_3_T_6->b5_5__b1_3_T_6 [label="Top0" color=Red fontcolor=Red]
    b5_5__b1_3_T_6->b5_5__b3_3_T_8 [label="Top1" color=orange fontcolor=orange]
    b5_5__b1_3_T_6->b0_5__b1_3_T_1 [label="Empty0" color=royalblue fontcolor=royalblue]
    b0_5__b1_3_T_1 [label="b0_5__b1_3_T_1" color=grey91 style=filled shape=box];
    b0_5__b1_3_T_1->b5_5__b1_3_T_6 [label="Top0" color=Red fontcolor=Red]
    b0_5__b1_3_T_1->b0_5__b3_3_T_3 [label="Top1" color=orange fontcolor=orange]
    b0_5__b1_3_T_1->b0_5__b1_3_T_1 [label="Empty0" color=royalblue fontcolor=royalblue]
    b0_5__b1_3_T_1->b0_5__b0_3_T_0 [label="Empty1" color=aqua fontcolor=aqua]
    b0_5__b1_3_T_1->b0_5__b1_3_T_1 [label="0->1" color=green fontcolor=green]
    b0_5__b1_3_T_1->b1_5__b0_3_T_1 [label="0<-1" color=blue fontcolor=blue]
    b1_5__b0_3_T_1 [label="b1_5__b0_3_T_1" color=grey91 style=filled shape=box];
    b1_5__b0_3_T_1->b5_5__b0_3_T_5 [label="Top0" color=Red fontcolor=Red]
    b1_5__b0_3_T_1->b1_5__b3_3_T_4 [label="Top1" color=orange fontcolor=orange]
    b1_5__b3_3_T_4 [label="b1_5__b3_3_T_4" color=grey78 style=filled shape=box];
    b1_5__b3_3_T_4->b5_5__b3_3_T_8 [label="Top0" color=Red fontcolor=Red]
    b1_5__b3_3_T_4->b1_5__b3_3_T_4 [label="Top1" color=orange fontcolor=orange]
    b1_5__b3_3_T_4->b0_5__b3_3_T_3 [label="Empty0" color=royalblue fontcolor=royalblue]
    b1_5__b3_3_T_4->b1_5__b0_3_T_1 [label="Empty1" color=aqua fontcolor=aqua]
    b1_5__b3_3_T_4->b1_5__b3_3_T_4 [label="0->1" color=green fontcolor=green]
    b1_5__b3_3_T_4->b4_5__b0_3_T_4 [label="0<-1" color=blue fontcolor=blue]
    b4_5__b0_3_T_4 [label="b4_5__b0_3_T_4" color=grey78 style=filled shape=box];
    b4_5__b0_3_T_4->b5_5__b0_3_T_5 [label="Top0" color=Red fontcolor=Red]
    b4_5__b0_3_T_4->b4_5__b3_3_T_7 [label="Top1" color=orange fontcolor=orange]
    b4_5__b3_3_T_7 [label="b4_5__b3_3_T_7" color=grey64 style=filled shape=box];
    b4_5__b3_3_T_7->b5_5__b3_3_T_8 [label="Top0" color=Red fontcolor=Red]
    b4_5__b3_3_T_7->b4_5__b3_3_T_7 [label="Top1" color=orange fontcolor=orange]
    b4_5__b3_3_T_7->b0_5__b3_3_T_3 [label="Empty0" color=royalblue fontcolor=royalblue]
    b4_5__b3_3_T_7->b4_5__b0_3_T_4 [label="Empty1" color=aqua fontcolor=aqua]
    b4_5__b3_3_T_7->b4_5__b3_3_T_7 [label="0->1" color=green fontcolor=green]
    b4_5__b3_3_T_7->b5_5__b2_3_T_7 [label="0<-1" color=blue fontcolor=blue]
    b5_5__b2_3_T_7 [label="b5_5__b2_3_T_7" color=grey64 style=filled shape=box];
    b5_5__b2_3_T_7->b5_5__b2_3_T_7 [label="Top0" color=Red fontcolor=Red]
    b5_5__b2_3_T_7->b5_5__b3_3_T_8 [label="Top1" color=orange fontcolor=orange]
    b5_5__b2_3_T_7->b0_5__b2_3_T_2 [label="Empty0" color=royalblue fontcolor=royalblue]
    b0_5__b2_3_T_2 [label="b0_5__b2_3_T_2" color=grey87 style=filled shape=box];
    b0_5__b2_3_T_2->b5_5__b2_3_T_7 [label="Top0" color=Red fontcolor=Red]
    b0_5__b2_3_T_2->b0_5__b3_3_T_3 [label="Top1" color=orange fontcolor=orange]
    b0_5__b2_3_T_2->b0_5__b2_3_T_2 [label="Empty0" color=royalblue fontcolor=royalblue]
    b0_5__b2_3_T_2->b0_5__b0_3_T_0 [label="Empty1" color=aqua fontcolor=aqua]
    b0_5__b2_3_T_2->b0_5__b2_3_T_2 [label="0->1" color=green fontcolor=green]
    b0_5__b2_3_T_2->b2_5__b0_3_T_2 [label="0<-1" color=blue fontcolor=blue]
    b2_5__b0_3_T_2 [label="b2_5__b0_3_T_2" color=grey87 style=filled shape=box];
    b2_5__b0_3_T_2->b5_5__b0_3_T_5 [label="Top0" color=Red fontcolor=Red]
    b2_5__b0_3_T_2->b2_5__b3_3_T_5 [label="Top1" color=orange fontcolor=orange]
    b2_5__b3_3_T_5 [label="b2_5__b3_3_T_5" color=grey73 style=filled shape=box];
    b2_5__b3_3_T_5->b5_5__b3_3_T_8 [label="Top0" color=Red fontcolor=Red]
    b2_5__b3_3_T_5->b2_5__b3_3_T_5 [label="Top1" color=orange fontcolor=orange]
    b2_5__b3_3_T_5->b0_5__b3_3_T_3 [label="Empty0" color=royalblue fontcolor=royalblue]
    b2_5__b3_3_T_5->b2_5__b0_3_T_2 [label="Empty1" color=aqua fontcolor=aqua]
    b2_5__b3_3_T_5->b2_5__b3_3_T_5 [label="0->1" color=green fontcolor=green]
    b2_5__b3_3_T_5->b5_5__b0_3_T_5 [label="0<-1" color=blue fontcolor=blue]
    b2_5__b0_3_T_2->b0_5__b0_3_T_0 [label="Empty0" color=royalblue fontcolor=royalblue]
    b2_5__b0_3_T_2->b2_5__b0_3_T_2 [label="Empty1" color=aqua fontcolor=aqua]
    b2_5__b0_3_T_2->b0_5__b2_3_T_2 [label="0->1" color=green fontcolor=green]
    b2_5__b0_3_T_2->b2_5__b0_3_T_2 [label="0<-1" color=blue fontcolor=blue]
    b5_5__b2_3_T_7->b5_5__b0_3_T_5 [label="Empty1" color=aqua fontcolor=aqua]
    b5_5__b2_3_T_7->b4_5__b3_3_T_7 [label="0->1" color=green fontcolor=green]
    b5_5__b2_3_T_7->b5_5__b2_3_T_7 [label="0<-1" color=blue fontcolor=blue]
    b4_5__b0_3_T_4->b0_5__b0_3_T_0 [label="Empty0" color=royalblue fontcolor=royalblue]
    b4_5__b0_3_T_4->b4_5__b0_3_T_4 [label="Empty1" color=aqua fontcolor=aqua]
    b4_5__b0_3_T_4->b1_5__b3_3_T_4 [label="0->1" color=green fontcolor=green]
    b4_5__b0_3_T_4->b4_5__b0_3_T_4 [label="0<-1" color=blue fontcolor=blue]
    b1_5__b0_3_T_1->b0_5__b0_3_T_0 [label="Empty0" color=royalblue fontcolor=royalblue]
    b1_5__b0_3_T_1->b1_5__b0_3_T_1 [label="Empty1" color=aqua fontcolor=aqua]
    b1_5__b0_3_T_1->b0_5__b1_3_T_1 [label="0->1" color=green fontcolor=green]
    b1_5__b0_3_T_1->b1_5__b0_3_T_1 [label="0<-1" color=blue fontcolor=blue]
    b5_5__b1_3_T_6->b5_5__b0_3_T_5 [label="Empty1" color=aqua fontcolor=aqua]
    b5_5__b1_3_T_6->b3_5__b3_3_T_6 [label="0->1" color=green fontcolor=green]
    b5_5__b1_3_T_6->b5_5__b1_3_T_6 [label="0<-1" color=blue fontcolor=blue]
    b3_5__b0_3_T_3->b0_5__b0_3_T_0 [label="Empty0" color=royalblue fontcolor=royalblue]
    b3_5__b0_3_T_3->b3_5__b0_3_T_3 [label="Empty1" color=aqua fontcolor=aqua]
    b3_5__b0_3_T_3->b0_5__b3_3_T_3 [label="0->1" color=green fontcolor=green]
    b3_5__b0_3_T_3->b3_5__b0_3_T_3 [label="0<-1" color=blue fontcolor=blue]
    b5_5__b3_3_T_8->b5_5__b0_3_T_5 [label="Empty1" color=aqua fontcolor=aqua]
    b5_5__b3_3_T_8->b5_5__b3_3_T_8 [label="0->1" color=green fontcolor=green]
    b5_5__b3_3_T_8->b5_5__b3_3_T_8 [label="0<-1" color=blue fontcolor=blue]
   b5_5__b0_3_T_5->b0_5__b0_3_T_0 [label="Empty0" color=royalblue fontcolor=royalblue]
   b5_5__b0_3_T_5->b5_5__b0_3_T_5 [label="Empty1" color=aqua fontcolor=aqua]
   b5_5__b0_3_T_5->b2_5__b3_3_T_5 [label="0->1" color=green fontcolor=green]
   b5_5__b0_3_T_5->b5_5__b0_3_T_5 [label="0<-1" color=blue fontcolor=blue]
  b0_5__b0_3_T_0->b0_5__b3_3_T_3 [label="Top1" color=orange fontcolor=orange]
  b0_5__b0_3_T_0->b0_5__b0_3_T_0 [label="Empty0" color=royalblue fontcolor=royalblue]
  b0_5__b0_3_T_0->b0_5__b0_3_T_0 [label="Empty1" color=aqua fontcolor=aqua]
  b0_5__b0_3_T_0->b0_5__b0_3_T_0 [label="0->1" color=green fontcolor=green]
  b0_5__b0_3_T_0->b0_5__b0_3_T_0 [label="0<-1" color=blue fontcolor=blue]
    b1_5__b1_3_T_2 [label="b1_5__b1_3_T_2" color=grey87 style=filled shape=box];
    b1_5__b2_3_T_3 [label="b1_5__b2_3_T_3" color=grey82 style=filled shape=box];
    b2_5__b1_3_T_3 [label="b2_5__b1_3_T_3" color=grey82 style=filled shape=box];
    b2_5__b2_3_T_4 [label="b2_5__b2_3_T_4" color=grey78 style=filled shape=box];
    b3_5__b1_3_T_4 [label="b3_5__b1_3_T_4" color=grey78 style=filled shape=box];
    b3_5__b2_3_T_5 [label="b3_5__b2_3_T_5" color=grey73 style=filled shape=box];
    b4_5__b1_3_T_5 [label="b4_5__b1_3_T_5" color=grey73 style=filled shape=box];
    b4_5__b2_3_T_6 [label="b4_5__b2_3_T_6" color=grey69 style=filled shape=box];
}

Можно отрисовать граф на этом сайте и сохранить его в *.svg.

Редактировать *.svg можно при помощи бесплатной программы Inkscape.exe.

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

Существует 8 недостижимых состояний: 1/5_1/3; 1/5_2/3; 2/5_1/3; 2/5_2/3; 3/5_1/3; 3/5_2/3; 4/5_1/3; 4/5+2/3. В эти состояния никак не попасть как только не переливай содержимое сосудов. Если вы захотите завалить человека на собеседовании, то можно попросить его "как перелить жидкости так чтобы в каждой бутылине осталось по 2 литра?" или "как перелить жидкости так чтобы в каждой бутылке осталось по 1 литру?".

Формально можно отмерить не только 4 лита, а все значения от 1 до 8 включительно.

Вывод

Как видите, язык Front-End разметки Dot отлично подходит для автоматической отрисовки сложной векторной графики. Конечно dot тула несовершенна и даже планарные графы строит с пересечениями ребер. Если вы знаете тулу которая гарантирует планарность, то укажите это в комментариях.

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

Автор:
aabzel

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js