CODEWITHSUNDEEP
algorithmsortingsequence
Chunk222
Chunk222

Reputation: 11

What kind of algorithm applies?

TLDR: I'm effectively looking for an algorithm that would give me a combination of the minimum amount of total messages needed , whether they be "sequential" AND/OR "layered" in order to get to the final result.

=== For a hotel imagine 12 consecutive weeks.

For each of these weeks a price of 100$ exists.

The hotel’s manager decides to change the prices of all these weeks as such

enter image description here

His system currently allows him only to send “price change” messages “sequentially” like so:

  1. Week 1 to Week 2 = 120 $
  2. Week 3 to Week 4 = 150 $
  3. Week 5 to Week 6 = 120 $
  4. Week 7 to Week 9 = 200 $
  5. Week 10 = 120$
  6. Week 11 = 250$
  7. Week 12 = 120$

However, in this case he understands that it would be more efficient to send out the messages in a “layered” manner like so:

  1. Week 1 to Week 12 = 120 $
  2. Week 3 to Week 4 = 150 $
  3. Week 7 to Week 9 = 200 $
  4. Week 11 = 250$

Which algorithm allows the manager to always calculate the optimal “layered” option?? so that he may systematically choose the most efficient manner of sending out the messages, no matter how many weeks are concerned and bearing in mind that some weeks will not necessarily have their prices changed.

I'm effectively looking for an algorithm that would give me a combination of the minimum amount of total messages needed , whether they be "sequential" AND/OR "layered" in order to get to the final result. Those such an algorithm exist ?

Upvotes: 1

Views: 105

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

Here is a top-down memoized recursion in Python that should solve this problem in O(n^4) time (actually slightly longer because it is also keeping track of the moves to make - but this could be optimized away):

class Memoize:
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}
    def __call__(self, *args):
        if not self.memo.has_key(args):
            self.memo[args] = self.fn(*args)
        return self.memo[args]

@Memoize
def best_messages(a,b,value=None):
    """Return moves needed to make range old[a:b] have the target values

If value is not None, it means the range has been set to the given value
"""
    if value is None:
        while a<b and new[a]==old[a]:
            a+=1
        while a<b and new[b-1]==old[b-1]:
            b-=1     
    else:
        # Skip values that are correct
        while a<b and new[a]==value:
            a+=1
        while a<b and new[b-1]==value:
            b-=1     
    if a==b:
        return [] # Nothing to change

    best = None
    for s in range(a,b):
        for e in range(s+1,b+1):
            target = new[s]
            if target==new[e-1]:
                moves = [ (s,e,target) ] + best_messages(s,e,target) + best_messages(a,s,value) + best_messages(e,b,value) 
                if best is None or len(moves)<len(best):
                    best = moves
    return best

old = [100,100,100,100,100,100,100,100,100,100,100,100]
new = [120,120,150,150,120,120,200,200,200,120,250,120]
for s,e,value in best_messages(0,len(old))  :
    print "Week {} to Week {} = {}".format(s+1,e,value)

The basic principle is that it only makes sense to consider updates where we set the first and last in the update to the final target value because otherwise we can make the update shorter and still take the same number of moves.

Update

I think it can be optimized to work in O(n^3) time if you change:

for s in range(a,b):

to

s=a

Upvotes: 1

Related Questions