Подобрать цвета для раскраски башни из 10 этажей

Главная Форумы Программирование Помощь с решением задач на Prolog Решение головоломок на Prolog Подобрать цвета для раскраски башни из 10 этажей

В этой теме 3 ответа, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 неделя, 4 дн. назад.

  • Автор
    Сообщения
  • #4241

    toshytwx
    Участник

    Условия:
    1) Последовательность использования цветов должна соответствовать последовательности цветов радуги. При этом допускается повтор текущего цвета и пропуск не более двух цветов.
    2) Яркость каждого последующего цвета должна быть меньше чем яркость предыдущего.
    3) SWI prolog

    Вот, что у меня получилось (работает неправильно):

        :-dynamic layers/3.
    
        init_database :-
            assert(layers(lay1,0.1,red)),
            assert(layers(lay2,0.2,red)),
            assert(layers(lay3,0.4,orange)),
            assert(layers(lay4,0.3,orange)),
            assert(layers(lay5,0.5,yellow)),
            assert(layers(lay6,0.7,yellow)),
            assert(layers(lay7,0.6,green)),
            assert(layers(lay8,0.8,green)),
            assert(layers(lay9,0.7,cyan)),
            assert(layers(lay10,0.9,blue)),
            assert(layers(lay11,1,magente)).
    
        rainbow(red,orange).
        rainbow(orange,yellow).
        rainbow(yellow,green).
        rainbow(green,cyan).
        rainbow(cyan,blue).
        rainbow(blue,magente).
    
        % ?P1, -Result
        main(L1, Res):-
            layers(_, _, _),
            !,
            layers_main(L1, Res).
        main(L1, Res):-
            init_database,
            layers_main(L1, Res).
    
        % ?P1, ?Result
        layers_main(L1, [L1|Ls]) :-
            layers(L1, Alpha, Color),
            layers_add([(Alpha,Color)],Color,Ls).
    
        % ?History, ?Previous color, -Res
        layers_add(History, Color, [Next|Layers]) :-
            length(History, Length),
            Length < 10,
            add(History,Color,Next,Alpha,NextColor),
            layers_add([(Alpha,NextColor)|History],NextColor,Layers).
        layers_add(_, _, []).
    
        %+History, +Color, -Id, -Sides, -Color
        add(History,Color,Next,Alpha,NextColor):-
            layers(Next,Alpha,NextColor),
            next_color(Color,NextColor),
            check_alpha(Alpha, History).
        check_alpha(Alpha,[(Alpha1,_)]):-
            Alpha > Alpha1.
    
        % ?Color, ?NextColor
        next_color(C, C).
        next_color(C, C1) :-
            rainbow(C, C1).
        next_color(C, C1) :-
            rainbow(C, T1),
            next_color(T1, C1).

  • #4246

    Если доработаете свое решение – очень прошу скинуть окончательный вариант на форум.

    В целом, программа должна перебирать решения. У нас тут есть статья по решению логических задач и там описаны так называемые “переборные задачи”. Фактически полный перебор – это поиск в глубину (так устроен механизм перебора с возвратами prolog) – в вашей задаче это подойдет, т.к. глубина фиксирована 10 этажами.

    Чтобы выполнять такой перебор вам надо где-то фиксировать накопленный результат, это может быть, скажем, список цветов. При этом для генерации мы можем брать крайний цвет и из него генерировать следующие возможные.

    Есть требование:

    1) Последовательность использования цветов должна соответствовать последовательности цветов радуги. При этом допускается повтор текущего цвета и пропуск не более двух цветов.

    Согласно нему, “крайним цветом” может быть red, orange или yellow (потому что если yellow – то мы пропустим не более двух цветов). Ваша программа на настоящий момент это не предусматривает:

    first_color(red). 
    first_color(orange).
    first_color(yellow).

    Дальше – необходимо правило генерации следующего цвета. У вас для этого добавлено правило next_color, которое принимает текущий цвет и возвращает “следующий” допустимый (с учетом возможных пропусков). Однако, сейчас оно написано у вас так, что пропускает не более одного цвета, а по условию – пропустить можно не более двух.

    Исправить можно так:

        % ?Color, ?NextColor
        next_color(Color, Color).
        next_color(Color, NextColor):-
            rainbow(Color, NextColor);
    
            rainbow(Color, ColorGap_One),
            next_color(ColorGap_One, NextColor);
    
            rainbow(Color, ColorGap_One),
            next_color(ColorGap_One, ColorGap_Two),
            next_color(ColorGap_Two, NextColor).

    Есть еще одно требование:
    2) Яркость каждого последующего цвета должна быть меньше чем яркость предыдущего.

    Вам нужно правило, которое будет возвращать следующую возможную яркость. Что-то типа next_brightness. Если яркость при этом будет меняться от 1 до 0 – то выглядеть оно может так:

    first_brightness(1).
    
    next_brightness(Brightness, NextBrightness):-
      NextBrightness is Brightness - 0.1.

    Остается запустить перебор (это очень просто). я не понял что там у вас в решении с базой данных (и зачем она вообще нужна). Очень рекомендую посмотреть другие переборные задачи на нашем форуме и сделать по образцу. Когда будете оформлять решение – обратите внимание на правила оформления кода на нашем форуме (имена переменных C, Temp и т.п. – мало о чем говорят и вот в вашем случае Gap гораздо лучше подходит – ошибки в пропуске цвета вам возможно удалось бы избежать за счет правильного именования).

  • #4255

    toshytwx
    Участник

    Доброй ночи, высылаю мое решение. Проверил с входящей базой данных – вроде работает :)

    :-dynamic layers/3.
    
    init_database :-
        assert(layers(lay1,1,red)),
        assert(layers(lay5,5,yellow)),
        assert(layers(lay3,4,orange)),
        assert(layers(lay4,3,orange)),
        assert(layers(lay13,11,magente)),
        assert(layers(lay6,7,yellow)),
        assert(layers(lay7,6,green)),
        assert(layers(lay10,9,blue)),
        assert(layers(lay8,8,green)),
        assert(layers(lay2,2,red)),
        assert(layers(lay9,7,cyan)),
        assert(layers(lay11,10,magente)),
        assert(layers(lay12,8,cyan)).
    
    rainbow(red,orange).
    rainbow(orange,yellow).
    rainbow(yellow,green).
    rainbow(green,cyan).
    rainbow(cyan,blue).
    rainbow(blue,magente).
    
    first_color(red).
    first_color(orange).
    first_color(yellow).
    
    first_alpha(1).
    
    % ?P1, -Result
    main(L1, Res):-
        layers(_, _, _),
        !,
        layers_main(L1, Res).
    
    main(L1, Res):-
        init_database,
        layers_main(L1, Res).
    
    % ?P1, ?Result
    layers_main(L1, [L1|Ls]) :-
        layers(L1, Alpha, Color),
        first_color(Color),
        first_alpha(Alpha),
        layers_add([(Alpha,Color)],Color,Ls).
    
    layers_add(History, Color, [Next|Layers]) :-
        add(History,Color,Next,Alpha,NextColor),
        layers_add([(Alpha,NextColor)|History],NextColor,Layers).
    layers_add(_, _, []).
    
    add(History,CurrentColor,Next,NextAlpha,NextColor):-
        next_color(CurrentColor,NextColor),
        layers(_,CurrentAlpha, NextColor),
        not(member((CurrentAlpha,CurrentColor),History)),
        NextAlpha = CurrentAlpha,
        layers(Next,NextAlpha,NextColor),
        not(member((NextAlpha,_),History)).
    
    % ?Color, ?NextColor
    next_color(Color, Color).
    next_color(Color, NextColor):-
        rainbow(Color, NextColor);
        rainbow(Color, ColorGap_One),
        next_color(ColorGap_One, NextColor);
        rainbow(Color, ColorGap_One),
        next_color(ColorGap_One, ColorGap_Two),
        next_color(ColorGap_Two, NextColor).

    К слову пытался решить с помощью поиска в глубину, по данной Вами ссылке, но, увы так и не смог найти верного алгоритма для своего случая. Все задачи примеров прочитал – так и не смог подобрать нужные условия. Программа не всегда выдает цвета для 10 этажей башни, и мой SWI prolog очень странно работает с вещественными числами, почему-то при суммировании двух вещественных чисел, к примеру 0.2 + 0.1 ответ будет 0.3000000000000000000000004, пришлось заменить все значения Alpha на целые. Если Вам не составит труда, хотелось бы узнать решение задачи методом поиска в глубину и узнать эти тонкости работы SWI prolog с вещественными числами, уж больно долго я занимался отладкой что бы узнать такой неприятный факт.

    • #4256

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

      Перечислим все возможные цвета и напишем функцию, которая из них формирует список:

      color(red).
      color(orange).
      color(yellow).
      color(green).
      color(cyan).
      color(blue).
      color(magente).
      
      get_all_colors(Colors):-
        findall(Color, color(Color), Colors).
      

      Они нам пригодятся, т.к. нам надо не только находить следующий допустимый цвет, но и проверить, что “пропусков не больше двух” с конца радуги.

      зададим яркость, напишем функцию для получения следующей яркости. Ну и следующий уровень получим аналогично:

      first_brightness(10).
      
      next_brightness(Brightness, NextBrightness):-
        NextBrightness is Brightness - 1.
        
      next_layer(Layer, NextLayer):-
        NextLayer is Layer + 1.

      Чтобы получить следующий цвет – собираем список цветов и говорим, что между текущим цветом и следующим есть не более заданного числа элементов. С помощью этой функции мы можем не только найти следующий элемент (при этом пропускается согласно задания не более двух), но и после получения результата – проверить его корректность. От “конца” радуги тоже пропущено ведь не более двух элементов, а мы проверим, что от последнего цвета (magente) не более одного.

      next_color(Color, Color, _MaxGapSize).
      next_color(Color, NextColor, MaxGapSize):-
        get_all_colors(Colors),
        divide_list(Colors, [_, [Color], Gap, [NextColor], _]),
        length(Gap, GapSize),
        GapSize =< MaxGapSize.

      Для разбиения списка на части используется функция divide_list.

      Собственно, проверка последних цветов – получаем все цвета радуги, выбираем встроенной функций last последний из них и требуем, чтобы от текущего цвета до последнего было пропущено не более одного. На самом деле, в таком ключе можно переписать fist_color или наоборот явно перечислить допустимые последние цвета…

      check_last_colors([layer(_Layer, Color, _Brightness)|_Tail]):-
        get_all_colors(Colors),
        last(Colors, LastColor),
        next_color(Color, LastColor, 1).

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

      solve(Rainbow):-
        first_color(FirstColor),
        first_brightness(FirstBrightness),
        
        dfs([layer(1, FirstColor, FirstBrightness)], ReversedRainbow), 
        
        check_last_colors(ReversedRainbow),
        reverse(ReversedRainbow, Rainbow).

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

      dfs(Rainbow, Rainbow):-
        Rainbow = [layer(10, _Color, _Brightness)|_Tail], !.
      dfs(Buffer, Rainbow):-
        Buffer = [layer(HeadLayer, HeadColor, HeadBrightness)|_Tail],
        next_layer(HeadLayer, NextLayer),
        next_brightness(HeadBrightness, NextBrightness),
        next_color(HeadColor, NextColor, 2),
        dfs([layer(NextLayer, NextColor, NextBrightness)|Buffer], Rainbow).

      Вложения:

Для ответа в этой теме необходимо авторизоваться.