[Centraal] PHP - Golf wedstrijd

Waarom begint GOLF of jullie niet een globale website voor wedstrijden die een maand duren, dan heb je er wel 12 per jaar en kun je echt zien hoe divers mensen programmeren... (scripten).

quote:

Op zondag 18 december 2005 11:44 schreef Chandler het volgende:
Waarom begint GOLF of jullie niet een globale website voor wedstrijden die een maand duren, dan heb je er wel 12 per jaar en kun je echt zien hoe divers mensen programmeren... (scripten).

Leuk idee, ik heb alleen geen tijd om zoiets helemaal op te zetten en te ontwerpen. Ik kan wel een subdomein van gmta.nl leveren (golf.gmta.nl bijvoorbeeld) en alles wat je nodig zou kunnen hebben op een webserver

Het is een hoop werk om te maken en om te onderhouden, terwijl een topic ook prima voldoet.

quote:

Op zondag 18 december 2005 15:12 schreef SuperRembo het volgende:
Het is een hoop werk om te maken en om te onderhouden, terwijl een topic ook prima voldoet.

Dat valt ook weer mee, denk ik zo. De ingrediėnten:
- een layout
- een gebruikerssysteem met minimale rechten (user/admin) + registreersysteem
- een topicsysteem (om nieuwe wedstrijden te starten)
- een reageersysteem (zodat mensen kunnen reageren)

Voila

Oh, dan moeten we het wel anders noemen natuurlijk. Golf komt een beetje van phpfreakz af.

PHP-Limbo

PHPCOMPO ofzo

Zondag 18:00! Geweest ik heb medelijden met Crisp en de onbegrijpelijke stukken code waar hij lappen tekst over moet schrijven

quote:

Op zondag 18 december 2005 19:12 schreef JeRa het volgende:
Zondag 18:00! Geweest ik heb medelijden met Crisp en de onbegrijpelijke stukken code waar hij lappen tekst over moet schrijven

Dat valt wel mee hoor, ik begrijp de code prima
Ik ben al begonnen en zal het in de loop van de avond af proberen te maken

quote:

Op zondag 18 december 2005 19:13 schreef crisp het volgende:

[..]

Dat valt wel mee hoor, ik begrijp de code prima
Ik ben al begonnen en zal het in de loop van de avond af proberen te maken

Tof. Wat vind je van het idee van Chandler trouwens?

woei, ik kan zelfs wel een layout regelen en dat code werk wil ik ook wel doen... alleen de opgaven ben ik zekers NIET goed in

quote:

Op zondag 18 december 2005 19:19 schreef JeRa het volgende:

[..]

Tof. Wat vind je van het idee van Chandler trouwens?

Zo, nog even wat dingen geregeld voor de aankomst van onze zoon overmorgen maar nu zit ik er echt voor

Ik vind het idee van Chandler wel aardig, maar ben zelf bang dat op een gegeven moment de aandacht van een dergelijke opzet toch wel zal gaan verslappen. Ik heb nu een paar keer meegedaan met de Golfs en in het verleden ook wel aan een aantal andere contests meegedaan, maar ik zie aan mezelf dat ik het op een gegeven moment ook wel weer gezien heb en er dan weer een tijd niet naar omkijk...

Verwacht van mij voorlopig ook niet teveel input aangezien ik de komende tijd druk ben met andere zaken

Here goes:

Golf Intermezzo: Base64 encoding

Base 64 is letterlijk een numerings systeem met een basis van 64, de hoogste macht van 2 die met standaard ASCII karakters kan worden weergegeven. Base64-encoding wordt daarom voornamelijk gebruikt om binaire data te encoden voor gebruik in transport-formaten die enkel ASCII-karakters kunnen bevatten zoals bijvoorbeeld e-mail.
De gebruikte karakters zijn A t/m Z, a t/m z, 0 t/m 9 aangevuld met, in standaard base64 encoding, het + en / symbool.

Het algoritme om data om te zetten naar base64-encoded data is vrij eenvoudig. Neem bijvoorbeeld de string 'FOK!'. Elke letter in deze string heeft een karakter-code, respectievelijk 70, 79, 75 en 33. Binair met 8 bits per byte ziet dat er zo uit:



Bij het encoden worden telkens 6 bits uit deze reeks bytes genomen, en vervangen door het symbool uit de base64-karaktersset dat staat op de index gevormd door het 6-bit getal:





In dit geval houden we nog 2 bits over; die worden aangevuld met 0-en, dus het laatste karakter wordt het karakter op index 010000, oftewel 16 = Q

Je ziet dus dat voor elke 3 bytes input er 4 bytes geoutput worden. Als er op het eind minder dan 4 bytes geoutput hoeven worden (zoals in dit geval) dan wordt de base64-encoded string aangevuld met een zogenaamd 'padding'-karakter, in dit geval het '='-teken. In totaal komt de encoded string er dus zo uit te zien:



Tot zover de theorie

De inzendingen

In totaal mocht ik 3 inzendingen ontvangen: van GlowMouse, JeRa en SuperRembo en voor zover ik heb kunnen beoordelen zijn 2 van deze inzendingen correct; die van SuperRembo gaat bij sommige stringlengtes de mist in, zo output hij bij de input 'FOK' 'Rk9=AA==' ipv 'Rk9L'.
Opvallend is wel dat elke inzending uniek is in de manier waarop het probleem is aangepakt

Ik begin even met de drie oplossingen, van groot naar klein:

SuperRembo, 248 tekens:


GlowMouse, 228 tekens:


JeRa, 214 tekens:


(whitespace moet je even wegdenken en <? moet je ervoor denken )

De uitleg (leermomenten )

Over het algemeen kunnen we het probleem in 3-en hakken: ten eerste moet je een string of array samenstellen van de karakters die gebruikt mogen worden; de 'base' als het ware, dan volgt het daadwerkelijk encoden en als laatste het eventuele aanvullen met '='-tekens.

Het eerste punt is duidelijk te herkennen in de scripts en het is ook duidelijk dat JeRa daarvoor de kortste methode heeft gevonden; JeRa had slechts 52 tekens nodig om de base-string samen te stellen tegenover de 61 van SuperRembo en 62 van GlowMouse. Zelfs mijn eigen methode was met 56 duidelijk nog langer dan noodzakelijk

Dan komt het lastige stuk, namelijk de implementatie van het algoritme zelf
Zoals gezegd zie je duidelijk aan de drie inzendingen dat er ook 3 heel verschillende oplossingen gekozen zijn. Heel in het kort kan ik het als volgt samenvatten:

GlowMouse heeft ervoor gekozen om mbv de string formatting functie sprintf() eerst de input om te zetten naar een string-representatie van de individuele bits. Uiteindelijk krijg je dus een lange string met enkel enen en nullen die hij vervolgens vakkundig weer in stukjes van lengte 6 hakt, omzet naar een decimaal getal en het juiste base64-karakter output. Geen bitshifting dus en daarmee ook origineel, begrijpelijke code en vooral ook korte code

SuperRembo schuwt het bitshiften echter niet en gaat voor de aanpak waarbij hij telkens 3 bytes inleest en meteen 4 bytes output, samengesteld door te AND-en, te OR-en en te shiften (een oplossing die je overigens vaak tegenkomt voor dit probleem). Jammer dat het bij sommige stringlengtes fout gaat...

JeRa tenslotte komt met een oplossing die ook in de richting komt van mijn eigen idee hieromtrent: een loop waarin je telkens een karakter inleest, en 1 (of 2 - als je genoeg bits over hebt) encoded karakter output. Binnen de loop houdt hij de overtollige bits vast in een variabele voor de volgende iteratie.

JeRa en GlowMouse moeten na de encoding slag nog de padding regelen in een klein loopje; dat kan idd door slim gebruik te maken van de modulus van de input-counter

Ten slotte wil ik jullie mijn eigen 196-er (die na toepassing van enkele truuks uit o.a. JeRa's oplossing nog terug te brengen is tot 182 tekens) niet onthouden; ik heb hier door gebruik te maken van een 'end'-indicator $e de padding geintegreerd in de main-loop wat mij de nodige besparing opleverde.
Dit is zondermeer de slechts begrijpbare oplossing, en ik ga 'm ook niet volledig uitleggen In plaats daarvan zal ik in de volgende post een (imho) nette oplossing presenteren met uitleg



Ter afsluiting roep ik JeRa uit tot winnaar; hij komt imho het dichtst bij een 'ideale' oplossing en heeft op een aantal punten z'n code korter weten te schrijven dan ikzelf. Verder laat hij zien goed thuis te zijn in het werken met bits en is zijn code to-the-point en zelfs voor de ervaren bitneuker nog goed te volgen (wat van mijn eigen versie niet te zeggen is).

JeRa: gefeliciteerd!

Yay! *bier voor iedereen* Ik vind die oplossing van GlowMouse enorm leuk, omdat ie zo origineel is je bent vaak zo erg met getallen aan het rekenen dat je soms niet inziet dat het ook verrekte kort kan met een simpele string-representatie

Ook erg benieuwd naar Crisp's uitleg over zijn (gecleanede) methode

edit:

quote:

Zelfs mijn eigen methode was met 56 duidelijk nog langer dan noodzakelijk

Ik gebruik geen '=' in mijn base, en als je die bij jouw methode weglaat is het aantal tekens ook 52

edit2: $r=$r<<8; is hetzelfde als $r<<=8; mocht je dat nog niet in je kleinere versie hebben

[ Bericht 20% gewijzigd door JeRa op 19-12-2005 00:18:53 ]

Nou JeRa, ik denk dat je in 1 oogopslag zelf wel zult zien wat het doet
Ik heb het even in een functie gegoten omdat je het meestal ook in die vorm zult gebruiken. De truuks met pos($_POST) kennen we allemaal wel, dus hier gewoon een 'nette' uitvoering:


Wat het doet is simpel; ik hou een bitpointer en een 'remainder' bij. De bitpointer laat zien hoeveel bits er nog in mijn 'remainder' zitten.
De while-loop loopt door tot ik alle bytes van mijn input-string heb gehad. Als eerste check ik of ik genoeg bits in mijn 'remainder' heb zitten - zo niet, dan vul ik 'm aan met blokjes van 8 bits (1 byte) uit mijn inputstring tot ik genoeg heb.
Vervolgens pak ik zoveel bytes als ik nodig heb voor mijn encoding (6 in dit geval) en vul mijn result aan met het bijbehorende karakter uit mijn base-set. Die bits zet ik in mijn remainder vervolgens op 0 dmv de AND-constructie met een mask van $bitpointer 1-bits die ervoor zorgt dat enkel de niet-gebruikte bits (low-order) overblijven.

Als ik op deze manier door de hele inputstring heen ben gegaan kan het zijn dat ik nog iets in mijn remainder heb staan ($bitpointer is dan niet 0); ik moet dus nog een karakter outputten door die remainder te left-shiften met 6 - $bitpointer bits.
Als vervolgens na aftrek van het aantal te encoden bits de bitpointer nog niet 0 is moet ik gaan padden totdat de bitpointer modulus 8 de 0 bereikt.

Het grote voordeel van deze aanpak is dat het eenvoudig is om te zetten naar een andere macht-van-2-basis zoals base32 of base128 (dat laatste gebruik ik bijvoorbeeld voor een javascript-compressie algoritme).

De 196 van mij heb ik momenteel overigens terug weten te brengen tot 176:



[ Bericht 0% gewijzigd door crisp op 19-12-2005 00:47:59 ]

JeRa gefeliciteerd

Ik heb er geen moment aan gedacht om range() te gebruiken.
Mijn aanpak was misschien wat te lomp, maar ik had ook geen zin meer om opnieuw te beginnen.

quote:

Op maandag 19 december 2005 00:06 schreef JeRa het volgende:
Ik gebruik geen '=' in mijn base, en als je die bij jouw methode weglaat is het aantal tekens ook 52

Die ,'=' had ik al buiten beschouwing gelaten

quote:

edit2: $r=$r<<8; is hetzelfde als $r<<=8; mocht je dat nog niet in je kleinere versie hebben

Nee, samen met die OR gaat dat niet goed...

Overigens mag iedereen zich wel een beetje winnaar noemen; ik had niet verwacht dat ik zulke goede inzendingen zou krijgen, en zelfs dat foutje van SuperRembo is nog te vergeven aangezien het volgens mij best wel eenvoudig te fixen is

quote:

Op maandag 19 december 2005 00:43 schreef crisp het volgende:
Nee, samen met die OR gaat dat niet goed...

Shame on me... na zoveel uittesten zou operator precedence er nu toch wel in moeten zitten bij mij.

quote:

Overigens mag iedereen zich wel een beetje winnaar noemen; ik had niet verwacht dat ik zulke goede inzendingen zou krijgen, en zelfs dat foutje van SuperRembo is nog te vergeven aangezien het volgens mij best wel eenvoudig te fixen is

En jij bent ook zeker een winnaar, 176 tekens is wel schandalig klein

quote:

Op maandag 19 december 2005 00:32 schreef crisp het volgende:
Het grote voordeel van deze aanpak is dat het eenvoudig is om te zetten naar een andere macht-van-2-basis zoals base32 of base128 (dat laatste gebruik ik bijvoorbeeld voor een javascript-compressie algoritme).

Waar gebruik je die compressie voor? Is het ook ergens in actie te bewonderen?

quote:

Op maandag 19 december 2005 07:43 schreef SuperRembo het volgende:

[..]

Waar gebruik je die compressie voor? Is het ook ergens in actie te bewonderen?

Een uitwerking van LZW/LZS met nog een aantal verbeteringen in javascript: http://therealcrisp.xs4all.nl/upload/jscompress.html
Ik gebruik hier dus base128 encoding voor het resultaat (overhead van base64 is 33%, van base128 slechts 14%).
Ik gebruik hier phased-in binary coding om de compressie-ratio met zo'n 10% te verhogen tov standaard LZW en werk nog aan een manier om de dictionary sneller aan te vullen wat over het algemeen ook nog zo'n 10% winst op kan leveren. Standaard LZW geeft meestal een compressie-ratio van zo'n 50% bij gemiddelde teksten, dit algoritme zou 60-70% moeten halen zonder alteveel in te boeten op performance of complexiteit.
Phased-in binary coding is wel een aardige techniek; stel dat je dictionary 10 codes bevat. In normaal LZW zou je die codes dan outputten als 4-bit, maar met phased-in binary coding kan je voor de kleinere codes toch nog 3 bits gebruiken:

Ziet er gaaf uit
Heb je dit gemaakt als studie, voor de lol of heb je ook een echte toepassing?

idd, hoe langer de text hoe meer compressie geweldig... kan het helaas zelf niet maken want snap er de balle van maar goed!

quote:

Op maandag 19 december 2005 19:27 schreef SuperRembo het volgende:
Ziet er gaaf uit
Heb je dit gemaakt als studie, voor de lol of heb je ook een echte toepassing?

Een beetje voor de lol eigenlijk. Ik had LZW al geimplementeerd in mijn javascript GIF generator (WIP) en wou eens kijken of het ook bruikbaar zou zijn voor een javascript compressor/obfuscator

Ik had eigenlijk niet gedacht dat compressie zo simpel was, in ieder geval goed te begrijpen. En de hoeveelheid code valt helemaal mee. Misschien moet ik m'n php animated gif class nog eens herschrijven met een eigen compressie routine. (Nu maak ik gebruik van gd)

Wanneer komt eigenlijk de volgende PHP Golf?

Ik heb namelijk een vrij nutteloze maar best uitdagende PHP-puzzel bedacht die we misschien als extra tussendoortje kunnen doen