Manhattan Police

Question

Introduction

You are the police chief of the NYPD and you have been tasked to position police officers so that all of the streets are patrolled. Your squad is short-staffed, however, meaning that you need to position as little officers as possible.

Challenge

Given a map of blocks, you must return the smallest number of officers needed to secure the streets.

Rules

There are three types of police officers: an L cop, a T cop and a cross cop. The T cop can see in three directions only. The L cop can see down two streets which are perpendicular. The cross cop can see down all four streets.

The map will be supplied via argv or STDIN as space separated numbers. The numbers represent the number of blocks in each column. For example:

Input 2 1 represents the following map:

Input 3 1 2 4 represents the following map:

A police officer may only be placed at an intersection and its view may only be along the side of a block (cops may not look into uninhabited areas).

A cop can only see for one block and cannot look along a street where another police officer is looking meaning that sight lines must not overlap.

Examples

Input: 2 1

Output: 4

Input: 2 2

Output: 4

Input: 3 1 4 1 5 9

Output: 22

Winning

The shortest code wins.

Answer 1

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

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

Takes input in the same format as in question.

UPDATE : Fixed the algorithm for test cases similar to what pointed out by @nutki. Although it made the code almost double in size, will try to golf it now that its fixed.

How it works (Slightly incomplete, will add the 2 1 2 parity explanation later)

As soon as I saw this question, I knew that there would be a mathematical formula to get the answer. After trying a couple of combinations, I figured that the formula is 2 * Number of blocks - Number of shared streets

Lets check is for 2 1 case:

2 * 3 - 2 = 4

Correct.

Lets check for 3 1 2 4 case:

2 * 10 - 10

Correct again. Yipee, so the code is

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

Now lets try this on some more examples:

3 3

Output:

2 * 6 - 7 = 5

But wait, the actual answer is 6

Lets try another:

5 5

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

You see the pattern ?

For every N N block pair, where N is positive integer greater than 2, I require float((N+1)/2)-1 extra cop apart from the formula above. Lets verify it again:

5 5 3

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

In the above example, we have 1 5 5 pair and 1 3 3 pair (from the 5 3 blocks)

Lets try another example

5 5 4 4

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

You must be thinking that there are only 5 5, 3 3 and 3 3 pairs (from blocks 5 5, 5 4 and 4 4 resp.) , thus only 4 extra cops required, but there is one more pair.

From the blocks 4 4, we used up only 3 3 so we have 1 1 free, this makes up another 3 3 block pair which can be visualized using the image below:

The red outlined are the usual pairs, the blue outlined is the perpendicular pair which I am talking about above.

It's kind of hard to explain as while the red outlined are just sharing 1 side of the pair, the blue one is sharing 1 side + 1 block too. But this logic works for all block combinations.

The code now is simply calculating that.

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

Note that 2 * Number of blocks - Number of shared sides can also be written as Number of blocks + Number of columns - Number of shared sides between adjacant columns

Try it online here