# Paint that fence

You are Tom Sawyer and you have to paint a fence of 102400 m long. Luckily, your friends decided to help you in exchange of various things. Each friend will paint L meters, starting from S with color C. S, L are integer amount of meters and 1 ≤ C ≤ 97. Getting bored you decide to find out how many meters of each color you have.

Input

Input is read from standard input. Each line contains three numbers S, L, C as described above.

Ouput

Output is written to standard output. For each color that appears on the final fence print the color number and the number of times it appears. Order by colors.

Examples

Input 0

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


Output 0

1 4
2 2
5 3


Input 1

 0 100 1
50 150 2


Output 1

 1 50
2 150


Input 2

 500 1000 1
0 2000 2


Output 2

 2 2000


More examples

Here is a small 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;
}


Running examples:

$./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  Your program must run in reasonable time. My solution runs in a few seconds on the last example. Shortest code wins. Include running time and your output for the last test. EDIT: This problem is not intended to be brute-forced, so a trivial solution is not acceptable. • Seems to me that the simplest way (allocate array, fill it, count # of each color in array, output) would run in a reasonable time. It seems like you intended coming up with an algorithm to be part of the challenge, though -- am I wrong? – Matthew Read Jul 5 '11 at 14:05 • I was thinking that 1000000 ops X 25000 average length = 25 * 10 ^ 9 would not run in reasonable time. I can increase the fence length if you think otherwise. – Alexandru Jul 5 '11 at 14:37 • Ah, I missed that the input was a million lines, my bad. – Matthew Read Jul 5 '11 at 14:58 • @Keith: ITYM Imperial Units: en.wikipedia.org/wiki/Imperial_units – Paul R Jul 5 '11 at 18:32 • Keith: I think you can assume that a Tom Sawyer today would be much more sensible and use SI. – Joey Jul 5 '11 at 23:15 ## 5 Answers ## Python, 221 239 chars 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]  Keeps F as an unordered list of triples (start of run, end of run, color) representing the current state of the fence. Since the random painting in the generator overpaints larges swathes fairly frequently, this list is never too long (typically in the 15-40 range). Runs in 37 seconds on the 1M example. • you can use G+=[(a,min(b,s),d)]*(a<s) etc. to get the for loop on one line – gnibbler Jul 8 '11 at 4:58 • for C in sorted(f[2] for f in F):print C,sum(b-a for a,b,c in F if c==C) saves a couple of characters over your last four lines, and avoids the need to know the magic number 98. – user2186 Jul 16 '11 at 22:53 • @Gareth: I think that would print duplicates if the same color was used by more than one range. There would need to be uniqification in there somewhere... – Keith Randall Jul 17 '11 at 3:36 • You're right: it would need to be sorted(set(...)) which is no longer an improvement. – user2186 Jul 18 '11 at 13:52 ## Haskell, 251 261269294 characters import Data.List w@(y@(f,d,e):z)§x@[a,b,c]|e<=d=z§x|a+b>d=(f,d,emina):((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


Something isn't quite right about this as it takes far too much time and stack... But it does produce the right answers:

$> 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


• Edit (294 → 269) replicate and group is just as efficient way of counting up the paint, and takes less code than the custom function s
• Edit (269 → 261) no need for max call
• Edit (261 → 251) no need for to cull paint 0 in f
• It is too slow. – Alexandru Jul 14 '11 at 7:12
• It's code-golf, no? For code-golf, usually restrictions like "reasonable time" mean, that for the target input size, it can't take days. Is there some criteria whereby 37 seconds (the other answer's time) is okay, but 44 seconds is too slow? I could just time mine on a faster CPU if you'd like! – MtnViewMark Jul 15 '11 at 4:21
• In this case it should take a few seconds * language slowdown. Correct me if I'm wrong, but isn't Haskell much faster than Python? (which is why I didn't down vote Keith's solution). There was a C brute force solution posted that took around the same time which, by the rules, was not permitted. – Alexandru Jul 15 '11 at 17:24
• Measured on the same machine, it does run much faster than the Python solution. The Python solution takes 133.556 seconds on my machine. The Haskell solution is 3x faster. Also, note that this Haskell solution isn't a "brute force" solution (by which I'm guessing you mean simply building an array of colors the length of the wall.) – MtnViewMark Jul 17 '11 at 17:00

## Perl - 148 bytes

It seems that Perl is the best to play with. easy to code shorter and faster. ;)

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  time: 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 chars, 1.3 seconds

Sadly, I did have to cut the stdin/out part of the requirement, which JavaScript doesn't support. Instead, I get the input from a file upload <input> instead (which I don't count in my char count, although I probably should).

Here is the ungolfed version. It's a function that takes the full input string... all 14MB of it! This is the one that takes 1.3 seconds; the golfed version takes about twice as long -- but it still beats the other solutions! Interestingly, it's twice as fast in Firefox than in Chrome. Live demo here.

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'));
}


And here's the golfed version.

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])}