Polícia de Manhattan

Introdução

Você é o chefe de polícia da polícia de Nova York e foi encarregado de posicionar policiais para que todas as ruas sejam patrulhadas. No entanto, seu esquadrão tem poucos funcionários, o que significa que você precisa posicionar o mínimo de oficiais possível.

Desafio

Dado um mapa de quarteirões, você deve devolver o menor número de policiais necessário para proteger as ruas.

Regras

Existem três tipos de policiais: um policial L, um policial T e um policial cruzado. O policial T pode ver apenas em três direções. O policial L pode ver abaixo duas ruas que são perpendiculares. O policial pode ver as quatro ruas abaixo.

O mapa será fornecido via argv ou STDIN como números separados por espaço. Os números representam o número de blocos em cada coluna. Por exemplo:

Entrada 2 1representa o seguinte mapa:

Entrada 3 1 2 4representa o seguinte mapa:

Um policial só pode ser colocado em um cruzamento e sua visão pode estar ao lado de um quarteirão (os policiais podem não olhar para áreas desabitadas).

Um policial pode ver apenas um quarteirão e não pode olhar ao longo de uma rua onde outro policial está olhando, o que significa que as linhas de visão não devem se sobrepor.

Exemplos

Entrada: 2 1

Resultado: 4

Entrada: 2 2

Resultado: 4

Entrada: 3 1 4 1 5 9

Resultado: 22

Ganhando

O código mais curto vence.

CJam, 68 61 84 ... 59 49 48 79 bytes

l~]__,+:+M@{:Ze<:X2/)_2*X-@+@@-\Z}*;[YY]/_,(\R*_,,:)W%{2\2*1a*+2+/_S*\,(@+\}/;+

Recebe entrada no mesmo formato que em questão.

UPDATE : Corrigido o algoritmo para casos de teste semelhante ao indicado por @nutki. Embora tenha feito o código quase dobrar de tamanho, ele tentará jogar golfe agora que está consertado.

Como funciona (ligeiramente incompleto, adicionará a 2 1 2explicação da paridade mais tarde)

Assim que vi essa pergunta, soube que haveria uma fórmula matemática para obter a resposta. Depois de tentar algumas combinações, percebi que a fórmula é2 * Number of blocks - Number of shared streets

Vamos verificar é o 2 1caso:

2 * 3 - 2 = 4

Corrigir.

Vamos verificar o 3 1 2 4caso:

2 * 10 - 10

Corrija novamente. Yipee, então o código é

l~]:L:+2*L:(:+L(+-[{_@e<}*]:+-

Agora vamos tentar isso em mais alguns exemplos:

3 3

Resultado:

2 * 6 - 7 = 5

Mas espere, a resposta real é 6

Vamos tentar outra:

5 5

2 * 10 - 13 = 7 // Answer is 9 instead.

Você vê o padrão?

Para cada N Npar de blocos, onde N é um número inteiro positivo maior que 2, eu exijo float((N+1)/2)-1um policial extra além da fórmula acima. Vamos verificar novamente:

5 5 3

2 * 13 - 18 = 8 // Answer is 11

No exemplo acima, temos 1 5 5par e 1 3 3par (dos 5 3blocos)

Vamos tentar outro exemplo

5 5 4 4

2 * 18 - 27 = 9 // Answer is actually 14

Você deve estar pensando que há somente 5 5, 3 3e 3 3pares (de blocos 5 5, 5 4e 4 4resp.), Portanto, apenas 4 policiais extras necessários, mas há mais um par.

A partir dos blocos 4 4, usamos apenas 3 3para termos 1 1livre, isso constitui outro 3 3par de blocos que pode ser visualizado usando a imagem abaixo:

O vermelho delineado são os pares usuais, o azul delineado é o par perpendicular do qual estou falando acima.

É meio difícil de explicar, enquanto o vermelho descrito está apenas compartilhando um lado do par, o azul está compartilhando um lado + 1 bloco também. Mas essa lógica funciona para todas as combinações de blocos.

O código agora está simplesmente calculando isso.

l~]__                        "Read the input numbers, convert to array and make two copies";
     ,+                      "Get the number of columns and add that to the block array";
       :+                    "Sum the array elements to get number of blocks + columns";
         M@                  "Push empty array to stack and rotate input array to top";
{                         }* "Run this block for each pair in the block array";
 :Ze<:X                      "Store the later block size in Z, and minimum of two in X";
       @\-                   "Rotate swap and subtract shared sides from total sum";
          X)Y/(:T+           "Increment halve and decrement. Store in T and add to sum";
                  XTY*-      "Find unused blocks from this pair for perpendicular pairs";
                       @+    "Add unused blocks to the array M";
                         Z   "Push Z to stack to be used in next iteration";
           ;[YY]             "Pop the last pushed Z and push array [2 2] to stack";
                /,(+         "Check how many perpendicular pairs exist, add to total sum";

Observe que 2 * Number of blocks - Number of shared sidestambém pode ser escrito como Number of blocks + Number of columns - Number of shared sides between adjacant columns

Experimente online aqui