PHP challenge 6: Leksikon sortering (update 2)

[Kagee]

... men jeg må dessverre melde at jeg har gått tom for oppgaver som ikke er alt for vanskelige, så det er bare å brainstorme ideer...

 

Nei! Var det ikke det som skjedde med Dabers's tråd?

 

Jeg så noen fine løsninger som antagelig ville gjort mitt script raske svarene her, f.eks Daniels "break n;".

[jeg_lyver_mye]

Ville ikke den kanskje gått litt fortere også hvis man brukt hash() fremfor md5()? Mener å ha lest at det er raskere...

[peros2k]

Ah, ikke rart kagee stakk av med den, han tok enslige tegn først. Jeg tok dem sist, samt det var mye tall, de hadde jeg langt bak :/

 

Litt ubalansert testdata egentlig, hvis man kjører tall først så vinner man jo på 5 av 8 tester.. og enslige tegn først så vinner man 4 av 8.. men men.

 

For inspirasjon til oppgaver kan du jo se på http://projecteuler.net/index.php?section=problems ..

[ze5400]

Hva med å finne et gitt antall siffer av π på kortest mulig tid?

[Vikdal]

Ah, ikke rart kagee stakk av med den, han tok enslige tegn først. Jeg tok dem sist, samt det var mye tall, de hadde jeg langt bak :/

 

Litt ubalansert testdata egentlig, hvis man kjører tall først så vinner man jo på 5 av 8 tester.. og enslige tegn først så vinner man 4 av 8.. men men.

Jeg satt å tenkte på akkurat det samme.

Hva med å kjøre en liten test til hvor du tester ytterpunktene og midtverdien bare? Tror resultatet kan bli veldig annerledes da.

altså teste med følgende: a - aa - aaa - 9 - 99 - 999 - og midtpunktet, elns. Vil ikke det gi annerledes resultat siden det da vil bli likt for alle

[MC2]

Vi kan godt ta å teste noen flere verdier, men som sagt gikk den benkingen ganske fort pga. mye annet på programmet den dagen. Noen som vil foreslå en rekke testverdier?

[peros2k]

Vi kan godt ta å teste noen flere verdier, men som sagt gikk den benkingen ganske fort pga. mye annet på programmet den dagen. Noen som vil foreslå en rekke testverdier?

Hva med 100 helt random verdier?

<?php
$val = array_merge(array(""), str_split("abcdefghijklmnopqrstuvwxyz0123456789"));

srand(time());
for ($i = 0; $i < 100 ; $i++)
       $arr[$i] = $val[rand(0, count($val))] . $val[rand(0, count($val))] . $val[rand(0, count($val))];

print_r($arr);
?>

 

Edit: eller blir kanskje ikke helt rettferdig den heller, siden sjansen for å få 2 blank og 1 enkelt tegn er rimelig lavt iforhold til å få 3 tegn (siden det er så utrolig mange flere av dem..)

Endret 29. november 2007 av peros2k

[Runar0]

Vil tro at verdene som nero nevnte vil gi mest like forhold. a aa aaa 9 99 999 z zz zzz 1 11 111 og kanskje noe andre som ligger midt i alfabetet pluss noen heilt random?

. 

Endret 29. november 2007 av Runar0

[Rasks]

Neste oppgave kunne være å lage funksjon som konverterer tall fra titallsystemet til binære tall, eller blir det for lett?

[Runar0]

Mulig denne blir litt for lett, og kanskje litt vanskelig å benche ettersom at forskjellene mellom svarene mest sansynlig blir veldig små.

[Rasks]

Var det jeg også tenkte. Man måtte i såfall ha benchet med ekstremt høy tall, men det kan bli tungvint.

[peros2k]

Neste oppgave kunne være å lage funksjon som konverterer tall fra titallsystemet til binære tall, eller blir det for lett?

 

print base_convert($tall, 10, 2);

 

for lett

[Gjest Slettet+142]

"Teknisk sett" så ville vel oppgaven ha vært å selv ha laget funksjonen som gjorde det, altså:

 

function decToBin($tall){ return base_convert($tall, 10, 2); }

echo decToBin(64);

 

 

Men MC2 komme med flere oppgaver daa

 

[email protected] 16:23:

 

Det er helt rett, Rasks

 

Endret 30. november 2007 av Slettet+142

[Rasks]

"Teknisk sett" så ville oppgaven vært å ikke bruke de innebygde funksjonene i php (decbin(), base_convert() osv.), men MC2 får gjøre hva han vil. Folket begynner å bli utålmodig.

Endret 30. november 2007 av Rasks

[peros2k]

Hva med følgende?

 

Si du har et kvadrat med masse tall, eksempelvis (bare mye større (100x100? 1000x1000?) og med tilfeldige tall):

 

1 2 3 4 5 6
7 8 9 0 1 2
3 4 5 6 7 8
9 0 1 2 3 4
5 6 7 8 9 0
1 2 3 4 5 6

 

Så skal man lage en funksjon som returnerer største sum når man begynner på toppen og ender på bunnen på følgende måte. Man begynner på første rad, velger et tall og beveger seg nedover rad for rad. På hver rad plukker man opp et tall (summen av tall skal være størst mulig). Når man står på et tall har man kun lov til flytte til tallet som direkte nedenfor (samme pos på raden under), eller direkte på skrått nedenfor.

 

Eksempel:

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

 

Startet på rad 1, plukket opp tallet 4.. gikk skrått til venstre, tok 9.. skrått til venstre igjen, tok 4... skrått til høyre, tok 1.. rett ned og tok 7.. skrått til høyre og tok 4... Sum for denne ruten: 4+9+4+1+7+4 = 29 .. åpenbart en dårlig rute.

 

Beste rute i dette eksempelet er antagelig 4+9+3+9+6+3 = 34 .. uten at jeg har testet det..

EDIT: Fantes en bedre, se neste post..

 

Merk at funksjonen ikke trenger å returnere ruten man fulgte, bare summen av tallene på den beste ruten man fant.

 

Hadde det vært noe, eller blir det for lett? for vanskelig? for kjedelig? osv..

Endret 30. november 2007 av peros2k

[Ernie]

Høyst interessant, men frykter den er litt vanskelig for en del?

 

Btw:

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]

4 + 9 + 6 + 3 + 9 +6 = 37

[JohndoeMAKT]

Stemmer det at det blir omtrent 450-500 tusen forskjellige baner i et rutenett på 10x10 verdier?

[Ernie]

Det hørtes litt høyt ut. Jeg får ca 105-106k.

 

Red.: Riktignok fult mulig jeg er helt på jordet da.

Endret 30. november 2007 av Ernie

[peros2k]

Stemmer det at det blir omtrent 450-500 tusen forskjellige baner i et rutenett på 10x10 verdier?

I underkant av 200.000 baner tror jeg, på første rad i har man 10 posisjoner å velge mellom. for hver av disse 10 har man 3 posisjoner i raden under.. 3 for hver i neste.. osv til man er på bunnen.. Dersom man ser bort ifra kantene hvor det bare er 2 alternativer, for letthetsskyld..

 

Så 10*3^9 = 196830 .. og litt mindre enn dette pga kantene..

 

Edit: Ernie sin beregning høres rett ut.

Endret 30. november 2007 av peros2k

[Ernie]

Regnet noe feil. Jeg tror det skal være helt eksakt 136.946 mulige veier.

 

Red.: Liste over antall muligheter "inn" til en "celle". For 1. kolonne blir det 1. + 2. kolonne i raden over, for 2. kolonne 1. + 2. + 3. osv.

		 1	   2	   3	   4	   5	   6	   7	   8	   9	  10
1		1	   1	   1	   1	   1	   1	   1	   1	   1	   1
2		2	   3	   3	   3	   3	   3	   3	   3	   3	   2
3		5	   8	   9	   9	   9	   9	   9	   9	   8	   5
4	   13	  22	  26	  27	  27	  27	  27	  26	  22	  13
5	   35	  61	  75	  80	  81	  81	  80	  75	  61	  35
6	   96	 171	 216	 236	 242	 242	 236	 216	 171	  96
7	  267	 483	 623	 694	 720	 720	 694	 623	 483	 267
8	  750	1373	1800	2037	2134	2134	2037	1800	1373	 750
9	 2123	3923	5210	5971	6305	6305	5971	5210	3923	2123
10	6046   11256   15104   17486   18581   18581   17486   15104   11256	6046

Summering av 10. rad skal vel gi antall mulig veier hvis jeg ikke tenker helt feil her? Uannsett, det blir nevnte tall over.

Endret 30. november 2007 av Ernie