Маленька гра

[b0rg]

http://freeweb.siol.net/danej/riverIQGame.swf

Задача (в переводе с японьского):

Надо перевезти всех на другой берег, НО!

1. Полицейский не может оставлять преступника с людьми одного.

2. Папа не может оставлять сыновей одних с мамой, а мать — дочерей с

папой.

3. Дети одни не могут плавать на плоту.

4. Плот сам по себе не возвращается и берет на борт не более 2-ух

человек.

Задачу дают при приеме на работу в Японии.

Нажимаем большую круглую кнопку и пытаемся перевезти...

[Zevs_Isver]

подозреваю что решется так же как и задача о перевозе волка-козы-капусты

только на больше итераций, так как больше клиентов для перевозки

[Shkoder]

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

[sku]

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

Все правильно... але це не наш підхід

sub check {

my $s=$_[0];

return 1 if $s eq "C";

return 0 if index($s,"C")>=0 and index($s,"P")<0;

return 0 if index($s,"d")>=0 and index($s,"F")>=0 and index($s,"M")<0;

return 0 if index($s,"s")>=0 and index($s,"M")>=0 and index($s,"F")<0;

return 1;

}

sub checkl {

my $s=$_[0];

return 0 if !check($s);

return 0 if index($s,"P")<0 and index($s,"C")<0 and index($s,"F")<0 and index($s,"M")<0;

return 1;

}

sub del {

(my $s, my $i)=@_;

my $res="";

$res.=substr($s, 0, $i) if $i>=1;

$res.=substr($s, $i+1) if $i<length($s)-1;

return $res;

}

sub equal {

(my $s1, my $s2)=@_;

my @a1=(); push @a1, substr($s1,$_,1) for (0 .. length($s1)-1);

my @a2=(); push @a2, substr($s2,$_,1) for (0 .. length($s2)-1);

@a1=sort {$a cmp $b} @a1;

@a2=sort {$a cmp $b} @a2;

return join("",@a1) cmp join("",@a2);

}

sub test {

(my $s1, my $s2, my $t, my $r)=@_;

foreach my $s (@arr) {

return if !equal($s, $t.$s1);

}

push @arr, $t.$s1;

# print "$s1\t$s2\t$t\n";

if ($s1 eq "") {

print $_."\n" foreach @{ $r };

$ret=1;

}

return if $ret;

if ($t==0) {

for my $i (0 .. length($s1)-1) {

for my $j ($i+1 .. length($s1)-1) {

my $s=$s1;

my $l=substr($s, $j, 1);

$s=del($s, $j);

$l.=substr($s, $i, 1);

$s=del($s, $i);

my $rr=[ @{ $r } ]; push @{ $rr }, "$s:\#$s2$l";

test($s, $s2.$l, 1, $rr) if check($s) and checkl($l) and check($s2.$l);

}

my $s=$s1;

my $l=substr($s, $i, 1);

$s=del($s, $i);

my $rr=[ @{ $r } ]; push @{ $rr }, "$s:\#$s2$l";

test($s, $s2.$l, 1, $rr) if check($s) and checkl($l) and check($s2.$l);

}

}

elsif ($t==1) {

for my $i (0 .. length($s2)-1) {

for my $j ($i+1 .. length($s2)-1) {

my $s=$s2;

my $l=substr($s, $j, 1);

$s=del($s, $j);

$l.=substr($s, $i, 1);

$s=del($s, $i);

my $rr=[ @{ $r } ]; push @{ $rr }, "$s1$l\#:$s";

test($s1.$l, $s, 0, $rr) if check($s1.$l) and checkl($l) and check($s);

}

my $s=$s2;

my $l=substr($s, $i, 1);

$s=del($s, $i);

my $rr=[ @{ $r } ]; push @{ $rr }, "$s1$l\#:$s";

test($s1.$l, $s, 0, $rr) if check($s1.$l) and checkl($l) and check($s);

}

}

}

@arr=();

test("MddFssPC", "", 0, []);

видає на виході:

MddFssCP#|

MddFss|#CP

MddFssP#|C

MdFss|#CPd

MdFssPC#|d

FssPC|#ddM

FssPCM#|dd

ssPC|#ddMF

ssPCF#|ddM

ssF|#ddMCP

ssFM#|ddCP

ss|#ddCPMF

ssF#|ddCPM

s|#ddCPMFs

sPC#|ddMFs

C|#ddMFsPs

CP#|ddMFss

|#ddMFssPC

M-mother, F-father, d-doughter, s-son, P-ecilopp, C-crime

Не бийте за неоптимізованість, писав "на швидкість", можна сказати

[Shkoder]

как думаешь, почему человек до сих пор выигрывает у компа в шахматы? он просто думает головой, а не перебирает все возможные варианты в поиске правильного а за iq своего компа я и так спокоен

[sku]

Щось це мені нагадує анекдот про підхід до проблеми гуманітарія і математика. А в мене все-таки математична освіта.

І в термін "думати головою" напевне ж входить підмножина "придумати програму, котра порахує за тебе"

[noven]

якась запроста задача для написання будьякого коду.

Шкодер +1