Logical FizzBuzz

Привет, абстрагирующимся. Прочитав эту статью, задумался, а как представлять эту задачу языком Пролог? Попробую выразить свое, затянувшееся, субботнее отношение к этой пятничной задаче, с помощью доступных декларативных формулировок.
В реализации на Скала, я увидел операцию "(value % n)" и пояснение, что значения value,n -это: type class "Integral" требующий от типа "T" возможности вычислять остаток от деления и иметь значение "zero".
Это меня подтолкнуло, на такую мысль, а может абстрагируемся еще больше, и отбросим арифметические операции этого "интэграл", может рассмотрим глубже идею натуральных чисел, сейчас попробую продемонстрировать и получить реализацию...

Это представляли еще в Древней Греции, натуральное число N — это 0 или следующее за ним натуральное число, результат функции p(N).
Записывать можно так N0= 0,
потом N1=p(0), и далее N2=p(p(0)) — вот такой ряд натуральных чисел, от 0 и далее следующее и следующее значение:

Изображаю это на Прологе:

natural(0).
natural(N+1):-natural(N).

если выполнить такую цель, получим бесконечность ответов:

?-natural(X).
X=0;
X=0+1;
X=0+1+1: .... ну и тд.

От этого, пользы большой не извлечь, а как часть объяснения годится, значения переменной X являются структурами, в Прологе есть инфиксные операции, которые могут соединить значения между собой, вместо громоздкой записи p(p(p..(p(0)..))), просто соединим символы знаком "+": 0+1+1+1+1… это просто такое символьное выражение, почти строка, а можно бы записать и как: zero plus one plus one.
Вот так, можно объявлять свой знак операции:

:-op(600, yfx, plus). %op(+Precedence, +Type, :Name) 
natural(zero).
natural(N plus one):-natural(N).

Будут такие представления чисел:

?- natural(X).
X = zero ;
X = zero plus one ;
X = zero plus one plus one ; ...

Далее, полезно будет сформулировать следующую проблему, как выражать сложение или вычитание над двумя такими натуральными числами?,
вот оно:

add(0, X, X).
add(X+1, Y, Z+1):- add(X, Y, Z).

Теперь можно решить вот такие цели для сложения:

?- add(0+1,  0+1+1, X).
X=0+1+1+1

И вот такой вопрос, превратится в вычитание натуральных чисел:

?- add(X,  0+1+1+1,  0+1+1+1+1).
X=0+1

Можно получать все возможные натуральные слагаемые, составившие определенное значение:

?- add(X, Y, 0+1+1+1+1).
X=0, Y=0+1+1+1+1;
X=0+1, Y=0+1+1+1;
X=0+1+1, Y=0+1+1;.. и тд.

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

В задаче, на вход поступят числа, записанные как целые, арабские, и если не отменять это условие и не просить пользователя передавать на вход, только что показанные структуры, реализую такое правило:

int_natural(0,0).
int_natural(X, Y+1):- X0 is X-1,  int_natural(X0, Y).

оно сможет конвертировать целое число в его "натуральное" представление:

?- int_natural(6,X).
X=0+1+1+1+1+1+1 

Операция is — это встроенное вычисление арифметических действий.
Теперь ближе к задаче, там было, про определить остаток от деления. Сначала продемонстрирую умножение:

mul(0, X, 0).
mul(X+1, Y, Z):- mul(X, Y, Z1), add(Z1, Y, Z).

это можно использовать и для обратной операции — для деления:

?- mul(0+1+1, 0+1+1, X).
X=0+1+1+1+1
?- mul(0+1+1, X, 0+1+1+1+1).
X=0+1+1

Вот так, сформулирую остаток от деления:

rem(X, X, 0).
rem(X, Y, R) :- add(X1,Y,X), rem(X1,Y,R),!.
rem(X, _, X):-!.

тут и отсечение (!) заранее установленно, что бы не шокировать читателей функцией обратной к "остатку от деления", это, наверное, операция "следующее число, не кратное на одну величину остатка", типа так:

?- rem(X, 0+1+1+1, 0+1).
X = 0+1+1+1+1 ;
X = 0+1+1+1+1+1+1+1 ;
X = ... + ... + 1+1+1+1+1+1+1+1+1 ... и тд.

"Прямое" использование этого правила вот:

?- rem(0+1+1+1+1, 0+1+1, X).
X = 0.
?- rem(0+1+1+1+1, 0+1+1+1, X).
X = 0+1. 

FizzBuzz

Отлично, всю задачу сформулировать теперь можно, таким видом:

fizz_buzz(N, fizzbuzz) :- rem(N, 0+1+1+1, 0), rem(N, 0+1+1+1+1+1, 0),!.
fizz_buzz(N, fizz) :- rem(N, 0+1+1+1, 0),!.
fizz_buzz(N, buzz) :- rem(N, 0+1+1+1+1+1, 0),!.
fizz_buzz(N, N).

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

?- int_natural(5, N),!, fizz_buzz(N, X).
N = 0+1+1+1+1+1,
X = buzz.
?- int_natural(15, N),!, fizz_buzz(N, X).
N = ... + ... + 1+1+1+1+1+1+1+1+1,
X = fizzbuzz.

или по условию, на выходе получаем тоже число:

?- int_natural(4, N),!, fizz_buzz(N, X).
N = X, X = 0+1+1+1+1.

Исключив предыдущие недостатки и немного подумав про производительность, упрощаю до такого "алгоритма":

fizz_buzz2(IN, R) :-once(int_natural(IN,N)),
                    once(rem(N, 0+1+1+1, 0) -> F=fizz; F=''),
                    once(rem(N, 0+1+1+1+1+1, 0) -> B=buzz; (F\='')->B=''),
                    atom_concat(F,B,R),!.
fizz_buzz2(N, N).

В этом варианте сразу переводим входное целое число и компонуем выходное значение из частей, если это потребовалось. Встроенное правило once(Goal), выполняет цель только один раз, для исключения возвратов и зацикливаний.
Вот такие примеры:

?- fizz_buzz2(2, X).
X = 2.
?- fizz_buzz2(15, X).
X = fizzbuzz.

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

?- findall(X, (between(1, 10, N), fizz_buzz2(N, X)), Result).
Result = [1, 2, fizz, 4, buzz, fizz, 7, 8, fizz|...].

Вот тут, можно попробовать.

Для заключения

Пролог, это любопытная возможность переносить в "символы" условия задач, это система опирающаяся на логику предикатов и встроенные процедуры автоматического доказательства теорем. Формулировка проблемы, при удачном выражении, позволяет находить решение для самой задачи, а также сразу иметь решение "обратной" к ней проблеме. А может вот таким вопросом, увидим, какие числа, приводят к fizz: ?- fizz_buzz(N, fizz).

Let's block ads! (Why?)