Not logged in. · Lost password · Register

katjab
Member since Oct 2019
86 posts
Subject: Problem 5, map coloring, availablecolors, etc.
I think I managed to fix the situation with the notebook. There may or may not be a bug in availablecolors (apart from the fact that it does the opposite of what it says). It works for me now on some tests. If it does not work for you, please let me know just how it crashes, best here in the forum.

If you run the sample paint query on a clean setup, you should get
ColoredMap = [sa:red, tas:red, vic:red, nsw:red, qld:red, nt:red, wa:red]
This post was edited on 2019-11-28, 17:54 by katjab.
michael_wagner
Member since Oct 2016
6 posts
In https://kwarc.info/teaching/AI/resources/hw5-setup.txt there is a missing semicolon, isn't it?

arrangecolors([Country:Neighbors|Rest], ColorList, TempList, ColoredMap) :-
    member(Color,ColorList),
%    Tracing:
%    write('Color:'), write(Color),write(' TempList:'), write(TempList),nl,
    different(Color,Neighbors,TempList) <- here
    arrangecolors(Rest,ColorList,[Country:Color|TempList], ColoredMap).
michael_wagner
Member since Oct 2016
6 posts
In reply to post #1
We already submitted a working solution with the original code.
Do you want us to find another one with the updated code?


original:
sortedcountries(Countries,TempList,SortedCountries) :-
    countrieswithconstraints(Countries,TempList,[],CountriesWithConstraints),
    keysort(CountriesWithConstraints,SortedCountriesWithConstraints),
    % write(SortedCountriesWithConstraints), nl,
    pairs_keys_values(SortedCountriesWithConstraints,_,SortedCountries).
katjab
Member since Oct 2019
86 posts
arrangecolors is in the Edit section, which is the one you were supposed to fix.
As for sortedcountries, either is ok.
sofa03
Member since May 2019
10 posts
Is there a solution to this assignement somewhere?
katjab
Member since Oct 2019
86 posts
Unfortunately the original solution got corrupted and I didn't get around to rewriting it - sorry about that! Someone might be willing to share their working solution.
floreien
Member for 2 weeks
2 posts
+1 sofa03
% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
% Edit section

arrangecolors([],_,ColoredMap,ColoredMap).
arrangecolors(CountryList, ColorList, TempList, ColoredMap) :-
    %5.1.(4)
    %Aenderung des ersten Elements um sortedcountries zu benutzen"

    %5.1.(4)
    %Aufrufen von sortedcountries mit neuer Liste L
    sortedcountries(CountryList,TempList,L),

    %5.1.(4)
    %um die geordnete Liste zu benutzen Aufruf von istgleich
    istgleich(L,[Country:Neighbors|Rest]),

    %5.1(2)
    %Zeile 21, in der member aufgerufen wird, da member eine Farbe aus ColorList nimmt, falls different true ist.
    %Falls differnet aber false ausgibt backtracked member automatisch und versucht es mit der naechsten Farbe.
    member(Color,ColorList),
    different(Color,Neighbors,TempList),
    arrangecolors(Rest,ColorList,[Country:Color|TempList], ColoredMap).

%5.1(3)
restrictedness(Neighbors,TempList,R) :-

    %Suche moegliche Farben
    availablecolors(Neighbors,TempList,[],List),
    %Da availablecolors eine Liste mit Duplikaten ausgeben kann -> removeDuplicates
    removeDuplicates(List,L),
    %Die Laenge von L ist dann die Anzahl der nicht zu gebrauchenden Farben
    length(L,S),
    %-> 4-S = R
    R is 4-S.


% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
% Maybe useful things

findneighbors(X, Map, Who) :-
    map(Map, Countries),
    neighbors(X,Countries,Who).

neighbors(_,[],[]).
neighbors(X,[X:Neighbors|_], Neighbors) :- !.  % Try this without the !
neighbors(X,[_|RestofCountries], Neighbors) :-
    neighbors(X,RestofCountries, Neighbors).

adjacent(X,Y,Map) :-
    findneighbors(X, Map, Countries),
    member(Y, Countries).


% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
% This you will most likely use
different(C, Nbs, [S1:C1|Rest]) :-
    not((member(S1,Nbs), C = C1)),
    different(C, Nbs,Rest).
different(_,_,[]).

availablecolors(_,[],Colors,Colors).
availablecolors(Neighbors,[NB:Color|TempListTail],TempColors,Colors) :-
    member(NB,Neighbors) ->
        availablecolors(Neighbors,TempListTail,[Color|TempColors],Colors);
        availablecolors(Neighbors,TempListTail,TempColors,Colors).

%5.1(3)
%Hilfsfunktion removeDuplicates aus frueherer Hausaufgabe
delete(_,[],[]).
delete(Xa,[Xa|Ra],Na):-!,delete(Xa,Ra,Na).
delete(Xa,[Ya|Ra],[Ya|Na]):-delete(Xa,Ra,Na).
removeDuplicates([],[]).
removeDuplicates([Xb|Rb],[Xb|Nb]):-delete(Xb,Rb,Ub), removeDuplicates(Ub,Nb).

countrieswithconstraints([],_,L,L).
countrieswithconstraints([Country:Neighbors|Rest],TempList,Accumulator,CountriesWithConstraints) :-
    countrieswithconstraints(Rest,TempList,[R-(Country:Neighbors)|Accumulator],CountriesWithConstraints),
    restrictedness(Neighbors,TempList,R).

sortedcountries(Countries,TempList,SortedCountries) :-
    countrieswithconstraints(Countries,TempList,[],CountriesWithConstraints),
    keysort(CountriesWithConstraints,SortedCountriesWithConstraints),
    % write(SortedCountriesWithConstraints), nl,
    pairs_keys_values(SortedCountriesWithConstraints,_,SortedCountries).


istgleich([],[]).
istgleich([Country:Neighbors|Rest],[Country:Neighbors|Rest]).

% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
% Main
paint(Map,ColoredMap) :-
    map(Map, Countries),
    colors(ColorList),
%    Tracing:
%    write('ColoredMap is '), write(ColoredMap), nl.
    arrangecolors(Countries,ColorList,[], ColoredMap).

%5.1(5) ich verstehe nicht was in dem Fall tiebreaker bedeuten soll
%im Zweifel regelt aber prolog mit backtracking
katjab
Member since Oct 2019
86 posts
Thanks!
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen