8
\$\begingroup\$

This challenge was originally posted on codidact.


At my job we have to sometimes lay out materials. Materials come in large long rolls and are cut into smaller pieces when being laid out.

When we order the rolls we draw up a layout document which describes how we are going to cut them and layout the pieces. This tells the manufacturer how we are going to use the rolls so they can make all the right adjustments. We then use the document when actually laying the materials out.

In reality these documents are very complex and include a lot of information, however for this challenge I will simplify them. We will say pieces are placed in a 1-dimensional list with no gaps. The document indicates which pieces come from which rolls and the order in which they are cut.The document uses color to indicate which roll each piece comes from and numbers them in order. However sometimes things don't get printed in color, or colors get smudged. But usually you can still figure out which pieces come from which rolls based on the numbers alone, since there are some constraints on how things can be placed.

Here are the two constraints:

  1. We lay out pieces from the same roll in order, so 1 is the first piece to be laid out, then 2 etc.
  2. If the piece number is greater than 1 it must be placed adjacent to another piece from the same roll.

So if we look at the following layout:

1,2,1,3

We can see that there are two rolls, since there are two 1s. We can also see that one of the rolls has 3 pieces since there is a piece labeled 3. The 3 is next to a 1, so they must come from the same roll, thus the pieces come from the following rolls:

[1,2,1,3]
[0,1,1,1]

In this challenge you are going to write a program which determines the color information based on a colorless layout.

Task

Take as input a list of positive integers representing a layout. Each integer is a piece number. Output a lists of integers representing the possible colorings of the layout.

Each coloring should be a list of integers with the same length as the input such that iff the pieces at two indices are from the same roll the same integer is at those indices in the coloring.

If there is no way to color the layout, output an empty list, if it is ambiguous output all the possible colorings.

If there is no layout just output an empty list.

This is code-golf, so the goal is to minimize the size of your source code as measured in bytes.

Test cases

The output does not have to exactly match the ones given here, the possibilities can be given in any order, and the rolls can be assigned different numbers, so long as each roll is assigned a different number.

[1,2,1] -> [[0,0,1], [0,1,1]]
[2,1,3,2,1] -> [[0,0,0,1,1], [0,0,1,1,1]]
[1,2,1,2,1] -> [[0,0,1,1,2], [0,0,1,2,2], [0,1,1,2,2]]
[1,6] -> []
[4,2,3,1] -> []
[1] -> [[0]]
[1,2,3,4] -> [[0,0,0,0]]
[4,3,1,2] -> [[0,0,0,0]]
[3,1,2,4] -> [[0,0,0,0]]
[1,2,1,3] -> [[0,1,1,1]]
[1,2,3,1] -> [[0,0,0,1]]
[1,2,2,1] -> [[0,0,1,1]]
\$\endgroup\$
13
  • \$\begingroup\$ Is alternative color valid output? \$\endgroup\$
    – l4m2
    Commented Aug 7, 2023 at 16:23
  • \$\begingroup\$ Might it be clearer to say “cut from” rather than “laid out”? My assumption is the point is that each piece is extracted with a single cut and that pieces are extracted in order. Maybe [2,1,3] -> [] is a good example if I’ve understood correctly. \$\endgroup\$
    – doug
    Commented Aug 8, 2023 at 6:01
  • \$\begingroup\$ Perhaps I’m not understanding correctly. \$\endgroup\$
    – doug
    Commented Aug 8, 2023 at 11:23
  • \$\begingroup\$ @doug I'm not sure how you are understanding. [2,1,3] should give [0,0,0] or such. \$\endgroup\$
    – Wheat Wizard
    Commented Aug 8, 2023 at 17:42
  • \$\begingroup\$ can the output be off by one - 1,1,2,2,3 instead of 0,0,1,1,2? \$\endgroup\$
    – ngn
    Commented Aug 8, 2023 at 19:10

11 Answers 11

4
\$\begingroup\$

Jelly, 18 bytes

ŒṖtL$ƬL>LƲƇƑƇJxẈƊ€

A monadic Link that accepts a layout as a list of positive integers and yields all possible colourings using a prefix of the positive integers.

Try it online!

How?

ŒṖtL$ƬL>LƲƇƑƇJxẈƊ€ - Link: list of positive integers, Layout
ŒṖ                 - all partitions of {Layout}
            Ƈ      - keep those {patitions} for which:
           Ƒ       -   {partition} is invariant under?:
          Ƈ        -     keep those {parts} for which:
         Ʋ         -       last four links as a monad:
     Ƭ             -         collect while distinct under:
    $              -           last two links as a monad:
   L               -             length
  t                -             trim all occurrences of {that} from both ends
      L            -         length of {that list of collected, trimmed parts}
        L          -         length {part}
       >           -         {collected count} greater than? {part length}
                 € - for each {valid partition}:
                Ɗ  -   last three links as a monad:
             J     -     indices {partition}
               Ẉ   -     length of each {partition}
              x    -     {indices} times {lengths}
\$\endgroup\$
4
\$\begingroup\$

JavaScript (Node.js), 107 bytes

f=([v,...a],L=[],k=0,G,h)=>v?1&(h<v^G/2|G>>v)?'':f(a,L=[...L,k],k,G|=1<<v,v)+f(a,L,1+k,G&G+2&&1):G?'':L+`
`

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Pyth, 31 bytes

ms.e.ekbdf.Am&SI._M.+dqSldSdT./

Try it online!

Explanation

ms.e.ekbdf.Am&SI._M.+dqSldSdT./Q    # implicitly add Q
                                    # implicitly assign Q=eval(input())
                             ./Q    # list all partitions of Q
         f                          # filter these partitions on lambda T
          .A                        #   check if all are truthy
            m               T       #   T mapped over lambda d
                   .+d              #     the deltas of d
                ._M                 #     mapped to their signs
              SI                    #     is invariant under sorting
             &                      #     and
                          Sd        #     sorted(d)
                      q             #     equals
                       Sld          #     range(1,len(d)+1)
m                                   # map the remaining valid partitions over lambda d
 s                                  #   flatten
  .e.ekbd                           #   convert each element of each partition part to its index in the partition
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 168 bytes

Returns a string, using commas and linefeeds as separators.

f=([v,...a],p=[],c=p,b=[...p,c])=>v?f(a,p,[...c,v])+(c+c&&f(a,b,[v])):b.some(c=>c.some(d=m=p=v=>m==(m|=1<<v)|d^p<(d^=v<2,p=v))|m+1&m+2)?"":b.map((c,i)=>c.map(_=>i))+`
`

Try it online!

Commented

Recursive part

We build all partitions of the input array a[].

f = (                  // f is a recursive function taking:
  [ v,                 // v = next piece number
       ...a ],         // a[] = array of remaining values
  p = [],              // p[] = current partition
  c = p,               // c[] = current piece cluster
  b = [...p, c]        // b[] = copy of p[] with c[] added
) =>                   //
v ?                    // if v is defined:
  f(a, p, [...c, v]) + //   do a recursive call with v added to c[]
  (                    //
    c + c &&           //   if c[] is not empty,
    f(a, b, [v])       //   do another recursive call with p[] = b[]
  )                    //   and c[] = [ v ]
:                      // else:
  ...                  //   final test (see below)

Final test

We test whether the partition b[] is valid.

b.some(c =>            // for each cluster c[] in b[]:
  c.some(d = m = p =   //   initialize d, m and p to NaN'ish values
  v =>                 //   for each value v in c[]:
    m == (m |= 1 << v) //     set the bit at index v in m and make sure
                       //     that m is modified by doing so
    | d ^ p < (        //     make sure that p and v are in the expected
      d ^= v < 2,      //     order, update p to v
      p = v            //     and update the direction if v = 1
    )                  //
  )                    //   end of inner some()
  | m + 1 & m + 2      //   make sure that m consists of a sequence of
                       //   consecutive bits set to 1, followed by a
                       //   trailing 0
)                      // end of outer some()
?                      // if it failed:
  ""                   //   append nothing
:                      // else:
  b.map((c, i) =>      //   turn each value in each cluster c[] in b[]
    c.map(_ => i)      //   into a roll number
  ) +                  //   implicit coercion to a string
  `\n`                 //   append a linefeed
\$\endgroup\$
2
\$\begingroup\$

Python3, 772 bytes:

E=enumerate
def f(l,I=[],r=[]):
 if len(I)==len(l):yield r;return
 for i,a in E(l):
  if a==1 and i not in I:
   j,k,Q,W=i,i,[],[]
   while(j:=j-1)>=0 and j not in I and l[j]!=1 and(Q==[]or Q[-1][0]<l[j]):Q+=[(l[j],j)]
   while(k:=k+1)<len(l)and k not in I and l[k]!=1 and(W==[]or W[-1][0]<l[k]):W+=[(l[k],k)]
   R=range(max(len(Q),len(W)))
   for x in R:
    for y in R:
     u=[Q[:x+1],W[:y+1]]
     for o,V in E(u):
      if V and V[0][0]==2:
       M=V+u[not o]
       if len(S:=[X for X,_ in M])==len({*S}):
        yield from f(l,I+[j for _,j in M]+[i],r+[M+[(a,i)]])
   yield from f(l,I+[i],r+[[(1,i)]])
def F(l):
 R=[]
 B={str(sorted(j))for j in f(l)}
 for i in map(eval,B):
  v=[-1]*len(l)
  for P,j in E(i):
   for _,I in j:v[I]=P
  R+=[v]
 return{*map(tuple,R)}

Try it online!

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

Python 3.8, 230 bytes

r=range
p=lambda l:[[l]]+[q+[l[n:]]for n in r(1,len(l))for q in p(l[:n])]
f=lambda Q:[[k for k,g in enumerate(q)for h in g]for q in p(Q)if all(sorted(d:=[0<s[i+1]-s[i]for i in r(len(s)-1)])==d and{*s}=={*r(1,len(s)+1)}for s in q)]

Try it online!

Essentially a port of my Pyth answer.

\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 66 bytes

thanks @doug for drawing my attention to this interesting challenge

{(,^x)(,/{@[y;z;:;]'(((x=1+/y=)')#y@-1 1+z;,1+|/y)1=x@:z}[x]')/<x}

Try it online!

The results are off by one compared to the examples (this is allowed).

\$\endgroup\$
1
  • \$\begingroup\$ IMHO, this is the "correct" answer to this problem. My own post not withstanding. ;) \$\endgroup\$
    – doug
    Commented Aug 25, 2023 at 10:11
1
\$\begingroup\$

Charcoal, 77 bytes

⊞υ⟦…θ¹⟧FΦθκ«≔⟦⟧ηFυ«⊞η⁺κ⟦⟦ι⟧⟧≔⊟κζ¿⁼№ζ¹›ι↨ζ⁰⊞η⁺κ⟦⁺ζ⟦ι⟧⟧»≔ηυ»EΦυ⬤ι⬤λ№λ⊕ξ⭆¹ΣEιEνξ

Attempt This Online! Link is to verbose version of code. Explanation:

⊞υ⟦…θ¹⟧

Start with a partition of just the first piece in a roll.

FΦθκ«

Loop over the remaining pieces.

≔⟦⟧η

Collect new potential partitions.

Fυ«

Loop over the current partitions.

⊞η⁺κ⟦⟦ι⟧⟧

Maybe this piece starts a new roll.

≔⊟κζ

Remove the last roll.

¿⁼№ζ¹›ι↨ζ⁰

If this piece could be part of the last roll...

⊞η⁺κ⟦⁺ζ⟦ι⟧⟧

... add that as an alternative.

»≔ηυ

Save the potential partitions for the next pass.

»EΦυ⬤ι⬤λ№λ⊕ξ⭆¹ΣEιEνξ

Output only those partitions whose rolls all contain all of the values from 1 up to their length, mapping each value to the roll index and flattening.

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 29 bytes

.œʒε1š1¡`R‚εD{Q}`y{āQP}P}εĀƶ˜

Port of @CursorCoercer's Pyth answer.

1-based output.

Try it online or verify all test cases.

Explanation:

.œ              # Get all partitions of the (implicit) input-list
  ʒ             # Filter it by:
   ε            #  Map over each part of the current partition:
    1š          #   Prepend a 1 to the part
      1¡        #   Then split the part on 1s
        `       #   Pop and push all split-parts separated to the stack
         R      #   Reverse the top/last split-part
          ‚     #   Pair it back together with the list before it)
           ε    #   Map over this pair of lists:
            D{Q #    Check if the list is sorted from lowest to highest:
            D   #     Duplicate the list
             {  #     Sort the copy
              Q #     Pop both lists, and check if they're equal
           }`   #   After the map: pop and push the two checks to the stack again
    y           #   Push the current part-list again
     {          #   Sort it from lowest to highest
      ā         #   Push a list in the range [1,length] (without popping the list)
       Q        #   Check if the two lists are the same
             P  #   Get the product of all values on the stack to see if this part is
                #   truthy
   }P           #  After the inner map: check if all parts of this partition were truthy
  }ε            # After the filter: map over the remaining partitions:
    Ā           #  Convert each character to a 1 (with an !=0 check)
     ƶ          #  Convert each inner value by its 1-based list-index
      ˜         #  Flatten this partition of indices to a single list
                # (after which the list of lists of (1-based) indices is output
                # implicitly as result)
\$\endgroup\$
1
\$\begingroup\$

Perl 5, 183 bytes

sub f{my@a;(join'',map chr,@_)=~m~^((.+)(?(?{$_=$2;$i=s/\x1/\0/;1while$c=chr++$i,s/\x00\Q$c\E|\Q$c\E\0/\0/;/[^\0]/||!(local@b=(@b,(1+$b[-1])x--$i))})(*F)))+\z(?{push@a,\@b})(*F)~s;@a}

Try it online!

With newlines for readability:

sub f{
my@a;
(join'',map chr,@_)=~
m~^((.+)(?(?{
$_=$2;
$i=s/\x1/\0/;
1while$c=chr++$i,s/\x00\Q$c\E|\Q$c\E\0/\0/;
/[^\0]/||!(local@b=(@b,(1+$b[-1])x--$i))
})(*F)))+\z(?{
push@a,\@b
})(*F)~s;
@a
}

Regexen as solution to any problem, but this one turned out somewhat long, therefore just for sake of completeness. Kind of seed-fill problem in 1-D. Last minute improvement was to number rolls from 1, per recent comment to OP. Otherwise (to number from 0) it was plus a few bytes.

\$\endgroup\$
1
\$\begingroup\$

K (ngn/k), 184136 bytes

(),&'*+(?,/{$[#*y:,/-1 1,/:'&'&/'(x:(x;y))=/:{|'y}\(0,/:-1_')'1|:'\(x+1;~y)
  {(@[;+/y;+;1]'x)_\:*|y}[x]'y
  &/*|x;,x;()]}.')/,1(1=)\(),

Try it online!

A beast! First, turn input into a single list of a list of singletons. This forms the initial list of partitions. Recursively search all such lists for indices which contain a singleton with value > 1 and whose neighbor to the right or left has a maximum value 1 less than the value of the singleton and either have length > 1 or have length 1 and a value equal to 1. Merge each such singleton with each such neighbor to form the next set of partitions.

[EDIT: same idea but only keep the length and the highest value of each sequence. These are always the same except for singletons with value > 1. I.e. those values waiting to be merged.]

\$\endgroup\$
1
  • \$\begingroup\$ The “prototypes” in ngn/k each represent an empty list. Here I’ve spent a few characters unifying them to (). Not sure what the convention is here but this looked prettiest. \$\endgroup\$
    – doug
    Commented Aug 8, 2023 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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