Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 , 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
share|improve this question
    
Can we take input as an array of 2-tuples? – lirtosiast Jan 27 at 0:35
    
@ThomasKwa No, the input must be a 1-dimensional array. – Doorknob Jan 27 at 0:36
up vote 2 down vote accepted

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>}/
share|improve this answer

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
share|improve this answer

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
}
share|improve this answer

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]);
    }
}
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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