Konkurs JavaScript na najkrótszy skrypt

Szymon Piłkowski wpadł na pomysł, by zrealizować konkurs na najkrótszy skrypt będący rozwiązaniem problemu, nad którym ostatnio pracował. Idea bardzo szybko przypadła mi do gustu i momentalnie uzyskała ostateczną formę.

O co chodzi?

Przypuśćmy, że pracujemy nad skryptem, który indeksuje odpowiedzi do pytań używając liter, np.:

Jak masz na imię?

  1. Adam
  2. Adrian
  3. Bartosz
  4. Dariusz

Weźmy jednak pod uwagę, że pracujemy ze skończonym alfabetem, np. abcd, wtedy pytanie z sześcioma odpowiedziami będzie wyglądać tak:

a. Adam
b. Adrian
c. Bartosz
d. Dariusz
aa. Hieronim
ab. Łukasz

Czternaście odpowiedzi?

a. Adam
b. Adrian
c. Bartosz
d. Dariusz
aa. Hieronim
ab. Łukasz
ac. Marian
ad. Paweł
ba. Piotr
bb. Prometeusz
bc. Protazy
bd. Robert
ca. Władysław
cb. Zbigniew

Potem analogicznie np. przy większych liczbach aaa, aab, aac, aad, aba, abb, abc, abd etc. Mądrym głowom na pewno przypomina się pewien dział matematyki.

To, co chcemy uzyskać, to dwie funkcje.

Pierwsza zwróci odpowiedni układ liter dla n-tej odpowiedzi. W powyższym przypadku, dla szóstej odpowiedzi (licząc od zera) będzie to: ac.
Druga zachowa się dokładnie odwrotnie, na podstawie układu liter, np. cd, zwróci nam, że chodzi o 15. odpowiedź.

Uznajemy, że kod startowy wygląda tak, jak poniżej. Wielokropek oznacza, że możecie dokonywać tam modyfikacji.

var alfabet = "abcdefghjpz679";
var convertToLetters = function(...){...};
var convertToNumber = function(...){...};

Zabroniona jest jakakolwiek modyfikacja skryptu startowego, choćby usunięcie średników!

Input/output

convertToLetters(6); // "g"
convertToNumber("a"); // 0
convertToNumber("ab"); // 15

Kod ma działać dla dowolnego alfabetu bez powtórzeń, składającego się ze znaków ASCII. Co za tym idzie, rozważyć powinniście też jednoznakowy alfabet. Zabronione jest używanie zewnętrznych bibliotek, liczy się tylko czysty JavaScript (ECMA 3/5). Wygrywa osoba, która przedstawi działające rozwiązanie, posiadające jak najmniej znaków. Liczymy je dla każdej funkcji oddzielnie i sumujemy. Pod uwagę bierzemy oczywiście białe znaki jak spacja czy nowy wiersz!

Zakładamy, że wszystko ma działać dla n >= 0 (funkcja convertToLetters). Zabronione są używanie predefiniowanych zmiennych globalnych (natomiast możecie je deklarować w funkcjach) i zmiana natywnych prototypów.

Rozwiązania będziemy testować w środowisku node.js v0.4.7 (i tu docelowo skrypt ma działać) bez dodatkowych modułów.

Rozwiązania i terminy

Konkurs trwa do końca lipca. Rozwiązania należy wysyłać używając prostego formularza. W przypadku kilku zwycięzców zadecyduje termin oddania pracy.

Nagrody

Wyróżnimy trzy skrypty! Każda osoba z podium dostanie wejściówkę na konferencję onGameStart, która odbędzie się w Warszawie, 22-23 września (podziękowania tutaj dla Michała Budzyńskiego). Ponadto, dla wszystkich wyróżnionych mamy naklejki tej konferencji, a także smycze Mozilli.

Od nas natomiast, zwycięzca może wybrać dla siebie nagrodę główną pomiędzy licencją Personal License na IDE WebStorm i książką Christiana JohansenaTest-Driven JavaScript Development. To, co zostanie, automatycznie przechodzi w ręce osoby na drugim miejscu.

Let’s get ready to rumble!

Komentarze

1

Ale czy ktoś może przenieść konferencję na inny termin? Natenczas albowiem byczył się będę na wywczasie.

GregT
2

1/ Czy skrypt ma być głupoodporny? Tj wystarczy że działa dla prawidłowych danych? Czy potrzeba jakichś zabezpieczeń?
2/ czy kosztem miejsca można leciec na zmiennych globalnych?

Me
3

Ad 1. n >= 0
Ad 2. dobra uwaga, używanie zmiennych globalnych i zmiana natywnych prototypów są zabronione

4

gdzie „n” to…? najmniejsza liczba wejsciowa dla convertToLetters?
alfabet.length >= 1?

Me
5

Najmniejsza liczba wejsciowa. Tak, alfabet co najmniej jednoliterowy.

6

Widze, ze argumenty tez mozna dowolnie nazywac? ;)

shfx
7

tak, dowolne nazwy argumentow.

8

Czy uznajemy obie funkcje jako komplet? Tzn, czy jedna do działania może korzystać z drugiej, czy muszą być totalnie niezależne?

9

niezalezne. ciezko mi zreszta wyobrazic sobie dlaczego mialyby z siebie korzystac :)

10

1. Czy zakładamy że wprowadzone dane są poprawne? Czy należy brać pod uwagę błąd np. nieistniejąca litera w alfabecie np. input > „ax”? Czy wystarczy jak funkcja zwróci wartość domyślną tj. -1?

2. dla n >= 0. Gdy mamy zero to jak funkcja ma wyglądac: convertToLetters() ? Coś konkretnego ma zwrócic w tym przypadku?

3. Można zgłosić poprawiany kod kilka razy? (np. po uploudzie stwierdziłem, że mogłem jeszcze zaoszczędzić parę znaków lub zauważylm błąd)

rav
11

Sorry dla 2 chyba znalazłem odpowiedz kilka komentarzy powyżej.

rav
12

Przypominam, liczymy od 0, a nie od 1. Walidację możecie zignorować – chodzi o implementację skryptu działającą na prawdziwych, poprawnych danych.

Najlepiej nie wysyłajcie pochopnie, bo robi się po naszej stronie śmietnik. Oczywiście można wysłać kilka razy, o ile będzie to w lipcu, aczkolwiek nie zachęcam z w/w powodów.

13

Może podajcie jakieś proste przykładowe dane testowe z wynikami, żeby każdy mógł odsiać niedziałający kod?
Dzięki temu zwiększy się szansa, że będą do Was dochodzić poprawne rozwiązania, a wszyscy będą się mogli skupić na skracaniu algorytmu/zapisu.

bartaz
14

178 znaków :D No, jestem ciekawy czy można lepiej, będą opublikowane najlepsze skrypty?

billy0o
15

@billy0o: dla całego pliku czy wnetrza funkcji? :)

rav
16

@billy0o: Przypadkiem nie korzystasz ze zmiennych globalnych? :)

wojtekk
17

sam kod obu funkcji, bez zmiennych globalnych. :)

billy0o
18

co do bałaganu po waszej stronie, nie można po prostu po zakończeniu konkursu wybrać najnowszej pracy przesłanej przez daną osobę?

ps. 174 średniki i nawias..

billy0o
19

@billy0o to nie lepiej napisać ile ma cały plik? :P każdy sobie wtedy policzy ile znaków masz w srodku

rav
20

@rav: pod uwagę w konkursie bierze się długość kodu wewnątrz funkcji. znaki z kodu startowego są nieistotne, to po co je liczyć?

billy0o
21

@billy0o W sumie to wszystko jedno :)

rav
22

Ja bym proponował, by używać ilości znaków dla całego pliku, żeby nie było szoku, że ktoś ma potem tylko 120 znaków np. ;-)

23

Czy mam rozumieć, że ktoś wyrobił się już w 120 znaków, czy tylko z kosmosu wzięta liczba?

24

Kosmosu ;)

25

Poniewaz podajesz wielokropki w ciele i w sygnaturze funkcji:

var convertToLetters = function(…){ … };

Zakladam, ze mimo iz w przykladach uzycia jest jeden argument, zmiana sygnatury funkcji jest dozwolona, np.
convertToLetters(alphabet, 6); // "g"

Right?

Pytanie wiec, liczymy tylko cialo funkcji, czy tez z nazwami argumentow?

mee
26

Nie, zmiana wywołania funkcji nie jest dozwolona. Zawsze to będzie:

convertToLetters(6);

Itd.

Natomiast w ciele funkcji i w miejscu na definicje parametrow mozna robic, co sie podoba. Nie bede wyjasnial, co to daje, bo za duzo zdradze.

27

dobrze, zatem czy ilość znaków jest liczona również z argumentami, czy tylko same ciało funkcji?

var convertToLetters = function(a,b){a=b}; // liczone jako 3 znaki czy jako 5?

bo jeśli argumenty są też liczone do długości skryptu to nic nie zmienia :P

billy0o
28

Panowie, oficjalne wyniki będą dla całego skryptu wraz z kodem startowym. Czyli, liczymy od var alfabet do końca.

var alfabet = "abcdefghjpz679";
var convertToLetters = function(...){ ... };
var convertToNumber = function(...){ ... };

Co za tym idzie, cokolwiek w „…” również jest liczone do ostatecznego wyniku. Jaśniej? ;-)

29

A koledzy wyzej, ktorzy pisali dlugosci swoich funkcji podali wartosc dla convertToLetters czy convertToNumber? bo chyba nie dla obu?;)
Pierwsza mi sie miesci w 163 znakach i nie wiem czy slusznie sie ciesze ;)

Ly
30

Ciała obu funkcji, połączone razem, bez kodu startowego.

billy0o
31

O, no to falstart ;) Ale jeszcze was dogonię ;)

Ly
32

Żebyśmy mieli to na piśmie:

Wydajność nie jest w ogóle brana pod uwagę, tak?

33

@wildcard

niezalezne. ciezko mi zreszta wyobrazic sobie dlaczego mialyby z siebie korzystac :)

Szkoda, bo na tym oparłem mój pomysł. W ciałach funkcji i argumentach mam razem 146 znaków dzięki temu. Da się to ograniczenie jeszcze odkręcić/cofnąć ? ;)

Czytałem tylko komentarze na zielono w poszukiwaniu reguł, dopiero później się zabrałem za pozostałe.

PS. Też niedawno robiłem coś takiego. Tyle, że optymalizowałem pod wydajność w pierwszej kolejności

34

@Zbyszek T,

a) wydajnosc nie ma w tym konkursie znaczenia,

aa) rozumiem, ale nie moge raz jakiegos ograniczenia nakladac, a nastepnie zdejmowac. masz racje – info o tym powinno byc jakos wytluszczone. nie mam niestety takiego fajnego zielonego koloru jak Damian, zatem.. Damian, moglbys dac mi zielony kolorek? nie? no to dodac info o odrebnosci funkcji do regul? :>

ja piszac swoja wersje do uzycia w „prawdziwym swiecie” tez skupialem sie na wydajnosci, ten konkurs to raczej zabawa (+edukacja) :)

35

@ard Bez względu na to, czy jest to ograniczenie, czy nie to i tak przy danych wejściowych rzędu 2^32 skrypt Zbyszka będzie wymagał wywłaszczenia, więc raczej wytułszczonym zielonym trzeba podać górny zakres N zgodnie ze sztuką. I żeby nie było pobitych garów, nie podpowiadaj Michałowi ;)

36

@opengrid Trochę mnie zbiłeś z tropu. Na wszelki wypadek dorzucę wersję gdzie nie jest zachowana zasada niezależności funkcji najwyżej ją odrzucicie :-)

Michał
37

To ja też chcę dorzucić taką wersję! jest krótsza o 1/3 :)
Ale jak rozumiem liczy się tylko najnowszy upload formularzem, więc trochę nie ma jak podać dodatkowej wersji…

@opengrid przy danych rzędu 2^32 może się już zacząć psuć rzutowanie typów. Chyba, że ktoś używał Math.floor() :D

38

„Ja bym proponował, by używać ilości znaków dla całego pliku, żeby nie było szoku, że ktoś ma potem tylko 120 znaków np. ;-)”

Czyli białe znaki też się liczą? Szczegóły ale krytyczne w przypadku tego typu konkursu.

39

Białe znaki zawsze się liczą. Javascript akurat pozwala na usunięcie prawie wszystkich białych znaków, nawet po return można w pewnych warunkach nie zrobić :)

40

Ktoś w przykładach powyżej przedstawił kawałek kodu:

var convertToLetters = function(a,b){a=b};

Abstrahując od jego niepoprawności, czy jest zgodny z zasadami? W definicji problemu dookoła kodu są spacje. Rozumiem, że muszą tam zostać. Czy słusznie?

samuil
41

Ja zinterpretowałem to tak, że „tam” oznacza bloki w kodzie, więc u mnie spacji nie ma.
Sprawę można łatwo zunifikować jednym wyrażeniem regularnym, więc nie martwiłbym się, że organizatorzy sobie nie poradzą. A zgłoszeń do konkursu pewnie i tak będzie kilka lub kilkanaście ;)

42

Panowie, oczywiście, że można, mea culpa, że napisałem ze spacjami :-)

43

to jaki teraz jest rekord?

Ly
44

@ferrante #42 i #28

s/Panowie/Proszę\ Państwa/g, z dobrze poinformowanych źródeł wiem, że tu się wypowiadają nie tylko faceci. :)

45

Panowie pytają, to się panom odpowiada :)

Ly
46

@marcoos W pierwszej chwili wydawało mi się, że 42 i 28 to odpowiedź dla @Ly :D

@Ly Już Ci miałem powiedzieć ile mam w tej chwili, ale doszedłem do wniosku, że gdyby mi ktoś powiedział jakąś liczbę różniącą się od mojej o więcej niż 20 znaków w dowolną stronę, zadziałałoby to demotywująco. Więc nie powiem, tajemnica :X

47

@Zbyszek T. demotywująco dla jednych, motywująco dla drugich, kwestia podejścia. Ale pewnie po twoim komentarzu już sie nikt nie pochwali wynikiem ;) Zobaczymy 1 sierpnia :)

Ly
48

@Ly Przeceniasz moje możliwości i wolny czas ;) Nie spodziewam się zwycięstwa, ale dobrze się bawiłem przez te dwa wieczory, które udało mi się na to wygospodarować.

Szkoda, że konkurs kończy się po meet.js, bo omówienie trocków byłoby świetnym punktem programu.

49

Ponieważ podajesz wielokropki w ciele i w sygnaturze funkcji:

var convertToLetters = function(…){ … };

Zakładam, ze mimo iż w przykładach użycia jest jeden argument, zmiana sygnatury funkcji jest dozwolona, np.

convertToLetters(alphabet, 6); // „g”

Right?

Nie, zmiana wywołania funkcji nie jest dozwolona. Zawsze to będzie:

czysty tekst

convertToLetters(6);

Itd.

Natomiast w ciele funkcji i w miejscu na definicje parametrów można robić, co się podoba. Nie będę wyjaśniał, co to daje, bo za dużo zdradzę.

Nie proszę o dodatkowe wyjaśnienia, tylko się pytam: JAK bez użycia zmiennej alfabet jako zmiennej globalnej można przekazać jej zawartość do funkcji, jednej i drugiej, jeśli nie wolno do tego użyć dodatkowego parametru. A jeśli wolno, to prezentowane wywołanie jest niekompletne – brakuje właśnie zmiennej z alfabetem. Albo więc należy ją po prostu pobrać, a więc potraktować jako globalną, albo przekazać ją w parametrze, co należy uwzględnić przy wywołaniu. Dlatego więc coś mi się tu nie zgadza…
A tak ogólnie to ciekawy konkurs, spędziłem całe popołudnie, ale nie uważam tego za czas stracony, problem był rzeczywiście interesujący. Choć ja osobiście w programowaniu stawiam zawsze na wydajność, a nie na ilość znaków w kodzie:)

Tomek
50

Nie wiem o co ten ambaras… Tak, używasz GLOBALNEJ zmiennej alfabet.

51

No i dzięki:) bo inaczej by się nie dało, a nie chciałem, żeby z tak błahego powodu odrzucono moje zgłoszenie, które jest już na ukończeniu i niedługo zostanie wysłane;)

Tomek
52

Mam pytanie.
Czy w bloku sprawdzenia input/output nie ma błędu? Mając implementację obu funkcji można by sobie od razu robić sprawdzenie – czyli funkcja convertToLetters zwraca mi ciąg znaków a ten od razu podstawiam do funkcji convertToNumer weryfikując czy ta zwróciła mi tą samą liczbę co podstawiłem do convertToLetters.. skoro tak to:

15=>ab
ab=>15

Więc czemu

1=>a
a=>0 ??

paweł
53

Dla alfabetu z przykładu:

convertToLetters(1) -> "b" // a nie a
convertToLetters(0) -> "a"

convertToNumber("a") -> 0

bartaz
54

jw.

55

Przypominam ostatecznie, że funkcje nie mogą korzystać jedna z drugiej.

56

convertToNumbers: 96
convertToLetters: 81
… i nie wiem jak jest możliwe mieć mniej … kurde

57

Oops, też mam 178 :P

58

@Darrel

W ramach motywacji (lub demotywacji) podpowiem, że można mieć mniej ;)

bartaz
59

Nie naturalniej byłoby „numerować” {a,b,c} -> [a,b,c,ba,bb,bc,ca,…]?

sieciobywatel
60

nie, nawet przeglądarki tak nie robią.

61

@bartaz

Dużo mniej? ;)

@sieciobywatel

Różnica między systemem pozycyjnym a tym konkretnym nie jest taka wielka ;)

samuil
62

No skoro spoilujecie, to macie.
171 body funkcji+definicje atrybutów;
276 bajtów cały plik

Obcięcie ostatnich kilku znaków było najbardziej odjechane.

63

Da się mniej ;)

wojtekk
64

No i się zaczęło, za chwile zakończymy konkurs bez jury :D

PS. 165 ciała funcji, 169 z argumentami, 275 bajtów do przesłania

billy0o
65

Nie dosc ze licytacja, to jeszcze niedzieli bedzie tyle spoilerow, ze kazdy bedzie w stanie to napisac w przyzwoitej dlugosci ;)
a poniekad wiem ze da sie jeszcze mniej :)

Ly
66

mialo byc ‚do niedzieli’ yhm

Ly
67

niezalezne. ciezko mi zreszta wyobrazic sobie dlaczego mialyby z siebie korzystac :)

Kawałek kodu który pobudzi Twoją wyobraźnię :)
var convertToNumber = function(str){
var num = 0;
while( convertToLetters(num++) !== str ){}
return num-1;
};

Tylko to rozwiązanie i tak jest niedozwolone.

Grzegorz
68

Różnica między systemem pozycyjnym a tym konkretnym nie jest taka wielka ;)

jest:)

dla mnie na tym właśnie polega trudność funkcji convertToLetters, nad którą posiedziałem dwa wieczory, podczas gdy convertToNumber napisałem za jakieś półtorej godziny…
myślałem też nad wykorzystaniem wzajemnym obydwu funkcji, choć po prawdzie, to od samego początku, jeszcze przed potwierdzeniem zakazu, stawiałem na poszukiwanie niezależnych rozwiązań
co nie oznacza, ze normalnie, poza konkursem, gdybym miał już napisana jedną funkcję, to nie martwiłbym się, jak znaleźć druga, tylko je połączył…
no ale to jest konkurs i trzeba akceptować jego warunki:)

Tomek
69

Ly, da się ponoć 2 znaki mniej ;)

wojtekk
70

@Tomek ja miałem odwrotnie – optymalizacja convertToNumber zajęła mi znacznie więcej czasu :)

Poza konkursem uciekał bym od rozwiązania z pętlą – jest bardzo mocno nieoptymalne :/

wojtekk
71

@wojtekk a jak inaczej jak nie pętlą? rekurencyjnie? BTW. chyba po poprzednim wpisie stałeś się nieoficjalnym liderem :)
@Tomek niezależne rozwiązania są na pewno bliższe optymalnym. Jak tak patrzę na swoje, to poza jednym brzydkim przypisaniem, wyszedł mi nie najgorszy algorytm

Ly
72

@ly miało być „z rekurencją” oczywiście :/

wojtekk
73

@wojtekk @Ly

W tej dyskusji chyba nie chodzi ani o pętlę ani o rekurencję, tylko o wykorzystanie jednej funkcji w drugiej i poszukiwanie (w pętli) poprawnego rozwiązania. Jak w przykładzie podanym przez Grzegorza.

bartaz
74

Chyba nie muszę dodawać, że rozwiązanie zostało wymyślone tylko na potrzeby konkursu.
W normalnych warunkach nigdy bym czegoś takiego nie napisał.

Co do długości kodu @billy0o wynoszącego 165 bajtów kto da więcej? Ekhm… mniej :)

Grzegorz
75

Ciiii, bo beda bany ;)

76

@bartaz Zgadza się – chodzi o to, że takie rozwiązanie w realnym świecie jest mocno nieoptymalne (w przykładzie który podałeś).

wojtekk
77

z ostatniej chwili – 167 bajtów :D jak mogłem pominąć ten nawias -,-

billy0o
78

To jak się licytujecie to może całą długością pliku, mamy wtedy przynajmniej jednoznaczny punkt odniesienia :)

Ly
79

@ly prezes nie pozwala ;) Cierpliwość ćwiczyć będziemy musieć :D

wojtekk
80

dla jakich max N ma działać convertToLetters – pytam bo mam nie do końca stabilną wersję mieszczącą się w 65b :D

abuduba
81

drugie pytanie :

Zabronione są używanie zmiennych globalnych….

Dotyczy to już utworzonych czy także tych które utworze w funkcji?
Tzn. czy trzeba deklarować zmienne przez var ( lub ta druga opcja jak mamy do czynienia z funkcja ;) ) ?

abuduba
82

#80 @abuduba – ja mam nadzieję, że dla nieograniczonego w dlugosci alfabetu (przynajmniej w teorii). Ograniczenie z góry na tym etapie konkursu byłoby baaardzo nie fair :>

Ly
83

tfu piszę o alfabecie, a na myśli masz liczbę – z liczbami to samo – mam nadzieję, że z góry „n” ogranicza tylko wielkość typu number w JS :>

Ly
84

tak myslalem :)
bo dla `małych` n(nie zerkalem gdzie jest prog)
a=parseInt(a) a|=0 :)

abuduba
85

wcielo mi strzałke *a=parseInt(a) == a|=0

abuduba
86

a jak wyglada sprawa z deklaracja zmiennych w funkcji #81 ?

abuduba
87

@abuduba jak zrobisz np. takie zadanko (link poniżej) to się domyślisz.
pl.spoj.pl/problems/BEZPRZEC/

Grzegorz
88

@abuduba
Z komentarzy #2 i #3 wynika chyba, że trzeba deklarować zmienne przez var

89

@Zbyszek T

wyspałem się, przeczytałem wszystkie komentarze od pierwszego i nie rozumiem dlaczego zadawałem takie głupie pytania:)
zeby byly lokalne w funkcji wcale nie potrzeba(owszem mozna) przez var – jest na to jeszcze jeden sposob.

tak do wszystkich – pewnie i tak wiecie ale co tam,
Do zrobienia inta nie przejdzie podwojna tylda.(ani inne operatory bitowe jak np int =float|0 )

int = Math.pow(2,32)/2 //== 2147483647 -max dodatnia liczba signed int32
~~(int-1) //== 2147483647 -wszystko ok
~~int // == -2147483648 boooooom!
// kilka(naście) potęg dalej i po każdej operacji bitowej wychodzi -1

Tak czy inaczej mam sposob oszczedzajacy 2 znaki w stosunku do parseInt

btw. udało mi sie zrobić 70znaków w body convertToLetters – ma ktoś mniej? bo nie wiem czy mam jeszcze kombinować czy wziąć się za drugą :))

abuduba
90

oj sorry -pierwsza linjka
int= 2147483648

abuduba
91

to wlasnie bylo do przewidzenia, jeszcze pare godzin i tu beda cale funkcje o.O

Ly
92

@abuduba

Na Twoim miejscu zajął bym się kodowaniem, a nie komentowaniem, bo czasu zostało niewiele, a może się to obrócić przeciwko Tobie ;)

bartaz
93

@abuduba
Ostatnia wskazówka – to jest konkurs na najkrótszy kod, więc nikt raczej nie oczekiwał, że będziesz stosował parseInt(x,10) zamiast ~~ tylko po to, żeby obsłużyć bezsensownie duże liczby, z których kod literkowy wyjdzie na parę linijek :P

Może nie trafię w czyjś gust, ale najwyższa liczba, na jakiej testowałem mój kod to 200 :)

94

Przede wszystkim po tak dużych liczbach ciężko się już iteruje, bo tracą one rozdzielczość. Wychodzi, że x == x+1, a to może zaboleć.
Tak więc ja zgadzam się ze Zbyszkiem, że nie o to tu chodzi. Też testowałem chyba do ~100-200 i mam nadzieję, że dalej nie ma jakiegoś dziwacznego błędu :D

95

A odwołując się do treści zadania:

Przypuśćmy, że pracujemy nad skryptem, który indeksuje odpowiedzi do pytań używając liter

Nie wyobrażam sobie pytania, które miałoby liczbę odpowiedzi rzędu 2^32 ;)

bartaz
96

Nie wyobrażam sobie pytania, które miałoby liczbę odpowiedzi rzędu 2^32 ;)

Np: jakie liczby można zapisać na 32 bitach :P

97

Ostatni raz zwracam uwagę ;-)

98

ok. już nie będę.
Pobiłem(i to porządnie) rekord @billy0o, podejrzewam że już jest dawno nieaktualny chociaż nikt się nie chwali.

:)

abuduba
99

@abuduba a działa prawidłowo?
Bo już zaczynam wątpić w to gdzie mogę usunąć jeszcze te kilkanaście bitów z mojej funkcji.

Mój kod do testowania:
eval(require('fs').readFileSync('ferrante f6ca8600842f2b6f0c1ba13873128de1.js')+'');
var sys = require('sys');

var str, num, err = 0;
for( var i = 0; i < 1e6; ++i ){
str = convertToLetters(i);
num = convertToNumber(str);
sys.puts( i + '\t' + str + '\t' + num );
err += i !== num ? 1 : 0;
}
sys.puts('total errors: ' + err);

Może komuś się przyda.

Grzegorz
100

pytanie też co znaczy że rekord jest porządnie pobity :) Bo dla niektórych to może oznaczać 3 znaki, a dla innych 10 (a jeszcze innych 20+) :P

Ly
101

zakomentowałem sobie tylko linijkę z sys.puts(…


$ node a.js
total errors: 0

mam oczywiscie node v0.4.7
Wysłałem już swoje rozwiązanie :)

abuduba
102

@ly – 10+

abuduba
103

@abuduba

Słabo to strategicznie rozegrałeś :p

samuil
104

@samuil -wcale mi nie zależy na wygranej , liczę na to że ktoś zrobi 20+ mniej znaków od @billy0o i będę mógł sobie zobaczyć taki kod. Może się czegoś naucze :)

abuduba
105

Przyznam, że jestem bardzo ciekawy wyników konkursu :) Siedzę teraz na wakacjach i nie mogę przestać sprawdzać, czy czegoś nie napisaliście. Już zresztą żaliłem się Damianowi, że mi zadanie wycięło 2 dni z życia :P

Powodzenia wszystkim :)

PS. Kiedy będziemy mogli spodziewać się wyników, Damian? Będziecie potrzebowali chwilę na ogarnięcie zgłoszeń, czy np. macie maszynkę do tego?

106

@ly Udało Ci się zejść niżej? :)

btw. ciekawe dyskusje – i ja straciłem na zabawę z kodem kilka wieczorów :)

wojtekk
107

@wojtekk Co znaczy niżej? ;) Punkt odniesienia się trochę rozmył ostatnio, więc ciężko powiedzieć ;) A moja najkrótsza wersja powstała przedwczoraj, od tamtej pory już nic lepszego mi do głowy nie przyszło :]

Ly
108

Domyślam się odpowiedzi, ale chciałbym się upewnić (ze względu na środowisko testowe), że w założeniach mówimy o zmiennych „globalnych” na poziomie modułu?

109

Wielkie dzięki za nadesłane rozwiązania. Komisja obraduje i analizuje wyniki naszym skromnym node’owym skryptem ;-)

110

komisja jest, poki co, przerazona iloscia nadeslanych rozwiazan! ;)
wyniki beda w tym tygodniu, o ile niebo nie runie nam na glowy.

111

Nie wiem dlaczego ale wrzuciłem wszystkie zmienne jako argumenty… straciłem przez to 4znaki. Chyba przez presję , bo czasu nie ma a konkurs znalazłem kilka dni przed jego końcem.. Będę już stałym bywalcem ferrante.pl więc czekam na kolejny konkurs bo w tym mi raczej nie poszło :)

abuduba
112

@abuduba — Ogólnie zastosowanie dodatkowych (niewykorzystanych w tej roli) argumentów powoduje, że masz dostęp do zmiennych zadeklarowanych lokalnie, ale bez użycia słowa kluczowego var. W zależności od tego ile ich jest może się to opłacać lub nie :)

Może lepiej poczekajmy z takimi dywagacjami na publikację najlepszych rozwiązań. Temat będzie bardziej namacalny.

samuil
113

@abuduba konkursy ferrante i ich rezultaty uczą pokory (przynajmniej mnie), więc jeszcze nie wiadomo, czy Ci te 4 znaki wystarczą do moralnego zwycięstwa :)

114

@samuil –

Ogólnie zastosowanie dodatkowych (niewykorzystanych w tej roli) argumentów powoduje, że masz dostęp do zmiennych zadeklarowanych lokalnie, ale bez użycia słowa kluczowego var. W zależności od tego ile ich jest może się to opłacać lub nie :)

Tak, wiem. Zaćmiło mnie a teraz pluję sobie w twarz.

abuduba
115

@opengrid –

jeszcze nie wiadomo, czy Ci te 4 znaki wystarczą do moralnego zwycięstwa :)

kod który wysłałem ma 259bajtów. Myślę że jeszcze bez czwórki miałbym szansę na top 3 :))

abuduba
116

@abuduba — bez kolejnych czterech przekroczyłbyś okrągłą granicę :)

samuil
117

wyniki beda w tym tygodniu, o ile niebo nie runie nam na glowy.

Dzisiaj niebo robiło zrzuty swej zawartości, więc będziemy musieli czekać dłużej? :P

118

wyslalem juz wyniki Damianowi, ale on sie teraz opala gdzies w miejscach w ktorych nieba maja lepsze obyczaje. ;-)

119

Jak wysyłałeś mogłeś dać na CC do nas :)

120

[…] już zwycięzców konkursu na najkrótszy skrypt. Jak liczyliśmy oficjalne […]

121

Podpowiedź dla organizatorów – w komentarzach zawarliście trzy dodatkowe reguły:

#3
Ad1. n >= 0
Ad 2. dobra uwaga, używanie zmiennych globalnych i zmiana natywnych prototypów są zabronione

#55
Przypominam ostatecznie, że funkcje nie mogą korzystać jedna z drugiej.

wojtekk
122

Coś wyniki przepadły ;>

123

Emocje też już opadły ;)

Mi już wszystko jedno jaki będzie wynik, swoje już „wygrałem”, czego się nauczyłem to moje.

A jury pewnie dalej urlopuje :P

bartaz
124

Pewnie tak ;)
Mi w zasadzie też na wynikach nie zależy, bo nawet jakbym zgarnął wejściówki, to i tak skorzystać bym nie mógł. Ale szkoda trochę uciętej rozmowy o rozwiązaniach.

125

Tutaj można pogadać o rozwiązaniach lub na JSnews w sumie. Co do wygranych rozwiązań szacunek za pomysł z odwracaniem bitowym. I w sumie pierwszą funkcję też można było krótko napisać w wersji iteracyjnej jak widać.

126

Wersja rekurencyjna ma potencjał, ale niestety jej długość psuje nazwa funkcji ‚convertToLetters’ ;)

A odwracanie bitowe to nie tyle pomysł, co znajomość tricku, który wymyślił pewnie ktoś dawno temu. Ale fajnie, że pojawiła się tu dyskusja na temat big intów i tego, że bitowe operacje przestają działać na bardzo dużych liczbach.

Ilość tricków, sztuczek, pomysłów i iteracji, które ten kod przeszedł do obecnej postaci jest tak duża, że starczyłoby na niemały artykuł :)

bartaz
127

Co ciekawsze – od odwracania bitowego lepiej wychodził |0, bo nie trzeba było brać całości w nawias (priorytety operatorów).

Co do iteracyjnej pierwszej… Próbowałem, ale mi wychodziło dłużej, z powodu jednego małego warunku, który musiałem uwzględnić. Jak zobaczyłem ostatecznie, że można go było w 4 znakach obrobić i że całość się skracała o 15 znaków, to się na siebie wkurzyłem :D

128

[…] już ostatecznych (oby ;)) zwycięzców konkursu na najkrótszy skrypt. Jak liczyliśmy oficjalne […]

129

Stracić na uniwersalności skryptu…

Dodaj komentarz

Dozwolone tagi: <blockquote>, <code>, <strong>