Give each soldier some ammo :)

Question

Given a problem:

You have a certain amount of soldiers.

Each soldier has a given rank (some are officers, sergeants, etc). Now they are to go and kill some guys.

You have a limited amount of ammunition. Depending on the rank, each person is given a box of ammunition. The soldiers are standing in a straight line.

The person with a higher rank has to be given more ammunition if a person of lower rank is next to him.

Each person has to be given at least one box.

Example: using numbers from 1 upwards to represent rank: 4 2 3 2 2 1 3 6. the equivalent boxes of ammunition are: 2 1 2 1 2 1 2 3.

The fastest way for me to come up with the list of ammunition is to take the first three ranks and compare them to each other (i.e. from the example, I pick 4 2 3 ).Next I increment by one (i.e. 2 3 2) and make a comparison again. Obviously, this takes a lot of time.Is there a faster way?

NOTE: Soldiers with same rank standing next to each other don't care how much ammunition each has.

soldier_num = int(input())
i = 0
rating_array = []
ammo_array = []
can_can = soldier_num
while(i < soldier_num):
    rating_array.append(int(input()))
    ammo_array.append(1)
    i += 1
i = 0
while(i < soldier_num):
    if(i == 0):
        if((rating_array[i] > rating_array[i+1]) and (ammo_array[i] <= ammo_array[i+1])):
            ammo_array[i] += 1
            i = i-1
            can_can += 1

    if(0<i<(soldier_num-1)):
        if((rating_array[i] > rating_array[i+1]) and (ammo_array[i] <= ammo_array[i+1])):
            ammo_array[i] += 1
            i = i-1
            can_can += 1

        elif((rating_array[i] > rating_array[i-1]) and (ammo_array[i] <= ammo_array[i-1])):
           ammo_array[i] += 1
            i = i-1
            can_can += 1

        elif((rating_array[i] < rating_array[i-1]) and (ammo_array[i] >= ammo_array[i-1])):
            ammo_array[i-1] += 1
            i = i-1
            can_can += 1

        elif((rating_array[i] < rating_array[i+1]) and (ammo_array[i] >= ammo_array[i-1])):
            ammo_array[i+1] += 1
            i = i-1
            can_can += 1

    i += 1
    if(i == (soldier_num-1)):
        if((rating_array[i] > rating_array[i-1]) and (ammo_array[i] <= ammo_array[i-1])):
            ammo_array[i] += 1
            can_can += 1



print(can_can)

In other word you haven't tried to do your homework/test question yet. Show some code. — Back2Basics, Oct 31 '13 at 15:21
StackOverflow members resent being given more homework than they already have; Asking us to solve your homework annoys us. But we're happy to help you solve the problem yourself. What you have to do is tell us what you think the solution should be, how you've tried to achieve it, and maybe some guesses at how it *should* be solved. Then, we won't feel like we're just doing your work for you, and we'll be happy to help :) — jwarner112, Oct 31 '13 at 15:25
@Back2Basics: So now that I've posted my code, any sugestions? — Nwaiwu Gilbert, Oct 31 '13 at 15:40
I've seen this question here, but my search-skill failed me. It was about giving raises to employees based on performance reports. Swap raises/bullets and rank/report and it's the same thing. Maybe someone else can find it? — Geobits, Oct 31 '13 at 15:50
@Geobits:do you have any personal opinion of the eproblem? I tried looking — Nwaiwu Gilbert, Oct 31 '13 at 16:01
This seems similar to the [candy distribution](http://stackoverflow.com/questions/11292913/candies-interviewstreet) problem. — beaker, Oct 31 '13 at 16:22

score 1 · Accepted Answer · answered Oct 31 '13 at 16:29

There are 4 possible categories for each number:

Both neighbors are higher (valley)
Both neighbors are lower (peak)
Left is higher, right is lower (downhill)
Right is higher, left is lower (uphill)

Count out-of-bounds indices as infinity when you're looking for valleys and 0 when looking for peaks. Since you say "neighbors of the same rank don't care", you can count them the same way.

First reduce all the valleys to 1. This should be straightforward.

To reduce the uphill elements, iterate through the array and reduce them to left+1.

To reduce the downhill ones, iterate backwards and reduce them to right+1.

Finally, peaks are lowered to whichever neighbor is higher, plus one.

For your example:

4 2 3 2 2 1 3 6    < original

4 1 3 1 2 1 3 6    < valleys reduced
4 1 3 1 2 1 2 3    < uphill reduced
2 1 3 1 2 1 2 3    < downhill reduced
2 1 2 1 2 1 2 3    < peaks reduced

Abhishek Bansal · Answer 2 · 2013-10-31T16:25:03.527

0

Hint:You have to define peaks and valleys in this case. Peaks are elements that are >= their nieghbours. Valleys are elements <= their neighbours.

Assign 1 box to the valleys.

The peaks and valleys shall alternate. The number of boxes to peak = larger of distance from previous valley and next valley.

edited Oct 31 '13 at 16:25

answered Oct 31 '13 at 16:13

Abhishek Bansal

12,589
4
31
46

Give each soldier some ammo :)

2 Answers2