16
\$\begingroup\$

Introduction

This is a log of length 5:

#####

I want to pile a bunch of these logs on top of each other. How I do this is that I slide a new log onto the topmost one from the right, and stop sliding when their left or right ends align (don't ask why). If the new log is longer, it slides all the way to the left end of the topmost log:

########  <-
#####

If it is shorter, it only slides until their right ends align:

  ######  <-
########
#####

As I slide more logs into the pile, their positions are determined by the current topmost log:

           ##
       ######
       ###
      ####
      ##
  ######
########
#####

This looks physically impossible, but let's pretend it works.

The task

Your input shall be a non-empty list of positive integers, representing the lengths of my logs. The leftmost number is the first log I put to the pile, so it ends up at the bottom. In the above example, the input would be [5,8,6,2,4,3,6,2]. Your output shall be, for each column of the resulting pile, the number of logs that cross that column. In the above example, the correct output would be [2,2,3,3,3,2,4,6,3,3,1,2,2].

Rules and scoring

Input and output can be in any reasonable format. The output can only contain positive integers, i.e. it must not have leading or trailing 0s. Normal code-golf rules apply: you can write a full program or a function, the lowest byte count wins, and standard loopholes are forbidden.

Test cases

[1] -> [1]
[4] -> [1,1,1,1]
[3,2] -> [1,2,2]
[2,3] -> [2,2,1]
[2,2,2] -> [3,3]
[2,3,2] -> [2,3,2]
[3,2,3] -> [1,3,3,1]
[1,3,2,2,1,3,1] -> [2,3,5,1,2]
[4,3,4,2,4,3,4,2] -> [1,3,3,5,5,3,4,2]
[5,8,6,2,4,3,6,2] -> [2,2,3,3,3,2,4,6,3,3,1,2,2]
[5,10,15,1,1,1,1,1,2] -> [3,3,3,3,3,2,2,2,2,2,1,1,1,1,7,1]
[13,12,2,10,14,12] -> [1,2,2,2,2,2,2,2,2,2,2,5,5,3,3,3,3,3,3,3,3,2,2,2,2]
[12,14,3,6,13,1,1] -> [2,2,2,2,2,2,2,2,2,2,2,5,4,4,2,2,2,1,1,1,1,1,1,3]
[7,5,12,5,1,10,14,5] -> [1,1,3,3,3,3,3,1,1,2,2,2,2,5,2,2,2,2,2,2,2,2,3,2,2,2,2]
[14,5,1,3,12,6,2,2,1,7,9,15] -> [1,1,1,1,1,1,1,1,1,2,2,2,2,5,2,2,1,1,1,2,2,2,2,4,8,3,3,3,3,3,3,2,2,1,1,1,1,1,1]
\$\endgroup\$
  • 2
    \$\begingroup\$ We can easily "pretend" it works, by just having them all on the ground rather than stacking them up into the air (sliding them next to each other). \$\endgroup\$ – Jonathan Allan Sep 7 '17 at 17:59
  • 1
    \$\begingroup\$ That last test case looks like Norway! \$\endgroup\$ – Stewie Griffin Sep 7 '17 at 19:15
7
\$\begingroup\$

Jelly,  18  16 bytes

-2 bytes prompted by help from miles

Maybe there is a quicker way using mathematics rather than construction like this does?

IN0;»0+\0ẋ;"1ẋ$S

Try it online! or see the test-suite.

How?

IN0;»0+\0ẋ;"1ẋ$S - Link: list of positive integers, logLengths  e.g. [4, 3, 3, 1, 4, 3]
I                - incremental differences                            [-1, 0,-2, 3,-1]
 N               - negate (vectorises)                                [ 1, 0, 2,-3, 1]
  0;             - zero concatenated with that                      [0, 1, 0, 2,-3, 1]
    »0           - maximum (vectorises) of that and zero            [0, 1, 0, 2, 0, 1]
      +\         - cumulative reduce with addition                  [0, 1, 1, 3, 3, 4]
        0ẋ       - zero repeated (vectorises)    [[],[0],[0],[0,0,0],[0,0,0],[0,0,0,0]]
              $  - last two links as a monad (right is implicitly logLengths):
            1ẋ   -   one repeated     [[1,1,1,1],[1,1,1],[1,1,1],[1],[1,1,1,1],[1,1,1]]
           "     - zip with:
          ;      -   concatenation
              [[1,1,1,1],[0,1,1,1],[0,1,1,1],[0,0,0,1],[0,0,0,1,1,1,1],[0,0,0,0,1,1,1]]
              ... this is an upside-down version of the logs like those in the OP
                  with 0 for spaces and 1 for # with any right-hand-side spaces missing.
               S - sum                                           [1, 3, 3, 5, 2, 2, 2]
\$\endgroup\$
  • \$\begingroup\$ We can get to 17 bytes if we combine our solutions: IN»0+\0;;"x@€0,1S \$\endgroup\$ – miles Sep 7 '17 at 18:24
7
\$\begingroup\$

Jelly, 19 13 bytes

IN0»0;+\+"RṬS

Try it online!

Saved 2 bytes thanks to @Jonathan Allan.

Explanation

IN0»0;+\+"RṬS  Input: array A
I              Increments
 N             Negate
  0»           Max with 0
    0;         Prepend 0
      +\       Cumulative sum
        +"     Vectorized add with
          R    Range, vectorizes over each integer
           Ṭ   Create a list with 1's at the specified indices
            S  Sum
\$\endgroup\$
3
\$\begingroup\$

Python 3, 114 109 bytes

Edit: Saved 5 bytes thanks to @Mr.Xcoder

f=lambda x,i=1:x[i:]and x[i]>=x[~-i]and f(x,i+1)or[i]+f([q-(e<i)for e,q in enumerate(x)if(e<i)<q])if x else[]

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Husk, 16 bytes

Fż+Ṡzo`Ṙ↔ḋ2eo∫Ẋ<

Try it online!

Explanation

              Ẋ    For all adjacent pairs, x y
               <   return max(0,x-y)
            o∫     Cumulative sum, with an extra 0 at the start
   Ṡz              Zip the input list and ^ with ...
           e         Make a two element list
        ↔ḋ2          The list [0,1]
     o`Ṙ             Repeat each in ^ by ^^
Fż+               Sum the columns
\$\endgroup\$
1
\$\begingroup\$

Perl 5, 64 + 1 (-a) = 65 bytes

for(@F){$e<$s+--$_?$e=$s+$_:($s=$e-$_);$_++for@r[$s..$e]}say"@r"

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Mathematica, 76 60 58 57 bytes

#2&@@@Tally[l=j=0;##&@@(Range@#+(j+=Ramp[l-(l=#)]))&/@#]&

Try it on Wolfram Sandbox

\$\endgroup\$
0
\$\begingroup\$

Kotlin 1.1, 113 103 bytes

{var l=0
var r=0
it.flatMap{l=maxOf(l,r-it+1)
r=l+it-1
(l..r).toList()}.groupBy{it}.map{it.value.size}}

Beautified

{
    // Current row leftmost value
    var l = 0
    // Current row rightmost value
    var r = 0
    // For each log
    it.flatMap {
        // Work out the new leftmost point
        l = maxOf(
                l,
                r - it+1)
        // Use it to work out the new rightmost point
        r = l + it-1
        // Record the used columns
        (l..r).toList()}
            // Group the column numbers together
            .groupBy { it }
            // Count the amount of times each column is used
            // Put the results into a list
            .map { it.value.size }
}

Test

var z:(List<Int>)->List<Int> =
{var l=0
var r=0
it.flatMap{l=maxOf(l,r-it+1)
r=l+it-1
(l..r).toList()}.groupBy{it}.map{it.value.size}}

fun main(args: Array<String>) {
    println(z(listOf(5, 8, 6, 2, 4, 3, 6, 2)))
    println(listOf(2,2,3,3,3,2,4,6,3,3,1,2,2))
}
\$\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.