Stack Exchange Answerer

Question

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 t_i 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 q_i 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 code-golf, so the shortest code in bytes wins.

Answer 1

Python 3.8, 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.

Answer 2

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)

Answer 3

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

Answer 4

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

Answer 5

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!

Answer 6

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!

Answer 7

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.

Answer 8

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

Answer 9

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

Answer 10

Ruby, 68 64 60 59 58 bytes

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

Try it online!

Answer 11

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!

Answer 12

Charcoal, 44 bytes

Ｎθ≔ＥＮ⟦Ｎι⟧ηＷ∧笋θ§⌊η⁰«≔⌊ηι≧⁻§ι⁰θ≔Φη⁻⌕ηιλη⟦Ｉ⊟ι

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

Ｎθ

Input T.

ＥＮ⟦Ｎι⟧η

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

Ｗ∧笋θ§⌊η⁰«

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.

⟦Ｉ⊟ι

Print the question's original index.

Answer 13

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

Answer 14

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

Answer 15

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!

Answer 16

Husk, 9 bytes

↑#≤²∫O¹ηÖ

Try it online! Outputs an empty list if no solution is possible.