Stacking blocks

Question

Given an input of a list of blocks to drop at certain points, output the height of the resulting "tower."

The best way to explain this challenge is by example. The input will be a list of 2n integers representing n blocks. The first integer is the block's x position, 0-indexed, and the second is how wide the block is. For example, an input of 2 4 represents the block (with x coordinates labeled below):

 ####
0123456789

Now, let's say the input is 2 4 4 6. That is, one block at x=2 with a width of 4, and one at x=4 with a width of 6:

 ######
 ####

Note that a.) blocks always "drop" from the very top of the tower and b.) blocks will never "fall over" (i.e. they will always balance). So, an input of 2 4 4 6 12 1 represents:

 ######
 #### #

Note that the final block has fallen all the way to the "ground."

Your final output should be the maximum height of the tower at each x-value up to the largest. Hence, the input 2 4 4 6 12 1 should result in output 0011222222001:

 ######
 #### #
0011222222001

Input may be given as either a whitespace-/comma-separated string, an array of integers, or function/command line arguments. The block positions (x values) will always be integers 0 or greater, the width will always be an integer 1 or greater, and there will always be at least one block.

Output may be given as a single string separated by non-numerical characters (ex. "0, 0, 1, ..."), a single string listing all the digits (ex. "001..."—the maximum height is guaranteed to be 9 or less), or an array of integers.

Since this is code-golf, the shortest code in bytes will win.

Test cases:

In Out
---------------------------------------------------------
2 4 4 6 12 1 0011222222001
0 5 9 1 6 4 2 5 1133333222
0 5 9 1 2 5 6 4 1122223333
0 5 2 5 6 4 9 1 1122223334
20 1 20 1 20 1 00000000000000000003
5 5 000011111
0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 4 123456789999

• lirtosiast: Can we take input as an array of 2-tuples?
• Doorknob: @ThomasKwa No, the input must be a 1-dimensional array.

Answer 1

Python 3, 89

def f(a):
 h=[]
 while a:x,w,*a=a;h[:x+w]=(h+[0]*x)[:x]+[max(h[x:x+w]+[0])+1]*w
 return h

Try it online.

The function takes and returns a list of integers.

def f(a): # input as list of integers
 h=[] # list of heights
 while a: # while there's input left
 x,w,*a=a; # pop first 2 integers as x and w
 h[:x+w]= # change the heights between 0 and x+w
 (h+[0]*x)[:x]+ # left of x -> unchanged but padded with zeros
 [max(h[x:x+w]+[0])+1]*w # between x and x+w -> set to the previous max + 1
 return h # return the list of heights

Answer 2

CJam, (削除) 34 (削除ここまで) 30 bytes

Lq~2/{eeWf%e~_2$:).*:e>f*.e>}/

Input as a CJam-style array, output as a string of digits.

Run all test cases.

Here are two variants of another idea, but it's currently 2 bytes longer:

Lq~2/{_:3円$><0+:e>)aeez.*e_.e>}/
LQ~2/{_:3円$><0+:e>)aeez.+e~.e>}/

Answer 3

Ruby, (削除) 88 (削除ここまで) 87 bytes

f=->i{o=[]
(s,l,*i=i
r=s...s+l
o[r]=[([*o[r]]+[0]).max+1]*l
o.map! &:to_i)while i[0]
o}

Try it online.

Inspired by grc's answer, but in a different language and just slightly shorter.

Explanation:

f=->i # lambda with parameter i, expects array of ints
{
 o=[] # output
 (
 s,l,*i=i # pop start and length
 r = s...s+l # range is used twice, so shorten it to 1 char
 o[r] =
 [(
 [*o[r]] # o[r] returns nil if out of bounds, so splat it into another array
 +[0] # max doesn't like an empty array, so give it at least a 0
 ).max+1]*l # repeat max+1 to fill length
 o.map! &:to_i # replace nil values with 0
 ) while i[0] # i[0] returns nil when i is empty, which is falsy
 o # return o
}

Answer 4

APL, 79 bytes

{⊃{o←(z←(≢⍵)⌈a←+/⍺)↑⍵⋄e←(z↑(-a)↑⍺[1]⍴1)⋄o+0⌈o-⍨e×ばつe⌈.+e×ばつo}/⌽(⊂⍬),↓(×ばつ≢⍵)⍴⍵}

Input as an APL Array, output as an APL array of digits.

• Adalynn: {⊃{o←⍵↑⍨z←(≢⍵)⌈a←+/⍺⋄e←z↑(-a)↑⍺[1]⍴1⋄o+0⌈o-⍨e×e⌈.+e×o}/⌽(⊂⍬),↓⍵⍴⍨⌽2,.5×≢⍵} (My god, learn to use ⍨ right)
• lstefano: Please, be careful with your words... You don't seem to know the difference between ⊃ and 1↑ and because of this you give suggestions that cause the updated program to give the wrong result but I don't patronise you.
• Adalynn: Yeah, I get like that sometimes when I see a bunch of things able to be golfed. But the other golfs should still apply, though.
• lstefano: They all do. And I've integrated your suggestions, hopefully with proper credits.
• Adalynn: -- Did you? -- 0.5

Answer 5

Java 1.8, (削除) 351 (削除ここまで) 329 bytes

Not thrilled with this first attempt - I'm sure the double looping, and all those Integer.valueOf's can be golfed some more.

interface B{static void main(String[]x){Byte b=1;int i=0,s,c,m=0,h,a=x.length,t[];for(;i<a;){s=b.valueOf(x[i++]);c=b.valueOf(x[i++]);m=m>s+c?m:s+c;}t=new int[m];for(i=0;i<a;){h=0;s=b.valueOf(x[i++]);c=b.valueOf(x[i++]);for(m=s;m<s+c;m++)if(t[m]>=h)h=t[m]+1;for(m=s;m<s+c;)t[m++]=h;}for(i=0;i<t.length;)System.out.print(t[i++]);}}

Ungolfed

interface B {
static void main(String[]x){
 int start, count, maxWidth=0, height, args=x.length, totals[];
 Byte b=1;
 for (int i=0; i<args;){
 start = b.valueOf(x[i++]);
 count = b.valueOf(x[i++]);
 maxWidth = maxWidth>start+count ? maxWidth : start+count; 
 }
 totals=new int[maxWidth];
 for (int i=0; i<args;){
 height=0;
 start = b.valueOf(x[i++]);
 count = b.valueOf(x[i++]);
 for (int j = start; j<start+count; j++) {
 if (totals[j]>=height) {
 height=totals[j]+1;
 }
 }
 for (int j = start; j<start+count; j++) {
 totals[j] = height;
 }
 }
 for (int i=0;i<totals.length; i++){
 System.out.print(totals[i]);
 }
}
}