ID:103719
 
How many of you can solve the problem below?

The goal is to come up with a 100% coverage solution that does not use the trivial brute force approach.

If the response to this challenge is high and serious, I will morph this into a contest and offer prizes (e.g. cash, memberships, maybe some BYOND swag).

You are the leader of a base and in charge of defending it from hordes of
zombies. It gets tough though as the base is owned by a major corporation
and will only pay you based on financial performance, but you try your best
to kill the zombies in an economical fashion.

Zc number zombies attack you straight on and at a constant speed, that is,
the zombies stay in their initial column and any cluster of zombies in a row
stay in the same row.


________Zombie Horde___________
|   ZZ                         |
|      ZZZ                     |
|      ZZZ                     |           Attack
|              ZZZZZZ          |          Direction
|              ZZZZZZ          |              |
|              ZZZZZZ          |              |
|                              |              V
|                              |
|                              |
|                              |
|______________________________|

               You


You have two weapons at your disposal: one will take out entire rows of
zombies as they attack you, the other will take out entire columns of
zombies. You only fire the row weapon N number of times. The column weapon is
owned by your company and they would like you to fire this weapon as little
as possible -- they only reward you when you fire the weapon the minimum
possible times.

Using the above example, let's say N = 1:

________Zombie Horde___________
|   ZZ                         | @ Row weapon
|      ZZZ                     |
|      ZZZ                     |           Attack
|              ZZZZZZ          |          Direction
|              ZZZZZZ          |              |
|              ZZZZZZ          |              |
|                              |              V
|                              |
|                              |
|                              |
|______________________________|

The row weapon should be fired at the row of zombies in the back so that you
only have to fire the column weapon 9 times.

Let's say N = 2:

________Zombie Horde___________
|   ZZ                         |
|      ZZZ                     | @ Row weapon 1
|      ZZZ                     | @ Row weapon 2
|              ZZZZZZ          |
|              ZZZZZZ          |
|              ZZZZZZ          |
|                              |
|                              |
|                              |
|                              |
|______________________________|

The row weapon should be fired at the pair of rows containing three zombies so
that you only have to fire the column weapon 8 times.

Let's say N = 3:

________Zombie Horde___________
|   ZZ                         |
|      ZZZ                     |
|      ZZZ                     |
|              ZZZZZZ          | @ Row weapon 1
|              ZZZZZZ          | @ Row weapon 2
|              ZZZZZZ          | @ Row weapon 3
|                              |
|                              |
|                              |
|                              |
|______________________________|

The row weapon should be fired at the three rows containing six zombies each so
that you only have to fire the column weapon 5 times.

Problem name: Zombies

Input format:
* Line 1: A single integer: N
* Line 2..Zc+1: Coordinate locations of zombies

Sample Input:
3
0 3
0 4
1 6
1 7
1 8
2 6
2 7
2 8
3 14
3 15
3 16
3 17
3 18
3 19
4 14
4 15
4 16
4 17
4 18
4 19
5 14
5 15
5 16
5 17
5 18
5 19


Output Format:
* Line 1..N: "Row " & Row coordinate to fire row weapon.
* Line N+1: Number of columns to fire column weapon.

Sample Output:
Row 3
Row 4
Row 5
5

Objectives:
* Shortest computation time
* Best coverage

Notes:
There is a very obvious brute force way of minimizing the use of the column
weapon. This guarantees maximizing coverage at the great expense of computation.
This reminds me of something I did in my C++ class my sophomore year of High School. Fun stuff but I know I won't be able to do this. Feels bad man.
*cough* skip *cough*
lulz
Could you increase the fontsize of your preformatted text a little bit?
Airjoe wrote:
Could you increase the fontsize of your preformatted text a little bit?

Done!

Credit to you Joe for the first C4RPOB.
An excellent acronym!


I'll take a whack this coming weekend when I have some free time. Hopefully someone doesn't beat me!
Do the zombie coordinates have any upper bounds?
Unknown Person wrote:
Do the zombie coordinates have any upper bounds?

Technically, no since a solution should converge regardless of zombie count or zombie location. But, just so I don't belabor the exercise try a simple 64x64 grid -- again remember that the algorithm should easily expand beyond that.

This is a trick question. Clearly the most cost-effective solution is getting the heck out of there on one of the company's private jets. Or is the rent too damn high for those?
Do you have to fire the row gun "N" number of times? Just wondering, because one could technically make it more cost efficient by not firing, if the number of columns[at the end] will remain unchanged. If that makes sense.

And, will the zombies appear in clean format? Or, would it be better if I took under the assumption that they are of utter randomness, only staying in their initial column?

I'm going to be taking a crack at this; I'll see if I can't figure out something nice :)
Couldn't one method be, creating a matrix of boolean values(Since the zombie speed is the same, thus it has collective shape relative to no background). Afterwards, have a temporary list, and define certain methods such as "Column-Friends()" and what not.

Now, start with the row that has the most "Row-Friends", then make sure no zombie in that row has "Column friends" exceeding N-1. Also, make sure the overall "friends" stay bound within N-1 possible rows(Thus the purpose of the temp list)

If they do not, you start on the second-largest. So on, so forth, until you find one that completes it thoroughly. Once completed, you go on to repeat this process with a new "N", where N = InitialValue-ListValue, where List value is the current value before it was "trashed".

If the process can not be done, it means use of the row gun cannot "change" the number of times the column gun needs to be used.

This is on the assumption that those "rectangular clusters" of zombies are simply best-case scenarios of randomness. If rectangles exist, like above, much simpler methods can be used.

This is not the "best" way(Least I doubt it is) - But it is better than brute-force. It will return a value, thus skipping over many other "combinations", without testing them.

This method also worked with the above examples very well. Try N=4 or 5. In fact, I made my own little ones on my white-board.

If N=4, it will take out the three rows, from when N=3, then the new "N"=1. Now it takes out the one from N=1. Thus giving you only 3 columns that the Column Gun must hit.

Haha, I have not taken any Computer Science classes in awhile, nor optimization. I am currently thinking its better to have a couple of processes going at once. I wish I knew the names of some of those things.. I hate using "list" when I do not necessarily mean array.
Interesting, I look forward to the proposed solutions at the end, be it competition or otherwise.
It's helpful to look at the solution as a recursive one. While going out, I came up with a number of solutions, but none of them very elegant (no blatant brute-forcing, but very uninspired, I must say). One obvious thing to note is that columns with more than N zombies should be ignored, and this can make cases such as the sample one here very trivial. I'd like to know what progress Alathon, Stephen and Unknown Person made, if you guys tackled it already.
Toadfish wrote:
It's helpful to look at the solution as a recursive one. While going out, I came up with a number of solutions, but none of them very elegant (no blatant brute-forcing, but very uninspired, I must say). One obvious thing to note is that columns with more than N zombies should be ignored, and this can make cases such as the sample one here very trivial. I'd like to know what progress Alathon, Stephen and Unknown Person made, if you guys tackled it already.

While I do find the problem interesting and I plan to give it a shot, its going to be a bit before I have time to consider any serious implementations; I have a two week exam period right now in computer architecture and human-computer interaction, so my mind is elsewhere ;)

There are some interesting ways to look at the problem if you look at it as a plane-sweep with a custom-ordered heap structure; in other words, treating it as a problem of computational geometry. That might be slightly overkill for this problem, however - I haven't written anything down and only run through stuff in my head, so I can't say whether its possible to squeeze this down into an n lg n time, and I haven't looked at how the brute-force method scales yet.

Although I haven't done any induction to figure this out, the problem doesn't immediately seem to exhibit any of the properties that you'd like for greedy programming, dynamic programming or divide and conquer stereotypical solutions. I might take that back when I actually take a look at the problem.
Fire the column weapon once per column. You kill all zombies. Company angry? Quite possibly. World saved? Yes. Computation time? Minimal. Brute force? Not really. Serious answer? Not at all.
Chidori123 wrote:
...

You are thinking of a lot of the right and relevant things about the problem. I'm eager to see some of your pseudo code!

Alathon wrote:
That might be slightly overkill for this problem, however - I haven't written anything down and only run through stuff in my head, so I can't say whether its possible to squeeze this down into an n lg n time, and I haven't looked at how the brute-force method scales yet.

One thing to consider, with the amorphous counts of Zc and N, the data structure where you hold the coordinates will be enormously important. For the data structure, you can probably achieve worst case n log n performance for node searching, insertion, and deletion.
Bootyboy wrote:
...

Actually, I just typed that as to get someone started to prove me wrong. I must say I like the possible solutions that others are giving. Haha, I have the math skills, just not the computer science skills. Pseudo-coding would be the best I could do.

I was thinking the same thing about the coordinates actually, I honestly could not find a "elegant" method that would account for the worst-cases.

The best I came up with is a sort of goes process through from the "largest" to "smallest" amount of zombies in a row, taking into considering contingencies on N, and immediately deeming the row "non-worthy" if it breaks one of two rules. This is a rather "vulgar" looking way, from how I wrote it out.

You could make it recursive, but I'd say it plays on the general idea I wrote, simply returning a value that does the "recursion" with a different starting value. Rinse, Wash, Repeat - Until successful.

I am thinking, currently, it would be better to have a "memory-bank" for the "failed" attempts. I just thought of it, and I will think of a better way to put it in words. Basically, it is like this: The initial search starts at the row with largest zombies, from left to right - Ending if it fails two conditions. Afterwords, the search will remain going for the "second highest", etc - But the search left-right will not be the same. Instead, it will set about a form of priority queue for searching - Thus speeding up the "Will this work out". It skips over lots of unneeded element searches[Not doing left-right], based on the previous failures. The beauty is, the failures will only have to be listed in relation to the column, and not coordinates - Holding true/false, then seeing if the coordinate exists within the row being looked at. If it exists, it utterly skips the search. Its sort of an existence tester. Thus, initially it starts out "slow", yet speeds up. Seems good with large values of dimensions and zombies.

Also, I suppose it would be good to realize that there are "bounds" for the amount of times the column gun can be used, can be reduced[As long as N does not equal the amount of rows]. This can help tell how many times a process must be done with "N", if one process is completes, if it will work again, etc.

The above has bounds of: [2,6](For the first process) - It helps when, lets say, you have "N", and it goes through and you find out it is only relevant to use the row-gun once and it takes out the lower bound. In such cases, the new "N" will still be unable to complete the new lower-bound - Thus no reason to try the process again. It simply cuts done extra searches, using this method.
Well I just tried this out, and I think i ended up somewhere between n^2 and n^3. I might polish it up, but I think it works. I just need to test it out more.
Page: 1 2