8
\$\begingroup\$

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.

\$\endgroup\$
6
  • 3
    \$\begingroup\$ How far can a cop see? I.e., if I put a cop on an intersection, can he see all the way down both the streets? \$\endgroup\$
    – marinus
    Oct 6, 2014 at 17:46
  • 6
    \$\begingroup\$ What stops me from only using cross cops? It doesn't seem to matter whether a cop looks in uninhabitated areas or scans the same area as another cop as long as at least a T or L cop would be necessary there anyway. \$\endgroup\$
    – Ingo Bürk
    Oct 6, 2014 at 18:04
  • \$\begingroup\$ If you add the condition that sight lines can not overlap and cops can't look in uninhabited areas, this would be a bit more challenging. (doesn't help the story's plausibility, but...) \$\endgroup\$
    – Geobits
    Oct 6, 2014 at 18:20
  • 2
    \$\begingroup\$ I am picturing Chief Wiggum, Lou and Eddie. \$\endgroup\$ Oct 6, 2014 at 20:22
  • \$\begingroup\$ Clearly people get overly nervous if they see too many cops next to each other. \$\endgroup\$
    – Tally
    Oct 8, 2014 at 11:10

1 Answer 1

7
+100
\$\begingroup\$

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:

enter image description here

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

\$\endgroup\$
8
  • 1
    \$\begingroup\$ This produces the correct output for all of the tests I've tried so far. \$\endgroup\$
    – Beta Decay
    Oct 6, 2014 at 19:30
  • \$\begingroup\$ Why's input 2 2 2 giving the solution 5? Could you please explain how a 5 set combination is possible? \$\endgroup\$ Oct 6, 2014 at 20:31
  • \$\begingroup\$ Check 4 4 4 4 as well. The routine gives 11, but I can't see any way of doing it with fewer than 12. \$\endgroup\$
    – COTO
    Oct 6, 2014 at 20:42
  • \$\begingroup\$ I know I'm a bit late, but how does this work? \$\endgroup\$
    – Beta Decay
    Nov 9, 2014 at 0:41
  • \$\begingroup\$ This gives 18 for 2 2 1 1 2 2 1 2 2 1 1 2 2 my counter example for @FireFly solution. However I cannot see anything better than 19. Can you show the placement for this test case? \$\endgroup\$
    – nutki
    Nov 15, 2014 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.