переливания без перебора

В недавнем конкурсе _darkus_ предложил общественности приятную задачку:
У Вас есть два сосуда, один объёмом 5 литров, а другой объёмом 8 литров. Вы можете наливать сосуды до края какой-то жидкостью (будьте осторожны, возможно, что она едкая или ядовитая) из крана. Вы можете выливать жидкость из сосуда в технологическую раковину. Вы можете переливать жидкость из сосуда в сосуд так, что либо в первом сосуде закончится жидкость, либо второй наполнится до краёв (что произойдёт ранее). Ваша задача — отмерить 2 литра жидкости. Пишите программу сразу универсальной, получающей на вход объёмы двух сосудов и количество литров, которое необходимо отмерить (все объёмы являются строго целыми числами). Программа должна вывести алгоритм или написать, что решения нет.

Я вижу, что многие участники закодировали простой перебор и на этом успокоились, даже не начав думать. А могли бы подумать так:
Пусть объемы двух имеющихся сосудов - А и В. Тогда количество жидкости в них в любой момент - это пара чисел (а,b) - точка на декартовой плоскости где-то в прямоугольнике (0,0, A,B). Начальное положение - (0,0). Занимаясь на/вы/пере-ливаниями, мы двигаем точку в прямоугольнике. Лить мы можем пока какой-нибудь сосуд не наполнится или текущий не опустеет. Значит, двигается точка всегда до границы, и все достижимые состояния лежат на границе прямоугольника. Наливание в сосуд из крана и выливание в раковину затрагивают лишь один сосуд, поэтому это движение параллельно оси. Переливание из одного сосуда в другой сохраняет суммарное количество жидкости в сосудах, поэтому это движение параллельно прямой y=-x.


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

Мы можем двигаться из начала координат либо вправо-вниз, либо влево-вверх. Искомая точка лежит на этой прямой y=-x и характеризуется тем, что одна из ее координат при делении на объем сосуда дает искомый остаток (в данном примере - 2). Точек подходящих много, но нас интересует ближайшая к началу координат. Можно ли ее найти без перебора? По сути, задача свелась к делению в модульной арифметике. Координата искомой точки делится нацело на один из объемов и делится с требуемым остатком на другой:
Ax = By + z или Ax + z = By или просто (убрав знак в константу)
Ax + By = z
Тут на помощь приходит обратный или расширенный алгоритм Евклида, находящий по A,B такие x и y, что Ax + By = gcd(A,B). На Окамле в 64-битной арифметике он выглядит так:

let rec egcd a b = 
  if b = 0L then (1L, 0L) else 
  let q = a / b and r = rem a b in 
  let (s,t) = egcd b r in  (t, s - q*t);; 

Для A=8 и B=5 он находит x=2 y=-3, действительно 8*2 - 5*3 = 1. Чтобы из этих x и y получить одно из решений, можно умножить их на z/gcd(A,B), в нашем примере на 2: 8*4 - 5*6 = 2. Поскольку для любых целых x и y Ax+By кратно gcd(A,B), если искомый остаток z не кратен gcd(A,B), то решения не существует, можно и не искать. Однако так мы найдем лишь одно из решений, не обязательно ближайшее к началу координат. Но если (x,y) - решение, то (x+dx,y+dy) и (x-dx,y-dy) - тоже решения, где dx = B/gcd(A,B) и dy = A/gcd(A,B), ибо рисунок повторяется каждые lcm(A,B)=A*B/gcd(A,B) клеток. Поэтому, имея одно из решений, несложно найти лучшее:

let rec closer x y dx dy = 
  let dist a b = abs a + abs b in 
  let d0 = dist x y and dm = dist (x-dx) (y-dy) and dp = dist (x+dx) (y+dy) in 
  if dm < d0 && dm < dp then closer (x-dx) (y-dy) dx dy else 
  if dp < d0 && dp < dm then closer (x+dx) (y+dy) dx dy else 
  (x,y) 

Тут процесс итеративный, но итераций, как я понимаю, обычно будет около одной. Можно и вовсе без итераций, взяв остаток от деления на gcd(A,B) и сравнив две точки рядом с началом координат. Применение такой уточняющей функции дает решение x=-1 y=2: -8*1 + 5*2 = 2. В контексте задачи это означает, что нам надо дважды налить из крана в сосуд из 5 литров, из него переливая в другой сосуд (поскольку двигаемся всегда вдоль прямой y=-x в одном направлении, то всегда у нас в один сосуд льется жидкость из крана, а во второй - из первого). Осталось лишь, зная координаты оптимального решения, вывести последовательность шагов. Это оставим в качестве упражнения читателю. :)

кадр

Понравился кадр, что сделал на днях. Вид с острова на материк. Тут до материка 30 км: