Quanto tempo levará o Papai Noel para entregar seus presentes?

12

Eu publiquei esse desafio há um tempo atrás, que diz respeito a quantos elfos o Papai Noel precisa para entregar presentes.

Devido ao aumento da população, o Papai Noel está um pouco mais pressionado pelo tempo neste ano. Embora no passado operássemos de forma muito assíncrona, estamos começando a experimentar ser cada vez mais sincronizados. Portanto, Papai Noel precisa saber quanto tempo levará para entregar presentes a cada região com um determinado número de elfos.

O peso do carvão não mudou nos últimos dois anos - ainda é mais pesado que o presente, portanto, o Papai Noel precisa de três elfos por pessoa travessa na casa e de dois elfos por pessoa legal na casa.

Os elfos passam o ano todo treinando no Natal, para que não precisem descansar entre as entregas. Eles só podem entregar presentes para uma casa de cada vez e devem voltar o trenó do Papai Noel e coletar o próximo presente antes de ir para a próxima casa. Por razões que não tenho a liberdade de compartilhar, os elfos não passam o tempo viajando entre o trenó e as casas do Papai Noel (mas só podem viajar quando o trenó do Papai Noel está no telhado), nem o trenó passa o tempo passando de casa em casa. (Trenó do Papai Noel faz necessita de passar de casa em casa, a fim de combustível a cobrar, mas eu já estou dizendo muito).

Os elfos que entregam presentes precisam gastar quatro segundos * cada um entregando os presentes, e os elfos que entregam carvão precisam gastar cinco segundos * cada entregando (de acordo com os regulamentos da Santa Aviation Administration, luvas com pó de carvão sobre eles devem ser incineradas imediatamente após embarcar no trenó, o que leva algum tempo). Além disso, as casas devem ser visitadas na ordem em que estão no mapa, da esquerda para a direita, e os elfos não podem começar a entregar presentes para outras casas até que todos os presentes tenham sido entregues na casa em que estão atualmente.

Se supusermos que o Papai Noel tinha duendes mais do que suficientes para esta região, levaria apenas o tempo necessário para entregar um presente a alguém da lista impertinente, 5 segundos, por casa ou 4 segundos por casa, se todos forem agradáveis.

No entanto, ao contrário das temporadas anteriores, o Natal Papai Noel pode não ter mais do que elfos suficientes para cada região, portanto, 4 segundos é o tempo mínimo absoluto * necessário para entregar presentes a uma casa, a menos que haja 0 pessoas legais e 0 pessoas malcriadas. Nesse caso, levará 0 segundos.

Além disso, se apenas uma das casas tiver alguém na lista travessa, o Papai Noel precisará de pelo menos três elfos. Se pelo menos uma das casas tem alguém na lista legal e nenhuma delas tem pessoas na lista malcriada, o Papai Noel precisará de pelo menos dois elfos. Se nenhuma das casas estiver no espírito natalício, qualquer número de elfos (incluindo 0) levará 0 segundos.

No mapa do Papai Noel, uma casa é representada por a *e cada casa é dividida por a +. O Papai Noel ainda usa os mesmos mapas do outro desafio , mas incluirei documentação sobre eles aqui.

Haverá um número em ambos os lados da casa - o da esquerda representando o número de pessoas malcriadas na casa e o da direita representando o número de pessoas legais na casa. Se não houver um número em um lado, ele será interpretado como um 0.

Eu sei que pode parecer loucura, mas algumas pessoas "não gostam do Natal", então, às vezes, uma casa pode não ter um número em ambos os lados.

Um dos mapas do Papai Noel poderia se parecer com isso.

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

Digamos que o Papai Noel tenha nove elfos no trenó.

  1. (0s) A primeira casa tem 1 pessoa safada e 3 pessoas legais. Três dos elfos entregam carvão, levando cinco segundos, e seis entregam presentes, levando quatro segundos. Depois de cinco segundos, o trenó do Papai Noel se muda para a próxima casa

  2. (5s) A segunda casa tem 2 pessoas impertinentes e 0 legais. Seis dos elfos entregam carvão, levando cinco segundos. Depois de cinco segundos, o trenó do Papai Noel se muda para a próxima casa

  3. (10s) A terceira casa tem 0 impertinentes e 5 pessoas legais. Oito dos elfos vão entregar quatro presentes (o que é deixado para trás não pode entregar um presente). Após quatro segundos, todos os elfos estão de volta e dois deles vão entregar o outro presente (o trenó deve esperar que os elfos voltem antes de ir para a próxima casa), levando outros quatro segundos

  4. (18 anos) A quarta casa não está no espírito natalino, então tem 0 pessoas impertinentes e 0 legais, e é ignorada

  5. (18 anos) A quinta casa tem 4 pessoas impertinentes e 7 legais. Isso fica um pouco complicado ...

    I. Todos os nove elfos vão entregar três presentes de carvão (deixe t + 0s, retorne t + 5s) II. Após 5s, eles estão de volta ao trenó e três deles vão entregar o último presente de carvão (deixe t + 5s, retornam t + 10s) enquanto os outros seis vão entregar três presentes agradáveis ​​(deixe t + 5s, retorne t + 9s).

    III Após quatro segundos, seis dos elfos estão de volta e vão entregar mais três presentes agradáveis ​​(deixe t + 9s, retorne t + 13s).

    IV Um segundo depois que eles saem, os três elfos que estavam entregando o presente de carvão voltam e dois deles saem para entregar o último presente agradável (sair + 10s, retornar t + 14s)

  6. (18 + 14 = 32 segundos ) O Papai Noel terminou de entregar presentes para essa região.

Como podemos ver, o Papai Noel leva 32 segundos para entregar presentes a essa região. Essa foi uma versão simplificada demais de um dos mapas do Papai Noel. Normalmente, os mapas do Papai Noel têm várias linhas e têm uma forma quadrada para melhor se encaixar na lista dele. Um mapa normal pode se parecer com isso (a \nno final de cada linha)

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

Com 26 elfos (ou qualquer quantidade maior), o Papai Noel levaria 71 segundos .
Com 20 elfos , o Papai Noel levaria 76 segundos .
Com 15 elfos , o Papai Noel levaria 80 segundos .
Com 3 elfos , o Papai Noel levaria 288 segundos .
Com 2 elfos (ou qualquer quantidade menor), seria impossível.

Ah, e mais uma coisa - a ordem na qual os elfos entregam apresenta questões (por causa da diferença de horário de entregar presentes para pessoas impertinentes / legais), portanto, seu código sempre deve gerar a menor quantidade de tempo que os elfos podem levar para entregar presentes.

Desafio

Ajude o Papai Noel a determinar quanto tempo levará para um determinado número de elfos entregar presentes.

Moradias

  • Uma casa é representada por um *
  • Casas são divididas por +
  • O número à esquerda da casa simboliza o número de pessoas malcriadas (nenhum número significa 0)
  • O número à direita simboliza o número de pessoas legais (nenhum número significa 0)
  • Pode haver novas linhas ( \n) na entrada, que também devem ser tratadas como uma divisão

Elfos

  • O Papai Noel precisa da ajuda de três elfos para pessoas malcriadas (o carvão é muito mais pesado que os presentes), e esses elfos levarão cinco segundos * para entregar os presentes
  • Papai Noel precisa da ajuda de dois elfos para pessoas legais, e esses elfos levarão quatro segundos * para entregar os presentes
  • Se não houver número em ambos os lados da casa, o Papai Noel não a visitará e, portanto, não levará tempo (as pessoas que não estão no espírito natalício nem merecem carvão).

Papai Noel

  • Papai Noel deve entregar presentes às casas, um por um
  • Papai Noel não pode passar para a próxima casa até que todos os elfos estejam de volta no trenó e todos os presentes tenham sido entregues nessa casa (não queremos deixar os elfos para trás, não é?)
  • O trenó do Papai Noel não passa muito tempo viajando de casa em casa (novamente, por razões que não tenho a liberdade de compartilhar)

O que fazer

Dado o mapa de uma casa e um número de elfos, imprima quanto tempo levará o Papai Noel para entregar presentes às casas no mapa.

* (Posso não compartilhar a quantidade de tempo que os duendes levam para entregar presentes. Não posso confirmar nem negar que os horários incluídos neste desafio estão corretos)

Regras

  • Existem duas entradas - o mapa e o número de elfos. As entradas podem ser tomadas como argumentos para uma função, ou de STDIN ou equivalente. Se não for possível usar duas entradas no seu idioma, então, e somente então, você poderá aceitá-las como uma única sequência de caracteres de entrada, delimitada por algum caractere que normalmente não está em uma entrada (não uma +*\nou 0-9- a sequência de entrada não pode ser ambígua) por exemplo ,.
  • O número de elfos sempre será um número inteiro não negativo (0 é válido)
  • A saída pode ser o valor de retorno de uma função ou impressa em STDOUT ou equivalente. Se for impossível para o Papai Noel entregar presentes para a região em questão com um determinado número de elfos, você deve emitir um número negativo consistente ou uma mensagem consistente sem nenhum número nela
  • Tudo o que for impresso em STDERR será ignorado; portanto, você pode não imprimir o resultado ou a mensagem de erro em STDERR
  • Seu programa não pode travar devido a um número inválido de elfos para uma região
  • A saída deve ser apenas a quantidade total de tempo que o Papai Noel levará para entregar os presentes com o número determinado de elfos.
  • A saída deve sempre ser a menor quantidade de tempo necessária para os elfos entregarem presentes
  • A entrada irá conter apenas números, +, *, e novas linhas \n(a menos que você especifique outro personagem que a entrada vai incluir se o seu idioma não pode ter duas entradas (olhar para a primeira regra) )
  • Aplicam-se brechas padrão

Casos de teste

"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

(espero que eu tenha entendido tudo isso corretamente)

Pontuação

Papai Noel passa todos os dias sempre olhando para muitas coisas - todos os presentes que ele vai entregar, todos os elfos que ele tem, todas as casas para as quais ele entrega presentes ... Para o Papai Noel, o melhor presente de Natal seria capaz de ver um pouco de algo. Por esse motivo, o menor envio em bytes vence .

Entre os melhores

Este é um snippet de pilha que gera um placar de líderes e uma visão geral dos vencedores por idioma.

Para garantir que sua resposta seja exibida, inicie sua resposta com um título, usando o seguinte modelo de remarcação

## Language Name, N bytes

Onde N é o tamanho, em bytes, do seu envio

Se você deseja incluir vários números no seu cabeçalho (por exemplo, pesquisar pontuações antigas ou incluir sinalizadores na contagem de bytes), verifique se a pontuação real é o último número no cabeçalho

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

Mostrar snippet de código

code-golf string Jojodmo
fonte
Eu acho que 288 deve ler 281 : (1+0+0+1+2+3+1+0+0+0+4+1+0+0+1+2+3+2+0+0)*5+(2+0+4+0+4+0+6+0+0+0+2+1+4+3+0+3+10+0+5+0)*4=21*5+44*4=105+176=281(embora eu deva dizer que não li todo o "ensaio"!)
Jonathan Allan
@ JonathanAllan Yea ... Eu acidentalmente gastei muito tempo escrevendo o desafio ... oops ... Enfim, a principal coisa que falta é que o trenó do Papai Noel tenha que esperar que todos os elfos voltem a bordo antes de passar para a próxima casa, portanto, embora somar todos os números e multiplicá-los possa funcionar em alguns casos, ele não funciona na maioria dos casos. Por exemplo, com 9 elfos, a casa 4*7leva 14 segundos (que é coberta pela metade no "ensaio", pouco antes da introdução do mapa 2D), mas (4 * 5) + (7 * 4) = 48
Jojodmo
O valor 288 é, por exemplo, com 3 elfos, então eles sempre precisam executar o golpe completo naughty*5+nice*4em cada casa, certo? (note que não existe 4*7nesse exemplo)
Jonathan Allan
Os elfos sempre tiram o carvão do caminho primeiro (como no seu exemplo) ou agendam com eficiência? Por exemplo, se o mapa fosse 5*15e houvesse 9elfos, levaria (mínimo) 20 segundos ou 22 segundos? Veja estas representações textuais para ver uma ilustração desse exemplo.
Jonathan Allan
EDIT acima 5*15deve ler 4*15.
Jonathan Allan

Respostas:

4

Ruby , 433 400 bytes

Bem, este é realmente difícil, porque acontece que o agendamento dos elfos é NP difícil.

Além disso, por favor, seja gentil, esta é minha primeira submissão, por isso talvez eu tenha perdido algumas otimizações óbvias:

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

Experimente online!

Inicialmente, tive casos de teste mais longos, mas como estou repetindo todas as permutações possíveis para o agendamento, em alguns casos leva muito tempo, então os removi.

elyalvarado
fonte
2
Bem-vindo ao PPCG! Você definitivamente pegou um desafio difícil para a sua primeira resposta
Jo rei
2

Java (OpenJDK 8) , 344 bytes

A programação dos elfos é mais difícil do que eu pensava, então isso levou um pouco de tempo e é bastante longo.

Apesar disso, esse foi definitivamente o meu desafio favorito em codificar golfe! 

(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;}

Experimente online (com todos os testes)!

Explicação;

Prepare-se: é longo

    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: Essa resposta depende de minhas correções nos casos de teste estarem corretas

Luke Stevens
fonte
Eu acho (e-y*3)/2-> e-y*3>>1salva um byte. (O mais provável é também aplicável a (e-c*3)/2.)
Jonathan Frech
runTest("1*4",5,12);Falha (você entendeu "1*4", 5 elves => 13 FAILED. Fiquei impressionado com a forma como seu algoritmo era tão bom para agendar em tão poucos bytes, então o executei em todas as combinações possíveis de 0 a 7 (elfos, travessos e agradáveis) e encontrei apenas algumas onde ele não dar o melhor momento Este é o menor combinação foram falhar BTW, a lógica incrível com a programação, por um longo tempo eu não tinha idéia de como você fez isso...
elyalvarado