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

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

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

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

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

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

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

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

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

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

Фаза 4 отрисовать граф состояний

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

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

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

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

Easy!

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]; }

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

Эта задача может служить отличной иллюстрацией для обучения теории конечных автоматов 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. В эти состояния никак не попасть как только не переливай содержимое сосудов.

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

вывод

Как видите, язык программирования Dot отлично подходит для автоматической отрисовки сложной векторной графики.

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