Kanibali i misionari

Zadatak

Rješiti problem prijevoza kanibala i misionara. Na obali neke široke rijeke postoji čamac koji prevozi kanibale i misionare na drugu stranu obale. Kapacitet čamca je 7 putnika. U čamcu moraju biti najmanje 3 putnika da on može krenuti. U čamcu ne smije biti više kanibala od misionara, dok su sve ostale kombinacije putnika dozvoljene (npr. u čamcu mogu biti i samo kanibali). Kanibali i misionari dolaze sa obje strane rijeke. Jedan misionar dolazi svake dvije sekunde, a kanibal svake sekunde (odabir obale je slučajan). Nakon što pređu preko rijeke putnici odlaze dalje (nema ih više u sustavu). U sustavu neka postoji samo jedan čamac, a svaki misionar i kanibal predstavljaju po jednu dretvu/proces. Čamac je također jedna dretva/proces koji pri svakom prijelazu ispisuje koga prevozi (npr. "Prevezeni: misionar, kanibal, misionar, misionar"). Pretpostaviti da je čamac u početku na desnoj obali. Nakon što se u čamcu popune tri (ili više) mjesta, čamac pričeka još sekundu, u kojoj se još netko može ukrcati u čamac, prema navedenim pravilima, te potom kreće preko rijeke - što traje dvije sekunde. Dretve/procese misionare i kanibale stvara pomoćna dretva/proces. Ispravno sinkronizirati dretve/procese kanibale, misionare i čamac.

Primjer ispisa

Legenda: M-misionar, K-kanibal, C-čamac,
         LO-lijeva obala, DO-desna obala
         L-lijevo, D-desno

C: prazan na desnoj obali
C[D]={} LO={} DO={}

M1: došao na lijevu obalu
C[D]={} LO={M1} DO={}

K1: došao na desnu obalu
C[D]={} LO={M1} DO={K1}

K1: ušao u čamac
C[D]={K1} LO={M1} DO={}

K2: došao na lijevu obalu
C[D]={K1} LO={M1 K2} DO={}

M2: došao na desnu obalu
C[D]={K1} LO={M1 K2} DO={M2}

M2: ušao u čamac
C[D]={K1 M2} LO={M1 K2} DO={}

K3: došao na desnu obalu
C[D]={K1 M2} LO={M1 K2} DO={K3}

M3: došao na desnu obalu
C[D]={K1 M2} LO={M1 K2} DO={K3 M3}

M3: ušao u čamac
C[D]={K1 M2 M3} LO={M1 K2} DO={K3}

K3: ušao u čamac
C[D]={K1 M2 M3 K3} LO={M1 K2} DO={}

C: tri putnika ukrcana, polazim za jednu sekundu
C[D]={K1 M2 M3 K3} LO={M1 K2} DO={}

M4: došao na desnu obalu
C[D]={K1 M2 M3 K3} LO={M1 K2} DO={M4}

M4: ušao u čamac
C[D]={K1 M2 M3 K3 M4} LO={M1 K2} DO={}

K4: došao na desnu obalu
C[D]={K1 M2 M3 K3 M4} LO={M1 K2 K4} DO={}

C: prevozim s desne na lijevu obalu: K1 M2 M3 K3 M4

K5: došao na desnu obalu
C[D]={K1 M2 M3 K3 M4} LO={M1 K2 K4} DO={K5}

M5: došao na lijevu obalu
C[D]={K1 M2 M3 K3 M4} LO={M1 K2 K4 M5} DO={K5}

C: preveo s desne na lijevu obalu: K1 M2 M3 K3 M4
C: prazan na lijevoj obali
C[L]={} LO={M1 K2 K4 M5} DO={K5}

M1: ušao u čamac
C[L]={M1} LO={K2 K4 M5} DO={K5}

K2: ušao u čamac
C[L]={M1 K2} LO={K4 M5} DO={K5}

M5: ušao u čamac
C[L]={M1 K2 M5} LO={K4} DO={K5}

C: tri putnika ukrcana, polazim za jednu sekundu

K5: ušao u čamac
C[L]={M1 K2 M5 K4} LO={} DO={K5}

C: prevozim s lijeve na desnu obalu: M1 K2 M5 K4
...