Strona używa cookies (ciasteczek). Dowiedz się więcej o celu ich używania i zmianach ustawień. Korzystając ze strony wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki.    X

*Golf - Czyli kto napisze krótszy kod

Czytając blogi trafiłem na ten wpis. Jako, że sam co nieco skrobię, to mnie zaciekawiło. Oczywiście o perl golfie słyszałem już dawno. W każdym razie pomijając wstęp (pisarzem to nie jestem) mam przyjemność ogłosić challenge :P

Zadanie

Mamy policzyc mozliwe przejscia z podanego punktu na danej planszy. Plansza: 2 2 1 2 9 3, gdzie: 2 pierwsze liczby oznaczają wymiary planszy, a reszta oznacza pola wypelniane od lewej do prawej. Z jednego pola na drugie można wejść tylko jeśli kolejne pole jest mniejsze od tego interesującego nas. Na planszy nie ma 2 takich samych pól, dzięki czemu każde pole jest jednoznacznie identyfikowane przez swoja wartosc. Pole moze przejsc tylko na swoich sąsiadów. Sąsiad w rozumieniu "góra, dół, lewo, prawo, lewo góra, lewo dół, prawo góra, prawo dół". Plansza nie jest "ciągła". To znaczy, że pierwszy element nie jest sąsiadem ostatniego.

Dane wejściowe:

X Y {CIĄG LICZB ODDZIELONYCH SPACJAMI} : Z
Gdzie: X - Szerokość planszy
Y - Wysokość planszy
Ciąg liczb - pola planszy np. 1 9 4 13 42 11 90 0 44
Z - liczba, oznacza pole dla którego mamy znaleźć możliwe ruchy.

Wyjście Liczba liczb oddzielonych spacjami, które symbolizują pola na które można wejść bezpośrednio z Z.

Przykład:
Wejście: 2 2 1 2 3 4 : 1
Wyście: (puste wyjście)

Wejście: 22 1 2 3 4 : 2
Wyjście: 1

Zadanie wymyśliłem sam w trakcie pisania posta, więc nie zdziwiłbym się gdyby zawierało jakieś błędy lub niejasności.

Aha, kto wygrywa? Ten, którego kod ma najmniej znaków. Znaki liczone "wc -c".
Język? Dowolny, polecam assemblera. Co otrzyma zwycięzca? Hm. Nic. Ale nie o to w tym chodzi prawda? :)

A więc zapraszam do zabawy!  

programowanie hobby

Komentarze

0 nowych
soanvig   10 #1 20.04.2012 20:39

Dodaj, że każda instrukcja powinna być zapisana w oddzielnej linii, za wyjątkiem instrukcji łączonych, jak np. w Ruby:

puts "jestem fajny, bo mam ifa w jednej linijce i nie muszę mieć end" if a == b

soanvig   10 #2 20.04.2012 20:39

A, napisałeś, że najmniejsza ilość znaków. Czyli Java odpada w tym momencie xD

soanvig   10 #3 20.04.2012 20:49

Co nie zmienia faktu, że ja za cholerę nie rozumiem co mam zrobić. Znaczy rozumiem co mam zrobić, ale nie rozumiem tego ciągu cyfr, wypełniania itp. Po prostu całej kwintesencji.

matiit   7 #4 20.04.2012 21:04

2 2 1 2 3 4 : 3
Wyobraz sobie to jako:
1 2
3 4

W tym przypadku kazdy jest swoim sasiadem

4 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 : 5

Wyobraz sobie to jako

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Sąsiadami 5 są 1 2 6 9 i 10.
A z 5 mozesz dojsc na 1 2 bo są mniejsze

Druedain   14 #5 20.04.2012 21:41

Panie i panowie, a nie lepiej iść na SPOJ z takimi zabawami?

matiit   7 #6 20.04.2012 22:05

A co jest złego w takiej "wewnątrz dobroprogramowej" zabawie?
Tak samo można powiedzieć, żeby iść na joggera z blogowaniem ;)
Więcej luzu :P

Druedain   14 #7 20.04.2012 22:46

Nie napisałem, że to jest złe. Po prostu wydaje mi się, że może być problem z frekwencją i dobry pomysł upadnie. Ponadto brak ludzi mogących tworzyć sensowny kod w każdym pokazanym języku lub osób potrafiących to weryfikować, może spowodować tworzenie się uprzedzeń względem dobrych narzędzi.

Ale jeśli faktycznie coś fajnego ma się stać, to „Zadanie wymyśliłem sam w trakcie pisania posta, więc nie zdziwiłbym się gdyby zawierało jakieś błędy lub niejasności” nie powinno się pojawiać (czytaj, nie powinno być powodów do jego pisania)!

  #8 20.04.2012 23:04

@Druedain zamiast marudzić ,pokaż lepiej co potrafisz :D

Frankfurterium   10 #9 20.04.2012 23:09

To już nie zabawa językiem na przykładzie rzeczywistego problemu, tylko algorytmika - coś ewidentnie nie dla mnie. Niedawno skończyłem studia i jeszcze mi się niedobrze robi, kiedy patrzę na takie abstrakcyjne zadania z numerkami...

Druedain   14 #10 20.04.2012 23:48

Ja od razu mówię, że żaden ze mnie mastah…

Draqun   9 #11 21.04.2012 00:15

Pomysł fajny, ale ostatnio zadania ze SPOJ'a tak mnie poryły, że algorytmiki trochę odpuszczam. Aktualnie uczę się Pythona od tak do pewnego projektu na koło naukowe ;)

kuba144   5 #12 21.04.2012 00:40

Wyczuwam SPOJa kategorię Challenge ;)

matiit   7 #13 21.04.2012 01:17

No ludzie to jest proste akurat :) Nie bedzie to 50 znakow, ale na prawde dosc realistyczne zadanie. (Przy grach czesto trzeba robic cos takiego)

etam   10 #14 21.04.2012 01:29

Jeżeli chodzi o najmniejszą liczbę znaków, to assembler nie jest najlepszy.

alucosoftware   7 #15 21.04.2012 04:36

Zadanie nie jest trudne i - i przy najbardziej łopatologicznym podejściu - ogranicza się do inicjalizacji tablicy i paru instrukcji warunkowych. Tu na prawdę nie ma "algorytmiki"...

@matiit
Pomysł fajny, choć z góry zwycięży język wspierający zwięzłą składnię i nazewnictwo np. Scala.

matiit   7 #16 21.04.2012 08:42

@etam u dont say! przeciez assembler był wspomniany dla żartu.

Ja myślałem np. o Haskellu, ewentualnie Prolog, który sam potrafi 'myslec'

soanvig   10 #17 21.04.2012 13:06

Ja myślałem o zawodach pisania kodu, a nie o tego typu zadaniach. Tutaj trzeba mieć sposób (algorytm). Jeśli takowy posiadamy to używając najprostszych funkcji języka można to zrealizować jako program. Dlatego lepsze byłyby zadania, które wymagają jak najlepszej znajomości swojego języka, a nie umiejętności myślenia i tworzenia algorytmów :) Tak więc zgadzam się z @Frankfurterium

matiit   7 #18 21.04.2012 14:30

@soanvig No wiesz, myślenie też jest ważną częścią programowania. Do tego zadania i tak nie ma żadnych "tricky" sposobów więc mozna sie wykazać znajomością jkichś fajnych funkcji języka :P

matiit   7 #19 21.04.2012 15:04

Przeciez w tym zadaniu nie masz zbyt duzo mozliwych sposobow :)
totalny brute

  #20 21.04.2012 15:25

poziom trudności "dla przedszkolaka". gdzie tu algorytmy?!

matzu   5 #21 21.04.2012 16:35

Ogólnie pomysł ciekawy, a czy fajny, to wyjdzie w praniu, jak (jeśli) ludzie zaczną wrzucać jakiś kod.

Jeśli chodzi o treść zadania, to mi osobiście brakuje informacji o tym, czy kod ma obejmować walidację danych wejściowych? W sensie np. wymiar macierzy podany jako 2x2, a w ciągu znalazło się np. 15 liczb. Czy też może należy przyjąć, że dane wejściowe zawsze są poprawne?

Poza tym nie ma informacji, czy dane wejściowe mają być przekazywane jako argumenty wiersza poleceń, czy też może powinny być podawane już po uruchomieniu programu.

Nie ma też informacji o tym, czy jest jakiś limit znaków. Bez sensu wrzucać kod, jeśli takowy limit już dawno się przekroczyło.

Ja naskrobałem programik bez walidacji w języku C#. Kod i jego rezultat znajduje się tutaj: http://ideone.com/yL9Z0 . Jak widać jest on odpalany pod Mono 2.8, ale pod .NET Framework również działa bez problemu.

W kodzie na sztywno umieściłem "4 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 : 5 ", bo inaczej kompilator rzucał mi wyjątkiem (nie ma jak przekazać parametrów). Wystarczy to podmienić przed kompilacją na swoim komputerze na Console.ReadLine() i będzie ok.

matiit   7 #22 21.04.2012 16:47

matzu no wreszcie konkret :P
Walidacja nieobowiązkowa, zakładamy ze dane sa poprawne.
Dane wejściowe chciałem żeby były brane z argv
Twoj kod zaraz przejrze :) (swoj tez juz mam, ale chce poczekac na kogos w pythonie:D )

matiit   7 #23 21.04.2012 16:59

matzu: 704 znaki bez whitespace'ow

matzu   5 #24 21.04.2012 17:08

@matiit
"Dane wejściowe chciałem żeby były brane z argv "
Ok, to w tamtym kodzie co wrzuciłem wystarczy zamienić "4 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 : 5 " na args[0] (czyli args[0].Split(...)) i będzie ok. Wywołanie powinno wówczas wyglądać, np.:

nazwa.exe "2 2 1 2 3 4 : 3"

"704 znaki bez whitespace'ow"
Cholera, sporo :) No to czekamy na kolejne kody.

Ludvick   7 #25 21.04.2012 18:07

To ja mam taką propozycję: jak już zostanie wyłoniona "pierwsza czwórka" zawodów, to w ramach finałów niech każdy wykona to samo zadanie, ale z użyciem języka [url=http://pl.wikipedia.org/wiki/Malbolge]Malboge[/url] (kryteria mogą być takie: czas realizacji projektu, a w razie dwu lub więcej takich samych wyników - zadecyduje ilość znaków). :)

iluzion   5 #26 21.04.2012 22:14

Przyznam, że nie czytałem uważnie zadania, ale tak na szybko nieco inny sposób niż przedstawił matzu mógłby wyglądać tak: Pobrać listę indeksów pozycji mniejszych od wskazanej, a następnie sprawdzić czy indeksy te określają pozycje z sąsiedztwa. Początek naszkicowałem. Pozostaje napisanie funkcji sprawdzającej czy dana pozycja jest sąsiadem.

http://dpaste.com/hold/735206/

matiit   7 #27 21.04.2012 22:17

iluzion, sprawdzenie czy jest sąsiadem: wzor z liceum, do generowania punktow mozna sie wspomóc itertools.product (python).
Ja probuje to napisac w haskellu ale za cienki jestem :D

iluzion   5 #28 21.04.2012 22:35

@matiit

Od początku to zadanie wydawało mi się pisane pod Haskella;) Prawdopodobnie w Pythonie da się w tym wypadku napisać kod równoważny temu z Haskella, tyle tylko że będzie miał więcej znaków, bo np. lambda to 6 znaków, a nie jeden jak w Haskellu itd.

Porównanie:

Python
======

list(filter(lambda _: _ > 50, map(lambda _: _ ** 2, range(11))))

Haskell
=======

filter (>50) (map (**2) [1..10])

Frankfurterium   10 #29 22.04.2012 00:17

Podaj jeszcze ten wzór, to może trochę powalczę. Wszystkie te wzory przydawały mi się tak często, że nie warto było ich pamiętać ;-)

iluzion   5 #30 22.04.2012 10:48

@RaveStar

Wysoko ustawiłeś poprzeczkę sięgając po Clojure. Pozamiatane? :)

matiit   7 #31 22.04.2012 10:58

Frankfurterium: Pierwiastek z x1-x2 + y1-y2.
RaveStar, brawo, w haskellu na pewno nie uciułam krótszego kodu...

Chocimir   2 #32 22.04.2012 14:55

Czy plansza zawsze będzie kwadratowa? Czy wypełnienie zawsze będzie iść po kolei?
Moje pokręcone rozwiązanie w Pythonie o 311 znakach: http://wklej.to/wL1sc

matiit   7 #33 22.04.2012 15:09

Chocimir - plansza nie zawsze bedzie kwadratowa (po co wtedy byłyby 2 parametry wielkości? :P)
Wypełnianie zawsze po kolei.

Chocimir   2 #34 22.04.2012 15:27

Czyli np. na czwartym polu zawsze będzie czwórka, czy zawsze po ósemce dziewiątka, czy inaczej?
Możesz już pokazać swój kod ;)

matiit   7 #35 22.04.2012 16:14

Nie, moze byc tak:
3 3 9 8 1 2 3 5 6 4 44 : 4

floyd   15 #36 22.04.2012 16:48

Gdyby jeszcze krótkość kodu źródłowego przekładała się na szybkość działania programu czy algorytmu. Bardzo często jest jednak odwrotnie. Algorytm sortowania bąbelkowego jest znacznie krótszy niż algorytm sortowania szybkiego który jak sama nazwa wskazuje jest znacznie szybszy. Wydaje mi się, że wiem który z prezentowanych tu programików jest najszybszy i też nie jest to ten o najkrótszym kodzie choć przyznaję, że w tym przypadku nie ma to znaczenia. :)

Chocimir   2 #37 22.04.2012 16:54
Chocimir   2 #38 22.04.2012 17:45

RaveStar, dzięki za wychwycenie błędu. Poprawka: http://ideone.com/Vy0wc (335 znaków).

matzu   5 #39 23.04.2012 02:55

@Chocimir
Wyniki dla dwóch ostatnich testów masz na odwrót (żeby było jasne, ja ich nie przeprowadzałem):
Dla "4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 : 20" powinno być 14 15 19.
Dla "5 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 : 20" powinno być 15 16 19.

Swoją drogą dobrze wiedzieć, że na tej stronce można przekazywać argumenty wiersza poleceń. Nie zauważyłem tego na początku :P

anakkin   6 #40 23.04.2012 13:38

@Chocimir

Jesteś pewien, że Twój program działa poprawnie?
3 3 1 2 3 4 9 5 6 7 8 : 5

czyli:
1 2 3
4 9 5
6 7 8

dla 5 powinien pokazac:
1 2 3 4 6 7 8 9

anakkin   6 #41 23.04.2012 14:01

http://ideone.com/aFcag

326 znaków, Python ??

btw. proponuję porównanie zużycia pamięci kodu Clojure z innymi ;)

Autor edytował komentarz w dniu: 23.09.2016 15:46
matiit   7 #42 23.04.2012 15:08

anakkin nie, powinien pokazac 2 3
Bo nie mozna isc na pole o wiekszej wartosci

Chocimir   2 #43 23.04.2012 15:28

Matzu, masz rację jeśli pierwszy wymiar to wysokość (nie widzę w treści zadania). Ja przyjąłem że to szerokość.
Matiit, pokaż swój kod, prosimy!

matiit   7 #44 23.04.2012 15:30

Niestety moj kod (w pythonie) jest za dlugi :D
Obecnie jak skoncze prace siade przy wersji w haskellu :)

matiit   7 #45 23.04.2012 15:44

Chocimir:
Jest napisane co jest wysokością a co szerokością :)
"Dane wejściowe:

X Y {CIĄG LICZB ODDZIELONYCH SPACJAMI} : Z
Gdzie: X - Szerokość planszy
Y - Wysokość planszy"

anakkin   6 #46 23.04.2012 15:52

Przecież pole 5 ma największą wartość: 9 (?) to każde inne pole dookoła ma mniejszą. Albo coś nie skumałem zadania...

matiit   7 #47 23.04.2012 15:55

anakkin sąsiadamy 5 są 2 3 9 7 8
czyli 5 moze przejsc tylko na te liczby
A z nich mniejsze od 5 sa tylko 2 i 3

anakkin   6 #48 23.04.2012 16:53

ok, czyli 5 to nie będzie 5 z kolei, tylko z id=5
czaje ;)

Chocimir   2 #49 23.04.2012 16:59

Czytanie ze zrozumieniem rządzi. Ale to znaczy że ja mam dobrze :P

matzu   5 #50 24.04.2012 16:38

@Chocimir
Będziesz miał dobrze w momencie, gdy poprawisz błąd, który wychwycił nasz tajemniczy tester-ninja, a o którym wspomniałem w moim poprzednim komentarzu.

matzu   5 #51 24.04.2012 18:28

Mój błąd Chocimir, wyniki dla tych powyższych danych wejściowych masz poprawne. To ja miałem na odwrót. Nie wiem dlaczego, ale zakodowałem sobie w głowie, że pierwsze dwie liczby to wymiar macierzy (a jak wiadomo w przypadku wymiaru macierzy jako pierwszą podaje się liczbę wierszy).

http://ideone.com/YwiU2

Wprowadziłem poprawkę (liczba znaków nie uległa zmianie, bo poprawka polegała na zamianie 0 na 1 i 1 na 0). Przy okazji dodałem możliwość przekazywania parametrów. Można więc sobie testować ten kod już z poziomu strony.

Dodaję jeszcze sprostowanie co do tej wypowiedzi "Swoją drogą dobrze wiedzieć, że na tej stronce można przekazywać argumenty wiersza poleceń. Nie zauważyłem tego na początku :P"

Ideone pozwala na przekazywanie parametrów, ale już po uruchomieniu programu. Nie są to argumenty wiersza poleceń. Nie sprawdzałem ile dokładnie takich parametrów można przekazać, ale na pewno więcej niż jeden.

soanvig   10 #52 10.06.2012 14:50

A wkleję to co zrobiłem przed chwilą w Rubim
http://ideone.com/dUpBd
652 znaki bez i 844 znaki ze spacjami.
Pierwszy kod ma za zadanie stworzenie ze stringu odpowiedniej tablicy dwuwymiarowej oraz wyłuskanie kluczy dla pozycji początkowej. Drugi to jest totalny prymitywny brute, którego już nie chce mi się optymalizować :D Na 100% można to zrobić lepiej na 100 innych sposobów, ale mi się nie chciało nawet myśleć... :D