Some reader of my blog asked me last week, what I actually did for work here in Singapore, because all the posts on this blog seem to relate to travel, parties and so on. Well, here’s a little insight.
One of my courses here at NTU is about artificial intelligence: Problem solving, game playing, reasoning and so on. It’s quite interesting! This subject also requires us to do some coursework: students have to come up with a formal problem formulation and a solution for the Sheep-and-Wolves1) problem. For those of you who want to try, here’s the description:
“Once upon a time, three sheep and three wolves wandered through some far, far away country and came across a river. Neither of the animals could swim, so they walked up and down the riverbank, not knowing how to cross it. After a while, however, the wolves spotted a small boat on the riverside, just spacious enough for two animals. The sheep were worried. ‘The boat can only carry two animals,’ the first said. ‘Not only that, but it cannot cross the river by itself. At least one animal has to paddle,’ the second sheep added. ‘Most importantly,’ the third sheep said, ‘if the wolves outnumber us on any side of the river, they will eat us!’ Now, can you help the sheep and find a way to carry all the animals safely across the river?”
Spoiler warning… parts of the solution follow!
After trying to figure out states, operators and branching factors for a while, I wondered how the situation would look like if we had, say, seven wolves and a bigger boat? Will there always be solutions? So I decided to sit down and write a program which solves the problem. 300 lines of code later, my computer told me that it takes 197 steps to carry 100 sheeps and 100 wolves over a river in a boat of size four. The solution itself is a little disappointing, however… every instance of the problem can be solved with a boat of size four, by simply ferrying two pairs of animals over the river, then one pair back, then fetch another sheep+wolf, etc.
Anyway, the programming was fun. If you want to try it out yourself, grab the code, then type make followed by ./sheep_wolves in a unix shell. And if by now, you think I’m a little crazy… it must be in the family!2)
1) Also known under the less politically correct name Cannibals-and-Missionaries Problem
2) Merci David für di wunderschön Kommentar!
sheeps et wöuf
yea that’s not the only problem which has a disapointing end when you try to extend it to the limits.
Und übrigens apropos multilingual. uf mire site hanis probiert z strukturiere, aber viu schribe när ire andere sprach aus dassi dr text läse, franz-> änglisch , änglisch -> dütsch, schwedisch -> franz. hie isches ja nid so tragisch.
Und spam trotz am captcha?
Re: sheeps et wöuf
In Kommentär han i bis itz ke Spam übercho, das Captcha schiint auso relativ guet z’funktioniere… vilicht isches z’beste, wenn i dr Spamfilter für Kommentär deaktiviere. Problematisch si eher d’Trackbacks. I finde ds System zwar genial, aber es isch halt für Maschine gmacht und drum o es gfundnigs Frässe für Spammer. Eh ja, mues no chli pröble, bis i e gueti Lösig finde.
Grüessli, Jonas