[Centraal] PHP - Golf wedstrijd

Overigens vind ik dit gedrag van PHP ietwat hinderlijk:

ord(chr(0)) === ord('')

Oftewel, de waarde van een binary null is hetzelfde als de waarde van een lege string.

Op 221 tekens nu trouwens. De riem wordt strak aangetrokken

[ Bericht 12% gewijzigd door JeRa op 14-12-2005 19:41:24 ]

En wanneer komt de uitslag?

quote:

Op woensdag 14 december 2005 22:36 schreef Chandler het volgende:
En wanneer komt de uitslag?

Na de einddatum wellicht?

Ik zit nu op 220 219 tekens

[ Bericht 8% gewijzigd door JeRa op 14-12-2005 22:53:38 ]

Na wat gekut met bitshiften zit ik nu op 253.

JeRa is goed bezig zo te horen
Ik ben erg benieuwd, ik denk dat hier best wel wat leuke dingen uit gaan komen

quote:

Op woensdag 14 december 2005 23:39 schreef crisp het volgende:
JeRa is goed bezig zo te horen
Ik ben erg benieuwd, ik denk dat hier best wel wat leuke dingen uit gaan komen

Heb je eigenlijk al een idee op welke strings je de inzendingen gaat testen? Het zou namelijk best wel eens zo kunnen zijn dat een scriptje schrikt van een lege string, eentje met niet-ascii tekens, etc (tot nu toe zit ik nog safe, gelukkig heb ik een kortere workaround gevonden voor het probleem met ord() zoals ik een paar posts hierboven had beschreven).

edit: handige eigenschap van de taal die PHP heet brengt mijn aantal nu naar 217. En nou stop ik voor vandaag de kleine versie van m'n script staat op 202 tekens.

edit2: spontane ingeving brengt me naar 214. Ooit moet ik leren stoppen.

[ Bericht 8% gewijzigd door JeRa op 14-12-2005 23:56:25 ]

base64_encode is natuurlijk primair juist bedoelt om binaire data te transporteren, dus daar zal het zeker mee overweg moeten kunnen (hoewel dat via een form wat lastiger te testen is). Een lege string zou gewoon ook een lege string terug moeten geven

quote:

Op donderdag 15 december 2005 00:10 schreef crisp het volgende:
base64_encode is natuurlijk primair juist bedoelt om binaire data te transporteren, dus daar zal het zeker mee overweg moeten kunnen (hoewel dat via een form wat lastiger te testen is). Een lege string zou gewoon ook een lege string terug moeten geven

Mja, ik zat vooral met dat formulier in gedachten ja. De drempel is dan wat lager om het alleen met user(/ascii)input te proberen ipv ook binaire data zit nu trouwens op 210 209 208 tekens, sinds gisteravond nog vier vijf zes tekentjes eraf kunnen halen. De kleine versie staat op 188 tekens.

[ Bericht 2% gewijzigd door JeRa op 15-12-2005 11:57:54 ]

als je algoritme goed in elkaar zit zou binaire input geen probleem mogen zijn

quote:

Op donderdag 15 december 2005 11:59 schreef crisp het volgende:
als je algoritme goed in elkaar zit zou binaire input geen probleem mogen zijn

Oh die van mij zit prima in elkaar maar af en toe erger ik me dus aan het gedrag van PHP die ord() altijd iets laat teruggeven waardoor een lege string gelijk wordt gesteld aan chr(0). Dat hebben ze bij strpos() toch beter gedaan nu heb ik dat nu niet meer nodig, dus ik ga maar eens verder met het verkleinen van m'n script.

Grmbl hij kon niet overweg met chr(48), ik denk dat een aantal mensen wel weet waarom. Weg 208 tekens

195

En de eerste inzending is binnen
Aangezien ik natuurlijk nu inspiratie op zou kunnen doen daaruit hou ik het bij mijn 195-er, hoewel het een heel andere approach is dan degene die ik heb genomen

quote:

Op vrijdag 16 december 2005 18:10 schreef crisp het volgende:
En de eerste inzending is binnen
Aangezien ik natuurlijk nu inspiratie op zou kunnen doen daaruit hou ik het bij mijn 195-er, hoewel het een heel andere approach is dan degene die ik heb genomen

Zeg eens, je hebt de wedstrijd verzonnen terwijl je al een vrij geoptimaliseerde versie had liggen, en dan doe je nog mee ook?

quote:

Op zaterdag 17 december 2005 00:45 schreef JeRa het volgende:

[..]

Zeg eens, je hebt de wedstrijd verzonnen terwijl je al een vrij geoptimaliseerde versie had liggen, en dan doe je nog mee ook?

Ik weet zeker dat jij er wel onder komt

quote:

Op zaterdag 17 december 2005 01:08 schreef crisp het volgende:

[..]

Ik weet zeker dat jij er wel onder komt

I'll try, maar ik moet nog eerst het probleem oplossen dat ie gvd één tekentje uit een subset van 256 tekentjes niet pikt

Puur uit nieuwsgierigheid; ik test mijn methode door vele malen een random input string van willekeurige lengte en willekeurige inhoud (bytes van 0 t/m 255) te genereren en de output van mijn methode te vergelijken met de output van base64_encode(). Heb jij ook iets dergelijks gedaan of bewijs je je code? (ik deed het eerst met het laatste totdat ik erachter kwam dat PHP eigenlijk niet zo heel consequent is)

Ik heb tot nog toe enkel getest met wat random strings - niet echt uitputtend yet.
De JS versie van mijn algoritme gebruik ik echter voor binaire strings en die heb ik meermalen met base64_encode() vergeleken.

quote:

Op zaterdag 17 december 2005 13:49 schreef crisp het volgende:
Ik heb tot nog toe enkel getest met wat random strings - niet echt uitputtend yet.
De JS versie van mijn algoritme gebruik ik echter voor binaire strings en die heb ik meermalen met base64_encode() vergeleken.

Ik had dus ook eerst een werkende versie die ik vervolgens ging optimaliseren waarna bleek dat bepaalde optimalisaties ervoor zorgden dat het in het geheel niet meer werkten als ie een bepaald teken tegenkwam. Ben benieuwd naar de oplossingen morgen

Ik zit nu op 214 tekens.

[ Bericht 3% gewijzigd door JeRa op 17-12-2005 14:28:59 ]

Inmiddels ook getest met random binairy strings en mijn versie werkt prima. Ook de inzending die ik al heb gekregen is goedgekeurd

Ziet er goed uit JeRa
Een aantal dingen heb je korter opgelost dan ik; als ik dat in mijn script zou integreren kom ik op 182 (maar ik doe uiteraard voor spek en bonen mee)

quote:

Op zaterdag 17 december 2005 21:31 schreef crisp het volgende:
Ziet er goed uit JeRa
Een aantal dingen heb je korter opgelost dan ik; als ik dat in mijn script zou integreren kom ik op 182 (maar ik doe uiteraard voor spek en bonen mee)

Tja, maar ik doe in essentie iets verkeerd. heb me vannacht dood lopen staren op substituties, extracties, transponaties en deleties, maar ik zag niets meer

Ik heb uiteindelijk het probleem van de padding toch in de 'mainloop' weten te integreren, dat scheelt toch weer een byte of wat

Ik kap er mee. 248 tekens ingestuurd.

Ik heb nu dus wel twee belangrijke dingen in PHP geleerd. Dit werkt niet zoals ik zou verwachten:

Het blijkt dat intern preg_replace() zend_string_eval() aanroept, die kennelijk de eerste de beste evaluatie retourneert. Dit in tegenstelling tot eval(), die de code écht als PHP code uitvoert. Een 'echo' kun je bij de preg_replace()-versie dan ook niet uitvoeren.

En dit:

Een "0", dat is toch hartstikke logisch, die wordt gecast naar de integer 0 en vervolgens ziet PHP dat als de conditie 'false' en dat terwijl een wérkelijke nul-waarde (chr(0)) gewoon wél wordt gepikt!

Oh, en nog die ene waar ik het al eerder over had:

Oftewel, genoeg valkuilen.

[ Bericht 13% gewijzigd door JeRa op 17-12-2005 23:43:31 ]

idd ook de entry van SuperRembo binnen; weer een heel andere approach, maar dat was ook de opzet uiteraard
Dat wordt morgen een flinke lap uitleg schrijven

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