8 Replies - 3746 Views - Last Post: 02 April 2013 - 03:33 PM

#1 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7053
  • View blog
  • Posts: 23,977
  • Joined: 05-May 12

Tower of Hanoi backup rotation: How to do it without labeled tapes?

Posted 26 February 2013 - 10:48 PM

I'm having a really tough time trying to figure out how to do the Tower of Hanoi backup rotation scheme if my "tapes" are unlabeled. I'm unwillingly coming to the conclusion that it is impossible to do it without labeling the "tapes".

Consider a backup producer that randomly produces backups. Some backups maybe only hours apart, and some maybe days or weeks apart. The only thing that I know for sure is that newer backups passed to my consumer will always be newer than the previous backup given to me.

As the consumer, I have limited space. I can only hold on to N backups. (For ease of discussion, let's say N == 5 because there is a nice graphic to reference in the wikipedia article.) I want to try to give as far back a backup as possible, but with relatively good coverage for the intermediate backups, hence the Tower of Hanoi scheme. Additionally, my consumer is almost stateless. The only state I can retain is the actual backups that I decide to keep. Hence, my description above of "unlabeled tapes".

So let's say that I start off with no backups. The first 5 backups that I get, I'll definitely keep. When the 6th and later backups arrive, how do I choose which backup to discard?

So far my intuition is pointing towards looking at the timestamp on the "tapes". In real life, the "tapes" are actually .zip files. If I get the timestamp and convert to binary, I can look at the number of trailing zeroes. I can use the number of trailing zeroes as a virtual label. No zeroes is an 'A' tape; 1 zero is a 'B' tape; 2 zeroes is a 'C' tape; etc. It sort of works if I could rely on the producer to send backups to the consumer at regular time intervals, but the random timing completely messes things up.

Is this a hopeless case of going without labels, and that I should just label the "tapes"?

The reason why I'm trying to go with minimal state is because the consumer that I'm trying to implement is to be written as a CMD batch file. Although it has support for parsing and writing files, it is not exactly the best tool. Should I just move up to implementing the consumer as a PowerShell script, and save a "label" into the alternate stream available on NTFS file systems?

Is This A Good Question/Topic? 0
  • +

Replies To: Tower of Hanoi backup rotation: How to do it without labeled tapes?

#2 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 409
  • View blog
  • Posts: 883
  • Joined: 27-June 09

Re: Tower of Hanoi backup rotation: How to do it without labeled tapes?

Posted 27 February 2013 - 11:32 AM

The order of the timestamps is sufficient
Whenever you backup tape 1, you discard the 2nd newest backup
Whenever you backup tape 2, you discard the 3rd newest backup
Whenever you backup tape 3, you discard the 4th newest backup
and so on.

As long as you know that you are using the nth tape from the schedule, then you discard the (n+1)th newest backup
Was This Post Helpful? 1
  • +
  • -

#3 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7053
  • View blog
  • Posts: 23,977
  • Joined: 05-May 12

Re: Tower of Hanoi backup rotation: How to do it without labeled tapes?

Posted 27 February 2013 - 05:24 PM

Thanks for responding. Unfortunately that doesn't simulate the Tower of Hanoi backup rotation. It just does something like a sliding window over n + 2 days.

Here's the output I'm getting as compare to Tower of Hanoi rotation:
=== Begin Trial rotator ==
[     0 ] Range: 1
[     0     1 ] Range: 2
[     0     1     2 ] Range: 3
[     0     1     2     3 ] Range: 4
[     0     1     2     3     4 ] Range: 5
[     0     1     2     4     5 ] Range: 6
[     0     1     4     5     6 ] Range: 7
[     0     4     5     6     7 ] Range: 8
[     4     5     6     7     8 ] Range: 5
[     4     5     6     7     9 ] Range: 6
[     4     5     6     9    10 ] Range: 7
[     4     5     9    10    11 ] Range: 8
[     4     9    10    11    12 ] Range: 9
[     9    10    11    12    13 ] Range: 5
[     9    10    11    12    14 ] Range: 6
[     9    10    11    14    15 ] Range: 7
[     9    10    14    15    16 ] Range: 8
[     9    14    15    16    17 ] Range: 9
[    14    15    16    17    18 ] Range: 5
[    14    15    16    17    19 ] Range: 6
[    14    15    16    19    20 ] Range: 7
[    14    15    19    20    21 ] Range: 8
[    14    19    20    21    22 ] Range: 9
[    19    20    21    22    23 ] Range: 5
[    19    20    21    22    24 ] Range: 6
[    19    20    21    24    25 ] Range: 7
[    19    20    24    25    26 ] Range: 8
[    19    24    25    26    27 ] Range: 9
[    24    25    26    27    28 ] Range: 5
[    24    25    26    27    29 ] Range: 6
[    24    25    26    29    30 ] Range: 7
[    24    25    29    30    31 ] Range: 8
Average range: 7
=== End Trial rotator ==
=== Begin Hanoi rotator ==
[  E: 0 ] Range: 1
[  E: 0  A: 1 ] Range: 2
[  E: 0  A: 1  B: 2 ] Range: 3
[  E: 0  B: 2  A: 3 ] Range: 4
[  E: 0  B: 2  A: 3  C: 4 ] Range: 5
[  E: 0  B: 2  C: 4  A: 5 ] Range: 6
[  E: 0  C: 4  A: 5  B: 6 ] Range: 7
[  E: 0  C: 4  B: 6  A: 7 ] Range: 8
[  E: 0  C: 4  B: 6  A: 7  D: 8 ] Range: 9
[  E: 0  C: 4  B: 6  D: 8  A: 9 ] Range: 10
[  E: 0  C: 4  D: 8  A: 9  B:10 ] Range: 11
[  E: 0  C: 4  D: 8  B:10  A:11 ] Range: 12
[  E: 0  D: 8  B:10  A:11  C:12 ] Range: 13
[  E: 0  D: 8  B:10  C:12  A:13 ] Range: 14
[  E: 0  D: 8  C:12  A:13  B:14 ] Range: 15
[  E: 0  D: 8  C:12  B:14  A:15 ] Range: 16
[  D: 8  C:12  B:14  A:15  E:16 ] Range: 9
[  D: 8  C:12  B:14  E:16  A:17 ] Range: 10
[  D: 8  C:12  E:16  A:17  B:18 ] Range: 11
[  D: 8  C:12  E:16  B:18  A:19 ] Range: 12
[  D: 8  E:16  B:18  A:19  C:20 ] Range: 13
[  D: 8  E:16  B:18  C:20  A:21 ] Range: 14
[  D: 8  E:16  C:20  A:21  B:22 ] Range: 15
[  D: 8  E:16  C:20  B:22  A:23 ] Range: 16
[  E:16  C:20  B:22  A:23  D:24 ] Range: 9
[  E:16  C:20  B:22  D:24  A:25 ] Range: 10
[  E:16  C:20  D:24  A:25  B:26 ] Range: 11
[  E:16  C:20  D:24  B:26  A:27 ] Range: 12
[  E:16  D:24  B:26  A:27  C:28 ] Range: 13
[  E:16  D:24  B:26  C:28  A:29 ] Range: 14
[  E:16  D:24  C:28  A:29  B:30 ] Range: 15
[  E:16  D:24  C:28  B:30  A:31 ] Range: 16
Average range: 12.484
=== End Hanoi rotator ==



Here's the quick and dirty code I'm using:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace HanoiBackup
{
    interface ITape
    {
        int TimeStamp { get; }
    }

    class Tape : ITape
    {
        public int TimeStamp { get; private set; }

        public Tape(int timeStamp)
        {
            TimeStamp = timeStamp;
        }

        public override string ToString()
        {
            return TimeStamp.ToString();
        }
    }

    class TapeRack : IEnumerable<ITape>
    {
        List<ITape> _backups = new List<ITape>();

        public int Capacity { get; private set; }

        public TapeRack(int capacity)
        {
            Capacity = capacity;
        }

        public void Add(ITape tape)
        {
            if (_backups.Count + 1 > Capacity)
                throw new InvalidOperationException("Too many backups!");

            _backups.Add(tape);
        }

        public void Remove(ITape tape)
        {
            _backups.Remove(tape);
        }

        public int Count
        {
            get { return _backups.Count; }
        }

        public IEnumerator<ITape> GetEnumerator()
        {
            return _backups.GetEnumerator();
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }

    interface IRotator
    {
        void Add(ITape tape);
    }

    class TrialRotator : IRotator
    {
        TapeRack _tapeRack;
        int _tapeCount = 0;

        public TrialRotator(TapeRack tapeRack)
        {
            _tapeRack = tapeRack;
        }

        public void Add(ITape tape)
        {
            if (_tapeRack.Count == _tapeRack.Capacity)
                RemoveTape();

            _tapeRack.Add(tape);
            _tapeCount++;
        }

        void RemoveTape()
        {
            int index = (_tapeCount + 1) % _tapeRack.Capacity;

            ITape candidate =
            _tapeRack.OrderBy(t => -t.TimeStamp)
                     .Skip(index)
                     .First();

            _tapeRack.Remove(candidate);
        }
    }

    class HanoiRotator : IRotator
    {
        TapeRack _tapeRack;
        int _maxRange;
        int _nextBackupDay;

        class TapeWrapper : ITape
        {
            public ITape Tape { get; private set; }
            public char Label { get; private set; }

            public int TimeStamp
            {
                get { return Tape.TimeStamp; }
            }

            public TapeWrapper(ITape tape, char label)
            {
                Tape = tape;
                Label = label;
            }

            public override string ToString()
            {
                return String.Format("{0}:{1,2}", Label, Tape);
            }
        }

        public HanoiRotator(TapeRack tapeRack)
        {
            _tapeRack = tapeRack;
            _maxRange = (int) Math.Pow(2, tapeRack.Capacity);
            _nextBackupDay = _maxRange / 2 - 1;
        }

        public void Add(ITape tape)
        {
            char label = ComputeLabel(_nextBackupDay);
            RemoveTape(label);
            _tapeRack.Add(new TapeWrapper(tape, label));
            _nextBackupDay = (_nextBackupDay + 1) % _maxRange;
        }

        char ComputeLabel(int day)
        {
            day = day % (_maxRange / 2) + 1;
            int countZeros = 0;
            while (day > 0 && day % 2 == 0)
            {
                ++countZeros;
                day /= 2;
            }
            return (char) (countZeros + 'A');
        }

        void RemoveTape(int label)
        {
            ITape candidate = _tapeRack.FirstOrDefault(t => ((TapeWrapper)t).Label == label);
            if (candidate != null)
                _tapeRack.Remove(candidate);
        }
    }

    class Program
    {
        const int Slots = 5;

        int GetRange(TapeRack tapeRack)
        {
            return tapeRack.Max(t => t.TimeStamp) - tapeRack.Min(t => t.TimeStamp) + 1;
        }

        void DumpTapeRack(TapeRack tapeRack)
        {
            Console.Write("[ ");
            foreach (var tape in tapeRack)
                Console.Write("{0,5} ", tape);
            Console.WriteLine("] Range: {0}",
                              GetRange(tapeRack));
        }

        double GetAverageRange(int count, TapeRack tapeRack, IRotator rotator)
        {
            int cycles = tapeRack.Capacity * 100;
            int rangeSum = 0;
            for (int i = 0; i < cycles; i++)
            {
                rotator.Add(new Tape(count++));
                rangeSum += GetRange(tapeRack);
            }
            return (double)rangeSum / cycles; 
        }

        void Run(string description, Func<TapeRack, IRotator> construct)
        {
            Console.WriteLine("=== Begin {0} rotator ==", description);
            int count = 0;
            var tapeRack = new TapeRack(Slots);
            IRotator rotator = construct(tapeRack);
            int cycles = (int) Math.Pow(2, Slots);
            for (int i = 0; i < cycles; i++)
            {
                rotator.Add(new Tape(count++));
                DumpTapeRack(tapeRack);
            }
            Console.WriteLine("Average range: {0}", GetAverageRange(count, tapeRack, rotator));
            Console.WriteLine("=== End {0} rotator ==", description);
        }

        void Run()
        {
            Run("Trial", t => new TrialRotator(t));
            Run("Hanoi", t => new HanoiRotator(t));
        }

        static void Main(string[] args)
        {
            new Program().Run();
        }
    }
}


Was This Post Helpful? 0
  • +
  • -

#4 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 409
  • View blog
  • Posts: 883
  • Joined: 27-June 09

Re: Tower of Hanoi backup rotation: How to do it without labeled tapes?

Posted 28 February 2013 - 08:17 AM

I don't have time to look over the code at the moment but here is a simulation of my suggestion with the left being the newest and the right being the oldest

I also forgot that when discarding the max tape, you just remove n instead of n+1
12345
remove 5th newest, new backup represents tape 5 ***
51234
remove 1+1=2nd newest, new backup represents tape 1
15234
remove 2+1=3rd newest, new backup represents tape 2
21534
remove 1+1=2nd newest, new backup represents tape 1
12534
remove 3+1=4th newest, new backup represents tape 3
31254
remove 1+1=2nd newest, new backup represents tape 1
13254
remove 2+1=3rd newest, new backup represents tape 2
21354
remove 1+1=2nd newest, new backup represents tape 1
12354
remove 4+1=5th newest, new backup represents tape 4
41235
remove 1+1=2nd newest, new backup represents tape 1
14235
remove 2+1=3rd newest, new backup represents tape 2
21435
remove 1+1=2nd newest, new backup represents tape 1
12435
remove 3+1=4th newest, new backup represents tape 3
31245
remove 1+1=2nd newest, new backup represents tape 1
13245
remove 2+1=3rd newest, new backup represents tape 2
21345
remove 1+1=2nd newest, new backup represents tape 1
12345
//repeat from ***


Was This Post Helpful? 1
  • +
  • -

#5 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7053
  • View blog
  • Posts: 23,977
  • Joined: 05-May 12

Re: Tower of Hanoi backup rotation: How to do it without labeled tapes?

Posted 28 February 2013 - 08:38 AM

I'm having a hard time figuring out the pattern for number you are using as the first operand for your addition. It seems like the key for what I need since it's the only state information that I need to retain beyond the relative ages of the tapes.

This post has been edited by Skydiver: 28 February 2013 - 08:54 AM

Was This Post Helpful? 0
  • +
  • -

#6 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 409
  • View blog
  • Posts: 883
  • Joined: 27-June 09

Re: Tower of Hanoi backup rotation: How to do it without labeled tapes?

Posted 28 February 2013 - 09:07 AM

You need to have a scheduler dictating this information. It can be derived from the number of times the process has run or you can just keep a seperate counter that increments every run. In our 5 tape example, you will need 4 bits. Add 1 to this 4 bit number. The bit that gets set to 1 is the number that is retrieved for the scheduler. If none of the 4 bits are set to 1, then 5 is returned.

1111
add 1, no bits are set to 1, return 5
0000
add 1, 1st bit is set, return 1
0001
add 1, 2nd bit is set, return 2
0010
add 1, 1st bit is set, return 1
0011
add 1, 3rd bit is set, return 3
0100
add 1, 1st bit is set, return 1
0101
add 1, 2nd bit is set, return 2
0110
add 1, 1st bit is set, return 1
0111
add 1, 4th bit is set, return 4
1000
and so on


Was This Post Helpful? 2
  • +
  • -

#7 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7482
  • View blog
  • Posts: 15,507
  • Joined: 16-October 07

Re: Tower of Hanoi backup rotation: How to do it without labeled tapes?

Posted 28 February 2013 - 10:46 AM

Fascinating. I've never seen this before. Looking at the pretty pictures; it's a binary tree.

I killed some brain cells figuring this out, I think. Here's what I came up with:
#include <stdio.h>

int pickHanoiBackup(int day, int size) {
	if (size>1) {
		int n = 1<<(size-1);
		return (day % n) ? pickHanoiBackup(day, size-1) : size;
	}
	return 1;
}

void showHanoiBackupPattern(int size) {
	int i, days = 1<<(size-1);
	for(i=0; i<days; i++) {
		char c = 'A' + pickHanoiBackup(i+1, size) - 1;
		printf("Day %d %c\n", i+1, c);
	}
}

int main() {
	showHanoiBackupPattern(5);
	return 0;
}



Results:
Day 1 A
Day 2 B
Day 3 A
Day 4 C
Day 5 A
Day 6 B
Day 7 A
Day 8 D
Day 9 A
Day 10 B
Day 11 A
Day 12 C
Day 13 A
Day 14 B
Day 15 A
Day 16 E



You should be able extend this as you like. The algorithm is valid for any given day, so as long as you know when you started, you're good to go.
Was This Post Helpful? 2
  • +
  • -

#8 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7053
  • View blog
  • Posts: 23,977
  • Joined: 05-May 12

Re: Tower of Hanoi backup rotation: How to do it without labeled tapes?

Posted 28 February 2013 - 09:13 PM

Thanks guys. That's what I needed!

I'm glad some of you found the problem interesting.
Was This Post Helpful? 0
  • +
  • -

#9 Momerath   User is offline

  • D.I.C Lover
  • member icon

Reputation: 1021
  • View blog
  • Posts: 2,463
  • Joined: 04-October 09

Re: Tower of Hanoi backup rotation: How to do it without labeled tapes?

Posted 02 April 2013 - 03:33 PM

I know this is late, but if you consider each letter from post #7 a bit in a binary number,(EDCBA) and switch the bit as you use that tape, it will give you
00001
00011
00010
00110
00111
00101

etc., which is Gray Code and the solution to many sliding puzzles :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1