彼のプレゼントを届けるのにどれくらいの時間がかかりますか?

私はサンタがプレゼントを配達する必要がある何人のエルフに関するこの挑戦を少し前に投稿しました。

人口増加のために、今年はサンタさんがもう少し時間をかけられました。以前は非常に非同期で動作していましたが、私たちはますます同期化することで実験を始めています。だから、サンタは、与えられた数のエルフでそれぞれの地域にプレゼントを配達するのにどれくらいかかるか知る必要があります。

石炭の重量は過去2年間で変化していません –
それはまだプレゼントよりも重いので、サンタは家のいたずら人1人につき3人のエルフと家の人には2人のエルフが必要です。

エルフはクリスマスのために一年中トレーニングをしているので、配達の間に休憩は必要ありません。彼らは一度に1軒の家にのみプレゼントを配達することができ、次の家に行く前にサンタのそりに戻り、次の贈り物を集める必要があります。私が共有する自由がない理由で、エルフはサンタのそりと家の間を移動する時間を費やすことはありません(しかし、サンタのそりが屋根の上にあるときのみ旅行することができます)。
(サンタのぬいぐるみは、燃料を回収するために家から家に移動する必要がありますが、あまりにも多くのことを言っています)。

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.

もしサンタがこの地域のために十分な数のエルフを持っていたとすれば、いたずらリストに載っている人にプレゼントを渡すのにかかる時間は、5秒、1人、4秒です。

しかし、これまでの季節とは異なり、このクリスマスサンタは、各地域に十分な数のエルフを持っていない可能性があります。したがって、4秒は、どのプレゼントにでもプレゼントを配達するのに必要な
* 0人の素敵な人と0人のいたずら人がいない限り、与えられた家には0秒かかるでしょう。

さらに、家の中にもいたずらリストに誰かがいる場合、サンタは少なくとも3人のエルフを必要とします。少なくとも1つの家に素敵なリストに誰かがいて、誰にもいたずらリストに人がいない場合、サンタは少なくとも2人のエルフを必要とします。クリスマスの精神に恵まれない家がいない場合、0を含む任意の数のエルフが0秒かかります。

サンタの地図では、家は * で表され、各家は +
で分割されます。サンタは引き続き他の課題と同じマップを使用していますが、ここではそれらに関するドキュメントを取り上げます。

家の両側に番号があります –
左側のものは、家のいたずら人の数を表し、右側のものは家の素敵な人の数を表します。片側に数字がない場合、0と解釈されます。

私はそれが狂ったように聞こえるかもしれないことを知っていますが、一部の人々は
“クリスマスが好きではありません”ので、時には家はそれの両側に数字を持っていない場合があります。

サンタの地図の1つは、このようなものに見えるかもしれません。

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

サンタさんには9個のエルフが並んでいるとしましょう。

  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.

ご覧のとおり、この地域にサンタをプレゼントするには、サンタには
32秒となります。しかし、それはサンタの地図のうちの一つの単純化されたバージョンでした。通常、サンタの地図には複数の線があり、リストに合わせるために正方形になっています。法線マップは次のようになります(各行の最後に
n

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.

チャレンジ

指定された数のエルフがプレゼントを配達するのにどれくらいの時間がかかるかを判断するのに役立ちます。

住居

  • 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

エルフ

  • サンタさんはいたずらな人のために
    3人のエルフの助けが必要であり(石炭はプレゼントよりも重い)、これらのエルフは
    5秒 * プレゼントを送る
  • サンタさんは素敵な人のために 2人のエルフの助けが必要です。プレゼントを届けるには
    4秒 * >
  • 家の両側に番号がない場合、サンタはその家を訪れることはないため、時間がかかりません(クリスマスの趣味でない人は石炭に値する人でもありません)。

サンタ

  • サンタは家に一つずつプレゼントを届けなければなりません
  • すべてのエルフが背中に戻り、すべてのプレゼントがその家に届けられるまで、サンタは隣の家に移動できません(私たちはエルフを後ろに残したくはありません。
    >
  • サンタのぬいぐるみは、家から家まで旅する時間を費やすことはありません(私は自由に共有することはできません)。

対処方法

家の地図とエルフの数があれば、地図上の家にプレゼントを配達するのにどれくらいの時間がかかるでしょうか。

* (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 チャレンジ are correct)

ルール

  • 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

テストケース

"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

(うまくいけば私はそれがすべて正しいです)

スコアリング

サンタさんは毎日、常にたくさんのものを探しています。彼が提供するすべてのプレゼント、彼が持っているすべてのエルフ、彼が提供しているすべての家がプレゼントします…サンタにとって、最高のクリスマスプレゼントは少しのものを見ることができるでしょう。このため、バイト単位での最短送信が勝つ

リーダーボード

This is a Stack Snippet that generates both a リーダーボード and an
overview of winners by language.

あなたの回答が確実に表示されるように、次のMarkdownテンプレートを使って見出しで回答を開始してください

## Language Name, N bytes

Nはあなたの投稿のサイズ(バイト単位)です。

ヘッダーに複数の数字を含める場合(たとえば、古いスコアを打つか、またはバイト数のフラグを含めるなど)、実際のスコアがヘッダーの最後の番号であることを確認してください

## Language Name, K X + 2 = N bytes

<div class=”snippet” data-lang=”js” data-hide=”true”
data-console=”false” data-babel=”false”> <div
class=”snippet-code snippet-currently-hidden”>

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="

"+e.body.replace(OVERRIDE_REG,"")+"

")});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;/s.lang?1:e.langs*([^n,]*[^s,]),.*?(-?d+)(?=[^nd<>]*(?:<(?:s>[^n<>]*</s>|[^n<>]+>)[^nd<>]*)*</hd>)/,OVERRIDE_REG=/^Overrides*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"> 

リーダーボード

<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"> 

Winners by Language

<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>Link</td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td>Link</td></tr></tbody> </table>

</div> </div>

ベストアンサー

Ruby, 433 bytes

まあ、これは実際には難しいです、それはelfスケジューリングがNP困難であることが判明したからです。

また、これは私の最初の提出物ですので、私はいくつかの明らかな最適化を見逃しているかもしれません。

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

ruby – オンラインで試す “>オンラインで試してみてください!

私は当初、より長いテストケースを持っていましたが、スケジューリングのすべての可能な順列を繰り返しているので、時間がかかることがあるため、取り除きました。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です