[Contest] Xopus challenge

[Aphelion]

Hey mensen,

Hierbij eens wat anders dan een lastig probleem; een leuk probleempje!
Ik las vanochtend in de Metro of de Spits een vacature van Xopus. Er stonden echter geen eisen, maar slechts het volgende blokje code. Ik vermoed dat dit Java is? Zeker weet ik het echter niet!

code:

Function PrettyPrintLargeNumber(num)
{
    var out = "";
    var inp = num.ToString();
    
    for (var i = inp.length  - 1; 1, j = 0;
        I >= 0;
        I --, j++)
    {
        if (j % 3 == 0 && I != inp.length - 1)
        {
            out = "." + out;
        }

        out = inp.CharAt(i) + out;
    }

    return out; 
}

Hierbij was het verzoek, om deze functie te optimaliseren. Maak hem mooier, sneller en efficienter.

Nu ben ik niet echt geinteresseerd om daar te werken, maar het is misschien wel leuk om hier op GoT te kijken wie naar ons idee de mooiste opschoning voor deze functie weet te maken. Excuses voor foute overnames / syntax (hoofdletters etc?) ik heb het snel overklopt met mn PDA!

Zelf ben ik geen held in talen behalve VB, dus heb ik geprobeerd het bovenstaand te vertalen naar VB.NET. Nu echter nog het optimaliseren!

code:

Private function PrintNum(ByVal lngNum as long) as string

    Dim strResult as string = ""
    Dim strInput as string = lngNum.ToString
    
    Dim I as integer = strInput.Length - 1
    Dim j as integer = 0

    Do while I >= 0

        I = I - 1
        J = j + 1

        If j % 3 = 0 AND I IsNot inp.Length - 1; 1) then
            strResult = "."; + strResult
        End If
    loop    

    return strResult
    
End function

Ik ben benieuwd naar jullie oplossingen !

[Glabbeek]

Dit is javascript, dat kan je bijvoorbeeld zien aan de 'var' keywords.

[mr_obb]

Hier staat een blog met het codeblok.

http://xopus.com/devblog/2008/prettyprintlargenumber

JavaScript:

function prettyPrintLargeNumber(num)
{
  var out = "";
  var inp = num.toString();
   for (var i = inp.length - 1, j = 0; 
       i >= 0; 
       i--, j++)  
  {    
    if (j % 3 == 0 && i != inp.length - 1)
      out = "." + out;    
      out = inp.charAt(i) + out; 
  }
  return out;
}

[ Voor 64% gewijzigd door mr_obb op 05-03-2008 17:50 ]

[Nick_S]

En ik weet ook heel zeker, dat als je met je geoptimaliseerde stukje VB.net aankomt bij Xopus, dat je dan geen kans maakt op een baan. Xopus is gespecialiseerd in Javascript en heeft een WYSIWYG XML Editor voor in de browser gemaakt. Ik werk er op dit moment mee en het werkt ook nog, namespaces et al.

[Cartman!]

Ik ben vanmorgen uiteindelijk op dit uitgekomen met googlen en dingen aanpassen:

code:

function prettyPrintLargeNumber(out)
{
    out += '';
    var rgx = /(\d+)(\d{3})/;
    while (rgx.test(out)){out = out.replace(rgx, '$1' + '.' + '$2');}
    return out;
}

Ik stuur em niet in verder, niet op zoek naar een baan bij Xopus maar vond het wel een leuke actie.

[crisp]

Lon (van Xopus) wees me hier eergisteren al op, toen kwam ik in eerste instantie uit op:

JavaScript:

function prettyPrintLargeNumber(n)
{
    var i=(n+='').length-3;return i>0?prettyPrintLargeNumber(n.substr(0,i))+'.'+n.substr(i):n;
}

recursief dus, jammer dat die functienaam zo lang is

Deze (of iets soortgelijks) heb ik echter naar hem gemailed (niet om te solliciteren maar voor de lol) omdat ik hier gebruik maak van een feature in javascript die niet iedereen kent, namelijk de mogelijkheid om een functie als replace argument te gebruiken:

JavaScript:

function prettyPrintLargeNumber(n)
{
    return(n+'').replace(/(\d+)(\d{3})/,function(a,b,c){return prettyPrintLargeNumber(b)+'.'+c});
}

echter dankzij Cartman! zag ik zojuist een nog veel kortere manier:

JavaScript:

function prettyPrintLargeNumber(n)
{
    while((t=n+'')&&(n=t.replace(/(\d+)(\d{3})/,'$1'+'.'+'$2'))!=t);return n;
}

edit: nog wat korter en zonder (global) tempvar:

JavaScript:

function prettyPrintLargeNumber(n)
{
    while((n+='')!=(n=n.replace(/(\d+)(\d{3})/,'$1.$2')));return n
}

[ Voor 8% gewijzigd door crisp op 06-03-2008 00:18 ]

[The Fox NL]

Nog een andere manier, in delphi code. Geen regex fratsen, maar een andere methode.

Delphi:

function PrintPrettyNumber2(const aNum: Int64): string;
var
  lTemp: Int64;
begin
  lTemp := Abs(aNum);
  repeat
    Result := IntToStr(lTemp mod 1000) + Result;
    lTemp := lTemp div 1000;
    if lTemp > 0 then
      Result := '.' + Result;
  until (lTemp = 0);
  if aNum < 0 then
    Result := '-' + Result;
end;

[RobIII]

C#:

string prettyPrintLargeNumber(long num) { return num.ToString("N0"); }

Visual Basic .NET:

Function prettyPrintLargeNumber(ByVal num As Long)
    Return num.ToString("N0")
End Function

Visual Basic:

'VB6 / VBA / VBS
Function prettyPrintLargeNumber(num)
    prettyPrintLargeNumber = FormatNumber(num, 0, vbUseDefault, vbUseDefault, vbTrue)
End Function

SQL:

CREATE FUNCTION prettyPrintLargeNumber(@num bigint)
RETURNS varchar(20)
AS
BEGIN
    DECLARE @result varchar(20)
    Set @result = CONVERT(varchar, CAST(@num AS money), 1)
    RETURN Left(@result, Len(@result)-3)
END

[ Voor 50% gewijzigd door RobIII op 06-03-2008 00:03 ]

[Verwijderd]

One liner:

JavaScript:

function prettyPrint(num) {
    return (num + '').split('').reverse().join('').replace(/(\d{3})/g, '$1.').substring(0,Math.ceil((num + '').length / 3 * 4) - 1).split('').reverse().join('');
}

Iets leesbaarder:

JavaScript:

function prettyPrint(num) {
    return (num + '')
            .split('').reverse().join('')
            .replace(/(\d{3})/g, '$1.')
            .substring(0,Math.ceil((num + '').length / 3 * 4) - 1)
            .split('').reverse().join('');
}

Leuk

[? ?]

..

[ Voor 135% gewijzigd door ? ? op 25-01-2013 09:52 ]

[crisp]

benchmarks: http://therealcrisp.xs4all.nl/prettyprint.html

ik heb de vrijheid genomen om de variable-namen in te korten en zoveel mogelijk whitespace te strippen voor de byte-vergelijking van de functie-body
met nog een kleine aanpassing in de regexp is dit volgens mij naast het kortst ook het snelst:

JavaScript:

function prettyPrintLargeNumber(n)
{
    while((n+='')!=(n=n.replace(/(\d)(\d{3})$/,'$1.$2')));return n
}

[ Voor 20% gewijzigd door crisp op 06-03-2008 02:00 ]

[Verwijderd]

Wat doen jullie allemaal moeilijk ?
Hoort bij coden ook niet het slim gebruik maken van de aanwezige library's

Delphi:

function prettyPrintLargeNumber(n : cardinal)  : string;
begin
  result := formatfloat('0,00', n);
end;

[ Voor 3% gewijzigd door Verwijderd op 06-03-2008 01:14 ]

[MueR]

PHP:

function PrintPrettyNumber($num) {
  print number_format($num);
}

[RobIII]

Verwijderd schreef op donderdag 06 maart 2008 @ 01:08:
Wat doen jullie allemaal moeilijk ?
Hoort bij coden ook niet het gebruik maken van de aanwezige library's

Delphi:

function prettyPrintLargeNumber(n : cardinal)  : string;
begin
  result := formatfloat('0,00', n);
end;

Geeft die niet een getal met decimalen terug? Ik neem aan dat dit Delphi is? Duh; staat erboven Ik ben niet (meer) zo heel bekend met Delphi, maar als dit decimalen teruggeeft heb je 't niet alleen korter gemaakt maar ook stuk

Volgens mijn (vage) herinnering is dit al voldoende:

Delphi:

function prettyPrintLargeNumber(n : cardinal)  : string;
begin
  result := formatfloat(',0', n);   //of 0, ??
end;

[ Voor 27% gewijzigd door RobIII op 06-03-2008 01:21 ]

[Verwijderd]

RobIII schreef op donderdag 06 maart 2008 @ 01:11:
[...]

Geeft die niet een getal met decimalen terug? Ik neem aan dat dit Delphi is? Ik ben niet (meer) zo heel bekend met Delphi, maar als dit decimalen teruggeeft heb je 't niet alleen korter gemaakt maar ook stuk

nope, n is sowieso cardinal.

ik ga ff je verkorte versie checken, ben gewend om er in ieder geval iets te typen

@\/\/\/ ja goed, hij moet toch prettyworden, wie mooi wilt zijn ...
[edit]
jouw versie geeft leeg terug

[edit2]
yep nu is ie goed, maar een 0 aan de andere kant v/d komma had ook goed geweest

[ Voor 28% gewijzigd door Verwijderd op 06-03-2008 01:22 ]

[RobIII]

Verwijderd schreef op donderdag 06 maart 2008 @ 01:13:
[...]

nope, n is sowieso cardinal.

Waarna je 'm door een formatfloat heen gooit en vervolgens als (formatted) string returned. Maargoed, ik heb geen Delphi bij de hand hier en durf er ook niets om te verwedden (too long ago )

Verwijderd schreef op donderdag 06 maart 2008 @ 01:13:

jouw versie geeft leeg terug

Kleine typo Nu nog?

[ Voor 20% gewijzigd door RobIII op 06-03-2008 01:20 ]

[Verwijderd]

voor de echt dan maar een echte functie geschreven:

Delphi:

  function prettyPrintLargeNumber4(n : cardinal)  : string;
   var
     idx : integer;
  begin
    Result := inttostr(n);
    idx    := length(Result) - 2;
    while idx > 0 do
    begin
      Insert('.',Result,idx);
      dec(idx,3);
    end;
  end;

[_js_]

Een aantal van de oplossingen klopt niet (vooral de regex oplossingen en alle van RobIII niet).

In het origineel is bij invoer van een negatief getal als -123 het resultaat -.123, bij de foute oplossingen blijft het -123.

In de eis staat alleen mooier, sneller en korter, niets over fouten weghalen

[? ?]

..

[ Voor 100% gewijzigd door ? ? op 25-01-2013 09:52 ]

[unclero]

Ik zie al dat ik niet meer ga winnen..

5 Minuutjes gisteravond:

JavaScript:

function prettyPrintLargeNumber(num)
{
  var out = "";
  var j = 0;
  var i = num.toString().length;
  do {
    out = num.toString().charAt(--i) + (++j % 3 == 0 ? "." : "") + out;
  } while(i >= 0)
  return out;
}

[Verwijderd]

Hierbij mijn inzending! Niet de korste maar wel rekening gehouden met decimalen en negatieve getallen. Crisp, als je tijd hebt en je hebt zin om hem door je benchmark te halen graag!!!

code:

function prettyPrintLargeNumber(num)
{

    //convert number to string
    var out = num.toString();
    
    //is Number?
    if (isFinite(out))
    {
        
        //split decimals from number
        arr_sign_inte_fract = out.split('.');
        sign_inte = arr_sign_inte_fract[0];     
        fract = arr_sign_inte_fract.length > 1 ? ',' + arr_sign_inte_fract[1] : "";
        alert(arr_sign_inte_fract.length);
        
        //split sign from number
        arr_sign_inte = sign_inte.split('-');
        sign = arr_sign_inte.length > 1 ? "-" : "";
        inte = arr_sign_inte.length > 1 ? arr_sign_inte[1] : inte = arr_sign_inte[0];


        //padd zeros
        switch (inte.length % 3)
        {
            case 0: 
                nrPadded = 0;
                break;
            case 1: 
                nrPadded = 2;
                inte = "00" + inte;
                break;
            case 2: 
                nrPadded = 1;
                inte = "0" + inte;
                break;
        }

        //add dots after each three digits
        inte = inte.replace(/([0-9]{3})/g,"$1.");
        
        //remove leading zeros and last dot
        inte = inte.substring(nrPadded,inte.length-1);
        
        //combign the integral part with the fractional part and add the sign
        out = sign + inte + fract;
    }
    else
    {
        //not a number -> return ""
        out = "";
    }
    return out;
}

Mijn eerste inzending was afgekeurd. Ik maakte gebruik van toLocaleString() die gebruikt maakt van de windows instelling voor het tonen voor grote getallen. Niet generiek dus. weet iemand die vanuit code te tweaken?

grtz,

Bart

code:

function prettyPrintLargeNumberBart(num)
{
    var out = num.toLocaleString();
    out = out.replace(".00","");
    
    while (out.search(",") != -1)
    {
        out = out.replace(",",".");
    }
    return out;
}

[ Voor 14% gewijzigd door Verwijderd op 06-03-2008 12:07 ]

[PrisonerOfPain]

crisp schreef op donderdag 06 maart 2008 @ 01:01:
met nog een kleine aanpassing in de regexp is dit volgens mij naast het kortst ook het snelst:

Aangezien er geen target platform bij genoemd word kun je niet zomaar van 'de snelste' spreken.

Dit zijn de resultaten onder Safari 3.0.4.

code:

prettyPrintLargeNumber0 (original - 120 bytes): 345ms
prettyPrintLargeNumber1 (Cartman! - 81 bytes): 391ms
prettyPrintLargeNumber2 (Blues - 140 bytes): 427ms
prettyPrintLargeNumber3 (crisp - substr() version - 90 bytes): 183ms
prettyPrintLargeNumber4 (crisp - regexp recursive replacement function - 93 bytes): 315ms
prettyPrintLargeNumber5 (crisp - regexp loop function - 62 bytes): 444ms
prettyPrintLargeNumber6 (crisp - regexp loop function modified - 62 bytes): 306ms

[Aphelion]

Crips, gaaf van je benchmark tool! Wat mij op eens te binnen schoot; hoort bij 'pretty' programmeren ook niet een juiste error handling. of validatie van de input. (Dank aan Nosemans). Ik ben benieuwd of ze hier naar gaan kijken bij de inzendingen.

[crisp]

PrisonerOfPain schreef op donderdag 06 maart 2008 @ 11:35:
[...]


Aangezien er geen target platform bij genoemd word kun je niet zomaar van 'de snelste' spreken.

Mwa, je kan de resultaten in verschillende browsers natuurlijk een bepaalde zwaarte geven, bijvoorbeeld op basis van marktaandeel

[unclero]

Cool

En die van mij?

[pedorus]

De mijne is 80 karakters, negative-bug compliant, en is sneller in FF en IE. Enkel prettyPrintLargeNumber6 is sneller in FF, maar die geeft niet het juiste antwoord. Ik zal de meeste karakters geven:

JavaScript:

function prettyPrintLargeNumber(n){return ?????????????????????????????????????}

spoiler: hint

gebruikt replace

spoiler: hint2

gebruikt look-forward

spoiler: oplossing

(n+'').replace(/.(?=(...)+$)/g,'$&.')

leuk probleempje

[crisp]

pedorus schreef op donderdag 06 maart 2008 @ 12:59:
De mijne is 80 karakters, negative-bug compliant, en is sneller in FF en IE.
[...]

Nice! Ik zat gisteren ook aan look-ahead/behind te denken maar helemaal vergeten dat je $& kon gebruiken

[Verwijderd]

crisp schreef op donderdag 06 maart 2008 @ 13:22:
Nice! Ik zat gisteren ook aan look-ahead/behind te denken maar helemaal vergeten dat je $& kon gebruiken

Mijn RegEx-Fu is failing. Zou een van jullie deze eens kunnen verhelderen?

JavaScript:

(n+'').replace(/.(?=(...)+$)/g,'$&.')

[LvdO]

Leuk dat onze advertentie iedereen zo bezig houdt!

Ik heb een vergelijking gemaakt van het origineel met onze eigen verbeteringen, de ingezonden code tot nu toe en jullie code:

Versie	IE7	FF2	O9.2	S3	Negatief	Decimalen
Origineel	515	531	313	312	nee	nee
Xopus: Snelste	219	281	750	250	ja	nee
Xopus: Meest correcte	344	344	797	313	ja	ja
Snelste inzending IE7	235	265	140	125	nee	nee
Snelste inzending FF2	250	250	141	125	nee	nee
Snelste inzending O9.2	250	266	125	110	nee	nee
Snelste inzending S3	250	266	125	110	nee	nee
Meest correcte inzending	609	625	1094	437	ja	ja
Cartman!	500	422	1141	391	ja	nee
crisp 1	359	281	156	157	nee	nee
crisp 2	938	860	813	484	ja	nee
crisp 3	531	390	1109	563	ja	nee
Blues	968	1078	985	422	nee	nee
Nosemans	609	625	1094	437	ja	ja
pedorus	219	250	671	204	nee	nee

De vierde functie van crisp en de functie van unclero werken helaas niet voor alle getallen waar het origineel wel voor werkt, dus die meetingen heb ik weggelaten.

Ik heb nu de volgende benchmark gebruikt:

JavaScript:

  var t0 = new Date();
  for (var i=0; i < 10000; i++)
    f(i * i);
  var t1 = new Date();

[? ?]

..

[ Voor 98% gewijzigd door ? ? op 25-01-2013 09:52 ]

[pedorus]

Verwijderd schreef op donderdag 06 maart 2008 @ 14:24:
Mijn RegEx-Fu is failing. Zou een van jullie deze eens kunnen verhelderen?

JavaScript:

replace(/.(?=(...)+$)/g,'$&.')

.	een willekeurig karakter (niet end-line). Zet hier \d neer voor een cijfer zodat '-' niet gematched wordt
(?=	groepje vanaf hier, waarbij het groepje zelf niet meetelt voor het gematchte resultaat. Dit is belangrijk omdat we in dit groepje nog meer matches kunnen hebben.
(...)+$	een veelvoud van 3 willekeurige karakters totaan het einde (niet end-lines). Je kan hier ook iets als (\d{3})+\b van maken voor dingen als "1234567 apen en 1122 kippen"
)	eind groepje
'$&.'	vervang gematchte tekst (dus 1 willekeurig karakter) door die tekst met een . erachter
g	alle vervangen vanaf de vorige positie. Omdat het groepje hierbij niet meetelt, is de vorige positie dus gelijk het karakter erna. VB met gematchte underlined en nog over te matchen tussen haakjes: [10000000]->10.[000000]->10.000.[000]->10.000.000

Ik zag nog een methode om nog 1 karakter te besparen: de spatie na return verwijderen - 79 karakters maar minder mooi (waarschijnlijk niet-standaard).

[unclero]

LvdO schreef op donderdag 06 maart 2008 @ 16:13:
De vierde functie van crisp en de functie van unclero werken helaas niet voor alle getallen waar het origineel wel voor werkt, dus die meetingen heb ik weggelaten.

Hmmm... ik kan zeker niet nog een poging wagen om tot verbeteringen te komen?

* unclero really wished he'd spend more than those 5 minutes on that code

[LvdO]

era.zer schreef op donderdag 06 maart 2008 @ 16:25:
Wat is eigenlijk de bedoeling?
De output geven zoals de originele, of correcte negatieve getallen, correcte floating points, ... ?
Want in js heb je ook 1.4E10 getalletjes, zeer duidelijk is de opdracht die op de site staat niet.

De bedoeling is: maak een kortere, snellere en fraaiere versie van het origineel.

Snel kan je meten, kort is lastiger (bytes, lines, statements?) en fraai is helemaal subjectief. Je wordt dus gedwongen tot een compromis. Degene die dat (volgens ons) het beste kan krijgt de fles whiskey. Dat lijkt redelijk arbitrair, maar we hebben een paar inzendingen die de drie criteria erg goed weten te combineren.

We verwachten dat de code minimaal werkt in de gevallen waar het origineel voor werkt, alle uitbreidingen vallen onder het kopje fraaier.

[pedorus]

LvdO schreef op donderdag 06 maart 2008 @ 16:54:
Snel kan je meten, kort is lastiger (bytes, lines, statements?) en fraai is helemaal subjectief.

Ik zou juist zeggen dat kort goed te meten is (bytes, na versimpeling variabelen en whitespace, zoals bij google.com). Het aantal bytes is makkelijk te meten en die moeten vaak worden overgezonden bij JavaScript, wat bandbreedte en tijd kost.
Snel is juist een stuk lastiger: welke configuratie/browser gebruikt je? Welke verhoudingen tussen de browsers gebruik je? Zal dit in de toekomst nog steeds hetzelfde zijn? En zelfs als je dezelfde functie op dezelfde computer met dezelfde browser meet krijg je steeds net andere waardes...
Aangezien dit een functie is voor GUI-output is snelheid daarnaast veel minder relevant. Zoveel waardes passen er nu ook weer niet op een scherm.

[? ?]

..

[ Voor 105% gewijzigd door ? ? op 25-01-2013 09:52 ]

[EfBe]

Print de originele functie niet ook een '.' in de fraction? Lijkt me niet goed. (voor de rest een rampzalige manier van mensenwerven natuurlijk, maar goed.. )

[LvdO]

unclero schreef op donderdag 06 maart 2008 @ 16:40:
Hmmm... ik kan zeker niet nog een poging wagen om tot verbeteringen te komen?

Sure.

pedorus schreef op vrijdag 07 maart 2008 @ 12:51:
Het aantal bytes is makkelijk te meten

Goed punt. Echter de hoeveelheid bytes is voor ons minder van belang aangezien we de code toch comprimeren voor we releasen. Weinig statements is veel belangrijker want dat maakt de code leesbaarder en de kans op bugs kleiner.

Snel is juist een stuk lastiger

Snelheid meten is inderdaad lastig. Gelukkig zijn de verschillen in de inzendingen zo groot dat we voor de beoordeling geen rekening hoeven te houden met de details die je noemt.

Voor Xopus zelf is dat een ander verhaal, zeker de verschillen in performance karakteristiek tussen IE en bv. Safari zorgen voor problemen. In de praktijk pakken we de bottlenecks aan waar nodig.

Aangezien dit een functie is voor GUI-output is snelheid daarnaast veel minder relevant. Zoveel waardes passen er nu ook weer niet op een scherm.

Dat klopt, in de praktijk zouden we vast niet zoveel aandacht besteden aan deze functie (die geen onderdeel is van Xopus overigens). Echter performance is vitaal voor de gebruiksbeleving en als je 42K regels Javascript naar een browser stuurt, telt elke ms.

Verder is het natuurlijk gewoon een leuke uitdaging om zo'n simpel stuk code sneller te maken.

era.zer schreef op vrijdag 07 maart 2008 @ 13:39:
Een vraag:
12345,12345 wat moet dat worden in Amerikaans formaat (zoals xopus wil)
12.345,12345 of 12.234,12.345 ?

De output van de originele functie is Nederlands formaat.

EfBe schreef op vrijdag 07 maart 2008 @ 13:48:
Print de originele functie niet ook een '.' in de fraction? Lijkt me niet goed.

Dat klopt.

(voor de rest een rampzalige manier van mensenwerven natuurlijk, maar goed.. )

Het enige rampzalige voor ons is de tijd die het kost om het reageren op de onverwacht grote hoeveelheid inzendingen.

[? ?]

..

[ Voor 100% gewijzigd door ? ? op 25-01-2013 09:52 ]

[creative8500]

Weinig statements is iets anders dan alles op 1 regel zetten... Eloquentie is in code wel degelijk belangrijk; ook simpelweg in spreektaal ben je duidelijker wanneer je minder woorden voor hetzelfde gebruikt.

[? ?]

..

[ Voor 198% gewijzigd door ? ? op 25-01-2013 09:52 ]