PHP challenge 6: Leksikon sortering (update 2)

[JohndoeMAKT]

Slik jeg tenkte: For hvert hopp har du tre valg ( ser bort fra kantene ) så det blir 3^9 for hver kolonne pluss den øverste rekka.

 

((10+(10*(3^9)))*0.8)=157472

 

(Når jeg kom frem til tallet lengre oppe i tråden brukte jeg 3^10 som nok er feil. 0.8 er for å redusere i forhold til katene, men 0.8 er nok mest sannsynlig altfor lite)

 

Vi har nok alle samme svar (nå) og det er bare kuttet for sidene som gir variasjonen på 70000.

Endret 30. november 2007 av JohndoeMAKT

[Peter]

*snip*

Kul oppgave!

[MC2]

Sorry folkens. Jeg har vært alt for opptatt i det siste. Har jobbet 10-12 timer daglig og det ser ut å bli sånn fremover til jul. Hvis noen har lyst å vikaere for meg så hadde det vært kjempe fint!

[peros2k]

Vikarierer for deg jeg da.. Gidder du oppdatere første post?

Oppgaven er som følger:

 

Gitt et n x n kvadrat bygd opp av tilfeldige tall fra 0 til 99, lag en funksjon som regner ut høyest oppnålige sum dersom man beveger seg igjennom kvadratet fra topp til bunn etter følgende regler:

 

* Startposisjon i topp rad er helt fri.

* Det er lov å flytte seg til tallet direkte under det gjeldende.

* Det er lov å flytte seg til tallet under til høyre ( tenk array-index + 1 i raden under)

* Det er lov å flytte seg til tallet under til venstre ( array-index - 1 i raden under)

 

Eksempel på 6x6 kvadrat:

1 2 3 [b]4[/b] 5 6
7 8 [b]9[/b] 0 1 2
3 4 5 [b]6[/b] 7 8
9 0 1 2 [b]3[/b] 4
5 6 7 8 [b]9[/b] 0
1 2 3 4 5 [b]6[/b]

Funksjonen skal her returnere 4+9+6+3+9+6 = 37

 

Se vedlegg for 4 eksempler på datasett.. 1000x1000, 100x100, 10x10 og 6x6.

 

Hvordan lese datasett?

Følgende funksjon returnerer et 2d array bygd opp som følger: $data[radnummer.. 0 til n-1][element i rad.. 0 til n-1]

function readdata($i) {
foreach (explode("\n", trim(file_get_contents($i))) as $line)
	$data[] = explode(" ", trim($line));

return $data;
}

$data = readdata("10.txt");
print_r($data);

Konkurransen:

Konkurransen deles i to klasser, en for 10x10 og en for 100x100 datasettene, siden man med enkelte fremgangsmåter antagelig ikke vil ha sjanse på 100x100 datasettet med tanke på hastighet. Et 1000x1000 datasett er også vedlagt for de som vil prøve seg på det.

 

Kriterier innen hver klasse er:

1) Korrekt løsning.

2) Hastighet.

3) Ved lik hastighet så prøves større datasett (f.eks 20x20)..

 

Tidsfrist:

Ca en uke, kl 21:00 søndag 9.desember.

 

Send løsning til meg på PM.

inndata.zip

Endret 1. desember 2007 av peros2k

[MC2]

Sånn, da er første post oppdatert. Takker

[peros2k]

Svarene på de 4 eksempel datasettene er forøvrig:

 

6x6 : 37

10x10 : 806

100x100 : 8227

1000x1000 : 81689

 

(med forbehold om at jeg har kodet noe feil, men tror ikke det)

 

Og en endring.. Tidsfristen til søndag er selvfølgelig 9. desember, ikke 8.

Endret 1. desember 2007 av peros2k

[Kagee]

Kan tallene hardkodes, eller er innlesningen en del av oppgaven?

[peros2k]

Kommer til å benke med forskjellige datasett (tilfeldig generert), så må ha en form for innlesing. Det er jo uansett bare å kopiere funksjonen fra oppgaven og så har du innlesing på plass som gir deg tallene i et 2d-array.

[Kagee]

Det er en feil med datasettene dine:

I alle filene er det 20x større sjanse for at et tall er 1-9.

 

Er dette meninga?

 

Test med følgende kode

<?php
$file = file_get_contents('1000.txt');
for ($i = 1; $i <= 99; $i++) {
echo $i . " - " . substr_count($file, $i) . "\n";
}
?>

[peros2k]

Neida.. det er fordi substr_count teller 1-9 også når de er en del av et større tall..

 

prøv: print substr_count("90 9 91 92 93", "9");

 

du får her 5..

 

Tallene ble forøvrig generert med følgende kode, så kan dere bruke den til å lage flere datasett til å teste med..

$dim er størrelsen på kvadratet.. $max angir intervallet på tallene, tilfeldig tall mellom 0 og $max

function gen_square($dim,$max) {
       for ($i = 0; $i < $dim; $i++) {
               for ($y = 0; $y < $dim; $y++)
                       $data .= rand(0,$max) . " ";
               $data .= "\n";
       }
       return $data;
}

print gen_square(1000, 99);

[Kagee]

Aha - så klart - min feil

[dabear]

Bra dere at konkurransen har blitt fortsatt sia tråden min

 

Har jeg lov til å bruke pcntl_fork på den siste oppgaven der?

 

Har jeg lov til å bruke php 5 ony-features? tenker på foreach($foos as &$bar)

Endret 1. desember 2007 av dabear

[Ernie]

Har jeg lov til å bruke pcntl_fork på den siste oppgaven der?

Jeg synes ikke det En annen ting er om du faktisk tjener på det. Det er trossalt prosesser, ikke tråder.

Har jeg lov til å bruke php 5 ony-features? tenker på foreach($foos as &$bar)

Kan ikke se noen grunn til at det ikke skal være lov? PHP5 er ikke akkurat direkte ny. Endret 1. desember 2007 av Ernie

[peros2k]

Har jeg lov til å bruke pcntl_fork på den siste oppgaven der?

Ja, så lenge du holder deg til et fornuftig antall barn, jeg vil ikke ha noe som ligner på en fork-bomb

 

(tror egentlig du ikke kommer til å tjene så mye på det som ernie sier)

 

Har jeg lov til å bruke php 5 ony-features? tenker på foreach($foos as &$bar)

Ja, jeg kommer til å benke på php 5.2.1. Endret 1. desember 2007 av peros2k

[dabear]

Hva om jeg kommer til $row[0] og skal gå til neste rad. vil da kun $nextrow[0] og $nextrow[1] være lovlige? Sia å gå til venstre ikke gir noe resultat ($nextrow[-1]). Eller skal $nextrow[-1] være lik $nextrow[count($nextrow)] ? Samme spørsmål når det gjelder ytregrenser på høyre side.

[peros2k]

Hva om jeg kommer til $row[0] og skal gå til neste rad. vil da kun $nextrow[0] og $nextrow[1] være lovlige? Sia å gå til venstre ikke gir noe resultat ($nextrow[-1]). Eller skal $nextrow[-1] være lik $nextrow[count($nextrow)] ? Samme spørsmål når det gjelder ytregrenser på høyre side.

 

Når man står på kantene vil egentlig bare elementet rett under, og elementet på skrått innover som ikke går utenfor kanten være gyldig ja.. Men, det er egentlig ikke så farlig om du går over kanten, siden man da vil få verdi 0 da det ikke er noe der.. og 0 har ingen innvirkning på en summering. (ruten som gikk over kanten vil selvfølgelig bli en dårlig rute)

[Peter]

Er man pålagt å gjøre innlesingen først, eller kan man gjøre begge deler samtidig?

[peros2k]

Er man pålagt å gjøre innlesingen først, eller kan man gjøre begge deler samtidig?

 

Den forstod jeg ikke helt? Du har jo ikke noe data å jobbe på før du har lest det inn? Og innlesingen er bare å kopiere den funksjonen fra oppgaven, kjøre den på en av datafilene og så får man dataen (2d array) som funksjonen du lager skal ta som input.

 

<?php

function readdata($file) {
       foreach (explode("\n", trim(file_get_contents($file))) as $line)
               $data[] = explode(" ", trim($line));

       return $data;
}

function findmax($data) {

       ... denne skal du lage, gjør noe her....

       return $max;
}

$data = readdata("10.txt");
print findmax($data);
?>

 

Bare for å gjøre det helt klart, det man skal lage er findmax($data) funksjonen her..

[Peter]

Man trenger ikke lese inn HELE filen for å ha noe å jobbe med, man kan f.eks. jobbe med èn og èn linje og på den måten frigjøre minne underveis samtidig som man slipper å loope flere ganger.

[peros2k]

Man trenger ikke lese inn HELE filen for å ha noe å jobbe med, man kan f.eks. jobbe med èn og èn linje og på den måten frigjøre minne underveis samtidig som man slipper å loope flere ganger.

Ah, ja, det er ingen problem å gjøre det slik hvis du vil lage din egen innleser. Nå skal det sies at selv 1000x1000 krever bare et par mb minne.