PHP challenge 6: Leksikon sortering (update 2)

[peros2k]

Trikset som ble brukt heter dynamisk programmering, man bygger opp mange små løsninger underveis.. La oss ta et enkelt eksempel..

 

 

1 2 3 4

5 6 7 8

9 1 2 3

4 5 6 7

 

La oss begynne på andre rad og ta for oss hvert element..

Vi begynner med 5.. hva er beste måten vi kan nå 5 på? Vi kan nå 5 fra 1 og 2 på raden ovenfor.. Med andre ord, beste oppsamlet verdi til 5 er til nå 5+2.. Så nå vet vi at i første rute på andre rad kan vi få totalt 7.

 

6 kan nås fra 1,2,3.. 3 er klart best.. 6+3 er maks verdi vi kan nå denne ruten på. 7 kan nås fra 2,3,4.. best er 4+7=11.. 8 kan nås fra 3 og 4.. best er 4+8=12..

 

Vi har nå samlet opp verdiene.

 

1 2 3 4

7 9 11 12

 

Neste rad.. 9.. hva er beste mulig oppsamlede sum man kan få til nå. Jo, 9 + max(7,9) fra raden ovenfor.. Neste element er 1.. kan nås fra 7,9,11.. osv..

 

1 2 3 4

7 9 11 12

18 12 14 15 <-- beste sum vi kan oppnå på elementene på 3. rad, vi vet ikke hvordan i kommer oss dit, men vi vet det er mulig..

 

Siste rad:

1 2 3 4

7 9 11 12

18 12 14 15

22 23 21 22

 

Beste rute igjennom kvadratet har sum 23.. Vi vet ikke hvor ruten går, men vi vet den finnes og at den har denne verdien.

 

Som en liten ekstra, det går an å regne ut ruten fra resultatet vi nettopp fant, ved hjelp av:

// $data er opprinnelig 2d-array..
// $values er utregnet max for hvert nivå som over..
function findroute($data, $values) {

$row = count($values) - 1;
$elem = array_search(max($values[$row]), $values[$row--]);

$path[] = $elem;

while ($row >= 0) {
	foreach (array(-1,0,1) as $offset) {
		if (($values[$row][$elem-$offset] + $data[$row+1][$elem])  == $values[$row+1][$elem]) {
			$elem = $elem - $offset;
			$path[] = $elem;
			$row--;
		}
	}
}

print_r(array_reverse($path));

}

Endret 15. desember 2007 av peros2k

[grimjoey]

aha. ikke dumt. takk for forklaringen.

[MC2]

Hvis det blir enda en oppgave snart så kan jeg dessverre ikke benke den heller. Jeg skal hjem å feire jul med familien, så noen får overta.

 

Men hva med en liten (enkel) oppgave i mellomtiden? Feks. leksikon sortering av lange arrays bestående av strenger? De fleste algoritmene som da ble utivklet i første sorteringsoppgaven vil være ganske ueffektive på lange arrays, og de fleste av de vil ikke fungere på strenger heller. God ide? Dårlig ide?

[MC2]

Nå har ny oppgave blitt gitt ut (sjekk første posten).

 

Denne er også hostet av peros2k, så alle bidragene sendes til han på pm.

 

Og, god jul mens vi er i gang!

[grimjoey]

er det meningen at funksjonen skal printe ut resultatet men beholde key->value assosiasjon som natsort? eller skal funksjonen returnere et array med sorterte elementer i form av naturlig sortering?

[MC2]

er det meningen at funksjonen skal printe ut resultatet men beholde key->value assosiasjon som natsort? eller skal funksjonen returnere et array med sorterte elementer i form av naturlig sortering?

Sånn, det var noe jeg hadde glemt å spesifisere. Jeg synes at vi kan droppe key-value assosiasjonene, ellers burde funksjonen returnere den sorterte arrayen, sortert etter natural order reglene.

[Kagee]

Så eksempler på ting vi skal sortere er f.eks

123
abc123
AB12cd
ab1dcd

 

Skal de da sorteres aB3, Ab3 eller ... ?

[MC2]

Så eksempler på ting vi skal sortere er f.eks

123
abc123
AB12cd
ab1dcd

 

Skal de da sorteres aB3, Ab3 eller ... ?

Det er bare å sortere de slik som natsort sorterer de, borsett fra at du slipper å bry deg om key-value relasjoner.

 

Jeg anbefaler at dere graver litt i php manualen (finnes mange fancy funksjoner som kommer at spare dere masse tid)

Endret 20. desember 2007 av MC2

[peros2k]

Ser ut som om folk har hatt det travelt i julen, har ikke fått noen bidrag til challenge 6.

[grimjoey]

sendte bidraget mitt til mc2 tidligere. glemte å resende til deg. har sendt deg det nå

Endret 29. desember 2007 av grimjoey

[peros2k]

Ok, da har vi iallfall et bidrag, noen flere som også har sendt til mc2?

[MC2]

Ok, da har vi iallfall et bidrag, noen flere som også har sendt til mc2?

Oj, jeg har ikke fått inn noe. Tror vi må utsette denne til etter nyttår eller hvis folk har forslag til artigere oppgaver er det bare å poste dem.