15
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Can we take input as an array of 2-tuples? \$\endgroup\$ – lirtosiast Jan 27 '16 at 0:35
  • \$\begingroup\$ @ThomasKwa No, the input must be a 1-dimensional array. \$\endgroup\$ – Doorknob Jan 27 '16 at 0:36
2
\$\begingroup\$

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>}/
\$\endgroup\$
6
\$\begingroup\$

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

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

APL, 79 bytes

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

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

\$\endgroup\$
  • \$\begingroup\$ {⊃{o←⍵↑⍨z←(≢⍵)⌈a←+/⍺⋄e←z↑(-a)↑⍺[1]⍴1⋄o+0⌈o-⍨e×e⌈.+e×o}/⌽(⊂⍬),↓⍵⍴⍨⌽2,.5×≢⍵} (My god, learn to use right) \$\endgroup\$ – Zacharý Jul 31 '17 at 22:06
  • \$\begingroup\$ 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. \$\endgroup\$ – lstefano Aug 2 '17 at 9:39
  • \$\begingroup\$ 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. \$\endgroup\$ – Zacharý Aug 2 '17 at 23:50
  • \$\begingroup\$ They all do. And I've integrated your suggestions, hopefully with proper credits. \$\endgroup\$ – lstefano Aug 3 '17 at 8:48
  • \$\begingroup\$ -- Did you? -- 0.5 \$\endgroup\$ – Zacharý Aug 3 '17 at 10:36
0
\$\begingroup\$

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]);
    }
}
}
\$\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.