15
\$\begingroup\$

Oof! You've been coding the whole day and you even had no time for Stack Exchange!

Now, you just want to rest and answer some questions. You have T minutes of free time. You enter the site and see N new questions. To write an answer for each you'll need ti minutes. Of course, as a dedicated reputation gatherer, you want to answer as many questions as you can.

Can you write a program to calculate which questions do you have to answer to write maximum posts in T minutes?

Input

First line of input consists T minutes you have for answering, and N, how many new questions are on the site.
The second line has N numbers: time you need to answer qi question.

Output

Write either an array or numbers split with space: indexes of questions(counting from 0 or 1 - what is better for you) you should answer in order to write as many answers as you can. If you can't answer any questions, write nothing or anything to express that it's impossible. If there are several variants, write any.

Examples

Inputs               Possible outputs


60 5
30 5 10 20 3    0 1 2 4, 0 1 3 4 or 1 2 3 4

10 5
1 9 5 7 2         0 2 4 or 0 3 4

5 5
1 1 1 1 1         0 1 2 3 4

60 5
48 15 20 40 3  1 2 4 or 1 3 4

5 1
10                     

1 0
                        




And of course it's , so the shortest code in bytes wins.

\$\endgroup\$
  • 3
    \$\begingroup\$ Isn't this just taking the minimum from the question list until the sum is the first input? \$\endgroup\$ – NoOneIsHere Nov 28 at 18:51
  • 3
    \$\begingroup\$ @NoOneIsHere Yep, the task is more code-golfing than making an algorithm. \$\endgroup\$ – Ver Nick says Reinstate Monica Nov 28 at 18:53
  • 3
    \$\begingroup\$ Can we not take N as input? \$\endgroup\$ – Luis Mendo Nov 28 at 22:11
  • 6
    \$\begingroup\$ FYI: codegolf.meta.stackexchange.com/questions/2447/… \$\endgroup\$ – Jonathan Allan Nov 28 at 22:26
  • 3
    \$\begingroup\$ @VerNicksaysReinstateMonica There is a problem then: it is unobservable if a program uses an input or not. I could claim I'm "taking" three inputs in TIO, but my program could actually be ignoring one of them \$\endgroup\$ – Luis Mendo Nov 28 at 22:27

15 Answers 15

10
\$\begingroup\$

Python 3.8 (pre-release), 81, 79, 75 bytes

Using the walrus operator :=:

lambda k,l:[i for j,i in sorted((v,k)for k,v in enumerate(l))if(k:=k-j)>=0]

Try it online!

-2 bytes thanks to @JoKing

-4 bytes thanks to @justhalf

Python 3, 158, 137, 136, 130, 127, 117, 103, 95 bytes

def f(k,l):
 q=[]
 for j,i in sorted((v,k)for k,v in enumerate(l)):k-=j;q+=[i]*(k>=0)
 print(q)

Try it online!

-21 bytes thanks to @79037662 by limiting indentation to 1-space.

-14 bytes thanks to @ mypetlion

-8 bytes thanks to @justhalf

Both solutions ignore N parameter.

\$\endgroup\$
  • \$\begingroup\$ One easy golf is to use only a single space for the indents: tio.run/… \$\endgroup\$ – 79037662 Nov 28 at 19:40
  • \$\begingroup\$ Wouldn't that be -7 bytes? \$\endgroup\$ – Redwolf Programs Nov 28 at 19:42
  • 1
    \$\begingroup\$ @game0ver Oh, nvm...you originally had -1 total in the message. I only counted -1 byte per indent level instead of -3. \$\endgroup\$ – Redwolf Programs Nov 28 at 20:11
  • 1
    \$\begingroup\$ Another -3 bytes by modifying k instead of m. This trick can be applied to the Python 3.8 solution, too. Reducing it by 4 bytes by removing m. \$\endgroup\$ – justhalf Nov 29 at 11:00
  • 1
    \$\begingroup\$ @justhalf That's brilliant, never crossed my mind to modify k instead :) Thank you! \$\endgroup\$ – game0ver Nov 29 at 11:06
5
\$\begingroup\$

Japt, 22 21 16 15 bytes

ð à ñÊÔæÈxgU <V

Try it

ð à                 combinations of indexes of 1st input
    ñÊÔ             sorted by length and reversed
       æ            get first element returning true when passed throug...
        ÈxgU        elements of input at X indexes reduced by addition
               <V   less than 2nd input

Takes input as [times...], time , amount

Saved 1 stealing from @Shaggy ÈxgU

\$\endgroup\$
  • \$\begingroup\$ Well, damn! Wrote my solution up hours ago but got distracted by work and only now, after posting it, do I see this, which can be golfed down to my exact solution. Sorry. One of these days I'll learn to reload before posting! \$\endgroup\$ – Shaggy Nov 28 at 22:43
  • \$\begingroup\$ Your sorting method can be golfed to ñÊ but isn't actually necessary as à sorts by descending length. And r+ can be just x. \$\endgroup\$ – Shaggy Nov 28 at 22:45
  • \$\begingroup\$ I regolfed a bit by myself to 16.. You still beaten me @Shaggy, thanks for the tips! \$\endgroup\$ – AZTECCO Nov 28 at 23:16
  • 1
    \$\begingroup\$ Ah, I think I might have been thinking of ã, which sorts by ascending length. \$\endgroup\$ – Shaggy Nov 28 at 23:33
  • 1
    \$\begingroup\$ @Embodiment of Ignorance it is valid too because we don't have to maximize the time, it was specified in the comments. \$\endgroup\$ – AZTECCO Nov 29 at 7:23
5
\$\begingroup\$

05AB1E, 9 13 12 bytes

ā<æʒ¹sèO@}éθ

Takes the inputs in the order: \$q_i\$, \$N\$ (which is mostly ignored, see explanation below), \$T\$.
Uses 0-based indexing.

+4 bytes as bug-fix for test case [1,1,1,1,1] resulting in [0,0,0,0,0] instead of [0,1,2,3,4] (and now switched from 0-based to 1-based indexing).
-1 byte thanks to @Grimmy (and back to 0-based indexing again).

Try it online or verify all test cases or get all possible outputs for the test cases instead of just one.

Explanation:

             # Take the (implicit) input-list qi
ā            # and push a list in the range [1, list-length] without popping the input itself
 <           # Decrease each by 1 to make it 0-based: [0, list-length)
  æ          # Get the powerset of this list of indices
             #  i.e. [0,1,2] → [[],[0],[1],[0,1],[2],[0,2],[1,2],[0,1,2]]
   ʒ         # Filter this list of lists by:
    ¹        #  Push the first input-list qi again
     s       #  Swap to put the current list of the filter at the top of the stack
      è      #  Index each into the list qi
       O     #  Sum these values
        @    #  Check if the (implicit) input-integer is >= this sum
             #  (The very first iteration it will use the second input, which is the length N;
             #   every other iteration it will use the third input, which is the total time T.
             #   Since the very first inner list of the powerset will be the empty list,
             #   this causes no problems; which is how we ignore the mandatory length N input)
         }é  # After the filter: sort all remaining inner lists by length
           θ # Pop and leave the last one, which is (one of) the list(s) with the most items
             # (after which the result is output implicitly)
\$\endgroup\$
  • \$\begingroup\$ You can go back to 0-based indexing by using instead of āø. \$\endgroup\$ – Grimmy Nov 29 at 13:25
  • 1
    \$\begingroup\$ Here's a 12 \$\endgroup\$ – Grimmy Nov 29 at 13:31
  • \$\begingroup\$ @Grimmy Thanks! And I had no idea we had the builtin . \$\endgroup\$ – Kevin Cruijssen Nov 29 at 13:54
4
\$\begingroup\$

dzaima/APL, 15 14 13 bytes

+\∘<⍛≤+/⍛↑⍋⍤⊣

Try it online!

+\∘<⍛≤+/⍛↑⍋⍤⊣  train; left arg = ⍺ = t, right arg = ⍵ = T
     ≤         ⍺ <= ⍵
    ⍛          with ⍺ modified to
   <             sorted
+\∘              and then, cumulative sum
               so, cumulativeSum(sort(q)) ≤ T

          ⍋    the indices required for sorting
           ⍤⊣  applied on ⍺
               so, the output, sorted by question time, if T=∞

         ↑     take first ⍺ elements from ⍵ (⍺ is `+\∘<⍛≤`, ⍵ is `⍋⍤⊣`)
      +/⍛        but summing ⍺ first
\$\endgroup\$
4
\$\begingroup\$

Jelly, 8 bytes

ṢÄ>¬TịỤ{

A dyadic Link accepting the question times on the left and the total time on the right which yields the 1-indexed indices.

Try it online! (footer calls the Link and prints a formatted version of its output.)

(If we must take the number of questions, this works as full program accepting: question times; total time; number of questions.)

How?

ṢÄ>¬TịỤ{ - Link: ts; T        e.g. [1, 9, 5, 7, 2]; 10
Ṣ        - sort ts                 [1, 2, 5, 7, 9]
 Ä       - cumulative sums         [1, 3, 8,15,24]
  >      - greater than (T)?       [0, 0, 0, 1, 1]
   ¬     - logical NOT             [1, 1, 1, 0, 0]
    T    - truthy indices          [1, 2, 3]
       { - use left argument:
      Ụ  -   indices by value      [1, 5, 3, 4, 2]   (i.e index 4 has 2nd largest value)
     ị   - index into              [1, 5, 3]

Alternative 8:

ỤṁṢÄ>Ðḟɗ - indices-by-value moulded-like (cumulative-sums of sorted(ts) if not greater than T)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Does Jelly have a single byte operator for <=, which would allow you to skip the NOT? \$\endgroup\$ – Shaggy Nov 28 at 23:11
  • \$\begingroup\$ No it does not. \$\endgroup\$ – Jonathan Allan Nov 28 at 23:13
  • \$\begingroup\$ Shame. It looks like some solutions are assuming that the result must be strictly <T rather than <=T so it might be worth asking for clarification on that. \$\endgroup\$ – Shaggy Nov 28 at 23:16
  • \$\begingroup\$ @tsh Ah yeah, that's a bug, I should use T not M (since if no cumulative sums are not greater than the right argument the zeros will be the maximal values. T will instead get truthy indices, so non-zeros). Thanks for spotting that. (FWIW the alternative 8 byte solution works as-is) \$\endgroup\$ – Jonathan Allan Nov 29 at 10:49
4
\$\begingroup\$

JavaScript (V8), 117 113 110 105 85 71 63 bytes

(-3 thanks to Ver Nick says Reinstate Monica)

(-20 thanks to Arnauld)

(-14 thanks to Shaggy)

(-8 thanks to tsh)

a=>g=t=>(a[y=a.indexOf(i=Math.min(...a))]=t)<i?[]:[y,...g(t-i)]

Try it online!

Could probably be golfed some more...a function which takes input in three arguments: time, number of questions (not actually used), and an array of question times.

It will repeatedly find the smallest element in the array, and set it to the time available, removing it from the possibilities for the next iteration. It puts the index of the value into the output array.

Thanks to everyone who's contributed to golfing this answer...54 bytes shorter than the original!

\$\endgroup\$
  • \$\begingroup\$ You can replace true with 1 \$\endgroup\$ – Ver Nick says Reinstate Monica Nov 28 at 19:29
  • \$\begingroup\$ @Arnauld Thanks! I forgot you could put variable assignments as arguments like that... \$\endgroup\$ – Redwolf Programs Nov 28 at 21:25
  • \$\begingroup\$ 71 bytes. On my phone so can probably be golfed a bit further. \$\endgroup\$ – Shaggy Nov 28 at 23:05
  • 1
    \$\begingroup\$ Maybe 63 bytes? I'm not sure if this is correct (since previous comments does not suggest this with no reason) \$\endgroup\$ – tsh Nov 29 at 10:04
  • \$\begingroup\$ Good shout, @tsh, completely missed that. \$\endgroup\$ – Shaggy Nov 29 at 12:35
3
\$\begingroup\$

Japt -h, 14 bytes

Assumes 0 is not a valid unit of time.

ð à ñÊfÈxgU §V

Try it

ð à ñÊfÈxgU §V     :Implicit input of array U=q and integer V=T
ð                  :0-based indices of U
  à                :Combinations, which, fortunately, includes the empty array, covering the last test case.
    ñ              :Sort by
     Ê             :  Length
      f            :Filter
       È           :By passing each throughout a function
        x          :  Reduce by addition
         gU        :    After indexing each back in to U
            §V     :  Less than or equal to V?
                   :Implicit output of last element

Or, if we have to take N as input (or 0 is a valid unit of time).

o à ñÊfÈxgV §W

Try it

Where U=N, V=q, W=T, o creates the range [0,U) and everything else is as above.

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

Red, 133 bytes

func[t b][s: 0 sort collect[foreach n sort collect[repeat i length? b[keep/only
reduce[b/:i i]]][if(u: s + n/1)<= t[s: u keep n/2]]]]

Try it online!

1-indexed. Ignores N

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

R, 44 41 bytes

function(m,t)order(t)[cumsum(sort(t))<=m]

Try it online!

Takes input as Time, times. Returns numeric() for empty output.

Order the times, take cumulative sum and then select the times where the cumulative sum is less than or equal to total time.

-1 in the end to get 0-index

-1 byte thanks to Giuseppe
-2 bytes since 0-index is no longer needed

\$\endgroup\$
  • \$\begingroup\$ The OP seems to indicate 0 or 1 indexing doesn’t matter. \$\endgroup\$ – cole Nov 29 at 9:04
  • 1
    \$\begingroup\$ 43 bytes \$\endgroup\$ – Giuseppe Nov 29 at 15:49
3
\$\begingroup\$

Ruby, 68 64 60 59 58 bytes

->t,q{q.map.with_index.sort.reject{|x,|0>t-=x}.map &:last}

Try it online!

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

Charcoal, 44 bytes

Nθ≔EN⟦Nι⟧ηW∧笋θ§⌊η⁰«≔⌊ηι≧⁻§ι⁰θ≔Φη⁻⌕ηιλη⟦I⊟ι

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input T.

EN⟦Nι⟧η

Input N and make a list of N questions with their original index.

W∧笋θ§⌊η⁰«

Loop until there are no more questions that can be answered in the remaining time.

≔⌊ηι

Get the shortest question and its original index.

≧⁻§ι⁰θ

Subtract the question's time from the time remaining.

≔Φη⁻⌕ηιλη

Remove the question from the list of questions.

⟦I⊟ι

Print the question's original index.

\$\endgroup\$
  • \$\begingroup\$ You have 3000 posts by now, congrats :) \$\endgroup\$ – Ver Nick says Reinstate Monica Nov 28 at 21:08
  • \$\begingroup\$ @VerNicksaysReinstateMonica wow, I'm actually first at something ;-) \$\endgroup\$ – Neil Nov 29 at 1:26
2
\$\begingroup\$

JavaScript (ES10),  78  75 bytes

Saved 3 bytes thanks to @Neil

Takes input as (T)(list). Ignores N.

t=>a=>a.map((...x)=>x).sort(([a],[b])=>a-b).flatMap(([v,i])=>(t-=v)<0?[]:i)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ +1 for outgolfing me by 27 bytes...never would have thought of anything like this! \$\endgroup\$ – Redwolf Programs Nov 28 at 20:13
  • 1
    \$\begingroup\$ -3 bytes: map((...x)=>x) \$\endgroup\$ – Neil Nov 28 at 21:03
  • \$\begingroup\$ @Neil Nice one! Thanks. \$\endgroup\$ – Arnauld Nov 28 at 21:44
2
\$\begingroup\$

Python 3, 72 bytes

recursive solution, generating line separated console output

def f(T,L):
 if L:M=min(L);I=L.index(M);L[I]=T;T<M or(print(I),f(T-M,L))

Try it online!

def f(T,L):
 if L:            # do nothing if input is empty
  M=min(L)
  I=L.index(M)
  L[I]=T          # set found list item to remaining time (item will be ignored next iteration)
  T<M or(print(I),f(T-M,L))   # if the found question can be answered in the given time output and find next
\$\endgroup\$
2
\$\begingroup\$

J, 16 bytes

(>:+/\@/:~)#/:@]

Try it online!

Attempt at an explanation:

>:                create mask of left arg greater than or equal to...
  +/\@/:~         cummulative sum of sorted right arg
         #        copy where true
          /:@]    from permutation that sorts right arg
\$\endgroup\$
  • \$\begingroup\$ any explanation? \$\endgroup\$ – Varad Mahashabde Dec 1 at 17:15
  • 1
    \$\begingroup\$ @Varad Mahashabde: Here is an attempt. If you need more context please let me know. \$\endgroup\$ – Traws Dec 1 at 20:09
2
\$\begingroup\$

C++11, 293 221 219 bytes

Here to decimate the competition I am not.

Notes :

  1. g++ allows for variable-sized arrays. It saves bytes, so that what I did.
  2. the range-based for loops needs a reference to write correctly?!
#include<iostream>
void f(int t,int c,int*a){int m,i;int y[c];for(int&b:y)b=0;for(;;){for(m=-1;y[++m]&m<c;);for(i=-1;++i<c;)if(a[m]>=a[i]&!y[i])m=i;if(t>=a[m]&!y[m]){y[m]=1;t-=a[m];}else break;}for(i=-1;++i<c;)if(y[i])std::cout<<i<<' ';}

Expanded version :

#include <iostream>

void AnswerMostOfTheQuestions(int time_left, int question_count, int answer_times[]) {
  int minimum_term;
  bool is_answered[question_count];
  for(bool& b : is_answered) 
    b = 0 ; // No questions have been answered
  while (1) {
    // Find the first unanswered question
    for (minimum_term = 0; is_answered[minimum_term] and minimum_term < question_count; ++minimum_term);
    // Find unanswered question which takes least time to answer
    for (int i = 0; i < question_count; ++i) 
      if(answer_times[minimum_term] >= answer_times[i] && ! is_answered[i]) 
        minimum_term = i;
    if (time_left >= answer_times[minimum_term] &&  not is_answered[minimum_term]) {
      // Answer question (which consumes time)
      is_answered[minimum_term] = true;
      time_left -= answer_times[minimum_term];
     } 
    else break;
  }
  // Print index of every answered question 
  // 'cause returning them is a waste of bytes to implement
  // Just echo it to a file or something
  for (int i = 0; i < question_count; ++i) 
    if(is_answered[i]) 
      std::cout<<i<<' ';
}

int main(int c, char** v) {
  int question_count = atoi(v[2]), free_time = atoi(v[1]);
  int answer_times[question_count];
  for (int i = 0; i < question_count; ++i)
    answer_times[i] = atoi(v[i+3]);
  // Run solution
  AnswerMostOfTheQuestions(free_time, question_count, answer_times);
}

Try it online!

New contributor
Varad Mahashabde is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to CG&CC! I can't really help you golf this program, as I am not a C++ golfer, but I suggest you to look at tips for golfing in C++. Additionally, submissions don't have to be full programs, they can be functions taking input and outputting through their return value, which may or may not save bytes in this case. \$\endgroup\$ – Embodiment of Ignorance Dec 1 at 18:16
  • 1
    \$\begingroup\$ Also, while(1) can be for(;;). I suggest adding a Try it Online! link for future submissions \$\endgroup\$ – Embodiment of Ignorance Dec 1 at 18:25
  • 1
    \$\begingroup\$ for(i=3;i<c;++i) can be golfed to for(i=2;++i<c;) saving a byte. \$\endgroup\$ – Noodle9 Dec 1 at 22:27
  • 1
    \$\begingroup\$ if(t-atoi(v[m])>=0&&!y[i-3]) can be golfed to if(t>=atoi(v[m])&&!y[i-3]) saving 2 bytes. \$\endgroup\$ – Noodle9 Dec 1 at 22:32
  • 1
    \$\begingroup\$ np :-) Also think you can golf bool y[c];for(bool&b:y)b=0; to int y[c];for(int&b:y)b=0; saving 2 bytes. \$\endgroup\$ – Noodle9 2 days ago

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.