Charminator

CDW · Jun 6, 2007

Eingereicht von Ivan Dolvich

(aus dem Bundeswettbewerb Informatik, sollte aber zu schaffen sein, eventuell ist Schwierigkeit 3 sogar übertrieben

)

Aufgabenstellung: tratsCH trATsch

Die Leute vom Planeten Chator schreiben gern Schlechtes ubereinander.
Wer vielen uber andere Schlechtes schreibt, gilt als besonders charmant.
Aber natürlich nur, wenn die Kompromittierten nichts davon erfahren.
Chatonen schreiben nur an Leute, die Ihnen sympathisch sind. Doch die
können den Tratsch weitertragen, und eventuell genau an den Falschen.
Ein Chatone muss also gut aufpassen, dass er keinen Charmefehler macht.
Dieses Missgeschick passierte unlängst Ator, als er Btor Schlechtes
über Dtor schrieb. Zu dumm: Dtor ist dem Ctor sympathisch, der wiederum
Btor sympathisch ist.

Und so landete der Tratsch bei Dtor, der uber Ator verständlicherweise
sehr verärgert war. Dies hätte Ator mit ein wenig Übersicht vermeiden
können, denn schließlich wissen alle Chatonen voneinander, wer wem
sympathisch ist.

Aufgabe:
Programmiere einen Charminator, der einliest, welche Chatonen welchen
anderen sympathisch sind. Er soll auf dieser Grundlage möglichst kompakt
für alle Chatonen ausgeben, wem der Betreffende uber wen Schlechtes
schreiben kann, ohne einen Charmefehler zu riskieren.
Teste dein Programm an drei Beispielen für mindestens 5 und höchstens 10
Chatonen; verwende auf jeden Fall das folgende Beispiel:

Code:

  Dem Chatonen      sind sympathisch:
  A                 B E
  B                 C
  C                 D G
  D                 C
  E                 F
  F                 B E G
  G                 H
  H                 D

Bedenke dabei, dass eine Tratschnachricht von Chatone x nach Chatone y
weder x noch y betrifft und dass ein Chatone eine Nachricht, die
ursprünglich von ihm selbst stammt und wieder bei ihm ankommt, nicht
weiterleiten wird ? so dumm sind Chatonen nicht

Losungsidee nach Benjamin Berger

Die Sympathiebeziehungen der Chatonen werden als ein gerichteter Graph
aufgefasst: die Chatonen sind die Knoten, die direkten
Sympathiebeziehungen die gerichteten Kanten. Dann wird
der Weg einer Nachricht von einem Chatonen S (Sender) an einen dem S
sympathischen Chatonen E (Empfänger) für alle möglichen Paare (S,E) wie
folgt nachvollzogen: Der Graph wird beginnend bei E rekursiv durchsucht
(Tiefensuche), bis entweder S selbst erreicht wird (der die
Nachricht nicht weiterleitet) oder ein gefundener Chatone schon besucht
wurde, die Nachricht also schon erhalten hat. Über alle Chatonen, die
nicht besucht wurden, kann S bei E tratschen ? da E an sie den Tratsch
eben nicht weiterleiten kann.

J.U.B. · Jun 6, 2007

Also habe ich das jetzt wie folgt verstanden:
man solle ein Programm entwickeln in dem man zusätlich zu den ausgaben wehm wer sympathish ist noch über wehm er lästern kann ausgeben... ungefär so?:

Code:

Dem Chatonen     sind sympatisch:   und kann über diese lästern:
A                B E
B                C                   A E F
C                D G                 A B E F
D                C                   A B E F
E                F                   A
F                B E G               A
G                H                   A B E F
H                D                   A B E F

CDW · Jun 6, 2007

Wer wem sympatisch ist, soll vom Benutzer eingegeben werden.
Das Programm soll dann ermitteln, wem ein bestimmter Chatone über einen anderen eine Lästernachricht schicken kann, ohne dass der Chatone, über den dabei gelästert wird, es mitbekommt.

Also: ein Chatone lästert über einen andern. Dabei schickt er seine Lästernachricht an die ihm sympatischen Chatonen. Diese wiederum leiten diese Nachricht an die ihnen sympatischen.

Bsp: A lästert über C. Schickt also seine Nachricht an B,E weiter. E schickt diese an F, B dagegen leitet sie an C weiter - Fehler.

J.U.B. · Jun 6, 2007

Ok
Ich hätte dann folgende Lösung in PVX

Code:

dim chaton$[8], sym$[8], ok$[8], xy$[1000], okdu$, lehr$(20)
chaton$[1]="A"
chaton$[2]="B"
chaton$[3]="C"
chaton$[4]="D"
chaton$[5]="E"
chaton$[6]="F"
chaton$[7]="G"
chaton$[8]="H"
lehr$(20)="                    "
	
FOR B=1 TO 8 STEP 1
PRINT 'CS',
PRINT "Bitte geben Sie ein wer ",chaton$[B]," sympatisch ist."
INPUT "Eingabe: ",sym$[B]
NEXT

PRINT 'CS',

for I=1 TO 8 STEP 1
	LET A=1
	FOR K=1 TO 8 STEP 1
		IF chaton$[I]=chaton$[K] THEN {
		} ELSE {
			okdu$=""
			LET A=1
			xy$[A]=chaton$[I]
			L=LEN(sym$[I])
			FOR H=1 TO L STEP 1
				A++
				xy$[A]=sym$[I](H,1)
			NEXT
			FOR D=A-L TO 20 STEP 1
				FOR E=1 TO A-1 STEP 1
					IF xy$[E]=xy$[D] THEN {
						IF okdu$<>"Y" THEN {
							okdu$="X"
						}
					}
					IF xy$[E+1]=chaton$[K] THEN {
						okdu$="Y"
					}
				NEXT
				F=0
				FOR G=1 TO 8 STEP 1
					IF chaton$[G]=xy$[D] THEN {
						F=G
					}
				NEXT
				L=LEN(sym$[F])
				FOR H=1 TO L STEP 1
					A++
					xy$[A]=sym$[F](H,1)
				NEXT
			NEXT
			IF okdu$="X" THEN {
				ok$[I]=ok$[I]+chaton$[K]+" "
			}
		}
	NEXT
NEXT
PRINT "Dem Chatonen:    sind symphatisch:    und kann ",CHR(252),"ber folgende l",CHR(228),"stern:"
FOR I=1 TO 8 STEP 1
L=LEN(sym$[I])
PRINT chaton$[I],"                ",sym$[I],lehr$(L),ok$[I]
NEXT

[EDIT]
und der gleiche code etwas umgeschrieben für NOMADS mit GUI sieht dann so aus:

Ivan Dolvich · Jun 13, 2007

Hier ist meine Lösung mit Groovy, hab sie nach der Lösungsidee gemacht. Die Idee klingt vielleicht etwas kompliziert, die Lösung ist aber einfach.

Code:

class Chaton 
{
    String name      // Name des Chatonen
    List symps       // sympatische Chatonen
    
    Boolean marked   // Markierung für die Suche
    
    void markDeep()
    {
        if (!marked) {
            marked = true      // sich selbst markieren
            symps.each { 
                it.markDeep()  // rekursiv weiter markieren
            }
        }
    }
}

List createChatons()
{
    Chaton a = new Chaton(name:"A")
    Chaton b = new Chaton(name:"B")
    Chaton c = new Chaton(name:"C")
    Chaton d = new Chaton(name:"D")
    Chaton e = new Chaton(name:"E")
    Chaton f = new Chaton(name:"F")
    Chaton g = new Chaton(name:"G")
    Chaton h = new Chaton(name:"H")
    
    a.symps = [b, e]
    b.symps = [c]
    c.symps = [d, g]
    d.symps = [c]
    e.symps = [f]
    f.symps = [b, e, g]
    g.symps = [h]
    h.symps = [d]
    
    return [a, b, c, d, e, f, g, h]
}

List chatons = createChatons()

for (chaton in chatons) {
    chatons.each { it.marked = false }
    chaton.markDeep()
    List result = chatons.findAll { !it.marked }
    println "${chaton.name}: ${result*.name}"
}

Ausgabe

Code:

A: []
B: ["A", "E", "F"]
C: ["A", "B", "E", "F"]
D: ["A", "B", "E", "F"]
E: ["A"]
F: ["A"]
G: ["A", "B", "E", "F"]
H: ["A", "B", "E", "F"]

J.U.B. · Jun 14, 2007

@ CDW:

Diese Aufgabe hätte ruhig Schwierigkeit: 1 bekommen könne (oder evtl auch 2).

@ Ivan:

Mach das selbe mal mit benutzereingabe für die sympatischen Chatonen.

Ivan Dolvich · Jun 14, 2007

Die Benutzereingabe habe ich mir jetzt gespart weil das nichts spannendes ist, und von das eigentliche Problem (den Graphen abbilden und durchsuchen) abweicht.

mauralix · Jun 16, 2007

Mir gefällt diese Aufgabe. Erinnert mich voll ans echte Leben. In meiner Gemeinde leben wohl viele Chatonen.

CDW · Jun 8, 2008

das ganze mal in Prolog (SWI). Und ja, ich lerne es gerade

Code:

sympatisch(a,b).
sympatisch(a,e).
sympatisch(b,c).
sympatisch(c,d).
sympatisch(c,g).
sympatisch(d,c).
sympatisch(e,f).
sympatisch(f,b).
sympatisch(f,e).
sympatisch(f,g).
sympatisch(g,h).
sympatisch(h,d).
chatone(X):-member(X,[a,b,c,d,e,f,g,h]).

fatale_weiterleitung(Laesterer,Opfer,_):-
         Opfer=Laesterer.
fatale_weiterleitung(Laesterer,Opfer,Laesterkette):-  
         sympatisch(Laesterer,Freund),          
         not(member(Freund,Laesterkette)),     
         fatale_weiterleitung(Freund,Opfer,[Freund|Laesterkette]),!.  

darf_laestern(Chatone, OpferListe):-
         findall(Opfer, (chatone(Opfer),       
         not(fatale_weiterleitung(Chatone,Opfer,[]))),    
         OpferListe).          

laesterListe(Chatone,Liste):-
         chatone(Chatone),darf_laestern(Chatone,Liste).

Code:

sympatisch(a,b).
sympatisch(a,e).
sympatisch(b,c).
sympatisch(c,d).
sympatisch(c,g).
sympatisch(d,c).
sympatisch(e,f).
sympatisch(f,b).
sympatisch(f,e).
sympatisch(f,g).
sympatisch(g,h).
sympatisch(h,d).
chatone(X):-member(X,[a,b,c,d,e,f,g,h]).

%die weiterleitung ist fatal, wenn der Laesterer das Opfer ist ;)
fatale_weiterleitung(Laesterer,Opfer,_):-Opfer=Laesterer.
fatale_weiterleitung(Laesterer,Opfer,Laesterkette):-   %oder: wenn der Laesterer
         sympatisch(Laesterer,Freund),          %einen Freund hat
         not(member(Freund,Laesterkette)),      % (der die Nachricht noch nicht bekommen hatte)
         fatale_weiterleitung(Freund,Opfer,[Freund|Laesterkette]),!.  % und der sie fatal weiterleiten könnte!

%ein Chatone darf laestern, wenn das Opfer nichts davon mitbekommt
darf_laestern(Chatone, OpferListe):-
         findall(Opfer,          %es gibt eine Liste vom Typ "Opfer"
         (chatone(Opfer),        %darin stehen alle, an die keine Nachrichten von
         not(fatale_weiterleitung(Chatone,Opfer,[]))),     %einem Chatonen weitergeleitet werden
         OpferListe).            %und diese Liste heisst "OpferListe" ;)

laesterListe(Chatone,Liste):-
         chatone(Chatone),darf_laestern(Chatone,Liste).

ausgabe:

Code:

?- laesterListe(Chatone,Opfer).
Chatone = a,
Opfer = [] ;
Chatone = b,
Opfer = [a, e, f] ;
Chatone = c,
Opfer = [a, b, e, f] ;
Chatone = d,
Opfer = [a, b, e, f] ;
Chatone = e,
Opfer = [a] ;
Chatone = f,
Opfer = [a] ;
Chatone = g,
Opfer = [a, b, e, f] ;
Chatone = h,
Opfer = [a, b, e, f] ;

CDW · Aug 15, 2008

Code:

sym(a,[b,e]).                                                                   %Chatonenliste
sym(b,[c]).
sym(c,[d,g]).
sym(d,[c]).
sym(e,[f]).
sym(f,[b,e,g]).
sym(g,[h]).
sym(h,[d]).
chatone(X):-sym(X,_).

schreibt_an(X,X,_).                                                             %X schreibt dann an Y, wenn Y in der Kontaktliste ist
schreibt_an(X,Y,Memlist):- sym(X,List),(member(Y,List)                          % oder: "indirekt", wenn Z aus der Kontaktliste
                      ;                                                         % es weiterleitet und es irgendwann
                      member(Z,List),\+member(Z,Memlist),                       %bei Y ankommt
                      schreibt_an(Z,Y,[Z|Memlist])),!.
                                                                                %Chatone X darf über jene Chatonen
laestern(X):- findall(_,(chatone(C),                                            %laestern, die sein Schreiben nicht
                      \+schreibt_an(X,C,[]),ausgabe(C)),_).                     %bekommen!
laestern:-    findall(_,(chatone(C),                                            %pruefe alle chatonen
                      kopfzeile(C),laestern(C)),_).

ausgabe(C):-format('~k ',[C]).
kopfzeile(H):-nl,format('Chatone ~k darf laestern ueber:',[H]).

Startbar mit "laestern.". Einzelne Chatonen prüfen: laestern(Chatonenname).
Erweitern: einfach in die sympatic - Übersicht was hinzufügen/löschen, nach dem Muster: sym(Chatonenname,[Sympatisch,Sympatisch ...]).
Nicht-Isoprädikate: member,format
Ausgabe:

1163 ?- laestern.

Chatone a darf laestern ueber:
Chatone b darf laestern ueber:a e f
Chatone c darf laestern ueber:a b e f
Chatone d darf laestern ueber:a b e f
Chatone e darf laestern ueber:a
Chatone f darf laestern ueber:a
Chatone g darf laestern ueber:a b e f
Chatone h darf laestern ueber:a b e f
true.

MontyPerl · Nov 26, 2008

Auch prolog, mit hardgecodeten Sympathiebeziehungen und canTalkAbout Prädikat:

Code:

symp(a, b).
symp(a, e).

symp(b, c).

symp(c, d).
symp(c, g).

symp(d, c).

symp(e, f).

symp(f, b).
symp(f, e).
symp(f, g).

symp(g, h).

symp(h, d).



messageReaches(A, B, _):-
    symp(A, B).
messageReaches(A, C, L):-
    symp(A, B),
    \+ member(B, L),
    messageReaches(B, C, [B|L]).

messageReaches(A, B):-
    messageReaches(A, B, [A]).


canTalkAbout(Chaton, Victim):-
    Chatonen = [a, b, c, d, e, f, g, h],
    member(Victim, Chatonen),
    \+ Chaton = Victim,
    \+ messageReaches(Chaton, Victim).

Code:

?- canTalkAbout(c, X).

X = a ;

X = b ;

X = e ;

X = f ;

edit: Jahre später....
Hier mal eine kleine C Lösung:

Code:

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    char ID;
    int visited;
    struct node *links[9];
} node;

void conn(node *n, const char *dests, node **all);
void traverse(node *n, char senderID);
void canTalk(node *s, node **all);

int main(void) {
    /*   Dem Chatonen      sind sympathisch:
     *   A                 B E
     *   B                 C
     *   C                 D G
     *   D                 C
     *   E                 F
     *   F                 B E G
     *   G                 H
     *   H                 D
     */
    node a = { 'a', 0, { NULL } };
    node b = { 'b', 0, { NULL } };
    node c = { 'c', 0, { NULL } };
    node d = { 'd', 0, { NULL } };
    node e = { 'e', 0, { NULL } };
    node f = { 'f', 0, { NULL } };
    node g = { 'g', 0, { NULL } };
    node h = { 'h', 0, { NULL } };

    node all = { '\0', 0, { &a, &b, &c, &d, &e, &f, &g, &h, NULL } };

    conn(&a, "be",  all.links);
    conn(&b, "c",   all.links);
    conn(&c, "dg",  all.links);
    conn(&d, "c",   all.links);
    conn(&e, "f",   all.links);
    conn(&f, "beg", all.links);
    conn(&g, "h",   all.links);
    conn(&h, "d",   all.links);

    int i;
    for (i = 0; all.links[i]; i++) {
        canTalk(all.links[i], all.links);
    }
    return 0;
}

void conn(node *n, const char *dests, node **all) {
    int i, j, k;
    k = 0;
    for (i = 0; dests[i]; i++) {
        for (j = 0; all[j]; j++) {
            if (dests[i] == all[j]->ID) {
                n->links[k] = all[j];
                k++;
            }
        }
    }
    n->links[k] = NULL;
    return;
}

void canTalk(node *s, node **all) {
    int i;
    for (i = 0; s->links[i]; i++) {
        traverse(s->links[i], s->ID);
    }
    s->visited = 1;

    printf("%c can talk about:\t", s->ID);
    for (i = 0; all[i]; i++) {
        if (!all[i]->visited) {
            printf("%c ", all[i]->ID);
        }
        all[i]->visited = 0;
    }
    printf("\n");

    return;
}

void traverse(node *n, char senderID) {
    n->visited = 1;
    if (n->ID == senderID) {
        return;
    }
    int i;
    for (i = 0; n->links[i]; i++) {
        if (! n->links[i]->visited) {
            traverse(n->links[i], senderID);
        }
    }
    return;
}

Lesco · Jun 17, 2009

Hier noch eine Variante in Haskell:

Code:

import Control.Arrow
type Persons a = [(a,[a])]

persons = [("a",["b","e"])
          ,("b",["c"])
          ,("c",["d","g"])
          ,("d",["c"])
          ,("e",["f","g"])
          ,("f",["b","e","g"])
          ,("g",["h"])
          ,("h",["d"]) ]

isPath :: Ord a => Persons a -> a -> a -> [a] -> Bool
isPath ps src dst visited
    | src == dst = True
    | src `elem` visited = False
    | otherwise = any (\src' -> isPath ps src' dst (src:visited)) . maybe [] id . lookup src $ ps

canTalkAbout :: Ord a => Persons a -> a -> a -> Bool
canTalkAbout ps a b = not . isPath ps a b $ []

potTargets :: Ord a => Persons a -> a -> [a]
potTargets ps a = filter (canTalkAbout ps a) . map fst $ ps

fullList ps = map ((id &&& potTargets ps) . fst) ps