9
\$\begingroup\$

<< Prev Next >>

Thanks to the PPCG community, Santa has managed to remanufacture all of his presents and after the assembly line, the presents are now ready to be moved into the transport docks!

Each of Santa's transport docks only holds a range of present sizes because the transport sleighs are specialized for a specific size (any lighter and it would be wasteful, any heavier and the sleigh wouldn't be able to handle the load). Thus, he needs you to help him take his presents and sort them into the correct transport docks.

Challenge

Given a list and the transport dock ranges, stably organize the presents into the correct order.

Let's take this for example: the presents are [5, 3, 8, 6, 2, 7] and the dock ranges are [[1, 5] and [6, 10]].

The presents 5, 3, and 2 go into the first dock and the presents 8, 6, and 7 go into the second dock. This can be shown as [[5, 3, 2], [8, 6, 7]]. This list will be closer to being sorted than the input, but stably means that within each dock, the order of the presents must be the same as the order of the input (otherwise you could just sort the entire list).

Your final output for this case would be [5, 3, 2, 8, 6, 7] (as a flat list).

Formatting Specifications

You will be given input as a flat list of integers and a list of ranges in any reasonable format (for example, the range for the above case could be given as [[1, 5], [6, 10]], [1, 5, 6, 10], or [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]]). Your output should be a flat list of integers in any reasonable format.

The input can contain duplicate values; in this case, you need to return all instances of them. All present sizes will be in exactly one size range, and you can assume that the ranges will never overlap. There can be gaps in the ranges as long as all present sizes are covered.

Rules

  • Standard Loopholes Apply
  • This is , so the shortest answer in bytes wins
  • No answer will be accepted
  • You can assume that there will be no empty ranges ([7, 4] would be invalid because ranges go up)

Test Cases

[1, 2, 3, 4, 5, 6, 7] ; [[1, 3], [4, 7]] => [1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7] ; [[4, 7], [1, 3]] => [4, 5, 6, 7, 1, 2, 3]
[7, 3, 5, 4, 6, 1, 2] ; [[1, 3], [4, 5], [6, 7]] => [3, 1, 2, 5, 4, 7, 6]
[4, 7, 6, 3, 5, 2, 1] ; [[1, 4], [5, 7]] => [4, 3, 2, 1, 7, 6, 5]
[1, 1, 3, 3, 6, 4, 7] ; [[1, 4], [6, 7]] => [1, 1, 3, 3, 4, 6, 7]

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.

\$\endgroup\$
  • \$\begingroup\$ Always just 2 docks? \$\endgroup\$ – LiefdeWen Dec 5 '17 at 14:54
  • \$\begingroup\$ Can the ranges overlap? \$\endgroup\$ – RamenChef Dec 5 '17 at 14:54
  • \$\begingroup\$ @LiefdeWen See the 3rd test case. \$\endgroup\$ – Mr. Xcoder Dec 5 '17 at 14:58
  • \$\begingroup\$ Will the docks pairs always be {small,big} \$\endgroup\$ – LiefdeWen Dec 5 '17 at 15:08
  • \$\begingroup\$ @RamenChef No.. \$\endgroup\$ – HyperNeutrino Dec 5 '17 at 15:25

23 Answers 23

5
\$\begingroup\$

Haskell, 26 bytes

a#s=[x|r<-s,x<-a,elem x r]

Try it online! Example usage: [1,2,3,4,5,6,7] # [[1,2,3],[4,5,6,7]] yields [1,2,3,4,5,6,7].

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

Jelly, 4 bytes

fЀẎ

Try it online!

Takes input as present list, full ranges.

\$\endgroup\$
  • \$\begingroup\$ yaay that's the jelly solution I expected :DDD \$\endgroup\$ – HyperNeutrino Dec 5 '17 at 15:27
  • \$\begingroup\$ @HyperNeutrino Hehe the expected solution turns out not to be the shortest. By finding the way 05ab1e's outer product works, I figured that fþF works in Jelly too, for 3 bytes. Credit goes to Adnan. \$\endgroup\$ – Mr. Xcoder Dec 5 '17 at 18:12
  • \$\begingroup\$ @Mr.Xcoder Either you or Adnan should post that. \$\endgroup\$ – Erik the Outgolfer Dec 5 '17 at 18:17
  • \$\begingroup\$ @Mr.Xcoder I'll wait a bit and see :P but it looks considerably different, if I end up posting it, I will post another answer. \$\endgroup\$ – Erik the Outgolfer Dec 5 '17 at 18:52
4
\$\begingroup\$

Mathematica, 39 bytes

x##&@@Cases[x,#|##&@@Range@##]&@@@#&

-22 bytes from JungHwan Min
-4 bytes from Martin

Try it online!

\$\endgroup\$
  • \$\begingroup\$ You can also get rid of the entire Range thing by just taking the expanded ranges as input. \$\endgroup\$ – Martin Ender Dec 7 '17 at 15:38
3
\$\begingroup\$

Pyth, 5 bytes

s@Rvz

Try it here!

Pyth, 10 bytes

s.gx}LkQ1E

Try it here!

How they work

s@Rvz  | Full program.

  R    | Right map...
 @     | ... Using intersection.
   vz  | Of the first input with the second.
s      | Flatten by one level.
s.gx}LkQ1E  | Full program.

 .g      E  | Group the items in the second input by...
    }LkQ    | Map over the first input, and check if the current item is in the list.
   x    1   | Take the index of the first truthy element.
s           | Flatten.

Takes the docks first, with all the integers in the ranges, and then the presents on a new line.

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

Python 2, 49 46 bytes

thanks to @HyperNeutrino for -3 bytes

lambda p,b:[x for l in b for x in p if x in l]

Try it online!


Ungolfed

def f(presents, groups):
  result = []
  for group in groups:
    for present in presents:
      if present in group:
        result.append(present)
  return result

Try it online!

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

05AB1E, 3 bytes

δØ

Try it online! (thanks to Adnan for letting me know δ exists, -1 byte)

How it works

δØ  | Full program.

δ    | Double-vectorize the next command (something like an outer product).
 Ã   | List intersection. Since this is a dyad, the first input is automatically
     | used to fill the missing argument (as far as I know).
  ˜  | Flatten.
\$\endgroup\$
  • \$\begingroup\$ Well, €Ã˜ doesn't seem to work. \$\endgroup\$ – Erik the Outgolfer Dec 5 '17 at 17:24
  • \$\begingroup\$ No, there isn't. BTW the reason €Ã˜ fails is because à takes two arguments, and expects a function with one argument, so it returns [[]] instead (I think that's a bug), so then ˜ will flatten, returning []. ε, though, works differently. For each element of the top item, it makes a new stack and then returns the top of each new stack, so when there aren't enough items in it for a function, it takes an implicit input instead. \$\endgroup\$ – Erik the Outgolfer Dec 5 '17 at 17:39
  • \$\begingroup\$ I haven't tested it yet, but is δØ what you are looking for? \$\endgroup\$ – Adnan Dec 5 '17 at 17:57
  • \$\begingroup\$ @Mr.Xcoder I don't think that's exactly the dyadic map Pyth has, it behaves more like outer product or something. \$\endgroup\$ – Erik the Outgolfer Dec 5 '17 at 18:04
3
\$\begingroup\$

Retina, 37 36 bytes

O$`(\d+)(?=.*¶(.*)\[.*\b\1\b)
$2
G1`

Try it online! Takes input as a list of presents on the first line and a list of ranges on the second line; the link includes a header to split the test cases into the desired format. Edit: Saved 1 byte thanks to @MartinEnder. Explanation: The first stage matches the presents and finds the matching dock. The presents are sorted by the substring from the start of the line to the [, thus grouping the presents by dock. The second stage then deletes the docks.

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

Enlist, 3 bytes

f₱Ẏ

Try it online!

How it works

f₱Ẏ  | Full program.

 ₱   | Map over right argument.
f    | Using list intersection, counting multiplicities.
  Ẏ  | Tighten (flatten by 1 level).
\$\endgroup\$
  • 1
    \$\begingroup\$ :D Enlist was not forgotten :D Actually it kinda was, just not by the community but rather by me :( :P \$\endgroup\$ – HyperNeutrino Dec 6 '17 at 0:23
2
\$\begingroup\$

APL+WIN, 29 bytes

(,⍉<\p←n∘.≤∊¯1↑¨⎕)/(×/⍴p)⍴n←⎕

Prompts for screen input for both the integers and ranges. The integers as a flat list and the ranges as a nested vector, e.g case 3:

(1 3) (4 5) (6 7)

Explanation:

(×/⍴p)⍴n←⎕ prompt for screen input of integers and replicate by the number of ranges 

∊¯1↑¨⎕ prompt for screen input of ranges and select the top of each

p←n∘.≤ create a boolean matrix using outer product with less than the top of each range

,⍉<\ identify the first range which each element fits in and ravel into a partition vector

(.....)/.... use the partition vector to select the elements in each range in order
\$\endgroup\$
2
\$\begingroup\$

C++, 127 bytes

Take input as two arrays represented by pairs of pointers [start, end).

#import<algorithm>
[](int*A,int*x,int*B,int*y){for(;B!=y;B+=2)A=std::stable_partition(A,x,[&](int a){return a>=*B&&a<=B[1];});}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Well, C++ has a built-in for everything... or does it? / Given that the input ranges doesn't contains 0, it is possible to golf down some bytes using null-terminated array B, although it may be considered cheating. / Unfortunately [&](int a)->int{a=a>= instead of [&](int a){return a>= doesn't save any bytes. / #import<algorithm> can be #import<regex>, at least on TIO. I found that after search exhaustively ("manual binary search") all header listed in this page and this one is the shortest. / Also, +1 from me. \$\endgroup\$ – user202729 Dec 6 '17 at 11:27
2
\$\begingroup\$

J, 15 bytes

[/:[:I.e.&>"0 1

Takes the input as the left argument and the ranges as the right argument. The ranges are boxed lists of the complete ranges.

e.g. for the first range:

   NB. This produces the range
   (1 2 3 ; 4 5 6 7)
┌─────┬───────┐
│1 2 3│4 5 6 7│
└─────┴───────┘

Try it online!

Explanation

[/:[:I.e.&>”0 1
          >”0 1  Pair each element on the left with each range on the right
       e.        Is the element in the range?
     I.          Indices of ones
[/:              Sort the elements by this array
\$\endgroup\$
2
\$\begingroup\$

J, 26 24 bytes

2 bytes thanks to cole

[:;]<@#~1=-&1 0"1@[I."1]

How it works:

The left argument holds the ranges.

-&1 0"1@[ decreases the lower boundary of each range by 1

I."1] checks in which range fits each present

1= is it in the correct range

]<@#~ copies and boxes the presents which are in the current range

; - raze (unboxing)

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ I'm pretty sure you can't remove zeroes since the input is integral (e.g. fails this test case (0 4,:_3 _1) f _2 _1 0 1 2) \$\endgroup\$ – cole Dec 6 '17 at 1:05
  • \$\begingroup\$ @cole Hm, I had totally neglected these cases. I'll need to think about them. \$\endgroup\$ – Galen Ivanov Dec 6 '17 at 7:35
  • 1
    \$\begingroup\$ Yeah I think that the easiest way would probably be to box and then raze. 24 bytes that way. \$\endgroup\$ – cole Dec 6 '17 at 8:53
  • \$\begingroup\$ @cole Thank you! It's not only shorter but easily solves the problem with 0. \$\endgroup\$ – Galen Ivanov Dec 6 '17 at 9:13
2
\$\begingroup\$

R, 113 48 55 41 bytes

A previous version didn't correctly sort objects when the docks weren't in increasing order.

function(P,D)for(d in D)cat(P[P%in%d],"")

Try it online!

Takes D as a list of vectors of ranges, i.e., list(4:7,1:3) would be [[4, 7], [1, 3]].

Probably the naive answer I should have arrived at ages ago; prints to stdout.

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

Japt, 6 bytes

ñ@VbøX

Try it


Explanation

Implicit input of array U (presents) and 2d-array V (full ranges). Sort (ñ) the presents by passing them through a function (@) that gets the index of the first element (b) in V that contains (ø) the current present (X).

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

Python 2, 97 85 bytes

l,d=input()
k=lambda i,j=0:-~j*(d[j][0]<=i<=d[j][1])or k(i,j+1)
print sorted(l,key=k)

-11 bytes from ovs

-1 byte from Mr. Xcoder

Try it online!

Sorts the list using a recursive lambda as the key. Explanation coming soon™ below.

Explanation:

l,d=input()             # l is the lsit of presents, d is the list of ranges
k=lambda i,j=0:-~j*(d[j][0]<=i<=d[j][1])or k(i,j+1)# recursive lambda to sort with
k=lambda i,j=0:                                    # i is the present
                                                   # j is the index in the list of ranges
               -~j*(d[j][0]<=i<=d[j][1])           # return the index of the list of
                                                   # ranges(plus one) if the present is
                                                   # in the range
                                        or k(i,j+1)# if the present is not in the range,
                                                   # try the next range
print sorted(i,key=k)   # print the list of presents sorted by the lambda
\$\endgroup\$
1
\$\begingroup\$

Javascript ES6, 53 47 45 bytes

p=>l=>l.map(d=>p.filter(a=>d.includes(a)))+''

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 45 bytes. You can take the whole ranges as input. A slightly nicer alternative 47 byter \$\endgroup\$ – Mr. Xcoder Dec 5 '17 at 16:56
1
\$\begingroup\$

PowerShell, 37 bytes

param($a,$b)$b|%{$i=$_;$a|?{$_-in$i}}

Try it online!

Takes $a as a literal array of the presents and $b as an array of arrays, each of which are the full range (e.g., @(1,2,3,4,5) instead of @(1,5)). We then loop over each item in $b with |%{...}. Inside, we need to set a helper $i to be the current item, then use a Where-Object clause against $a to pull out only those items that are -in the current $b array.

Those are left on the pipeline and output is implicit. Since the default behavior of Write-Output inserts a newline between array elements, that's what we get. Here is a slightly tweaked version that is -joined together via commas instead of a newline, just to show differences.

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

Red, 73 bytes

f: func[b r][n: copy[]foreach p r[foreach a b[if find p a[append n a]]]n]

Try it online!

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

C# (.NET Core), 50 + 18 bytes

a=>b=>b.SelectMany(x=>a.Where(y=>y>=x[0]&y<=x[1]))

+18 bytes from

using System.Linq;

It takes a collection for presents and a collection of arrays for docks.

Try it online!

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

Windows Batch (CMD), 90 79 bytes

set/pX=||exit
set/pY=
for %%n in (%*)do if %X% LEQ %%n if %%n LEQ %Y% %%n
%0 %*

Use LF end-of-line format. Each end-of-line character can be counted as 1 byte.

No TIO (because TIO uses Linux)

Take the list from command line arguments, and ranges from stdin.

For example, if the program is run (assume the file is named r1.cmd)

r1 7 3 5 4 6 1 2

and with stdin input

1
3
4
5
6
7

, the program will output to stderr with format

'3' is not recognized as an internal or external command,
operable program or batch file.
'1' is not recognized as an internal or external command,
operable program or batch file.
'2' is not recognized as an internal or external command,
operable program or batch file.
'5' is not recognized as an internal or external command,
operable program or batch file.
'4' is not recognized as an internal or external command,
operable program or batch file.
'7' is not recognized as an internal or external command,
operable program or batch file.
'6' is not recognized as an internal or external command,
operable program or batch file.

(corresponds to output sequence 3 1 2 5 4 7 6)


Explanation:

set /p X=       Prompt for variable X (min range)
   ||exit       If failed (end of file), exit - similar to short-circuit of logical OR
set /p Y=       Prompt for variable Y
for %%n in (%*)do     For each number %%n in all command-line arguments
   if %X% LEQ %%n     If X <= n
      if %%n LEQ %Y%  and n <= Y
         %%n          run command named "n", which lead to an error.

%0 %*           Call itself, process other ranges

Ungolfed code (with interaction enabled if true is passed as argument 1; prompt for the list from stdin, use goto to avoid stack overflow - actually I've just tried to run a script that call itself over 70000 times without seeing any problem, so I guess it should be pretty safe):

@echo off

set INTERACTIVE=%1

if "%INTERACTIVE%" == "true" (
    set rangeMinPrompt=Enter range min: 
    set rangeMaxPrompt=Enter range max: 
    set listPrompt=Enter list: 
) else (
    set rangeMinPrompt=
    set rangeMaxPrompt=
    set listPrompt=
)


set /p list=%listPrompt%

:loop_label

set /p rangeMin=%rangeMinPrompt%&& set /p rangeMax=%rangeMaxPrompt%|| exit /b

for %%n in (%list%) do (
    if %rangeMin% LEQ %%n (
        if %%n LEQ %rangeMax% (
            echo %%n
        )
    )
)

goto :loop_label
\$\endgroup\$
  • \$\begingroup\$ You can save more bytes by requiring the presents to be command-line arguments and use (%*). Having done this, you can then use %0 %* to restart the script after processing each range. (I actually ended up with a larger byte count because I used your interactive version with the nice touches &&, exit/b and echo as my starting point.) \$\endgroup\$ – Neil Dec 6 '17 at 10:41
  • \$\begingroup\$ @Neil Nice, thanks! I originally tried using %1 but the quotes " make the space not working as separators, so I ended up using set /p. \$\endgroup\$ – user202729 Dec 6 '17 at 10:48
  • \$\begingroup\$ Oh wow, there is even $~1... \$\endgroup\$ – user202729 Dec 6 '17 at 10:51
1
\$\begingroup\$

Clean, 59 bytes

import StdEnv;f p l=flatten[[n\\n<-p|a<=n&&n<=b]\\[a,b]<-l]

Try it online!

Takes two lists, returns a list.

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

Wolfram Language (Mathematica), 34 bytes

r#~SortBy~{#&@@@r~Position~#&}&

Try it online!

is the Function operator.

This is an unnamed curried function which should be called first with the list of (expanded) dock ranges and then with the list of presents. For example, if you assign the function to f:

f[ {{4,5,6,7},{1,2,3}} ][ {1,2,3,4,5,6,7} ]

The list of presents simply sorted by the first-level position of the value in the list of dock ranges. We need to wrap the SortBy function in a list to make the sort stable.

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

Julia 0.6, 31 30 bytes

p%d=vcat((∩(p,x)for x=d)...)

Try it online!

Redefines the % operator and maps the set intersection∩() over the docks d maintaining order and multiplicity of the first imput, the list of presents p. vcat with the input expanded to multiple arguments via ... flattens the resulting nested array.

Edit, -1Byte: List comprehension instead of map().

\$\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.