She sells sanctuary

Question

A huge storm is ravaging the world and as you and your family run away from it, you come across a gigantic shelter run by a girl. She tells you that "she sells sanctuary" and that different types of rooms are offered at different prices.

A room may only house one person.

The challenge

Write a program which takes in two inputs: the number of people staying at the sanctuary and an array, map, object or string, whatever is convenient as long as the structure is similar to:

[[2, 3], [3, 5], [6, 7]]

In this case, it's a two dimensional array, but it could be a string, like

2,3 3,5 6,7

For each entry, the first item is the number of rooms offered for that type, and the second item is the cost of one room. For instance,

[[1, 2], [3, 4]]

means that one room is offered for the first type for 2 dollars each, and three rooms for the second type at 4 dollars each.

Since your family has limited resources, you would like to find the configuration for which as little money is spent as possible. So, your program should output a few numbers containing information about the number of rooms. At the end, it should also output the total cost.

This might all sound confusing, so take a sample input:

First input: 5
Second input: [[2, 5], [2, 3], [7, 100]]

The cheapest possible configuration is to have two people stay in the first type, costing 3 * 2 = 6 dollars, then two people in the second type for 5 * 2 = 10 dollars, and one person in the last type, for 100 * 1 = 100 dollars. The total cost is therefore 116 dollars. Your output for this test case would be

2 // two people in the first type of room
2 // two people in the second type of room
1 // one person in the third type of room
116 // total cost

Let us try another.

first input: 10
second input: [[1340993842, 5500], [1, 5000]]

The cheapest configuration is to have one person stay in the second type, and the other nine in the first type. The cost is therefore 9 * 5500 + 1 * 5000 = 54500. Output:

9
1
54500

A few extra rules:

• The number of people staying will never be more than the total number of rooms.
• Standard loopholes are disallowed as usual.
• The last output must be the price.
• You may output as an array if you would like.
• Nobody else is staying in the sanctuary.
• Shortest answer in bytes wins because this question is code-golf.
• Input may be taken as rest parameters.
• Order may be reversed, so for example the price might be the first item. You must make it clear though.
• The rooms are not guaranteed to be ordered from cheapest to most expensive.
• Output must be in order of the types given

Answer 1

Wolfram Language (Mathematica), 42 bytes

Minimize[{#.x,Tr@x>#3},x∈Cuboid[0#,#2]]&

Try it online!

Input [prices, availability, #people].

---

Cuboid represents a hyperrectangular region, given two opposite corners: \$\texttt{Cuboid[$(a_1,...,a_n)$,$(b_1,...,b_n)$]}=\{(x_1,...,x_n)\;|\;\forall i=1,...,n:a_i\le x_i\le b_i\}\$.

Minimize finds the minimum value of the expression \$\textit{prices}\cdot x\$ (the total price) and the corresponding vector \$x\$, where we additionally have the restrictions \$x\in\texttt{Cuboid[$0$,$\textit{availability}$]}\$ and \$\sum_ix_i=\textit{#people}\$.

Minimize[           (* minimize *)
 {#.x,              (*  the total price, given *)
  Tr@x==#3},        (*  the total number of people *)
 x∈Cuboid[0#,#2]]   (* and the room availability *)

> saves one byte over == while still returning the same result (albeit with a warning).

Answer 2

JavaScript (ES6), 104 bytes

Saved 5 bytes thanks to @tsh

Expects (list)(n), where the list consists of [available_i, price_i] pairs.

Returns [[booked_1, ..., booked_N], total_cost].

(p,o=p.map(_=>s=0))=>g=n=>n?g(n-1,p.find(([k,c],i)=>k*!p.some(([K,C])=>K&&C<c)&&++o[s+=c,i])[0]--):[o,s]

Try it online!

Commented

( p,                        // outer function taking the list p[]
  o = p.map(_ => s = 0)     // o[] = booking array, initialize to 0's
                            // s = total cost
) =>                        //
g = n =>                    // g is a recursive function taking the number of people n
  n ?                       // if there's still at least one room to book:
    g(                      //   do a recursive call:
      n - 1,                //     decrement n
      p.find(([k, c], i) => //     look for a room [k, c] at position i:
        k *                 //       if it is still available
        !p.some(([K, C]) => //       and there is not another room type
          K && C < c        //       that is cheaper and still available
        ) &&                //       then:
          ++o[s += c, i]    //         increment o[i] (i.e. book a room with index i)
                            //         and add c to the total cost
      )                     //     end of find() (guaranteed to be successful)
      [0]--                 //     decrement the number of available rooms of this type
    )                       //   end of recursive call
  :                         // else:
    [o, s]                  //   stop the recursion and return the results

Answer 3

R, 95 bytes

function(n,l)list(rowSums(outer(l[2,],y<-sort(unlist(Map(rep,l[2,],l[1,])))[1:n],`==`)),sum(y))

Try it online!

Answer 4

J, 30 bytes

1 :'(](],1#.*)1#.]=/u{./:~@#)'

Try it online!

Solution is a J adverb which modifies the first input, takes a list of available rooms as the left arg, and a list of prices as the right arg. For example, the first test case is written like:

2 2 7 (5 f) 5 3 100

Note that the output is a J array, not space-separated standard output -- even though J displays arrays with only a space between elements.

how

Using the above test case as an example...

• /:~@# Copy # the right arg elementwise using the left arg as a mask:

  2 2 7 # 5 3 100
  5 5 3 3 100 100 100 100 100 100 100
  

  and sort /:~:

  3 3 5 5 100 100 100 100 100 100 100
  

• u{. Take "first input" u elements from that:

  3 3 5 5 100
  

• ]=/ Create a table showing where the prices ] are equal to that:

  0 0 1 1 0
  1 1 0 0 0
  0 0 0 0 1
  

• 1#. Sum rows:

  2 2 1
  

• ](...) Taking the last result as the new right arg, and the prices ] as the new left arg, apply the verb in parens...

• ],1#.* Append to the new right arg ], the sum of 1#. the two args multiplied elementwise *:

  2 2 1 116
  

Answer 5

Jelly, 17 bytes

Wẋ$Ṫ$€ẎṢḣµċⱮ³,SḢ$

A full program that accepts two arguments, the list of pairs of room price and associated availability, and the number of guests which prints a list containing a list of room allocations, in the same order as the input pairs, and the total price.

Try it online!

How?

Wẋ$Ṫ$€ẎṢḣµċⱮ³,SḢ$ - Main Link: list of [price, available] pairs, R; guests, N
     €            - for each ([p,a] in R)
    $             -   last two links as a monad:
  $               -     last two links as a monad:
W                 -       wrap -> [[p,a]]
 ẋ                -       repeat -> [[[p,a],...p times],[[p,a],...a times]]
   Ṫ              -     tail -> [[p,a],...a times]
      Ẏ           - tighten from a list of list of pairs to a list of pairs
       Ṣ          - sort
        ḣ         - head (to N)
         µ        - start a new monadic chain, f(X=this list of [price, availability] pairs)
           Ɱ³     - for [p,a] in R:
          ċ       -   count occurrences of [p,a] in X
                    -> allocations
                $ - last two links as a monad:
              S   -   sum (e.g. [[1,4],[7,9]] -> [8,13])
               Ḣ  -   head -> total price
             ,    - pair (the allocations and total price)
                  - implicit print

---

Maybe Wẋ$Ṫ$€ẎṢḣ©ċⱮ⁸®SḢ is acceptable for 16 - It's all OK until you consider the output when only a single priced room type exists: since Jelly list representations of a single element display just that element, we find that, for example, [[15,7]] 3 would print 345 (rather than [3]45). Note, however, that we do know that the leading digits of this output will be the number of guests, so it is "parseable".

Answer 6

Excel, 200 198 bytes

=LET(r,A2#,n,ROWS(r)+1,x,SEQUENCE(n),q,{1,2,3,4},s,SORT(IFS(q=3,x,x=n,0,1,r),2),c,INDEX(s,,1),m,A1-MMULT((x>TRANSPOSE(x))*1,c),y,IF(m<c,m,c),INDEX(SORT(IF(q=4,IF(x=1,SUM(y*INDEX(s,,2)),y),s),3),,4))

Answer 7

Python 3.8, 108 bytes

Input is a list of [number, price] pairs. The numbers of booked rooms are printed and the total price is returned.

f=lambda p,r:p and(print(w:=min((X:=r.pop(0))[0],max(0,p-sum(x for x,y in r if y<X[1]))))or w*X[1]+f(p-w,r))

Try it online!

Answer 8

Jelly, 21 bytes

Ṣẋ/€,€"ỤẎḣƓZðṪċⱮJ},§{

Try it online!

Takes the number of people from STDIN and a list of [price, number] from a command-line argument. Outputs [counts, price].

Explanation

Ṣẋ/€,€"ỤẎḣƓZðṪċⱮJ},§{   Main monadic link
Ṣ                       Sort
 ẋ/€                    For each sublist, repeat the first item the second item number of times
    ,€"Ụ                Pair each number with the corresponding index in the original list
        Ẏ               Flatten by one level => [[price, index], ...]
         ḣƓ             Take the first [number on STDIN] items
           Z            Transpose => [prices, indices]
            ð           Remember this list
             Ṫ          Take the second item (the list of prices) and remove it from the list
              ċⱮJ}      Count the occurences of each index of the original list
                  ,§{   Pair with the sum of what remains of the remembered list

Answer 9

Clojure, 152 145 105 98 bytes

#(let[x(take %2(for[[i j](sort %)k(repeat j i)]k))][(for[i %](count(keep #{(i 0)}x)))(apply + x)])

Try it online!

Takes input as the listing of rooms with price given first followed by the number of guests, outputs the results as a vector.

Explanation

First, we sort the input vector, by default sort is performed by the first element, which is the price. Next, we "explode" the input using repeat, simulating the actual row of rooms sorted by price, and take the first N elements, where N is the number of guests:

[[5, 2], [3, 2], [100, 7]], 5 => 3 3 5 5 100 | 100 100 100 100 100 100

Then, we loop through the vector of rooms again, and count how many of each price do we have in the cheapest collection x. After the discussion with OP it was settled that the prices of different room types may not be the same, and therefore, price can be used as the room type ID.

Finally, we add the total sum of the prices to the output.

Answer 10

JavaScript (ES6), 103 bytes

(n,i,t=0,p=[...i].sort((a,b)=>a[1]-b[1]).map(v=>v[0]<n?n-=v[0]:v[0]=n))=>[i.map(([x,y])=>(t+=x*y,x)),t]

Similar to the other JavaScript answer, it returns [[booked_1, ..., booked_N], total_cost].

However, it's just a single function that expects (n, list) (where list is an array of arrays, e.g. [[1,2],[3,4]], just like the examples provided).

Here's the idea:

(n,                             // the number of family members
 i,                             // a list of rooms, e.g. [[1,2],[3,4]]
 t=0,                           // initialize total cost
 p=[...i]                       // shallow copy array
     .sort((a,b)=>a[1]-b[1])    // sort the shallow copy
     .map(v=>                   // loop it
         v[0]<n                 // if there is more family members than rooms,
             ?n-=v[0]           // put as many as possible in this room
             :v[0]=n            // otherwise, put the remaining ones in it
         )
                                // we've now edited the elements of the original array
                                // so the first number is the amount of people staying
                                // in that room, not the amount of rooms of that type
                                // that are available

)=>[                            // return an array
    i.map(([x,y])=>(            // loop the list of rooms
        t+=x*y,                 // add the cost to t
        x                       // return the number of people staying in the room
        )
    ),
t]                              // finally, the total cost as last element of array

Answer 11

Charcoal, 29 bytes

ＵＭη⊞ＯικＦθ⊞υ§⌊Φη⁻§κ¹№υλ²ＩＥη№υκ

Try it online! Input is the number of people and a list of [price, count] pairs, and output is a list of counts in the same order. Explanation:

ＵＭη⊞Ｏικ

Push the index to each pair, so they are now [price, count, index].

Ｆθ

Repeat for each person.

⊞υ§⌊Φη⁻§κ¹№υλ²

Filter out the prices of the counts that have been used up, find the minimum, and push the original index to the list of persons.

ＩＥη№υκ

Print the number of persons allotted to each type.

Answer 12

Java, 156 152 bytes

r->p->{int l=r.length,o[]=new int[l+1],i,j;for(;p-->0;--r[j][0],++o[j],o[l]+=r[j][1])for(i=j=-1;++i<l;)j=r[i][0]>0&(j<0||r[i][1]<r[j][1])?i:j;return o;}

Try it online!

Saved 4 bytes thanks to ceilingcat

Answer 13

05AB1E, 21 bytes

ε`и}{˜I£©¹€нsk{γ€g®Oª

First input as a list of pairs \$[price, amount]\$. Output as an array (with the last item being the total price).

Try it online or verify all test cases.

Explanation:

ε             # Map over each pair in the first (implicit) input-list:
 `            #  Pop and push both values separated to the stack
  и           #  Repeat the first item the second item amount of times as list
}{            # After the map: sort the list based on their first items
  ˜           # Then flatten the list of lists
   I£         # Only leave the second input amount of leading values
     ©        # Store this list in variable `®` (without popping)
¹             # Push the first list of pairs again
 €н           # Only leave the first item (the price) of each pair
   s          # Swap so list `®` is at the top of the stack
    k         # Get for each the index in the list of prices
     {        # Sort these indices from lowest to highest
      γ       # Split it into groups of equivalent adjacent values
       €g     # Get the length of each group
         ®    # Push list `®` again
          O   # Pop and push its sum
           ª  # Append it to the list of lengths
              # (after which the result is output implicitly)