Malen Sie diesen Zaun

Sie sind Tom Sawyer und müssen einen 102400 m langen Zaun streichen. Zum Glück haben Ihre Freunde beschlossen, Ihnen beim Austausch verschiedener Dinge zu helfen. Jeder Freund wird malen L m, ausgehend von S mit Farbe C . S , L sind ganzzahlige Meter und 1 ≤ C ≤ 97. Wenn Sie sich langweilen, entscheiden Sie sich, herauszufinden, wie viele Meter jeder Farbe Sie haben.

Eingang

Die Eingabe wird von der Standardeingabe gelesen. Jede Zeile enthält drei Zahlen S , L , C wie oben beschrieben.

Ausgabe

Die Ausgabe wird in die Standardausgabe geschrieben. Drucken Sie für jede Farbe, die auf dem endgültigen Zaun erscheint, die Farbnummer und die Häufigkeit, mit der sie erscheint. Nach Farben sortieren.

Beispiele

Eingabe 0

                           ..............
0 3 1                      111...........
2 4 2                      112222........
1 2 3                      133222........
0 4 1                      111122........
7 3 5                      111122.555....

Ausgabe 0

1 4
2 2
5 3

Eingabe 1

 0 100 1
 50 150 2

Ausgabe 1

 1 50
 2 150

Eingabe 2

 500 1000 1
 0 2000 2

Ausgabe 2

 2 2000

Mehr Beispiele

Hier ist ein kleiner Generator:

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>


/* From http://en.wikipedia.org/wiki/Random_number_generation */
unsigned m_w;
unsigned m_z;

unsigned get_random()
{
  m_z = 36969 * (m_z & 65535) + (m_z >> 16);
  m_w = 18000 * (m_w & 65535) + (m_w >> 16);
  return (m_z << 16) + m_w;  /* 32-bit result */
}

int main(int argc, char **argv)
{
  int i;

  assert(argc == 2);
  m_w = 0xbabecafe;
  m_z = atoi(argv[1]);

  i = 10;
  while (i--);
    get_random();

  i = atoi(argv[1]);
  while (i--) {
    int s = (int) ((get_random() << 8) % 102397);
    int l = (int) ((get_random() << 8) % (102397 - s));
    int c = (int) ((get_random() << 8) % 97 + 1);
    printf("%d %d %d\n", s, l, c);
  }

  return 0;
}

Laufende Beispiele:

$ ./gen 1 | ./paint
6 535
$ ./gen 10 | ./paint
28 82343
36 3476
41 1802
49 4102
82 1656
$ ./gen 100 | ./paint
2 2379
22 17357
24 4097
25 1051
34 55429
42 9028
45 9716
66 1495
71 196
85 640
97 706
$ ./gen 1000 | ./paint
16 719
26 29
28 24
33 1616
55 371
65 35
69 644
74 16
84 10891
86 36896
87 50832
89 19
$ ./gen 10000 | ./paint
3 800
6 5712
14 3022
17 16
26 1
29 18770
31 65372
37 387
44 40
49 37
50 93
55 11
68 278
70 19
71 64
72 170
77 119
78 6509
89 960
97 15
$ ./gen 100000 | ./paint
2 6
8 26
12 272
24 38576
26 1
34 1553
35 8
36 19505
43 2
45 11
46 2
47 9
49 27339
50 139
53 3109
69 11744
92 89
$ ./gen 1000000 | ./paint
1 1
3 4854
6 523
13 1
16 11
18 416
22 7
24 3920
25 96
31 10249
32 241
37 1135
45 10
57 758
62 2348
65 11
66 7422
78 6
85 13361
87 3833
88 187
91 46
93 7524
96 45436

Ihr Programm muss in angemessener Zeit ausgeführt werden. Meine Lösung läuft im letzten Beispiel in wenigen Sekunden.

Der kürzeste Code gewinnt.

Geben Sie die Laufzeit und Ihre Ausgabe für den letzten Test an.

BEARBEITEN : Dieses Problem soll nicht brutal erzwungen werden, daher ist eine triviale Lösung nicht akzeptabel.

Python, 221 239 Zeichen

import sys
F=[]
for L in sys.stdin:s,l,c=map(int,L.split());F=sum([[(a,min(b,s),d)]*(a<s)+[(max(a,s+l),b,d)]*(b>s+l)for a,b,d in F],[(s,s+l,c)])
C=[0]*98
for a,b,c in F:C[c]+=b-a
for c in range(98):
 if C[c]:print c,C[c]

Hält F als ungeordnete Liste von Tripeln (Startbeginn, Laufende, Farbe) gespeichert, die den aktuellen Status des Zauns darstellen. Da das zufällige Malen im Generator die Schwaden ziemlich häufig übermalt, ist diese Liste nie zu lang (normalerweise im Bereich von 15 bis 40).

Läuft im 1M-Beispiel in 37 Sekunden.

Haskell, 251 261 269 294 Zeichen

import Data.List
w@(y@(f,d,e):z)§x@[a,b,c]|e<=d=z§x|a+b>d=(f,d,e`min`a):((f,a+b,e):z)§x
w§[a,b,c]=(c,a,a+b):w
r(c,a,b)=replicate(b-a)c
f l=shows(l!!0)" "++shows(length l)"\n"
main=interact$(>>=f).group.(>>=r).sort.foldl'(§)[].map(map read.words).lines

Daran stimmt etwas nicht, da es viel zu viel Zeit und Stapel kostet ... Aber es liefert die richtigen Antworten:

$> ghc -O3 --make -rtsopts -with-rtsopts -K32m 3095-PaintTheFence.hs 
Linking 3095-PaintTheFence ...

$> ./3095-gen 1000000 | time ./3095-PaintTheFence
1 1
3 4854
6 523
13 1
16 11
18 416
22 7
24 3920
25 96
31 10249
32 241
37 1135
45 10
57 758
62 2348
65 11
66 7422
78 6
85 13361
87 3833
88 187
91 46
93 7524
96 45436
       43.99 real        43.42 user         0.46 sys

• Bearbeiten (294 → 269) replicateundgroup ist ebenso effizient zu zählen , die Farbe an und lässt weniger Code als die benutzerdefinierte Funktions
• Bearbeiten (269 → 261) kein maxAnruf erforderlich
• Bearbeiten (261 → 251) Keine Notwendigkeit, Farbe 0 Zoll auszusortieren f

Perl - 148 Bytes

Es scheint, dass Perl das Beste ist, mit dem man spielen kann. einfach kürzer und schneller zu codieren. ;)

Code:

#!perl -n
($a,$b,$c)=split;substr($s,$a,$b,chr($c)x$b)}BEGIN{$s="z"x102400}{$s=~s/([^z])\1*/$H{$1}+=length$&/ge;print ord," $H{$_}
"for sort keys%H

Zeit:

time ./gen 1000000 | perl paint.pl
...
real    0m9.767s
user    0m10.117s
sys 0m0.036s

$ cat input.txt
0 3 1
2 4 2
1 2 3
0 4 1
7 3 5

$ cat input.txt  | perl -anE '@a[$F[0]..$F[0]+$F[1]]=($F[2])x$F[1];END{$i[$_]++for@a;$i[$_]&&say"$_ $i[$_]"for 1..$#i}'
1 4
2 1
5 3


$ cat input2.txt
500 1000 1
0 2000 2

$ cat input2.txt  | perl -anE '@a[$F[0]..$F[0]+$F[1]]=($F[2])x$F[1];END{$i[$_]++for@a;$i[$_]&&say"$_ $i[$_]"for 1..$#i}'
2 2000

JavaScript, 183 Zeichen, 1,3 Sekunden

Leider musste ich den stdin / out-Teil der Anforderung ausschneiden, den JavaScript nicht unterstützt. Stattdessen erhalte ich die Eingabe <input>stattdessen von einem Datei-Upload (den ich in meiner Zeichenanzahl nicht zähle, obwohl ich es wahrscheinlich sollte).

Hier ist die ungolfed Version. Es ist eine Funktion, die die vollständige Eingabezeichenfolge übernimmt ... alle 14 MB! Dies dauert 1,3 Sekunden. Die Golfversion dauert etwa doppelt so lange - aber sie schlägt immer noch die anderen Lösungen! Interessanterweise ist es in Firefox doppelt so schnell wie in Chrome. Live-Demo hier .

function Q(input) {

    var c = [];
    var l = input.trim().split(/\s/g);
    input = null
    var length = l.length;

    // Loop through each meter of the wall...
    for (var i = 0; i <= 102400; i++) {

        // ...and loop through each of the friends, finding
        // the last one who painted this meter...
        for (var j = length; j > 0; ) {
            j -= 3;

            // Start = +l[j]
            // Length = +l[j + 1]
            // Color = +l[j + 2]

            var S = +l[j];      
            if (S <= i && +l[j + 1] + S > i) {

                // ...and incrementing the color array.
                var C = +l[j + 2];
                if (!++c[C])
                    c[C] = 1;

                break;
            }
        }
    }

    console.log(c.map(function (a,b) {return b + ' ' + a}).filter(function (a) { return a }).join('\n'));
}

Und hier ist die Golfversion.

function G(i){l=i.trim(c=[]).split(/\s/)
for(i=0;i<102401;i++)for(j=l.length;j>0;)if(l[j-=3]<=i&&i-l[j+1]<l[j]){if(!++c[l[j+2]])c[l[j+2]]=1
break}for(k in c)console.log(k+' '+c[k])}