Policía de manhattan

Introducción

Usted es el jefe de policía de la policía de Nueva York y se le ha encomendado la tarea de posicionar a los oficiales de policía para que todas las calles estén patrulladas. Sin embargo, su escuadrón tiene poco personal, lo que significa que necesita posicionar la menor cantidad de oficiales posible.

Desafío

Dado un mapa de bloques, debe devolver el menor número de oficiales necesarios para asegurar las calles.

Reglas

Hay tres tipos de oficiales de policía: un policía L, un policía T y un policía cruzado. El policía T solo puede ver en tres direcciones. El policía L puede ver dos calles que son perpendiculares. El policía cruzado puede ver las cuatro calles.

El mapa se proporcionará a través de argv o STDIN como números separados por espacios. Los números representan el número de bloques en cada columna. Por ejemplo:

La entrada 2 1representa el siguiente mapa:

La entrada 3 1 2 4representa el siguiente mapa:

Un oficial de policía solo puede ser ubicado en una intersección y su vista solo puede ser a lo largo del costado de una cuadra (los policías no pueden mirar hacia áreas deshabitadas).

Un policía solo puede ver una cuadra y no puede mirar a lo largo de una calle donde está mirando otro oficial de policía, lo que significa que las líneas de visión no deben superponerse.

Ejemplos

Entrada: 2 1

Salida: 4

Entrada: 2 2

Salida: 4

Entrada: 3 1 4 1 5 9

Salida: 22

Victorioso

El código más corto gana.

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

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

Toma la entrada en el mismo formato que en cuestión.

ACTUALIZACIÓN : Se corrigió el algoritmo para casos de prueba similar a lo que señaló @nutki. Aunque hizo que el código tuviera casi el doble de tamaño, intentará jugarlo ahora que está solucionado.

Cómo funciona (Ligeramente incompleto, agregará la 2 1 2explicación de paridad más adelante)

Tan pronto como vi esta pregunta, supe que habría una fórmula matemática para obtener la respuesta. Después de probar un par de combinaciones, pensé que la fórmula es2 * Number of blocks - Number of shared streets

Vamos a comprobar es por 2 1caso:

2 * 3 - 2 = 4

Correcto.

Vamos a ver por 3 1 2 4caso:

2 * 10 - 10

Corregir de nuevo. Sí, entonces el código es

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

Ahora intentemos esto con algunos ejemplos más:

3 3

Salida:

2 * 6 - 7 = 5

Pero espera, la respuesta real es 6

Probemos otro:

5 5

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

¿Ves el patrón?

Para cada N Npar de bloques, donde N es un número entero positivo mayor que 2, requiero float((N+1)/2)-1más policía aparte de la fórmula anterior. Vamos a verificarlo de nuevo:

5 5 3

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

En el ejemplo anterior, tenemos 1 5 5par y 1 3 3par (de los 5 3bloques)

Probemos otro ejemplo

5 5 4 4

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

Usted debe estar pensando que sólo hay 5 5, 3 3y 3 3los pares (a partir de bloques 5 5, 5 4y 4 4resp.), Por lo tanto, sólo 4 policías extra que sea necesario, pero hay un par más.

De los bloques 4 4, utilizamos solo 3 3para tener 1 1libre, esto constituye otro 3 3par de bloques que se puede visualizar usando la imagen a continuación:

Los contorneados en rojo son los pares habituales, el contorneado en azul es el par perpendicular del que estoy hablando anteriormente.

Es un poco difícil de explicar, ya que mientras los contorneados rojos solo comparten 1 lado del par, el azul también comparte 1 lado + 1 bloque. Pero esta lógica funciona para todas las combinaciones de bloques.

El código ahora es simplemente calcular eso.

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

Tenga en cuenta que 2 * Number of blocks - Number of shared sidestambién se puede escribir como Number of blocks + Number of columns - Number of shared sides between adjacant columns

Pruébalo en línea aquí