Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The story

"2016? Al..right," grumbled toy seller Hilbert. He opened his eyes, wiped salad dressing trickling out of his ear and ate a morning kick-start cremeschnitte. Exemplar holidays. He needs to go to work now though, and finish the year's accounting.

Christmas is a very yielding period of the year, especially for his sales. Hilbert knows exactly how it works: A person comes into a shop and buys the first gift they are offered. They pay for it and run off to another shop. In practice, what the gift actually is doesn't really make a difference. The price is also irrelevant, provided it is not too high. It all depends on the time remaining until Christmas -- the shorter the time, the greater the remorse of the customers, the greater the price they are willing to pay.

All it takes for Hilbert is to look at his watch -- and he knows right away how much his customers can spend. He can easily take advantage of this fact: He just finds the most expensive gift he can sell to a given customer, and offer it to them. Only now has he realized that he forgot to employ this cunning strategy last year. That's gonna change though!

Nevertheless, Hilbert would like to know how much his business would have flourished, if he had actually used his grand scheme. He's managed to put together a list of people who came to his store, he is however not sure how much money he could have made on them.

Your task (TL;DR)

The input consists of an ascending list of prices of available gifts, and a list of customers' budgets. The list of budgets is in the same order as the customers arrived to the shop -- with a condition that every customer is willing to pay at least as much as the previous one, meaning it is also ascending.

For each customer, find the most expensive gift they are willing to pay for, and output it's price. If no gifts within the budget are available, output a 0.

You get a -40% characters bonus, if the asymptotic time complexity of your algorithm is O(n+m) (rather than the trivial O(n*m)) Where n, m are the lengths of the input lists.

This is , shortest bytes wins. Standard loopholes are prohibited.

Example

Input:

1 2 2 2 5 7 10 20
1 1 2 3 6 6 15 21 21 22

Output:

1 0 2 2 5 2 10 20 7 0

This task was taken from a local programming competition, and translated to English by me. Here is the original assignment: https://www.ksp.sk/ulohy/zadania/1131/

share|improve this question
9  
Bonuses are one thing to avoid when writing challenges. However, I think it might be fine here. If you want to keep it, I recommend changing it to a percentace based bonus. A 20 character bonus doesn't mean anything to a Java submission, but is basically mandatory for solutions in a golfing language. – DenkerAffe Mar 28 at 21:16
    
Can I award a bounty to OP for the backstory alone? Honestly, that made me smile; every challenge needs one of those. – cat Mar 29 at 1:53
    
@tac Thanks, but as is noted in the small text at the bottom, I didn't actually make up the backstory - I only translated it. – sammko Mar 29 at 6:59
    
@sammko yes, I saw that, but my above comment still holds :) – cat Mar 29 at 13:03

Pyth, 17 16 bytes

1 byte thanks to Pietu1998

VE=.-Q]
e|fgNTQ0

Demonstration

Explanation:

VE=.-Q]<\n>e|fgNTQ0
                        Implicit: Q is the list of prices.
VE                      For N in the list of budgets
             f   Q      Filter the list of prices
              gNT       On the current person's budget being >= that price
            |     0     If there aren't any, use 0 instead.
          e             Take the last (most expensive) value.
      <\n>              Print it out.
  =.-Q                  Remove it from the list of prices.
share|improve this answer
    
I think you can save 1 byte with VE=.-Q]\ne|fgNTQ0. Basically the same thing but with a loop. – Pietu1998 Mar 30 at 8:57

Haskell, 67 bytes

a#(b:c)|(h,t)<-span(<=b)a=last(0:h):(init(h++[0|h==[]])++t)#c
_#x=x

Usage example: [1,2,2,2,5,7,10,20] # [1,1,2,3,6,6,15,21,21,22] -> [1,0,2,2,5,2,10,20,7,0].

Split the prices in two parts: (h,t) where h are all prices <= the budget of the next customer and t are all the others. Take the last price of h and continue recursively with all but the last of h plus t and the remaining budgets. last(0:h) evaluates to 0 if h is empty. Similar: init (h++[0|h==[]]) ++ t adds a dummy element 0 to h if h is empty, so that init has something to drop (init fails on the empty list).

share|improve this answer

Java, 154 * 0.6 = 92.4 bytes

-13 bytes because the lambda can actually use int[], not Integer[] (thanks BunjiquoBianco)

This should take O(n+m) time and O(n+m) additional space (assuming I understand big O notation).

g->b->{int l=g.length,L=b.length,G=0,B=0,A=0;int[]a=new int[l],s=new int[L];for(;B<L;){while(G<l&&g[G]<=b[B])a[A++]=g[G++];s[B++]=A>0?a[--A]:0;}return s;}

Indented: (Try it online!)

static int[] toyStore(int[]g,int[]b) {
    int gl=g.length,bl=b.length,gp=0,bp=0,ap=0;
    int[] a=new int[gl],s=new int[bl];
    for (;bp<bl;) {
        while(gp<gl&&g[gp]<=b[bp])a[ap++]=g[gp++];
        s[bp++]=ap>0?a[--ap]:0;
    }
    return s;
}

public static void main(String[] args)
{
    System.out.println(Arrays.toString(
        toyStore(new int[] {1,2,2,2,5,7,10,20},
                 new int[] {1,1,2,3,6,6,15,21,21,22})
        ));
}

I show the non-lambda expansion here because the type declaration is cleaner and it's the exact same logic. The lambda is present at the ideone link.

Explanation:

Variables used:

  • g is the list of gift prices, b is the list of budgets.
  • gl is the length of g and bl is the length of b.
  • a is a Stack for affordable gifts, s is the output array of sold gifts.
  • gp, bp, and ap are pointers for g, b, and a respectively. bp is also the pointer for s.

Algorithm:

  • For each budget in the length of budgets
    • While this budget can buy the gift at g[gp]
      • Push the budget onto the Stack a and increment gp
    • Pop the top of a into s[bp] if it exists, else put 0.
share|improve this answer
    
Can't you curry the lambda? (i.e. (g,b)-> to g->b->? – Mars Ultor Mar 28 at 23:35
    
@somebody apparently, yes. For some reason it's never worked for me before but now it will. 0.o (You saved 0.6 bytes after the bonus.) – CAD97 Mar 28 at 23:38
    
You can save some bytes by using longs if the input is assumed to be long[] (takes you to 158bytes) - ideone.com/invHlc – BunjiquoBianco Mar 29 at 8:55
1  
@BunjiquoBianco in fact I can just use int[]. For some reason I was under the impression that since the type arguments take reference types (thus not the value-typed primitives like int) that I needed to use a array of reference types. But I can use an array of int just fine. I'll update once I get a chance. – CAD97 Mar 29 at 14:32
    
@CAD97 Ha! Can't believe I didn't make that link... – BunjiquoBianco Mar 29 at 16:09

Haskell, 87 * 0.6 = 52.2 bytes

g s(p:q)d@(b:c)|p<=b=g(p:s)q d
g[]p(b:c)=0:g[]p c
g(s:t)p(b:c)=s:g t p c
g _ _ _=[]
g[]

Completely different from my other answer, because I'm going for the bonus.

The last line (-> g[]) is not part of the definition, but calling overhead. Usage example: g [] [1,2,2,2,5,7,10,20] [1,1,2,3,6,6,15,21,21,22] -> [1,0,2,2,5,2,10,20,7,0].

Works basically in the same way as @CAD97's answer, i.e. uses a (initially empty) helper stack to keep track of the buyable items. In detail: check in order:

  • if the first price is less or equal than the first budget, move the price to the stack. Call again.
  • if the stack is empty, return a 0 followed by a recursive call with the budget dropped.
  • if both stack and budget list are not empty, return the top of stack followed by a recursive call with stack & budget popped.
  • else return the empty list.

This works in m+n time, because a) operations on the helper stack use constant time and b) in each of the recursive calls one of the lists is shortened by one element.

share|improve this answer

Jelly, 15 bytes

ṀṄ;©®œ^
Rf@€ç/Ṁ

Try it online!

How it works

ṀṄ;©®œ^  Helper link. Arguments: G, H (lists of affordable gifts)

Ṁ        Compute the maximum of G (0 if the list is empty).
 Ṅ       Print it.
  ; ®    Concatenate it with the register (initially 0).
   ©     Save the result in the register.
     œ^  Compute the multiset symmetric difference of the updated register and H.

Rf@€ç/Ṁ  Main link. Arguments: B (budgets), P (prices)

R        Range; replace each t in B with [1, ..., t].
 f@€     Intersect the list of prices with each budget range, obtaining, for each
         customer, the list of all gifts he's willing to pay for.
    ç/   Reduce the array of lists by the helper link.
         In each iteration, this computes and prints the most expensive gift for
         a customer, than removes the selected gift (and all previously
         selected gifts) from the next list.
      Ṁ  Compute the maximum of the resulting list, which corresponds to the last
         customer.
share|improve this answer

JavaScript, 85 * 0.6 = 51 bytes

f=(a,b,s=[],[t,...u]=a,[v,...w]=b)=>v?t<=v?f(u,b,[...s,t]):[s.pop()|0,...f(a),w,s)]:[]

Another clone of @CAD97's answer.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.