[Rt-devel] RT DEVELOPER CHALLENGE: TOWER OF HANOI

[Bron Gondwana]

On Sat, 23 Oct 2004 03:33:20 -0400, "Jesse Vincent"
<jesse at bestpractical.com> said:
> The first person to develop and document a solution to the famed Tower
> of Hanoi puzzle[1] using RT's Scrips system with queues modeling the
> rods, tickets modeling the disks and ticket relationships modeling the
> relative disk sizes will win a fabulous prize.[2]

I did threaten to write one that does the whole process in a single
ticket
and logs the output to a comment, so here you go.

Again, this is custom preparation code for an 'on comment' ticket which
matches tickets with content "move to <queuename>".  It correctly
handles
the single ticket case (only requiring 2 queues to exist even since you
don't need a temporary queue to move one ticket) and the case where you
try to move to the same queue you're currently on (even giving useful
error messages in a comment!).

As before, you set up the disks by having a parent/child relationship
between the tickets.  Only the first child will be considered in each
case (you can't have multiple disks on one rod in Hanoi!) - and I don't
throw error messages about it if you get that wrong.

The first unused queue plus the current queue of the ticket and the
target queue are used as the three rods.

It moves all tickets onto the same queue before starting rather than the
previous version's more intelligent handling of starting locations - but
this is so I can use a rather evil bit of maths to calculate which
ticket
to move!  I first used this algorithm to prove to my first year CompSci
lecturer that Hanoi could be solved without using recursion.

And I haven't explained the algorithm much in the commments, but feel
free
to ask questions about it or try to work it out yourself.

Enjoy,

Bron.

Here is an example output for tickets called X1-X4 (X4 being the
biggest) on
queues Q1-Q3.  We are moving from Q2 to Q3.  X1 was not on Q2 at the
start.
The example is followed by the code for the Scrip.

Format is: transaction_no (move_no): Action

============================
#               Thu Nov 04 22:23:06 2004        root - Comments added
move to Q3
	
#               Thu Nov 04 22:23:07 2004        RT_System - Queue
changed from Q2 to Q3                  

#               Thu Nov 04 22:23:07 2004        RT_System - Comments
added
Action Log for move to Q3:

Setup:
2514: Moved X1 to Q2 before starting

Moves:
2515 (1): Move X1 from Q2 to Q1
2516 (2): Move X2 from Q2 to Q3
2517 (3): Move X1 from Q1 to Q3
2518 (4): Move X3 from Q2 to Q1
2519 (5): Move X1 from Q3 to Q2
2520 (6): Move X2 from Q3 to Q1
2521 (7): Move X1 from Q2 to Q1
2522 (8): Move X4 from Q2 to Q3
2523 (9): Move X1 from Q1 to Q3
2524 (10): Move X2 from Q1 to Q2
2525 (11): Move X1 from Q3 to Q2
2526 (12): Move X3 from Q1 to Q3
2527 (13): Move X1 from Q2 to Q1
2528 (14): Move X2 from Q2 to Q3
2529 (15): Move X1 from Q1 to Q3

=================================================

my $comment = $self->TransactionObj->Content();

my @queues;
my @tickets;
my @notes;

if ($comment =~ m/^move to ([A-Za-z0-9_ ]+)/) {
  my $new_queue_match = lc($1);
  $new_queue_match =~ s/^\s+//;
  $new_queue_match =~ s/\s+$//;
  my $user = $self->TransactionObj->CurrentUser();
  my $old_queue_id = $self->TicketObj->Queue();
  push @tickets, $self->TicketObj;

  # Find the queues and place them in order [0, 1, 2] = [Source, Dest,
  Spare].
  my $queues = RT::Queues->new($user);
  $queues->UnLimit();
  my $queue_items = $queues->ItemsArrayRef;
  my %queue_names;
  foreach my $item (@$queue_items) {
    my $id = $item->id;
    my $name = $item->Name;
    my $matchname = lc($name);
    $matchname =~ s/^\s+//;
    $matchname =~ s/\s+$//;
    $queue_names{$id} = $name;
    if ($id == $old_queue_id) {
      $queues[0] = $id;
      # check that we're not going here too!.
      if ($new_queue_match eq $matchname) {
        $self->TicketObj->Comment(Content => "ERROR: $comment\n\nSource
        and Destination queue are the same: " . $item->Name . "!\n");
        return 0;
      }
    } elsif ($new_queue_match eq $matchname) {
      $queues[1] = $id;
    } elsif (!$queues[2]) {
      $queues[2] = $id;
    }
  }

  # check that we have the destination queue.
  unless ($queues[1]) {
    $self->TicketObj->Comment(Content => "ERROR: $comment\n\nUnable to
    find destination queue $new_queue_match\n");
    return 0;
  }

  # find out how many disks we have and set them up for the algorithm
  below.
  my $ticket = $self->TicketObj;
  my $num_moves = 2;
  while ($ticket) {
    my $members = $ticket->Members->ItemsArrayRef;
    if (@$members) {
      my $child_obj = RT::Ticket->new($user);
      $child_obj->Load($members->[0]->LocalBase);
      unless ($child_obj->Queue == $old_queue_id) {
        my ($res, $msg) = $child_obj->SetQueue($old_queue_id);
        push @notes, "  $res: Moved " . $child_obj->Subject . " to
        $queue_names{$old_queue_id} before starting";
      }
      push @tickets, $child_obj;
      $ticket = $child_obj;
      $num_moves *= 2;
    } else {
      $ticket = undef;
    }
  }
  @tickets = reverse @tickets;
  my @ticket_names = map { $_->Subject } @tickets;
  my @ticket_rods = map { +0 } @tickets;

  # only have to move the bottom disk once!
  $num_moves--;

  # check that there's a spare queue if we have more than one move to
  make.
  unless ($queues[2] or $num_moves == 1) {
    $self->TicketObj->Comment(Content => "ERROR: $comment\n\nCouldn't
    find a third queue to use, and there's more than one disk to
    move.\n");
    return 0;
  }

  # tidy up the messages a bit if there's Setup information.
  if (@notes) {
    unshift @notes, "Setup:";
    push @notes, '';
  }
  push @notes, "Moves:";

  # we have all the tickets in @tickets, small one at the start, and
  they're
  # all in the same queue ($queues[0]).  We're moving to $queues[1];

  # now the magic!
  foreach my $n (1..$num_moves) {
    my $base = 2;
    my $tick = 0;
    while ($n % $base == 0) {
       $tick++;
       $base *= 2;
    }
    my $move = (($#tickets + $tick) % 2) ? 2 : 4;
    my $old = $ticket_rods[$tick];
    $ticket_rods[$tick] =  ($old + $move) % 3;
    my ($res, $msg) =
    $tickets[$tick]->SetQueue($queues[$ticket_rods[$tick]]);
    push @notes, "  $res ($n): Moved $ticket_names[$tick] from
    $queue_names{$queues[$old]} to
    $queue_names{$queues[$ticket_rods[$tick]]}";
  }

  # record everything we did into the ticket :)
  $self->TicketObj->Comment(Content => "Action Log for $comment:\n\n" .
  join("\n", @notes));
}

return 1;
-- 
  Bron Gondwana
  brong at fastmail.fm