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]]

posted 9 months ago

CC BY-SA 4.0

WheatWizard‭

469 reputation 16 5 46 26