How long will it take Santa to deliver his presents?

Question

I posted this challenge a while ago, which concerns how many elves Santa needs to deliver presents.

Due to population increase, Santa is a little more pressed for time this year. Although in the past we operated very asynchronously, we are beginning to experiment with being more and more synchronized. So, Santa needs to know how long it will take him to deliver presents to each region with a given number of elves.

The weight of coal hasn't changed over the past two years — it's still heavier than presents, so Santa needs three elves per naughty person in the house, and two elves per nice person in the house.

Elves spend all year training for Christmas, so they don't need any rest between deliveries. They can only deliver presents to one house at a time, and must go back Santa's sleigh and collect the next gift before going to the next house. For reasons that I am not at liberty to share, elves do not spend time traveling between Santa's sleigh and houses (but can only travel when Santa's sleigh is on the roof), nor does his sleigh spend time moving from house to house. (Santa's sleigh does needs to move from house to house in order to collect fuel, but I'm already saying too much).

Elves that are delivering presents need to spend four seconds^* each delivering the presents, and Elves that are delivering coal need to spend five seconds^* each delivering it (as per Santa Aviation Administration regulations, gloves with coal dust on them must be incinerated immediately upon boarding the sleigh, which takes up some time). Additionally, the houses must be visited in the order they are on the map, from left to right, and elves can not begin delivering presents to other houses until all presents have been delivered to the house they are currently at.

If we assumed that Santa had more than enough elves for this region, it would take only as long as it takes to deliver a present to someone on the naughty list, 5 seconds, per house, or 4 seconds per house if everyone is nice.

Yet, as opposed to previous seasons, this coming Christmas Santa may not have more than enough elves for each region, so 4 seconds is the absolute minimum amount of time^* that it will take to deliver presents to any given house, unless there are 0 nice people and 0 naughty people in which case it will take 0 seconds.

Additionally, if even one of the houses has someone on the naughty list, Santa will need at least three elves. If at least one of the houses has someone on the nice list and none of them have people on the naughty list, Santa will need at least two elves. If none of the houses are in the Christmas spirit, any number of elves (including 0) will takes 0 seconds.

On Santa's map, a house is represented by a *, and each house is split by a +. Santa still uses the same maps as in the other challenge, but I'll include documentation about them here.

There will be a number on either side of the house - the one on the left representing the number of naughty people in the house, and the one on the right representing the number of nice people in the house. If there is no number on one side it is interpreted as a 0.

I know it may sound crazy, but some people "don't like Christmas", so sometimes, a house may not have a number on either side of it.

One of Santa's maps could look something like this.

1*3+2*+*5+*+4*7

Let's say Santa has nine elves in his sleigh.

1. (0s) The first house has 1 naughty and 3 nice people. Three of the elves deliver coal, taking five seconds, and six deliver presents, taking four seconds. After five seconds, Santa's sleigh moves to the next house

2. (5s) The second house has 2 naughty and 0 nice people. Six of the elves deliver coal, taking five seconds. After five seconds, Santa's sleigh moves to the next house

3. (10s) The third house has 0 naughty and 5 nice people. Eight of the elves go to deliver four presents (the one that is left behind can't deliver a present). After four seconds, all of the elves are back, and two of them go to deliver the other present (the sleigh must wait for the elves to get back before going to the next house), taking another four seconds

4. (18s) The fourth house is not in the Christmas spirit, so has 0 naughty and 0 nice people, and is skipped

5. (18s) The fifth house has 4 naughty and 7 nice people. This gets a bit complicated...

   I. All nine of the elves go to deliver three gifts of coal (leave t+0s, return t+5s) II. After 5s, they are all back on the sleigh, and three of them go to deliver the last present of coal (leave t+5s, return t+10s) while the other six of them go to deliver three nice presents (leave t+5s, return t+9s).

   III. After four seconds, six of the elves are back and go to deliver three more nice presents (leave t+9s, return t+13s).

   IV. One second after they leave, the three elves that were delivering the coal present get back, and two of them leave to deliver the last nice present (leave+10s, return t+14s)

6. (18 + 14 = 32 seconds) Santa is finished delivering presents to that region.

As we can see, it takes Santa a total of 32 seconds to deliver presents to this region. That was an over-simplified version of one of Santa's maps, though. Normally, Santa's maps have multiple lines, and are in a square shape as to better fit on his list. A normal map might look something like this (a \n at the end of each line)

1*2+*+*4+1*
2*4+3*+1*6+*
*+*+4*2+1*1
*4+*3+1*+2*3
3*10+2*+*5+*

With 26 elves (or any higher amount), it would take Santa 71 seconds.
With 20 elves, it would take Santa 76 seconds.
With 15 elves, it would take Santa 80 seconds.
With 3 elves, it would take Santa 288 seconds.
With 2 elves (or any lower amount), it would be impossible.

Oh, and one more thing — the order in which the elves deliver presents matters (because of the time difference of delivering presents naughty/nice people), so your code should always output the least amount of time that the elves can take delivering presents.

Challenge

Help Santa determine how long it will take for a given number of elves to deliver presents.

Houses

• A house is represented by a *
• Houses are split by +
• The number on the left of the house symbolizes the number of naughty people (no number means 0)
• The number on the right symbolizes the number of nice people (no number means 0)
• There may be newlines (\n) in the input, which should also be handled as a split

Elves

• Santa needs help from three elves for naughty people (coal is much heavier than presents), and it will take these elves five seconds^* to deliver the presents
• Santa needs help from two elves for nice people, and it will take these elves four seconds^* to deliver the presents
• If there is no number on either side of the house, Santa will not visit that house, and therefor it will not take any time (people not in the Christmas spirit don't even deserve coal)

Santa

• Santa must deliver presents to the houses one-by-one
• Santa can not move onto the next house until all of the elves are back on the sleigh and all of the presents have been delivered to that house (we don't want to leave elves behind, now do we?)
• Santa's sleigh doesn't spend any time traveling from house to house (Again, for reasons which I am not at liberty to share)

What to do

Given a map of a houses and a number of elves, print how long it will take Santa to deliver presents to the houses on the map.

_{* (I may not share the amount of time it takes elves to deliver presents. I can neither confirm nor deny that the times included in this challenge are correct)}

Rules

• There are two inputs — the map and the number of elves. The inputs can be either taken as arguments to a function, or from STDIN or equivalent. If taking two inputs is impossible in your language, then and only then may you accept the two inputs as a single input string, delimited by some character not normally in an input (not one of +*\n or 0-9 — the input string can't be ambiguous) e.g. ,.
• The number of elves will always be a non-negative integer (0 is valid)
• The output can either be the return value of a function, or printed to STDOUT or equivalent. If it is impossible for Santa to deliver presents to the given region with a given number of elves, you must output a consistent negative number, or a consistent message without any numbers in it
• Everything printed to STDERR will be ignored, so you may not print the result or the error message to STDERR
• Your program can not crash given an invalid number of elves for a region
• The output should be only the total amount of time it will take Santa to deliver the presents with the given number of elves.
• The output should always be the least amount of time it takes for the elves to deliver presents
• The input will only contain numbers, +, *, and newlines \n (unless you specify another character which the input will include if your language can't take two inputs _{(look at the first rule)})
• Standard loopholes apply

Test Cases

"1*1", 5 elves => 5
"1*1", 3 elves => 9
"1*2", 7 elves => 5
"1*2", 5 elves => 10
"1*2", 3 elves => 13
"2*1", 8 elves => 5
"2*1", 5 elves => 9
"2*1", 3 elves => 14
"1*" , 3 elves => 5
"1*" , 2 elves => (error message)
"*1" , 2 elves => 4
"*1" , 0 elves => (error message)
"*"  , 0 elves => 0

"1*1+1*1",   5 elves => 10
"1*1+1*1",   3 elves => 18
"1*1+*+1*1", 3 elves => 18
"1*2+2*1",   8 elves => 10
"1*2+2*1",   7 elves => 14
"1*2+2*1",   6 elves => 18
"1*2+2*1",   3 elves => 27
"1*2+2*1",   2 elves => (error message)
"*+*+*+*",   2 elves => 0
"*+*+*+*",   0 elves => 0

"1*3+2*+*5+*+4*7", 9 elves => 32

_{(hopefully I got all of that correct)}

Scoring

Santa spends every single day always looking at a lot of things — all of the presents he's going to deliver, all of the elves he has, all of the houses he's delivering presents to... For Santa, the best Christmas present would be being able to see a little bit of a something. For this reason, the shortest submission in bytes wins.

Leaderboard

This is a Stack Snippet that generates both a leaderboard and an overview of winners by language.

To ensure your answer shows up, please start your answer with a headline using the following Markdown template

## Language Name, N bytes

Where N is the size, in bytes, of your submission

If you want to include multiple numbers in your header (for example, striking through old scores, or including flags in the byte count), just make sure that the actual score is the last number in your header

## Language Name, <s>K</s> X + 2 = N bytes

var QUESTION_ID=151568;var OVERRIDE_USER=20634;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(-?\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Answer 1

Ruby, 433 400 bytes

Well, this one is indeed hard, because it turns out the elf scheduling is NP hard.

Also, please be nice, this is my first submission, so I might have missed some obvious optimizations:

->e,h{h.split(/\+|\n/).map{|h|n,g=h.split(?*).map(&:to_i)+[0,0];return-1if(g>0&&e<2)||(n>0&&e<3);([[3,5]]*n+[[2,4]]*g).permutation.map{|j|c=[0]*e;j.map{|q|w,y=q;k=l=0;r=c.map{|x|a=b=0;c[k..e].map{|r|r<=x ?a+=1:break};(t=k+=1).times{c[t-=1]<=x ?b+=1:break};[a,b]};d=r.inject([]){|v,x|v<<l if x[0]>=w;l+=1;v}.min{|a,b|c[a]<=>c[b]};b=d-r[d][1]+1;z=c[d]+y;(b..(b+w-1)).map{|x|c[x]=z}};c.max}.min||0}.sum}

Try it online!

I initially had longer test cases, but because I'm iterating over all possible permutations for the scheduling in some cases it takes to long, so I removed them.

Answer 2

Java (OpenJDK 8), 344 bytes

Elf scheduling is more difficult than I thought so this took a little while, and is pretty long.

Despite that, this has definitely been my favourite challenge to code golf!

(e,d)->{int r=0,x,y,c,p,b,g,m;for(String h:d[0].split("\\+")){d=h.split("\\*",-1);b=new Byte("0"+d[0]);g=new Byte("0"+d[1]);m=-1>>>1;for(y=1;y<=e/3&(x=(e-y*3)/2)>0;c=b/y+(b%y++<1?0:1),p=g/x+(g%x<1?0:1),x=c*5>p*4?c*5:p*4,m=x<m?x:m);for(y=0;b+g>0;b-=c,g-=p){c=e/3<b?e/3:b;x=(e-c*3)/2;p=x<g?x:g;if(c+p<1)return-1;y+=c>0?5:4;}r+=m<y?m:y;}return r;}

Try it online (with all tests)!

Explanation;

Brace yourself: It's a long one

    int r=0,x,y,c,p,b,g,m;               // Define all the variables I need

    for(String h:d[0].split("\\+")){     // Split houses on '+' and loop through them

        d=h.split("\\*",-1);             // Split the current house on '*' using the limit
                                         // to preserve empty strings.

        b=new Byte("0"+d[0]);            // Parse the naughty (b) and nice (g) people
        g=new Byte("0"+d[1]);
        
        m=-1>>>1;                        // Initialise minimum time as max integer using
                                         // overflow
        
        for(y=1;y<=e/3&(x=(e-y*3)/2)>0;  // For each number of elves that can concurrently
                                         // deliver coal, and still leave enough elves to
                                         // deliver presents

            c=b/y+(b%y++<1?0:1),         // Determine the number of runs needed to deliver
                                         // all coal using this number of elves

            p=g/x+(g%x<1?0:1),           // Determine the number of runs needed to deliver
                                         // all presents using this number of elves

            x=c*5>p*4?c*5:p*4,           // Get the maximum time required for the
                                         // delivery of coal or presents

            m=x<m?x:m);                  // If this is less than the current minimum time,
                                         // set it as the minimum time

        
        for(y=0;b+g>0;b-=c,g-=p){        // While there are still people to deliver to;

            c=e/3<b?e/3:b;               // Determine the max amount of coal to deliver

            x=(e-c*3)/2;                 // Determine how many presents can be
                                         // delivered with the remaining elves.

            p=x<g?x:g;                   // If this number is more than nice people
                                         // remaining, just use the nice people remaining

            if(c+p<1)return-1;           // If no presents can be delivered, return the
                                         // error code (-1)

            y+=c>0?5:4;                  // Increase the time by 5 if coal was
                                         // delivered, and 4 if only presents

        }                                // At the end of each loop (see above)
                                         // remove the presents and coal delivered
                                         // from the number of naughty and nice houses

        r+=m<y?m:y;                      // Increment the total time by which ever
                                         // is smaller of the calculated times
    }
    return r;                            // Return the total time

NB: This answer depends on my corrections to the test cases being correct