9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Matthew Read Jul 5 '11 at 14:05
  • \$\begingroup\$ 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. \$\endgroup\$ – Alexandru Jul 5 '11 at 14:37
  • \$\begingroup\$ Ah, I missed that the input was a million lines, my bad. \$\endgroup\$ – Matthew Read Jul 5 '11 at 14:58
  • 1
    \$\begingroup\$ @Keith: ITYM Imperial Units: en.wikipedia.org/wiki/Imperial_units \$\endgroup\$ – Paul R Jul 5 '11 at 18:32
  • 1
    \$\begingroup\$ Keith: I think you can assume that a Tom Sawyer today would be much more sensible and use SI. \$\endgroup\$ – Joey Jul 5 '11 at 23:15
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ you can use G+=[(a,min(b,s),d)]*(a<s) etc. to get the for loop on one line \$\endgroup\$ – gnibbler Jul 8 '11 at 4:58
  • \$\begingroup\$ 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. \$\endgroup\$ – user2186 Jul 16 '11 at 22:53
  • \$\begingroup\$ @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... \$\endgroup\$ – Keith Randall Jul 17 '11 at 3:36
  • \$\begingroup\$ You're right: it would need to be sorted(set(...)) which is no longer an improvement. \$\endgroup\$ – user2186 Jul 18 '11 at 13:52
1
\$\begingroup\$

Haskell, 251 261 269 294 characters

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

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
\$\endgroup\$
  • \$\begingroup\$ It is too slow. \$\endgroup\$ – Alexandru Jul 14 '11 at 7:12
  • \$\begingroup\$ 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! \$\endgroup\$ – MtnViewMark Jul 15 '11 at 4:21
  • \$\begingroup\$ 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. \$\endgroup\$ – Alexandru Jul 15 '11 at 17:24
  • \$\begingroup\$ 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.) \$\endgroup\$ – MtnViewMark Jul 17 '11 at 17:00
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$
$ 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
\$\endgroup\$
0
\$\begingroup\$

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

screenshot

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.