Advent Challenge 6: Transport Dock Relabeling!

Question

<< Prev Next >>

Thanks to the PPCG community, Santa managed to sort his presents into the correct order for moving into the transportation dock. Unfortunately, the transportation dock signs are broken so he doesn't know where to put all the presents! The presents are all grouped together and not by their ranges, which Santa admits would have been a better idea.

Now, given the presents in the sorted order, determine all possible minimal range configurations that would result in the present being in the correct order. That is, find all minimal range configurations such that sorting the presents according to the algorithm in Challenge #5 would not change the order.

Challenge

A minimal range configuration is a list of ranges such that the ranges are each as small as possible. That is, if a range is designated to cover a specific subset of presents, then the minimum and maximum of the range must be the same as that of the subset. In other words, shrinking any range in the cover would cause it to no longer be a cover.

The challenge is to find all possible minimal range configurations that would apply to the present sizes. Let's take an example: [3, 1, 2, 5, 4, 7, 6]

There is a trivial case, which is to take the range of the entire present configuration. In this case, [[1, 7]] would be a solution.

For examples with unique elements, another trivial case would be [[3], [1], [2], [5], [4], [7], [6]] (because the ranges don't need to be ordered).

For this example, we also see that [[1, 3], [4, 7]] and [[1, 3], [4, 5], [6, 7]] would work, as well as [[1, 3], [5], [4], [6, 7]] and [[1, 3], [4, 5], [7], [6]].

The final answer for [3, 1, 2, 5, 4, 7, 6] would be [[[3], [1], [2], [5], [4], [7], [6]], [[3], [1], [2], [5], [4], [6, 7]], [[3], [1], [2], [4, 5], [7], [6]], [[3], [1], [2], [4, 5], [6, 7]], [[3], [1], [2], [4, 7]], [[3], [1, 2], [5], [4], [7], [6]], [[3], [1, 2], [5], [4], [6, 7]], [[3], [1, 2], [4, 5], [7], [6]], [[3], [1, 2], [4, 5], [6, 7]], [[3], [1, 2], [4, 7]], [[1, 3], [5], [4], [7], [6]], [[1, 3], [5], [4], [6, 7]], [[1, 3], [4, 5], [7], [6]], [[1, 3], [4, 5], [6, 7]], [[1, 3], [4, 7]], [[1, 5], [7], [6]], [[1, 5], [6, 7]], [[1, 7]]].

Formatting Specifications

The input will be given as a flat list of positive integers within your language's reasonable supported number range in any reasonable format. The input may contain duplicate elements. The output should be given as a 3D list of positive integers in any reasonable format.

Each range in your output (which is at the second layer) can be represented either as [min, max], [num] if it's a single-value range, or as the entire range itself, but your output format must be consistent. Please specify if you wish to use a slightly different reasonable output format.

Duplicate values must be covered by a single range in the output; that is, no two ranges in the output may have any overlap.

Your solution may return the ranges in any order and this does not have to be deterministic.

Rules

• Standard Loopholes Apply
• This is code-golf so the shortest answer in bytes wins
• No answer will be accepted

Test Case for a list with duplicate elements:

2 3 2 4 -> [[[2, 3], [4]], [[2, 4]]]

Reference Implementation

The header is the link.

^{Note: I drew inspiration for this challenge series from Advent Of Code. I have no affiliation with this site}

You can see a list of all challenges in the series by looking at the 'Linked' section of the first challenge here.

Happy golfing!

Answer 1

Mathematica, 106 bytes

sSelect[MinMax/@s~TakeList~#&/@Join@@Permutations/@IntegerPartitions@Tr[1^s],Unequal@@Join@@Range@@@#&]

Try it online!

Martin saved 16 bytes

Answer 2

Brachylog, 17 16 bytes

{~c⟨⌋⟦₂⌉⟩ᵐ.c≠∧}ᶠ

Works on lists with duplicates as well. Ranges are represented by the lists of elements they contain. Try it online!

Explanation

The idea is to break the list into blocks and transform the blocks into ranges, then verify that they don't overlap.

{~c⟨⌋⟦₂⌉⟩ᵐ.c≠∧}ᶠ  Input is a list.
{             }ᶠ  Compute all possible outputs for this predicate:
 ~c                Break the list into contiguous blocks.
   ⟨    ⟩ᵐ         For each block,
    ⌋  ⌉           take its minimum and maximum,
     ⟦₂            and create the range between them.
          .        This is the output.
           c       Also, if you concatenate the output,
            ≠      its elements are distinct.
             ∧     Prevent the interpreter from thinking this is also the output.

Answer 3

JavaScript (ES6), 166 164 bytes

Edit: updated version that now supports duplicates

Prints the results directly to the console in [min, max] format.

f=(a,r=[],l=0)=>a[l++]?f([...a],r,l,f(a,[...r,[Math.min(...x=a.splice(0,l)),Math.max(...x)]])):a[0]|r.some(([x,y],i)=>r.some(([z])=>i--&&z>=x&z<=y))||console.log(r)

Test cases

f=(a,r=[],l=0)=>a[l++]?f([...a],r,l,f(a,[...r,[Math.min(...x=a.splice(0,l)),Math.max(...x)]])):a[0]|r.some(([x,y],i)=>r.some(([z])=>i--&&z>=x&z<=y))||console.log(r)

consoleLog = console.log;
console.log = s => consoleLog(JSON.stringify(s))

consoleLog('Test case: [3, 1, 2, 5, 4, 7, 6]')
f([3, 1, 2, 5, 4, 7, 6])
consoleLog('Test case: [2, 3, 2, 4]')
f([2, 3, 2, 4])

Answer 4

Pyth, 17 bytes

f{IsTmm}hSkeSkd./

Try it here!

Now that's much better. Outputs the whole ranges. See the revision history for the previous version (at a staggering 31 bytes).

How it works

f{IsTmm}hSkeSkd./  ~> Full program.

               ./  ~> List partition.
     m             ~> Map using a variable d.
      m       d    ~> Map over d using a variable k.
        hSk        ~> The minimum of k.
           eSk     ~> The maximum of k.
       }           ~> Inclusive integer range.
f                  ~> Filter those...
   sT              ~> Which, when flattened,
 {I                ~> Are invariant over deduplication.

Answer 5

Python 2, 179 bytes

lambda l:[l for l in[[range(min(x),max(x)+1)for x in P]for P in p(l)]if len(sum(l,[]))==len(set(sum(l,[])))]
p=lambda l:[[l[:i]]+a for i in range(1,len(l))for a in p(l[i:])]+[[l]]

Try it online!

Outputs a list of full ranges.

Heavily inspired by the reference implementation.

Builds all partitions, then ranges of min/max for each partition. A list of ranges is valid if no value appears more than once in the list.

---

sum(l,[]) flattens a list of lists, and allows me to check for duplicates:

l=[[1, 2], [2, 3]]
sum(l,[]) = [1,2,2,3]
len([1,2,2,3] == len(set([1,2,2,3]))  -> False (duplicates)