Drukowana wersja tematu

Kliknij tu, aby zobaczyć temat w orginalnym formacie

Forum PHP.pl _ Konkursy _ Rozmowy na temat prac konkursowych

Napisany przez: rzymek01 3.11.2010, 23:49:13

Wydzielone z: http://forum.php.pl/index.php?s=&showtopic=161533&view=findpost&p=803748 - DeyV

------------------------



nie mam jak zainstalowac, na płycie mam live bez żadnego serwera nic, a jak chce cos instalowac typu serwer etc to chce już zainstalowanego systemu

PS. nie ma co juz kombinowac, pozostawię starą wersję co wysłałem juz jakis czas temu z tą moją funkcją, która w językach kompilowanych na pewno działałaby szybciej, ale php jest interpretowany i tutaj z tym jest różnie :/

Już jest północ to można pisać o zadaniach biggrin.gif

Napisany przez: flashdev 3.11.2010, 23:59:42

Cytat(rzymek01 @ 3.11.2010, 23:49:13 ) *
Już jest północ to można pisać o zadaniach biggrin.gif


Spieszy Ci się zegarek winksmiley.jpg

Edit:
No i koniec konkursu.

Napisany przez: rzymek01 4.11.2010, 00:00:45

no co ty, juz mam 2 po biggrin.gif

Napisany przez: Pawel_W 4.11.2010, 00:10:00

no to nie wiem, wklejamy? biggrin.gif

Napisany przez: rzymek01 4.11.2010, 00:14:32

co mogę napisać,
patrząc z czysto algorytmicznego punktu widzenia, istotne części programu to:
1. generowanie fibo
2. dekodowanie ciągu
3. szukanie parametrów

ad1. tutaj jedyne co wymyśliłem, to liczenie każdego wyrazu ciągu modulo 36, aby od razu mieć pozycje w alfabecie i nie wyobrażam sobie poza tym liczenia fibo bez modulo 36, bo nie wiem jaki typ danych pomieściłby np. milionowy + jeden wyraz ciągu

ad2. i ad3. tutaj wymysliłem coś takiego, że dekoduje od lewej i od prawej równolegle i od razu porównuje czy to co odkodowałem to przypadkiem nie cyfra, bo w całym ciągu moga wystąpić tylko cyfry przy parametrach,
zaletą jest to, że o ile parametry nie znajdują się na samym środku, to nie muszę dekodować całego ciągu i ogolnie w miare szybko znajduje parametry,
wadą tego rozwiązania jest język PHP biggrin.gif, tzn. własna funkcja napisana PHP jest zawsze wolniejsza od wbudowanych, także nie wiem, czy akurat w przypadku PHP nawet preg_match by nie było szybsze, teoretycznie nie, ale trzeba miec na uwadze co napisalem wyzej

Generowanie prostokątów mam po bozemu, idę sobie po kolei jak każą, operacje to same dodawania i raz na obieg modulo, także O(K*W), ale przy ograniczeniu K i W do 20, sądze, że ten fragment kodu ma być po prostu poprawny i nie jest aż tak istotna złozoność budowania tych postokątów

PS. no i złożoność mojego programu:
n - długość ciągu
punkty 1,2 i 3 w czasie O(2n)=O(n)
prostokąty w czasie O(3*K*W)=O(K*W)

Napisany przez: flashdev 4.11.2010, 00:14:47

Cytat(Pawel_W @ 4.11.2010, 00:10:00 ) *
no to nie wiem, wklejamy? biggrin.gif


Dekodowanie ciągu:

  1. $length = http://www.php.net/strlen($argv[1]);
  2.  
  3. $rot_str = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789';
  4. $rot_arr = http://www.php.net/array('A' => 0, 'B' => 1, 'C' => 2, 'D' => 3, 'E' => 4, 'F' => 5, 'G' => 6, 'H' => 7, 'I' => 8, 'J' => 9, 'K' => 10, 'L' => 11, 'M' => 12, 'N' => 13, 'O' => 14, 'P' => 15, 'Q' => 16, 'R' => 17, 'S' => 18, 'T' => 19, 'U' => 20, 'V' => 21, 'W' => 22, 'X' => 23, 'Y' => 24, 'Z' => 25, '0' => 26, '1' => 27, '2' => 28, '3' => 29, '4' => 30, '5' => 31, '6' => 32, '7' => 33, '8' => 34, '9' => 35);
  5. $rot_len = 36; //strlen($rot_str);
  6.  
  7. $prev1 = $length;
  8. $prev2 = 0;
  9. for( $i = 0; $i < $length; ++$i ){
  10. $curr = ($prev2 + $prev1)%$rot_len;
  11. $prev2 = $prev1;
  12. $prev1 = $curr;
  13. $argv[1][$i] = $rot_str[($rot_arr[$argv[1][$i]] - $curr + $rot_len ) % $rot_len];
  14. }
  15.  
  16. $params = http://www.php.net/array();
  17. http://www.php.net/preg_match('/K([0-9])+/', $argv[1], $params['k']);
  18. http://www.php.net/preg_match('/W([0-9])+/', $argv[1], $params['w']);
  19. http://www.php.net/preg_match('/A([0-9])/', $argv[1], $params['a']);
  20. http://www.php.net/preg_match('/Z([0-9])/', $argv[1], $params['z']);
  21.  
  22. $cols = $params['k'][1] + 0;
  23. $rows = $params['w'][1] + 0;
  24. $min = $params['a'][1] + 0;
  25. $max = $params['z'][1] + 0;


W sumie, tej części kody nawet nie optymalizowałem. Udało się komuś pozbyć tej pętli? smile.gif
Testowałem wersję z array_map, ale była nawet trochę wolniejsza dla krótkich oraz długich ciągów.

Napisany przez: Pawel_W 4.11.2010, 00:15:46

http://wklej.org/hash/d9a8df00ee8/

no to ja zaszaleje, cały kod smile.gif

Napisany przez: starach 4.11.2010, 00:31:42

Cytat(Pawel_W @ 4.11.2010, 00:15:46 ) *
http://wklej.org/hash/d9a8df00ee8/

no to ja zaszaleje, cały kod smile.gif
Wszystkie zmienna walnął z pojedyńczych liter ale o define('LF', "\n") już zapomniał. ;P

Ładny kod. Niestety ja zdążyłem napisać tylko dekodowanie fib'a i mnie choroba do reszty rozłożyła... nadal jestem ledwo ciepły, ale ciekawość wzięła górę. winksmiley.jpg

Napisany przez: dr_bonzo 4.11.2010, 00:32:16

Pawel_W - wyprzedziles moj kod, ale chyba brakuje ci "\n" za 3cim prostokatem

Napisany przez: flashdev 4.11.2010, 00:35:48

Cytat(Pawel_W @ 4.11.2010, 00:15:46 ) *
http://wklej.org/hash/d9a8df00ee8/

no to ja zaszaleje, cały kod smile.gif


Zrobiłem po 5 testów w każdej serii po 500 pomiarów dla Twojego i mojego dekodowania.
Kod
Domyslne wejscie: 'I3OHUI5Y0UXU7VQS9U63C'

Twoje:
av:    0.00082    sd:    0.00265
av:    0.00068    sd:    0.00030
av:    0.00083    sd:    0.00052
av:    0.00071    sd:    0.00035
av:    0.00075    sd:    0.00038

moje:
av:    0.00094    sd:    0.00093
av:    0.00060    sd:    0.00031
av:    0.00057    sd:    0.00030
av:    0.00058    sd:    0.00029
av:    0.00062    sd:    0.00034

Dluzszy ciag wejsciowy: str_repeat('I3OHUI5Y0UXU7VQS9U63C', 1e3)

Twoje:
av:    0.00078    sd:    0.00050
av:    0.00066    sd:    0.00031
av:    0.00067    sd:    0.00035
av:    0.00067    sd:    0.00031
av:    0.00067    sd:    0.00034

moje:
av:    0.00059    sd:    0.00031
av:    0.00062    sd:    0.00033
av:    0.00059    sd:    0.00031
av:    0.00060    sd:    0.00032
av:    0.00057    sd:    0.00026


Trudno powiedzieć żeby były jakieś znaczące różnice.

Edit:
Poniżej podaję kod, którym mierzę czasy. Może się komuś przyda.
http://wklej.org/id/412325/

Napisany przez: dr_bonzo 4.11.2010, 00:39:15

Zrob dluzsze pomiary. Oficjalne testy sa po 1000 razy. U mnie daje to jakies 48s dla pojedynczego odpalenia ciagu z instrukcji.

Napisany przez: flashdev 4.11.2010, 00:41:13

Cytat(dr_bonzo @ 4.11.2010, 00:39:15 ) *
Zrob dluzsze pomiary. Oficjalne testy sa po 1000 razy. U mnie daje to jakies 48s dla pojedynczego odpalenia ciagu z instrukcji.


Zrobiłem 4 * 5 serii po po 500 pomiarów, czyli w sumie 4 * 2500 pomiarów.
Funkcję, którą mierzę czas podałem już wcześniej. Wykorzystuję require.

Aha i av to średnia oczywiście z tych 500 pomiarów, a sd to odchylenie standardowe.

Napisany przez: dr_bonzo 4.11.2010, 00:42:50

ah, niedoczytalem

Napisany przez: flashdev 4.11.2010, 00:44:28

Cytat(Pawel_W @ 4.11.2010, 00:15:46 ) *
http://wklej.org/hash/d9a8df00ee8/

no to ja zaszaleje, cały kod smile.gif


@Pawel_W bardzo fajnie to zrobiłeś z jednym preg`iem. Ale sam już się nie brałem za optymalizację tego bo nie wiem czy był sens. Wie ktoś może dokładnie jakie jest ograniczenie co do długości paramteru podawanego przy wywołaniu programu w linii poleceń?

Napisany przez: dr_bonzo 4.11.2010, 00:50:47

@Pawel_W

Kod
preg_match_all('#([KWAZkwaz]{1}[0-9]{1,2})#', $d, $m);


A co jak w odkodowanym kodzie bedzie "....K32XXXXXW7XXXX..."

to jaka wartosc bedzie miec K ?

Napisany przez: 8rol 4.11.2010, 00:52:23

@Pawel_W, spróbuj uruchomić swój skrypt z parametrem SLK92YNR (tj. K5W5A2Z7). Wydaje mi się, że coś jest wtedy nie tak.

Napisany przez: flashdev 4.11.2010, 00:57:53

Cytat(8rol @ 4.11.2010, 00:52:23 ) *
@Pawel_W, spróbuj uruchomić swój skrypt z parametrem SLK92YNR (tj. K5W5A2Z7). Wydaje mi się, że coś jest wtedy nie tak.


Sprawdziłem, działa dobrze:

Kod
array(4) {
  ["K"]=>
  string(1) "5"
  ["W"]=>
  string(1) "5"
  ["A"]=>
  string(1) "2"
  ["Z"]=>
  string(1) "7"
}

Napisany przez: zegarek84 4.11.2010, 01:04:46

http://wklej.org/id/412327/

Napisany przez: dr_bonzo 4.11.2010, 01:12:05

A to moj kod: http://paste-it.net/public/je4eef6/

Napisany przez: 8rol 4.11.2010, 01:28:03

dr_bonzo, wydaje mi się, że masz pewien problem z odbieraniem parametrów, dla przykładu: TN156JBHY (k5aw6a2z7).

Napisany przez: ayeo 4.11.2010, 02:12:54

No to i ja wkleję mojego zamulatora biggrin.gif Ale mi nie wyszło biggrin.gif Masakra tongue.gif

http://snippie.net/snip/1304797a

A wszyscy mówili, żeby potestować, zoptymalizować biggrin.gif

Napisany przez: my salsa 4.11.2010, 07:58:30

No więc poniżej i mój kod winksmiley.jpg Trochę nawalone pętli, ale szedłem wierszami

http://wklej.org/id/412341/

Może znajdzie się chętny, co by wrzucił wszystkie nasze prace, które tu udostępnimy na jeden serwer i odpalił testy jakieś? winksmiley.jpg

Napisany przez: askone 4.11.2010, 08:12:06

Gdy patrzę na Wasze kody to mam dziwne odczucie, że chyba troszkę namieszałem z moim rozwiązaniem. Czyżby myśl, iż nie sprawdziłem wszystkiego dokładnie była prawdziwa...

Fragment kodu (w pracy mam tylko to) dekodującego parametry:

  1. /**
  2.   * Dekoduje zaszyfrowany ciąg parametrów wejściowych.
  3.   * @uses modifiedFibonacci($base)
  4.   * @param string $paramsString
  5.   * @return string
  6.   */
  7. function decodeParamsString($paramsString)
  8. {
  9. $rotString = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
  10. $rotOffsetArray = http://www.php.net/array(
  11. "A" => 0, "B" => 1, "C" => 2, "D" => 3, "E" => 4, "F" => 5, "G" => 6, "H" => 7,
  12. "I" => 8, "J" => 9, "K" => 10, "L" => 11, "M" => 12, "N" => 13, "O" => 14, "P" => 15,
  13. "Q" => 16, "R" => 17, "S" => 18, "T" => 19, "U" => 20, "V" => 21, "W" => 22, "X" => 23,
  14. "Y" => 24, "Z" => 25, "0" => 26, "1" => 27, "2" => 28, "3" => 29, "4" => 30, "5" => 31,
  15. "6" => 32, "7" => 33, "8" => 34, "9" => 35
  16. );
  17. $decodedString = "";
  18. $fibonacciArray = http://www.php.net/array_slice(calculateModFibonacci(http://www.php.net/strlen($paramsString), 36), 1);
  19.  
  20. $paramsArr = str_split($paramsString);
  21. for($i = 0; $i < http://www.php.net/count($paramsArr); $i++)
  22. {
  23. $offset = $rotOffsetArray[$paramsArr[$i]] - $fibonacciArray[$i];
  24. $offset = ($offset < 0)? 36 - http://www.php.net/abs($offset) : $offset;
  25. $decodedString .= $rotString[$offset];
  26. }
  27.  
  28. return $decodedString;
  29. }
  30. /**
  31.   * Buduje tablicę wartości zmodyfikowanego ciągu Fibonacciego.
  32.   * Każda wartośc ciągu dzielona jest modulo $modulo celem wyliczenia pzesuniącia względnego.
  33.   * @param int $base
  34.   * @param int $modulo
  35.   * @return array
  36.   */
  37. function calculateModFibonacci($base, $modulo)
  38. {
  39. list( $cur, $nxt, $inc, $seq ) = http://www.php.net/array( $base, $base, 0, http://www.php.net/array() );
  40.  
  41. do
  42. {
  43. $inc++;
  44. $seq[] = $cur % $modulo;
  45. $add = $cur + $nxt;
  46. $cur = $nxt;
  47. $nxt = $add;
  48. }
  49. while ( $inc <= $base );
  50.  
  51. return $seq;
  52. }

Napisany przez: rolka 4.11.2010, 08:19:42

Mój kod: http://snippie.net/snip/b349642b
Tym testuję: http://snippie.net/snip/0da66426 - trochę jak stary kowboj, ale daje rozsądne wyniki i minimalizuje przypadkowość (przydało by się tylko jeszcze więcej iteracji)

Jak się okazuje o kilku rzeczach zapomniałem, kilku nie przewidzialem. Zobaczymy smile.gif
Z kilku tricków jestem zadowolony:


Mam nadzieję, że procedura testowa będzie w miarę miarodajna. Natomiast jeśli będzie taka jak w regulaminie to może wygrać każdy kogo kod przejdzie 1 etap smile.gif

Powodzenia!

Napisany przez: my salsa 4.11.2010, 08:29:42

Cytat(Pawel_W @ 4.11.2010, 00:15:46 ) *
http://wklej.org/hash/d9a8df00ee8/

no to ja zaszaleje, cały kod smile.gif



Cytat(rolka @ 4.11.2010, 08:19:42 ) *
Mój kod: http://snippie.net/snip/b349642b
Tym testuję: http://snippie.net/snip/0da66426 - trochę jak stary kowboj, ale daje rozsądne wyniki i minimalizuje przypadkowość (przydało by się tylko jeszcze więcej iteracji)

Jak się okazuje o kilku rzeczach zapomniałem, kilku nie przewidzialem. Zobaczymy smile.gif
Z kilku tricków jestem zadowolony:
    - dekodując wystarczyło odwrócić ciąg smile.gif reszta kodu była dokładnie taka sama jak przy kodowaniu
    - działa dla ciągu dowolnej długości (trick z sumą modulo dla 2 poprzednich wyrazów - tu pomysł ayeo podsunął)
    - do generowania prostokątów użyłem jednej pętli - generuję wszystkie 3 na raz

Mam nadzieję, że procedura testowa będzie w miarę miarodajna. Natomiast jeśli będzie taka jak w regulaminie to może wygrać każdy kogo kod przejdzie 1 etap smile.gif

Powodzenia!

Nie wiem czy zauważyłeś, ale zapomniałeś o wielkości znaków (i3ohui5y0uXU7VqS9u63C nie idzie)
W każdym razie świetny kod, według moich kiepskich testów (bo na windowsie winksmiley.jpg to bijesz na ryj moje rozwiązanie smile.gif

Napisany przez: dr_bonzo 4.11.2010, 08:35:51

Cytat(8rol @ 4.11.2010, 02:28:03 ) *
dr_bonzo, wydaje mi się, że masz pewien problem z odbieraniem parametrów, dla przykładu: TN156JBHY (k5aw6a2z7).


Zalozylem, moze i blednie, ze litery od parametrow wystapia tylko raz :/
----
Moj benchmark (oczywiscie srodowisko dalekie od laboratoryjnego - ale generalnie nic na kompie sie nei dzialo i nie dotykalem myszki smile.gif)

Czasy wygladaja na identyczne, zmieniaja sie z kazdym uruchomieniem.

Kod
$ php benchmark.php 100
Running 100 times, with code I3OHUI5Y0UXU7VQS9U63C
     4.506s - dr_bonzo.php // dr_bonzo
     4.583s - Pawel_W.php // Pawel_W
     4.499s - zegarek84.php // zegarek84
     4.604s - ayeo.php // ayeo
     4.510s - my-salsa.php // my salsa
     4.511s - rolka.php // rolka
     4.484s - cichy.php // cichy
     4.505s - phpion.php // phpion
     4.601s - flashdev.php // flashdev

Napisany przez: rolka 4.11.2010, 09:28:52

Cytat(my salsa @ 4.11.2010, 08:29:42 ) *
Nie wiem czy zauważyłeś, ale zapomniałeś o wielkości znaków (i3ohui5y0uXU7VqS9u63C nie idzie)


Aaaaaa! Wysłałem przez przypadek kod bez strtoupper przy $argv sciana.gif

Napisany przez: dr_bonzo 4.11.2010, 09:41:33

Wolne uwagi

- NIEWAZNE: co jak wypełniaczami są polskie krzaki i jak zachowa się strlen() ( alfabet to litery alfabety lacinskiego oraz cyfry )
- co jak parametry zdefiniowane sa kilka razy "K10.....K7" - wlasciwie to nie powinny - bo nie sprecyzowano ktory parametr wtedy wybrac
- co jak K W A Z moga byc tez wypelniaczami?

Moje próby rozwiązań

- wygenerować wszystkie rozwiązania, zapisać w tablicach/stringu w zmiennej i odczytywać zamiast wyliczać (!wolne)
- to samo ale zapisac na koncu pliku z kodem + __halt_compiler() + odczyt odpowiedzi znajdujacych sie zaraz za kodem; mniej parsowania dla php (!nie mozna odczytywac z plikow)
- uzyc pamieci wspoldzielonej - przy pierwszym odpaleniu wrzucic odpowiedzi do ramu a przy kolejnych je odczytywac, ale ze wzgledu ze potrzebowalem min 8MB pamieci, a jej ilosc zalezy od konfiguracji systemu i nie zostala podana, to porzucilem to rozwiazanie. Dla testu poprawnosci to rozwiazanie nie musi byc szybkie (!niepewne rozwiazanie).

Napisany przez: phpion 4.11.2010, 09:46:54

Cytat(dr_bonzo @ 4.11.2010, 09:41:33 ) *
- co jak parametry zdefiniowane sa kilka razy "K10.....K7" - wlasciwie to nie powinny - bo nie sprecyzowano ktory parametr wtedy wybrac

Wypełniaczami mogą być tylko litery, więc taka sytuacja nie zajdzie.
Cytat
Kody parametrów zostają umieszczone w większym ciągu, gdzie miejsca wokół kodów parametrów zostaną wypełnione losowymi literami.

Napisany przez: ayeo 4.11.2010, 09:47:46

Coś z tymi testami jest nie tak jeśli mój kombajn jest porównywalny ze skryptem @zegarek84, @dr_bonzo czy @rolka tongue.gif

Napisany przez: krowal 4.11.2010, 09:48:45

@phpion, też zrobiłem osobny sposób dla przypadku gdy a == z smile.gif
Moimi trikami było:
- generowanie wszystkiego w jednej pętli + pętla zagnieżdżona (generalnie iteracji wychodzi tyle samo co u ciebie winksmiley.jpg )
- spiralę jako jedyny prostokąt wypełniam w tablicy (tu się martwię czy podoła z rozwiązaniami innych)
- wiersze robię przez odwrócenie ciągu sekwencji, pocięcie go na kawałki o długości równej ilości kolumn i zlepienie w stringa oddzielonego "\n"
- wężyk robię przez dokładanie znaku z całej sekwencji, index wklejanego znaku obliczam na podstawie aktualnej wartości w i k w kolejnych iteracjach

oto mój kod: http://wklej.org/hash/298032511ac/ smile.gif

ps. phpion, oddałeś rozwiązanie z tym czymś na początku? :

  1. // Obliczenie dlugosci wejscia.
  2. $j = 7;


edit:
@ayeo ja próbowałem u siebie zrobić testy kilku rozwiązań i przy wywoływaniu skryptów w ten sposób (.bat pod win):
nie wiem czy to jest dobrze, nie znam się na batowych skryptach winksmiley.jpg (ściągnąłem gotowca z jakiejś strony)
  1. @echo off
  2. timer
  3. for /l %%i in (1 1 100) do (
  4. php -f plik_testowy.php I3OHUI5Y0UXU7VQS9U63C > test.txt
  5. )
  6. timer /s
też wszystkie rozwiązania miały te same czasy, chyba to nie jest miarodajne.

Napisany przez: phpion 4.11.2010, 09:51:06

Cytat(krowal @ 4.11.2010, 09:48:45 ) *
ps. phpion, oddałeś rozwiązanie z tym czymś na początku? :
  1. // Obliczenie dlugosci wejscia.
  2. $j = 7;

Na początku mam phpDoca, ale wywaliłem go wrzucając kod w sieć. Ale generalnie tak: jedna z pierwszych moich linijek to właśnie $j = 7, a co?

Napisany przez: krowal 4.11.2010, 09:54:37

Sądząc po tym jak później tego używasz to nie powinno być:

  1. $j = http://www.php.net/strlen($argv[1])
?

edit. sorry nie zauważyłem, że później zmieniasz to $j winksmiley.jpg

Napisany przez: phpion 4.11.2010, 09:58:10

Można też tak, jak najbardziej, ale while() jest szybszy od strlen() smile.gif tak przynajmniej wyszło z moich testów. Do tego nie ma co jechać od 0, bo minimalna długość ciągu to 8:

  1. $in = 'K1W1A1Z1'; // Podalem odkodowany, ale zakodowany bedzie mial tyle samo znakow.
  2.  
  3. $j = 7;
  4.  
  5. while (http://www.php.net/isset($in{++$j}));
  6.  
  7. http://www.php.net/echo $j;

Napisany przez: krowal 4.11.2010, 10:00:57

Ech teraz kolejne dwa tygodnie czekania smile.gif

Napisany przez: dr_bonzo 4.11.2010, 10:04:11

Jeszcze raz wklejam

Krotszy kod: I3OHUI5Y0UXU7VQS9U63C
Dluzszy kod: HB0EHYIJ4QXQQJCYDEUB8MXMMB0EHYIJ4QXQQJCYDEUB8MXMMB0EHYIJ4QXQQJCYDEUB8MXMMB0EHYIJ
4QXQQWFYDEUB8MXMMB0EHYIJ4QXQQJCYDEUB8MXMMB0EHYIJ4QXQQJCYDEUYDPXMMB0EHYIJ4QXQQJCY
D
EUB8MXMMB0EHYIJ4QXQQJCYDEUB8MXMMB0EHYIJ60WVTJCYDEUB8MXMMB0EHYIJ4QXQQJCYDEUB8MXMM
B
0EHYIJ4QXQQJCYDEUB8MXMMB0EHYIJ4QXQQ

Kod
Validating for code I3OHUI5Y0UXU7VQS9U63C
dr_bonzo
---8<--------------------------------------------------
123456
234567
132171
765432

455667
364751
273142
112233

321765
432176
543217
654321
--------------------------------------------------8<---
Pawel_W
---8<--------------------------------------------------
123456
234567
132171
765432

455667
364751
273142
112233

321765
432176
543217
654321--------------------------------------------------8<---
zegarek84
---8<--------------------------------------------------
123456
234567
132171
765432

455667
364751
273142
112233

321765
432176
543217
654321
--------------------------------------------------8<---
ayeo
---8<--------------------------------------------------
123456
234567
132171
765432

455667
364751
273142
112233

321765
432176
543217
654321
--------------------------------------------------8<---
my salsa
---8<--------------------------------------------------
123456
234567
132171
765432

455667
364751
273142
112233

321765
432176
543217
654321
--------------------------------------------------8<---
rolka
---8<--------------------------------------------------
123456
234567
132171
765432

455667
364751
273142
112233

321765
432176
543217
654321
--------------------------------------------------8<---
cichy
---8<--------------------------------------------------
123456
234567
132171
765432

455667
364751
273142
112233

321765
432176
543217
654321
--------------------------------------------------8<---
phpion
---8<--------------------------------------------------
123456
234567
132171
765432

455667
364751
273142
112233

321765
432176
543217
654321--------------------------------------------------8<---
krowal
---8<--------------------------------------------------
123456
234567
132171
765432

455667
364751
273142
112233

321765
432176
543217
654321
--------------------------------------------------8<---
flashdev
---8<--------------------------------------------------
123456
234567
132171
765432

455667
364751
273142
112233

321765
432176
543217
654321
--------------------------------------------------8<---


Kod
Validating for code HB0EHYIJ4QXQQJCYDEUB8MXMMB0EHYIJ4QXQQJCYDEUB8MXMMB0EHYIJ4QXQQJCYDEUB8MXMMB0EHYIJ
4QXQQWFYDEUB8MXMMB0EHYIJ4QXQQJCYDEUB8MXMMB0EHYIJ4QXQQJCYDEUYDPXMMB0EHYIJ4QXQQJCY
D
EUB8MXMMB0EHYIJ4QXQQJCYDEUB8MXMMB0EHYIJ60WVTJCYDEUB8MXMMB0EHYIJ4QXQQJCYDEUB8MXMM
B
0EHYIJ4QXQQJCYDEUB8MXMMB0EHYIJ4QXQQ
dr_bonzo
---8<--------------------------------------------------
01234567012345670123
34567012345670123454
27012345670123456765
16345670123456701076
05270123456701232107
74163456701234543210
63052701234567654321
52741634567010765432
41630527012321076543
30527416345432107654
27416305276543210765
16305274107654321076
05274163210765432107
74163054321076543210
63052765432107654321
52741076543210765432
41632107654321076543
30543210765432107654
27654321076543210765
10765432107654321076

34343434343434343434
25252525252525252525
16161616161616161616
07070707070707070707
70707070707070707070
61616161616161616161
52525252525252525252
43434343434343434343
34343434343434343434
25252525252525252525
16161616161616161616
07070707070707070707
70707070707070707070
61616161616161616161
52525252525252525252
43434343434343434343
34343434343434343434
25252525252525252525
16161616161616161616
07070707070707070707

76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
--------------------------------------------------8<---
Pawel_W
---8<--------------------------------------------------

--------------------------------------------------8<---
zegarek84
---8<--------------------------------------------------
Array


Array


Array
--------------------------------------------------8<---
ayeo
---8<--------------------------------------------------


--------------------------------------------------8<---
my salsa
---8<--------------------------------------------------
--------------------------------------------------8<---
rolka
---8<--------------------------------------------------
01234567012345670123
34567012345670123454
27012345670123456765
16345670123456701076
05270123456701232107
74163456701234543210
63052701234567654321
52741634567010765432
41630527012321076543
30527416345432107654
27416305276543210765
16305274107654321076
05274163210765432107
74163054321076543210
63052765432107654321
52741076543210765432
41632107654321076543
30543210765432107654
27654321076543210765
10765432107654321076

34343434343434343434
25252525252525252525
16161616161616161616
07070707070707070707
70707070707070707070
61616161616161616161
52525252525252525252
43434343434343434343
34343434343434343434
25252525252525252525
16161616161616161616
07070707070707070707
70707070707070707070
61616161616161616161
52525252525252525252
43434343434343434343
34343434343434343434
25252525252525252525
16161616161616161616
07070707070707070707

76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
--------------------------------------------------8<---
cichy
---8<--------------------------------------------------
01234567012345670123
34567012345670123454
27012345670123456765
16345670123456701076
05270123456701232107
74163456701234543210
63052701234567654321
52741634567010765432
41630527012321076543
30527416345432107654
27416305276543210765
16305274107654321076
05274163210765432107
74163054321076543210
63052765432107654321
52741076543210765432
41632107654321076543
30543210765432107654
27654321076543210765
10765432107654321076

34343434343434343434
25252525252525252525
16161616161616161616
07070707070707070707
70707070707070707070
61616161616161616161
52525252525252525252
43434343434343434343
34343434343434343434
25252525252525252525
16161616161616161616
07070707070707070707
70707070707070707070
61616161616161616161
52525252525252525252
43434343434343434343
34343434343434343434
25252525252525252525
16161616161616161616
07070707070707070707

76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
76543210765432107654
32107654321076543210
--------------------------------------------------8<---
phpion
---8<--------------------------------------------------

--------------------------------------------------8<---
krowal
---8<--------------------------------------------------


--------------------------------------------------8<---
flashdev
---8<--------------------------------------------------

Warning: str_split(): The length of each segment must be greater than zero in /Users/drbonzo/php-konkurs-jesien-2010/flashdev.php on line 40

Warning: implode(): Invalid arguments passed in /Users/drbonzo/php-konkurs-jesien-2010/flashdev.php on line 79




Warning: chunk_split(): Chunk length should be greater than zero in /Users/drbonzo/php-konkurs-jesien-2010/flashdev.php on line 109
--------------------------------------------------8<---

Napisany przez: krowal 4.11.2010, 10:36:45

@dr_bonzo, dzięki za rozwianie wątpliwości smile.gif
Pozostaje tylko mieć nadzieję, że kody nie będą aż tak długie i integer wytrzyma winksmiley.jpg

Napisany przez: flashdev 4.11.2010, 11:54:22

Jednak czytanie ze zrozumieniem to przydatna umiejętność.
"kolumny i wiersze w zakresie 3 – 20"
W ogóle nie zauważyłem tej linijki i optymalizowałem swoje prostokąty na rozmiary nawet 1000x1000 i większe. Miałem nadzieję, że będą takie duże w testach, żeby to miało sens.

@dr_bonzo, jeżeli chce Ci się to możesz też dorzucić do tych testów mój kod -> http://wklej.org/id/412411/

Napisany przez: dr_bonzo 4.11.2010, 12:11:08

@flashdev - dodane (patrz na 2 gorne posty)

Napisany przez: flashdev 4.11.2010, 12:14:36

Cytat(dr_bonzo @ 4.11.2010, 12:11:08 ) *
@flashdev - dodane (patrz na 2 gorne posty)


No to widzę, że zaszalałem...

Napisany przez: ayeo 4.11.2010, 12:41:01

Ale strzeliłem babola! W najprostszym momencie biggrin.gif Pokonkursowane biggrin.gif

Napisany przez: l0ud 4.11.2010, 15:08:54

Moje "cudo" tongue.gif

http://wklej.org/id/412490/

Napisany przez: sever88 4.11.2010, 15:21:35

Mój kod:
http://pastebin.com/AbQs4AjL

Nie mam żadnych specjalnych tricków.
Kolejne cyfry wrzucam na wybrane pozycje w stringu. Kod rozkodowuję na bieżąco sprawdzając czy jest interesujący znak. Tworzenie prostokątów jest dosyć sprawne, ale wynik w głównej mierze będzie zależał od rozszyfrowywania.
Pierwsza połowa kodu odpowiada za szyfr mimo że na to nie wygląda, po prostu są wykorzystywane te same nazwy zmiennych w obu częściach programu smile.gif

@phpion - fajne sztuczki wymyśliłeś, Twój kod wygląda mi na faworyta smile.gif

Napisany przez: damc 4.11.2010, 15:49:27

Ktoś jest zainteresowany tym, jak zrobić pierwszy prostokąt bez wpisywania do tablicy?

Napisany przez: rzymek01 4.11.2010, 18:04:59

Wiem, że teraz trochę naciągam, ale proszę o dołączenie moich dwóch kodów do testow tongue.gif

1. szukanie parametrów za pomocą preg_match:
http://wklej.to/J6KB
2. własna funkcja do szukania:
http://wklej.to/xKl4

PS. po fakcie patrzę, że moglem troche lepiej zoptymalizowac tongue.gif
PS2. proponuje testować na ciągu długości tak przynajmniej 10000-100000

Napisany przez: askone 4.11.2010, 18:19:53

Obiecany kod: http://wklej.org/id/412654/

Fajnie jeśli udało by się go sprawdzić w testach porównawczych;)

Napisany przez: Demio 4.11.2010, 18:21:47

http://wklej.org/id/412657/

Mój kod. Pozdrawiam.

Napisany przez: Pawel_W 4.11.2010, 18:49:41

widzę, że dużo osób tu stosuje pętlę for, a to jest przecież ogromne opóźnienie w stosunku do while smile.gif

Napisany przez: dr_bonzo 4.11.2010, 18:53:36

Jakis dowod?

Napisany przez: kaliberx 4.11.2010, 18:54:42

Cytat(sever88 @ 4.11.2010, 15:21:35 ) *
Mój kod:
http://pastebin.com/AbQs4AjL

Nie mam żadnych specjalnych tricków.


Nie ma to jak skromność. Według moich pomiarów masz najszybszy program ze wszystkich tu wysłanych.

Napisany przez: dr_bonzo 4.11.2010, 19:10:19

IMO

Dużo programów odpadnie na teście dokładnościowym.

Potem będzie loteria.

A na koniec wygra najladniejszy kod.

Napisany przez: Pawel_W 4.11.2010, 19:36:28

Cytat(dr_bonzo @ 4.11.2010, 18:53:36 ) *
Jakis dowod?

to chyba akurat łatwo sprawdzić smile.gif gdzieś na forum nospor o tym napominał smile.gif

Napisany przez: dr_bonzo 4.11.2010, 19:37:17

To czekam na kod. I wskazanie ile zyskam zamieniajac for -> while w tych programach.

Napisany przez: qba10 4.11.2010, 20:13:44

Cytat(sever88 @ 4.11.2010, 15:21:35 ) *
Mój kod:
http://pastebin.com/AbQs4AjL

Nie mam żadnych specjalnych tricków.
Kolejne cyfry wrzucam na wybrane pozycje w stringu. Kod rozkodowuję na bieżąco sprawdzając czy jest interesujący znak. Tworzenie prostokątów jest dosyć sprawne, ale wynik w głównej mierze będzie zależał od rozszyfrowywania.
Pierwsza połowa kodu odpowiada za szyfr mimo że na to nie wygląda, po prostu są wykorzystywane te same nazwy zmiennych w obu częściach programu smile.gif

@phpion - fajne sztuczki wymyśliłeś, Twój kod wygląda mi na faworyta smile.gif

Twój kod dla kodu UMUAAM4G9Z zwraca mi :

Kod
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000

00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000

00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000

A powinien
Kod
01234567890123456789
56789012345678901230
43456789012345678941
32345678901234567052
21256789012345678163
10149012345678989274
09038567890123090385
98927434567894101496
87816323456705212507
76705212567816323618
65694101498927434729
54583090321038545830
43472989876549656941
32361876543210767052
21250765432109878163
10149876543210989274
09032109876543210385
98987654321098765496
87654321098765432107
76543210987654321098

90909090909090909090
81818181818181818181
72727272727272727272
63636363636363636363
54545454545454545454
45454545454545454545
36363636363636363636
27272727272727272727
18181818181818181818
09090909090909090909
90909090909090909090
81818181818181818181
72727272727272727272
63636363636363636363
54545454545454545454
45454545454545454545
36363636363636363636
27272727272727272727
18181818181818181818
09090909090909090909

98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210
98765432109876543210

Napisany przez: jasin 4.11.2010, 21:41:08

Wszyscy wrzucają to i ja smile.gif
Wiem, że nie jest to super kod ale nie miałem czasu by go "dopieszczać" więc wyszło co wyszło.
http://pastebin.com/b95U9DK9

Napisany przez: flashdev 4.11.2010, 21:59:40

Cytat(dr_bonzo @ 4.11.2010, 19:37:17 ) *
To czekam na kod. I wskazanie ile zyskam zamieniajac for -> while w tych programach.


Kod
dane z 10 pomiarow
av:    1.389[s]    sd:    0.019[s]    _pusta petla for.php
av:    0.724[s]    sd:    0.017[s]    _pusta petla while.php

dane z 50 pomiarow
av:    1.443[s]    sd:    0.068[s]    _pusta petla for.php
av:    0.772[s]    sd:    0.058[s]    _pusta petla while.php


I jeszcze, żeby było widać co mierzyłem.

  1. <?php
  2. for( $i = 0; $i < $n; ++$i ){
  3. }


  1. <?php
  2. $i = $n;
  3. while( $i-- ){
  4. }


W obu przypadkach $n = 1e7;

jeszcze dane dla 200 pomiarów:
Kod
av:    1.428 [s]    sd:    0.051 [s]    _pusta petla for.php
av:    0.727 [s]    sd:    0.030 [s]    _pusta petla while.php


Już praktycznie nie widać, zeby coś się poprawiło. While zdecydowanie wygrywa z for`em i to prawie dwukrotnie.

Napisany przez: Pawel_W 4.11.2010, 23:35:31

Cytat(flashdev @ 4.11.2010, 21:59:40 ) *
Już praktycznie nie widać, zeby coś się poprawiło. While zdecydowanie wygrywa z for`em i to prawie dwukrotnie.

no więc właśnie smile.gif

dzięki za wykonanie pomiarów, jestem aktualnie na laptopie i nie mam tutaj zainstalowanego serwera smile.gif

Napisany przez: rzymek01 4.11.2010, 23:46:43

ciekawe skąd bierze się taka różnica...

o ile pamiętam w C/C++ nie ma takich róznic w działaniu tych pętli

Napisany przez: Pawel_W 4.11.2010, 23:53:12

Cytat(rzymek01 @ 4.11.2010, 23:46:43 ) *
ciekawe skąd bierze się taka różnica...

o ile pamiętam w C/C++ nie ma takich róznic w działaniu tych pętli

są, ale tylko przy kompilacji, kod wynikowy jest sprowadzany do takiej samej postaci smile.gif

Napisany przez: flashdev 4.11.2010, 23:55:05

Cytat(Pawel_W @ 4.11.2010, 23:53:12 ) *
są, ale tylko przy kompilacji, kod wynikowy jest sprowadzany do takiej samej postaci smile.gif


Dokładnie do 2 instrukcji
porównanie + ewentualny skok
inkrementacja/dekrementacja

W pętli for jeszcze jest ustawienie początkowej wartości na początku, ale w while też trzeba to zrobić, tylko poza pętlą.

Napisany przez: rzymek01 5.11.2010, 00:42:40

no własnie, pamietam, że jak sprawdzalem instrukcje asm to w przypadku for jak i while kompilator sprowadzal do tego samego smile.gif

Napisany przez: ernie242 5.11.2010, 11:00:03

Jestem pod wrażeniem Panowie blinksmiley.gif Niektóre kody są naprawdę sprytne! (co do innych - jestem zbyt głupi, żeby je rozszyfrować...)

Ja niestety nie miałem czasu za bardzo do tego przysiąść, a szkoda...

http://pastebin.com/7hts0LHU

Kod oparty na klasach byłby chyba jeszcze wolniejszy, za to opakowanie wszystkiego w funkcje pozwoliło mi na (jako tako) napisanie prostych testów podczas pisania skryptu:

http://pastebin.com/zR1Pe4LH

pozdrawiam

Napisany przez: phpion 5.11.2010, 13:01:33

No i zadek. Ja również odpadłem z rywalizacji. Po ostatnim prostokącie brakuje mi jednego znaku nowej linii. Cóż, trudno. Życzę Wam ostrej rywalizacji i jak najmniejszego wpływu przypadku na uzyskane wyniki.

Mój pechowy kod:
http://wklej.org/id/412353/
W moich testach 1000 wywołań zajmowało łącznie ok. 1,6 sekundy... ehhh...

Napisany przez: dr_bonzo 5.11.2010, 13:08:30

@phpion:

Cytat
W moich testach 1000 wywołań zajmowało łącznie ok. 1,6 sekundy... ehhh...


A jak odpalales program?

- za kazdym razem exec()? "... program zostanie wykonany 1000 razy..." - problemem jest to ze czas odpalenia programu chyba przewyzsza znacznie czas wykonania obliczen - wiec neiznaczne roznice w algorytmach nie beda widoczne.
- czy w 1 skrypcie php odpaliles 1000razy funkcje do obliczen (nie tracisz czasu na odpalanie kodu)?

Napisany przez: phpion 5.11.2010, 13:16:57

Testowałem to tak, że w kodzie na sztywno zapisałem zakodowany ciąg wejściowy (ten z PDFa). Następnie do kodu dodałem:

  1. $xdebug_time_index = xdebug_time_index();
  2. $xdebug_memory_usage = xdebug_memory_usage();
  3. $xdebug_peak_memory_usage = xdebug_peak_memory_usage();
  4.  
  5. $sql = http://www.php.net/mysql_pconnect('localhost', 'root', '');
  6. http://www.php.net/mysql_select_db('konkurs', $sql);
  7.  
  8. http://www.php.net/mysql_query('INSERT INTO xdebug (script, xdebug_memory_usage, xdebug_peak_memory_usage, xdebug_time_index) VALUES ("'.$_SERVER['REQUEST_URI'].'", '.$xdebug_memory_usage.', '.$xdebug_peak_memory_usage.', '.$xdebug_time_index.')');

dzięki czemu zapisywałem sobie uzyskane parametry do bazy danych. Później wyświetlałem je sobie odpowiednim widokiem, który obliczał sumaryczny czas wykonania, średni czas wykonania itp.

Skrypt wywoływałem poprzez:
Kod
ab -n1000 http://...


Szczerze mówiąc sądzę, że byłbym w zdecydowanej czołówce. Siedziałem nad tym praktycznie bite 2 tygodnie. Kombinowałem raz tak, raz srak (i w moich testach wyszło, że while jest faktycznie szybsze od for!) i w końcu spłodziłem to, co spłodziłem. Nawet głupie obliczanie długości wejścia zrobiłem while'm, gdyż było to szybsze niż strlen. No ale zapomniałem (źle doczytałem) końcowego entera sciana.gif

Aha, żeby umożliwić zapis danych do bazy musiałem zamienić die() na zwykłe echo, co też spowolniło działanie skryptu (sprawdzałem również bez zapisu do bazy).

// Edit:
Poniżej zebrane czasy zamieszczonych tu prac (uruchamiane w kolejności alfabetycznej z ok. 10 sekundowymi przestojami między kolejnymi uruchomieniami):
Kod
+---------------+-------------------+
| skrypt        | czas              |
+---------------+-------------------+
| phpion.php    |  1.63519223213194 |
| rolka.php     |  2.08828377723708 |
| sever88.php   |  2.11622476577766 |
| krowal.php    |  2.79060316085828 |
| l0ud.php      |  3.10421872138977 |
| dr_bonzo.php  |  3.55402493476858 |
| askone.php    |  3.72726726532000 |
| Daimos.php    |  3.82858920097367 |
| zegarek84.php |  4.41141557693496 |
| Pawel_W.php   |  5.93350315093991 |
| ernie242.php  |  7.32922220230119 |
| Demio.php     |  9.24934792518643 |
| jasin.php     | 21.57112717628520 |
+---------------+-------------------+

Napisany przez: ernie242 5.11.2010, 13:38:56

2 tygle. Wow, no to naprawdę szkoda :/

Napisany przez: dr_bonzo 5.11.2010, 13:46:36

@phpion - roznice w czasach sa ciekawe. Moze to "wina" php'a jako modul apacha i jakichs keszow.

Napisany przez: phpion 5.11.2010, 13:52:32

Może, nie wiem. Ja opierałem się na tych wynikach testując kolejne wersje swojego rozwiązania. Faktycznie - szkoda tych 2 tygodni (coprawda jedynie pracując po godzinach w domu, ale jednak...) ale mogę być wściekły tylko na siebie. Ponoć przypadków jak mój było więcej i zostaną upublicznione czasy wykonania wszystkich nadesłanych prac. Oczywiście błędne rozwiązania nie będą wchodziły w grę w konkursie. Dlatego jedyne co teraz mi pozostaje to cicha nadzieja, że moje rozwiązanie w liście ogólnej nie znajdzie się na żadnym z trzech pierwszych miejsc smile.gif hehe.

Napisany przez: ernie242 5.11.2010, 14:11:13

Być może podarują Tobie ten jeden LF smile.gif

Napisany przez: dr_bonzo 5.11.2010, 14:13:22

A mi smieci w kodzie i kiepski czas.

Napisany przez: phpion 5.11.2010, 14:15:09

Cytat(ernie242 @ 5.11.2010, 14:11:13 ) *
Być może podarują Tobie ten jeden LF smile.gif

Nie - już wyniuchałem tą sprawę. Jest to błąd w rozwiązaniu i tyle.

Teraz sobie pomyślałem o sztandarowym tekście: "Nie przyjechałem tu dla pieniędzy, przyjechałem się dobrze bawić, to tylko gra" smile.gif hehe.

Napisany przez: rzymek01 5.11.2010, 16:10:05

@phpion nie ma co się poddawać, nawet na olimpiadzie informatycznej nie karzą za brak znaku nowej linii smile.gif

PS. faktycznie, juz poprawiłem tongue.gif

Napisany przez: flashdev 5.11.2010, 16:21:15

Cytat(rzymek01 @ 5.11.2010, 16:10:05 ) *
@phpion nie ma co się poddawać, nawet na olimpiadzie informatycznej nie każą za brak znaku nowej linii smile.gif


Rzeczywiście dziwnie to zostało zorganizowane. Na takim spoj.pl dodatkowe entery nie odgrywają żadnej roli, ponieważ te linijki przez taką instrukcję jak scanf zostałyby odczytane w ten sam sposób, anwet jak by nie było enterów pomiędzy kolejnymi prostokątami.

karzą - karwinksmiley.jpg

Napisany przez: dr_bonzo 5.11.2010, 16:23:28

No dobra, ale to byl chyba najjasniej i najprecyzyjniej opisany punk regulaminu smile.gif

Napisany przez: Pawel_W 5.11.2010, 17:53:30

ja o tym dobrze wiedziałem i sam nie wiem, dlaczego nie dałem tej dodatkowej linii... może jakiś rozkojarzony byłem? smile.gif

Napisany przez: ADeM 5.11.2010, 22:54:48

Mój amatorski kod: http://pastebin.com/ETZPV0Ug

Napisany przez: phpion 6.11.2010, 13:40:51

Cytat(dr_bonzo @ 5.11.2010, 16:23:28 ) *
No dobra, ale to byl chyba najjasniej i najprecyzyjniej opisany punk regulaminu smile.gif

Może i było to dość jasno i wyraźnie napisane, ale ja (jak i ponoć całkiem sporo osócool.gif odczytaliśmy to nieco inaczej. Szczerze mówiąc miałem (mam?) nadzieję, że celem konkursu jest faktycznie napisanie skryptu, który w sposób najwydajniejszy wykona postawione zadanie (w zasadzie 2: odkodowanie ciągu i utworzenie prostokątów). Okazuje się jednak, że reguły są sztywne i tak naprawdę rozwiązanie schodzi na drugi plan, a jego miejsce zajmuje czytanie ze zrozumieniem. Moim skromnym zdaniem brakujący enter nie jest wyznacznikiem poprawności rozwiązania zadania. Rozumiem błędy w odkodowaniu ciągu, obliczania kolejnej wartości sekwencji, złe umieszczenie cyfr w prostokątach... no ale enter? To jakby na konkursie matematycznym podkreślić wynik końcowy, a nie napisać "Odp: Wynik to X".

Poza tym w poście informującym o konkursie DeyV napisał:
Cytat
Jeśli macie jakieś pytania lub sugestie -piszcie śmiało

Pytań było kilka i na żadne (ze związanych z postawionym zadaniem) nie uzyskaliśmy odpowiedzi. Jeśli więc z założenia miało to wyglądać "macie i główkujcie" to informacja o możliwości zadawania pytań była zbędna.

Może jestem rozgoryczony swoim przypadkiem i się czepiam, ale mogłoby to wyglądać nieco lepiej...

Napisany przez: Pawel_W 6.11.2010, 13:48:32

Cytat(phpion @ 6.11.2010, 13:40:51 ) *
To jakby na konkursie matematycznym podkreślić wynik końcowy, a nie napisać "Odp: Wynik to X".

no to jest akurat złe porównanie, bo na większości konkursów (przynajmniej tak było w podstawówce i gimnazjum) trzeba było udzielić pełnej odpowiedzi słownej smile.gif

ale popieram smile.gif

Napisany przez: phpion 6.11.2010, 14:13:01

No to może porównanie średnio trafne. Na konkursach/olimpiadach matematycznych bywałem w podstawówce, czyli jakiś czas temu winksmiley.jpg

Napisany przez: itsme 6.11.2010, 14:23:55

pamiętajcie że jezeli chodzi o pierwsza nagrode tutaj decyzje podejmuje polcode natomiast jezeli chodzi 2 i 3 to mentax.

Zatem można wliczyć na zdrowo rozsądkowe podejście do Waszych prac.
NIe mniej należy wrócić uwagę na fakt że tutaj prezentuje swój kod okolo 10-15 osób zaś prac konkursowych wpłynęło znacznie więcej.

teraz pozostało się uzbroić w cierpliwość !

Napisany przez: phpion 6.11.2010, 14:52:50

Cytat(itsme @ 6.11.2010, 14:23:55 ) *
Zatem można wliczyć na zdrowo rozsądkowe podejście do Waszych prac.

No i jakaś iskierka nadziei pozostaje. Ja osobiście nie upieram się, że prace typu jak moja muszą (nawet złe słowo!) być wzięte pod uwagę, ale zdrowo rozsądkowe podejście byłoby oczywiście mile widziane. Cóż - pozostaje nam czekać. Jakby nie było to konkurs był super pomysłem i mnie osobiście nauczył bardzo wiele. Coprawda w pracy codziennej nadal będę używał strlen zamiast while winksmiley.jpg ale jednak sporo do głowy weszło.

Napisany przez: flashdev 6.11.2010, 17:05:17

Cytat(phpion @ 6.11.2010, 14:52:50 ) *
No i jakaś iskierka nadziei pozostaje. Ja osobiście nie upieram się, że prace typu jak moja muszą (nawet złe słowo!) być wzięte pod uwagę, ale zdrowo rozsądkowe podejście byłoby oczywiście mile widziane. Cóż - pozostaje nam czekać.

Trzymam kciuki, żeby tak było.

Cytat(phpion @ 6.11.2010, 14:52:50 ) *
Jakby nie było to konkurs był super pomysłem i mnie osobiście nauczył bardzo wiele. Coprawda w pracy codziennej nadal będę używał strlen zamiast while winksmiley.jpg ale jednak sporo do głowy weszło.


Co do strlen, czytam to co piszesz i nie mogąc w to uwierzyć robie własne testy, których wyniki prezentuję poniżej.

Testowałem 8 skryptów, 6 z nich analogicznych do 2 poniższych:
  1. <?php
  2. $str = http://www.php.net/str_repeat('x', 1e4);
  3. while( $n-- ){
  4. $len = http://www.php.net/strlen($str);
  5. }

  1. <?php
  2. $str = http://www.php.net/str_repeat('x', 1e4);
  3. while( $n-- ){
  4. $len = 0;
  5. while(http://www.php.net/isset($str{++$len}));
  6. }


założenia:
$n = 1e6;
Każdy z kodów uruchomiony 10 razy. Wyniki to średnia i odchylenie.

wyniki pomiarów:
Kod
av:    0.423 [s]    sd:    0.012 [s]    _strlen 1e1.php
av:    0.426 [s]    sd:    0.027 [s]    _strlen 1e2.php
av:    0.425 [s]    sd:    0.014 [s]    _strlen 1e3.php
av:    0.433 [s]    sd:    0.019 [s]    _strlen 1e4.php

av:    1.208 [s]    sd:    0.010 [s]    _while strlen 1e1.php
av:    11.386 [s]    sd:    0.253 [s]    _while strlen 1e2.php
av:    113.773 [s]    sd:    1.262 [s]    _while strlen 1e3.php
av:    1178.517 [s]    sd:    26.398 [s]    _while strlen 1e4.php


Wniosków można było się spodziewać:
- strlen cechuje się praktycznie zerowym (pomijalnie małym do wykonania funkcji itd.) wpływem długości ciągu wejściowego na czas wykonywania,
- czas wykonania zliczania przy pomocy while jest liniowo zależny od długości ciągu,
- pętla while ma szanse wygrać z strlen przy ciągach o długości około 5 i mniejszych.

Przypominam jeszcze raz, że wyniki podawane tu na forum są tylko poglądowe a rzeczywiste wyniki mogą się sporo różnić, ponieważ nie znamy testów.

Napisany przez: phpion 6.11.2010, 17:19:06

Przyznam, że nie testowałem strlen vs while na długich ciągach znaków. Maksymalna długość to była ok. 30 znaków. Możliwe więc, że jest jak piszesz i wydajność while jest wprost proporcjonalna co długości ciągu, podczas gdy wydajność strlen jest bardziej stabilna. Gdzieś wyczytałem, że strlen po drodze dokonuje kilku dodatkowych operacji (m.in. zamienia znaki na małe) wobec czego szukałem alternatywnego rozwiązania.

Generalnie mój kod miał wiele odmian smile.gif Przykładowo parametry KWAZ zapisywałem jako tablicę, później próbowałem utworzyć z nich stałe, jednak okazało się, że najlepiej wypada po prostu dynamiczne (poprzez $$) tworzenie zmiennych. Do tego cieszyłem się z obsługi 2 specyficznych sytuacji, w których mógłbym deklasować inne rozwiązania:
1. Zakończenie dekodowania ciągu w momencie zebrania wszystkich parametrów, czyli dla np. K3W3A3Z3XXXXXXXXXXXXXXXXXXX kończymy w momencie dotarcia do pierwszego X.
2. Osobne generowanie prostokątów dla min = max.

Zobaczymy jak to będzie smile.gif

Napisany przez: flashdev 6.11.2010, 17:29:16

Cytat(phpion @ 6.11.2010, 17:19:06 ) *
Przyznam, że nie testowałem strlen vs while na długich ciągach znaków. Maksymalna długość to była ok. 30 znaków. Możliwe więc, że jest jak piszesz i wydajność while jest wprost proporcjonalna co długości ciągu, podczas gdy wydajność strlen jest bardziej stabilna. Gdzieś wyczytałem*, że strlen po drodze dokonuje kilku dodatkowych operacji (m.in. zamienia znaki na małe) wobec czego szukałem alternatywnego rozwiązania.

Generalnie mój kod miał wiele odmian smile.gif Przykładowo parametry KWAZ zapisywałem jako tablicę, później próbowałem utworzyć z nich stałe, jednak okazało się, że najlepiej wypada po prostu dynamiczne (poprzez $$) tworzenie zmiennych. Do tego cieszyłem się z obsługi 2 specyficznych sytuacji, w których mógłbym deklasować inne rozwiązania:
1. Zakończenie dekodowania ciągu w momencie zebrania wszystkich parametrów, czyli dla np. K3W3A3Z3XXXXXXXXXXXXXXXXXXX kończymy w momencie dotarcia do pierwszego X.
2. Osobne generowanie prostokątów dla min = max.

Zobaczymy jak to będzie smile.gif


* blinksmiley.gif - mam nadzieję, że nie w http://php.net/manual/en/function.strlen.php smile.gif

Co do 1 i 2 punktu to prawda, że mogło to pomóc, ale nie wiadomo jakie są testy. Nie wiadomo, czy ten zysk będzie większy niż czas na wykonanie tych 1k if`ów.
Żeby mieć jakieś wnioski trzebaby założyć, że np.
- długość ciągu jest losowa od 1 do 10k (przy większych u mnie nie działa),
- parametry w ciągu są rozmieszczone losowo,
- rozkłąd prawdopodobieństwa wylosowania danej liczby jest równomierny.
I z takimi założeniami można już robić jakieś obliczenia/symulacje.

A powyższe założenia są w miarę sensowne, ponieważ zakładam, że te testy generował komputer a nie człowiek.

Napisany przez: phpion 6.11.2010, 19:38:57

Cytat(flashdev @ 6.11.2010, 17:29:16 ) *
* blinksmiley.gif - mam nadzieję, że nie w http://php.net/manual/en/function.strlen.php smile.gif

Nie, nie był to manual. Nie wiem również ile w tym jest prawdy. Jeśli chodzi o ciąg wejściowy, to nie będzie on raczej generowany losowo. Przynajmniej ja będąc na miejscu organizatorów ułożyłbym kilka różnych ciągów sprawdzając reakcję programu w różnych warunkach. Takie 3 sztandarowe przykłady to właśnie:
- K3W3A1Z5XXXXXXXXXXX - czyli parametry podane na samym początku (można optymalizować poprzez przerwanie wyszukiwania),
- XXXXXK3W3A1Z1XXXXXX - czyli min = max (nie ma potrzeby odpalania całego algorytmu budowania prostokątów),
- no i jakiś "normalny" zestaw parametrów dla wygenerowania prostokątów.
Ja przyjąłem, że tego typu zestawy otrzymamy smile.gif

Napisany przez: ernie242 6.11.2010, 23:25:18

Cóż, powili zaczynam żałować, że zupełnie nie miałem czas na optymalizację skryptu. Można pewnie dużo się nauczyć. O np. to:

Cytat(flashdev @ 6.11.2010, 17:05:17 ) *
Wniosków można było się spodziewać:
- strlen cechuje się praktycznie zerowym (pomijalnie małym do wykonania funkcji itd.) wpływem długości ciągu wejściowego na czas wykonywania,
- czas wykonania zliczania przy pomocy while jest liniowo zależny od długości ciągu,
- pętla while ma szanse wygrać z strlen przy ciągach o długości około 5 i mniejszych.


Dziękuję za umieszczenie tego tutaj, byłem tego bardzo ciekaw. Gdy wcześniej usłyszałem, że użycie while może być szybsze niż strlen to pomyślałem sobie, że z PHP chyba musi być coś poważnie nie tak. A teraz wszystko jasne, według mnie, wyniki są logiczne.

Napisany przez: l0ud 7.11.2010, 21:38:43

@phpion, mógłbyś spróbować przeprowadzić te testy prędkości jeszcze raz, tym razem bez xdebug? Przetestowałem kilka kodów za pomocą zwykłej pętli (100000 iteracji) i buforowania wyjścia, a Twój kod, choć w czołówce - wcale nie wyszedł najszybszy.

Napisany przez: rzymek01 8.11.2010, 00:16:37

możesz zamieścic wyniki smile.gif

Napisany przez: chrix 8.11.2010, 23:35:09

Witam wszystkich!!!!

Jestem tu nowy, ale też wysłałem pracę na konkurs. Niestety też jest błąd - zrozumiałem, że kody KWAZ mogą być tylko wielkimi literami, a szum różnie - stąd skrypt nie robi toUpper - i pewnie na tym polegnie.
Ale może ktoś z kolegów będzie umiał ocenić szybkość tego skryptu



  1. <?php
  2. function a() {
  3. http://www.php.net/global $argv;
  4. $invcode='9876543210ZYXWVUTSRQPONMLKJIHGFEDCBA9876543210ZYXWVUTSRQPONMLKJIHGFEDCBA';
  5. $p=-1;
  6. $i=$move=$l=http://www.php.net/strlen($argv[1]);
  7. $last=$prelast='0';
  8. do {
  9. $of=$move%36;
  10. $idx=ord($argv[1][++$p]);
  11. ($idx<65)?$v=$invcode[57-$idx+$of]:$v=$invcode[100-$idx+$of];
  12. $vv=ord($v)-48;
  13. if ($vv>-1&&$vv<10) {
  14. switch($last) {
  15. case'K':
  16. $k=$vv;
  17. break;
  18. case'W':
  19. $w=$vv;
  20. break;
  21. case'A':
  22. $a=$vv;
  23. break;
  24. case'Z':
  25. $z=$vv;
  26. break;
  27. case'1':
  28. if($prelast=='K')$k=10+$vv;
  29. elseif($prelast=='W')$w=10+$vv;
  30. break;
  31. case'2':
  32. if($prelast=='K')$k=20;
  33. elseif($prelast=='W')$w=20;
  34. break;
  35. }
  36. }
  37. $prelast=$last;
  38. $last=$v;
  39. $step=$move;
  40. $move+=$l;
  41. $l=$step;
  42. }while(--$i);
  43. $pt='0123456789';
  44. $bar='-------------------------------
  45. -*****************************-
  46. -*****************************-
  47. -*****************************-
  48. -*****************************-
  49. -*****************************-
  50. -*****************************-
  51. -*****************************-
  52. -*****************************-
  53. -*****************************-
  54. -*****************************-
  55. -*****************************-
  56. -*****************************-
  57. -*****************************-
  58. -*****************************-
  59. -*****************************-
  60. -*****************************-
  61. -*****************************-
  62. -*****************************-
  63. -*****************************-
  64. -*****************************-
  65. -*****************************-
  66. ';
  67. $ii=(int)$w*$k;
  68. $bar[$k+33]='-';
  69. $s=33;
  70. $t=($w<<5);
  71. $off=33;
  72. $off2=$t+1;
  73. $off3=$t+$k;
  74. $K=$k>>1;
  75. $s=$off2+32;
  76. do {
  77. $bar[++$s]='-';
  78. ++$s;
  79. }while(--$K);
  80. $bar[$off3+32]='-';
  81. $bar3=$bar2=$bar;
  82. $v=$a;
  83. $vec=1;
  84. $vec2=-32;
  85. do {
  86. $bar[$off]=$pt[$v];
  87. $bar2[$off2]=$pt[$v];
  88. $bar3[$off3--]=$pt[$v];
  89. if ($bar[$off+$vec]!='*')switch($vec) {
  90. case'1':$vec=32;
  91. break;
  92. case'32':$vec=-1;
  93. break;
  94. case'-1':$vec=-32;
  95. break;
  96. case'-32':$vec=1;
  97. }
  98. $off+=$vec;
  99. $off2+=$vec2;
  100. if ($bar2[$off2]!='*') {
  101. $vec2=-$vec2;
  102. $off2+=$vec2+1;
  103. }
  104. if($bar3[$off3]!='*')$off3-=32-$k;
  105. ($v==$z)?$v=$a:++$v;
  106. }while(--$ii);
  107. $eff3=$eff2=$eff='';
  108. $off=33;
  109. $W=$w;
  110. do {
  111. $K=$k;
  112. do {
  113. $eff.=$bar[$off];
  114. $eff2.=$bar2[$off];
  115. $eff3.=$bar3[$off++];
  116. }while(--$K);
  117. $eff.='
  118. ';
  119. $eff2.='
  120. ';
  121. $eff3.='
  122. ';
  123. $off+=32-$k;
  124. }while(--$W);
  125. http://www.php.net/echo $eff,'
  126. ',$eff2,'
  127. ',$eff3,'
  128. ';
  129. }
  130. a();

Napisany przez: l0ud 8.11.2010, 23:40:49

Wyników nie dam, ale kod którym sprawdziłem 2 pierwsze prace i swoją z ciekawości:

http://wklej.org/id/415396/

Czyżbym źle mierzył, czy to xdebug powoduje narzut i związane z tym przekłamania?

[edit]

chrix, po teście - Twój kod działa przeciętnie szybko smile.gif Inna sprawa, że aby to sprawdzić musiałem wywalić tą całą funkcję z globalem.

Napisany przez: chrix 9.11.2010, 00:46:26

Wielkie dzięki!!!

no to chyba nie najgorzej. Założenie zawarcia skryptu w funkcji to przyjęcie ryzyka, że jej wywołanie zajmie mniej czasu parserowi php, niż sprawdzanie każdej zmiennej w tablicy globali, jak to ma podobno miejsce w kodzie na zewnątrz funkcji.
Z regulaminu wynika, że program będzie wywoływany w testach z konsoli samodzielnie

Kod
php.exe -f test.php COSTAMKOD > itd

Napisany przez: kaliberx 9.11.2010, 18:13:55

Jak dla mnie sposób pomiaru zaproponowany w regulaminie jest niezbyt dobry. Zakładając, że kod będzie w stylu:

  1. $prog = 'moj.php';
  2. $param = 'VTRNH7R1VZXZZ137DN3TZVXVVTTZ4CU1U40C2137DN3TZVXVVTRNH7R1VZXZZ137DN3TZV';
  3. for ($i=0; $i<1000; $i++) {
  4. http://www.php.net/popen("php -f $prog $param", "r");
  5. }


to:
1. Czas wykonania fork() z php zajmuje ponad 95% całości czasu!
2. Pomiar czasu jest obarczonym dużym błędem sięgającym 5% na moim systemie (Ubuntu 10.10, Core i5-720).
3. Przykładowo mój program wykonuje się w 12.8s a zwykły "Hello World" 12.4s.
4. Porównuję czas wykonania dwóch programów w którym każdy w środku ma pętlę 1000 razy to różnica między nimi wynosi 25%, tj. jeden 0.4s a drugi 0.5s. I teraz proponowanym sposobem pomiaru program pierwszy wykonuję się w czasie 12.8s a drugi 12.9s. Rożnica wynosi 0.75%! Ponadto pamiętajmy o punkcie drugim! Podsumowując, czas pierwszego programu mieści się w przedziale [12.5, 13.1], a drugiego [12.6, 13.2]. Więc który wygra?

Mam nadzieję, że popełniłem błąd w tym wywodzie, bo jeśli nie, to Jury będzie wybierać najładniejszy kod i na nic zdadzą się nasze wyrafinowane optymalizacje.

Napisany przez: dr_bonzo 9.11.2010, 18:54:41

@kaliberx: całkowicie sie z toba zgadzam. W regulaminie pisze ze program (jako calosc) bedzie odpalana 1000 razy, a nie sama "funkcja". I to niweluje kompletnie roznice miedzy rozwiazaniami.

Z tego powodu dałem sobie spokój z optymalizacjami po kilku godzinach.

Napisany przez: ernie242 10.11.2010, 21:12:02

Cytat(kaliberx @ 9.11.2010, 18:13:55 ) *
Jak dla mnie sposób pomiaru zaproponowany w regulaminie jest niezbyt dobry. Zakładając, że kod będzie w stylu:


Ok, ale jest napisane tylko, że będzie uruchamiany 1000 razy. Nic nie ma o tym JAK to będzie wykonane. Mogą użyć skryptu w Bash. Make. Rakefile. Cokolwiek innego...

Napisany przez: dr_bonzo 10.11.2010, 21:15:09

Cytat
Mogą użyć skryptu w Bash. Make. Rakefile. Cokolwiek innego...

To juz bez roznicy - najwieksza roznica jest miedzy odpalaniem skryptu 1000x jako "php -r plik.php" lub jako funkcja w petli odpalana 1000x.

AFAIR to w dokumentacji pisali ze czytac mamy z $argv, i odpalane bedzie jako "php -r plik.php CIAG_ZNAKOW"

Napisany przez: DeyV 17.11.2010, 20:23:24

Wyniki zostały ogłoszone. http://wortal.php.pl/Wortal/Aktualnosci/Wydarzenia/Konkursy/Konkurs-Jesien-2010-wyniki

Serdeczne gratulacje dla nagrodzonych, i gorące podziękowania wszystkim, którzy wzięli udział.

Pozdrawiam serdecznie smile.gif

Napisany przez: pauluZ 18.11.2010, 17:58:27

Po cichutku, bez dużego udzielania się na tym forum znalazłem się na 5. miejscu.
Wynik OK bez fail'ów.
Kod zwarty i cały czas miałem zgryz bo go skracałem zamiast optymalizować.
Pewnie wymiana jakiegoś drobniutkiego rozwiązania w moim kodzie pozwoliłaby
na przyspieszenie go o te pół sekundy jakie mi zabrakło przy 1000 wywołań smile.gif
Wklejam całość tutaj oraz przez link:

http://wklej.org/id/421468/

5. miejsce i kusi mnie strasznie chęć chwalenia się smile.gifsmile.gif - ajajaj smile.gif Pozdrawiam!!

Gratulacje!! dla zwycięzców oraz dla 4. miejsca --- także zamieść swój kod exclamation.gif
Jesteś lepszy ode mnie o 0.16 sekundy, hehehe

  1. <?php
  2. /**
  3.  * Polcode Code Contest PHP-2010.10
  4.  * Nick: pauluZ
  5.  */
  6. $t['A'] = 0; $t['B'] = 1; $t['C'] = 2; $t['D'] = 3; $t['E'] = 4; $t['F'] = 5; $t['G'] = 6; $t['H'] = 7; $t['I'] = 8; $t['J'] = 9;
  7. $t['K'] = 10; $t['L'] = 11; $t['M'] = 12; $t['N'] = 13; $t['O'] = 14; $t['P'] = 15; $t['Q'] = 16; $t['R'] = 17; $t['S'] = 18; $t['T'] = 19;
  8. $t['U'] = 20; $t['V'] = 21; $t['W'] = 22; $t['X'] = 23; $t['Y'] = 24; $t['Z'] = 25; $t['0'] = 26; $t['1'] = 27; $t['2'] = 28; $t['3'] = 29;
  9. $t['4'] = 30; $t['5'] = 31; $t['6'] = 32; $t['7'] = 33; $t['8'] = 34; $t['9'] = 35;
  10. $str = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789';
  11. $arg = $argv[1];
  12.  
  13. $lenght = http://www.php.net/strlen($arg);
  14.  
  15. $out = '';
  16. $fib[-2] = 0;
  17. $fib[-1] = $lenght;
  18. for ($i = 0; $i < $lenght; $i++) {
  19. $fib[$i] = $fib[$i-2] + $fib[$i-1];
  20. $j = ($t[$arg{$i}] - $fib[$i]) % 36;
  21. $out .= $str[(($j<0)?($j+36):$j)];
  22. }
  23. http://www.php.net/preg_match_all('([KWAZ][0-9][0-9]?)', $out, $matches);
  24. for ($i = 0; $i < 4; $i++) {
  25. ${$matches[0][$i]{0}} = http://www.php.net/substr($matches[0][$i], 1);
  26. }
  27. // ----------------------------------------------------
  28. // pierwszy prostokat - 1
  29. $p = $A;
  30. $sx = 1;
  31. $sy = 1;
  32. $kx = $K;
  33. $ky = $W;
  34. while (true) {
  35.  
  36. for ($x=$sx; $x<=$kx; $x++) {
  37. $result[$x][$sy] = $p;
  38. ($p==$Z) ? $p = $A : $p++;
  39. }
  40. $sy++;
  41. if ($sy > $ky) break;
  42.  
  43. for ($y=$sy; $y<=$ky; $y++) {
  44. $result[$kx][$y] = $p;
  45. ($p==$Z) ? $p = $A : $p++;
  46. }
  47. $kx--;
  48. if ($sx > $kx) break;
  49.  
  50. for ($x=$kx; $x>=$sx; $x--) {
  51. $result[$x][$ky] = $p;
  52. ($p==$Z) ? $p = $A : $p++;
  53. }
  54. $ky--;
  55. if ($sy > $ky) break;
  56.  
  57. for ($y=$ky; $y>=$sy; $y--) {
  58. $result[$sx][$y] = $p;
  59. ($p==$Z) ? $p = $A : $p++;
  60. }
  61. $sx++;
  62. if ($sx > $kx) break;
  63. }
  64.  
  65. for ($y=1; $y<=$W; $y++) {
  66. for ($x=1; $x<=$K; $x++) {
  67. http://www.php.net/echo $result[$x][$y];
  68. }
  69. http://www.php.net/echo "\n";
  70. }
  71. http://www.php.net/echo "\n";
  72. // ----------------------------------------------------
  73. // drugi prostokat - 2
  74. $p = $A;
  75. $x = 1;
  76. while ($x <= $K) {
  77. if ($x % 2 == 1) {
  78. for ($y=$W; $y>=1; $y--) {
  79. $result[$x][$y] = $p;
  80. ($p==$Z) ? $p = $A : $p++;
  81. }
  82. } else {
  83. for ($y=1; $y<=$W; $y++) {
  84. $result[$x][$y] = $p;
  85. ($p==$Z) ? $p = $A : $p++;
  86. }
  87. }
  88. $x++;
  89. }
  90.  
  91. for ($y=1; $y<=$W; $y++) {
  92. for ($x=1; $x<=$K; $x++) {
  93. http://www.php.net/echo $result[$x][$y];
  94. }
  95. http://www.php.net/echo "\n";
  96. }
  97. http://www.php.net/echo "\n";
  98. // ----------------------------------------------------
  99. // trzeci prostokat - 3
  100. $R = $K*$W;
  101. $groups = http://www.php.net/floor( $R / ($Z-$A+1) );
  102. $remain = $R - ($groups * ($Z-$A+1));
  103.  
  104. $sek_s = '';
  105. for ($i=$Z; $i>=$A; $i--) {
  106. $sek_s .= $i;
  107. }
  108. $sek = '';
  109. for ($i=1; $i<=$groups; $i++) {
  110. $sek .= $sek_s;
  111. }
  112. for ($i=$A; $i<=$A+$remain-1; $i++) {
  113. $sek = $i . $sek;
  114. }
  115.  
  116. http://www.php.net/echo http://www.php.net/chunk_split($sek, $K, "\n");
  117. http://www.php.net/echo "\n";

Napisany przez: dr_bonzo 18.11.2010, 18:05:45

Masz calkiem sexi kod

Kod
$sek_s .= $i;

Napisany przez: phpion 18.11.2010, 19:39:16

Cytat(dr_bonzo @ 18.11.2010, 18:05:45 ) *
Masz calkiem sexi kod

Kod
$sek_s .= $i;

Hehehe, dobre smile.gif

Na spokojnie w domu postanowiłem jeszcze raz odpalić testy. Sprawdziłem tylko te prace, które były przede mną i które zostały upublicznione. Oto wyniki.

1. Sumaryczne czasy dla każdego wejścia (1000 wywołań):
Kod
+-----------------------------------------------------+------------------+
| script                                              | sum_ti           |
+-----------------------------------------------------+------------------+
| phpion.php?in=Y5LU61ZGYAKM9C6Y6IWU3ZPC95LDGM0MT3V   | 1.50808167457590 |
| phpion.php?in=ZPPUXLMR2S93NEBWCIXOCKWFM             | 1.96194171905514 |
| ogaws.php?in=Y5LU61ZGYAKM9C6Y6IWU3ZPC95LDGM0MT3V    | 1.97012424469003 |
| pauluZ.php?in=Y5LU61ZGYAKM9C6Y6IWU3ZPC95LDGM0MT3V   | 2.07399821281427 |
| kaliberx.php?in=Y5LU61ZGYAKM9C6Y6IWU3ZPC95LDGM0MT3V | 2.16468429565446 |
| ogaws.php?in=ZPPUXLMR2S93NEBWCIXOCKWFM              | 2.24561262130736 |
| pauluZ.php?in=ZPPUXLMR2S93NEBWCIXOCKWFM             | 2.44730377197269 |
| kaliberx.php?in=ZPPUXLMR2S93NEBWCIXOCKWFM           | 2.50407171249373 |
| phpion.php?in=C0DNQDYNZOKH4T2PU57682QKFH8C3         | 2.59955668449399 |
| ogaws.php?in=C0DNQDYNZOKH4T2PU57682QKFH8C3          | 2.78515815734878 |
| kaliberx.php?in=C0DNQDYNZOKH4T2PU57682QKFH8C3       | 2.95505619049084 |
| pauluZ.php?in=C0DNQDYNZOKH4T2PU57682QKFH8C3         | 3.51078677177436 |
+-----------------------------------------------------+------------------+


2. Już widać, że dla każdego zestawu jestem na czele, ale podsumowanie totalne:
Kod
+--------------+------------------+
| script       | sum_ti           |
+--------------+------------------+
| phpion.php   | 6.06958007812503 |
| ogaws.php    | 7.00089502334617 |
| kaliberx.php | 7.62381219863903 |
| pauluZ.php   | 8.03208875656132 |
+--------------+------------------+


Oczywiście przy tych testach nic nie kombinowałem żeby "przyspieszyć" swój kod. Jak widać co test (część z Was podawała wyniki własnych testów) to inne dane :/

Napisany przez: Daimos 18.11.2010, 19:47:11

Cytat(phpion @ 18.11.2010, 19:39:16 ) *
Hehehe, dobre smile.gif

Na spokojnie w domu postanowiłem jeszcze raz odpalić testy. Sprawdziłem tylko te prace, które były przede mną i które zostały upublicznione. Oto wyniki.

1. Sumaryczne czasy dla każdego wejścia (1000 wywołań):
Kod
+-----------------------------------------------------+------------------+
| script                                              | sum_ti           |
+-----------------------------------------------------+------------------+
| phpion.php?in=Y5LU61ZGYAKM9C6Y6IWU3ZPC95LDGM0MT3V   | 1.50808167457590 |
| phpion.php?in=ZPPUXLMR2S93NEBWCIXOCKWFM             | 1.96194171905514 |
| ogaws.php?in=Y5LU61ZGYAKM9C6Y6IWU3ZPC95LDGM0MT3V    | 1.97012424469003 |
| pauluZ.php?in=Y5LU61ZGYAKM9C6Y6IWU3ZPC95LDGM0MT3V   | 2.07399821281427 |
| kaliberx.php?in=Y5LU61ZGYAKM9C6Y6IWU3ZPC95LDGM0MT3V | 2.16468429565446 |
| ogaws.php?in=ZPPUXLMR2S93NEBWCIXOCKWFM              | 2.24561262130736 |
| pauluZ.php?in=ZPPUXLMR2S93NEBWCIXOCKWFM             | 2.44730377197269 |
| kaliberx.php?in=ZPPUXLMR2S93NEBWCIXOCKWFM           | 2.50407171249373 |
| phpion.php?in=C0DNQDYNZOKH4T2PU57682QKFH8C3         | 2.59955668449399 |
| ogaws.php?in=C0DNQDYNZOKH4T2PU57682QKFH8C3          | 2.78515815734878 |
| kaliberx.php?in=C0DNQDYNZOKH4T2PU57682QKFH8C3       | 2.95505619049084 |
| pauluZ.php?in=C0DNQDYNZOKH4T2PU57682QKFH8C3         | 3.51078677177436 |
+-----------------------------------------------------+------------------+


2. Już widać, że dla każdego zestawu jestem na czele, ale podsumowanie totalne:
Kod
+--------------+------------------+
| script       | sum_ti           |
+--------------+------------------+
| phpion.php   | 6.06958007812503 |
| ogaws.php    | 7.00089502334617 |
| kaliberx.php | 7.62381219863903 |
| pauluZ.php   | 8.03208875656132 |
+--------------+------------------+


Oczywiście przy tych testach nic nie kombinowałem żeby "przyspieszyć" swój kod. Jak widać co test (część z Was podawała wyniki własnych testów) to inne dane :/

a moj kod? snitch.gif tez dawalem, ale dam jeszcze raz, moze stworzymy jawna liste, jesli nikt nie ma nic przeciwko

12 miejsce, a kod:
http://wklej.org/id/412341/

Napisany przez: mike 18.11.2010, 19:50:12

Nieważne, kto głosuje, ważne, kto liczy głosy ~ Józef Stalin
~phpion nieważne jakie testy Ci wychodzą. Ważne, że to nie Twoje testy decydują tongue.gif

Napisany przez: phpion 18.11.2010, 20:03:00

@mike:
Masz 100% racji. Wiem też, że to że sobie potestuję to już niczego nie zmieni (tym bardziej, że mam FAILa). Jestem pewien, że gdyby uruchomiono testy ponownie to uzyskiwane czasy byłyby minimalnie różne, ale przy takich różnicach spowodowałoby to przetasowanie zajmowanych miejsc i wygrałby zapewne kto inny. Tak jak pisałem w jednym z wcześniejszych postów: następna edycja konkursu mogłaby opierać się na zminimalizowaniu zużycia pamięci. Wówczas czarno na białym mielibyśmy wynik: ten zużywa tyle pamięci, tamten tyle. Koniec i kropka.

Napisany przez: NetCoder 18.11.2010, 20:31:20

4. Miejsce

http://pastebin.com/dPBerZs9

Kod stworzony z myślą o długich ciągach do rozszyfrowania, dzięki którym błąd pomiarowy i procentowy narzut odpalenia interpretera byłby minimalny winksmiley.jpg

Napisany przez: rzymek01 18.11.2010, 21:39:44

Cytat(NetCoder @ 18.11.2010, 20:31:20 ) *
Kod stworzony z myślą o długich ciągach do rozszyfrowania

też napisałem pod kątem długiego ciągu wejściowego, jednak organizatorzy testowali na bardzo krótkich ciągach :/

Mimo wszystko cieszę się z udziału, fajna inicjatywa tongue.gif

Napisany przez: chrix 18.11.2010, 22:49:43

Witajcie!

Mój kod wkleiłem na tym forum stronę wcześniej! Uzyskał 10 miejsce!
Też dostałem faila, ale jakoś nigdzie w regulaminie nie znalazłem informacji, że nie można użyć kodowania UTF (questionmark.gif)

Napisany przez: Pawel_W 19.11.2010, 00:12:31

Cytat(chrix @ 18.11.2010, 22:49:43 ) *
Też dostałem faila, ale jakoś nigdzie w regulaminie nie znalazłem informacji, że nie można użyć kodowania UTF (questionmark.gif)

mogło być użyte, zapewne zapisałeś jako UTF BOM smile.gif

Napisany przez: pauluZ 19.11.2010, 02:20:19

Chciałbym pochwalić kod Krzysztofa "ogaws"-a ! ! !

Jest właśnie taki jaki ja chciałem napisać ale jestem leniem smile.gifsmile.gif
(miałem w głowie takie przebłyski rozwiązań co widzę u ogaws)

- użycie $seq dla cyfr
- jedno echo na końcu

Generalnie jakoś czuję podobieństwo między moim kodem a ogaws-a
Ciekawe czy wprowadzenie jego pomysłów w mój kod zmieniło by kolejność w rankingu smile.gifsmile.gif
Ale już oczywiście za późno na te dywagacje ....
Gratuluje ogaws - sporo kasy Ci skapło z nagrody smile.gif

Napisany przez: Demio 19.11.2010, 21:56:14

15 miejsce, jestem zadowolony, zwłaszcza że większość uczestników jest chyba bardziej zaawansowana wiekowo od mnie smile.gif kod już gdzieś wcześniej podawałem - ciekawy konkurs, oby więcej takich smile.gif pozdrawiam serdecznie i gratuluję zwycięzcom.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)