Rt developer challenge: tower of hanoi

RT Developers
1

Perhaps it’s the fault of the delicious bottle of Port that a houseguest
brought me, but I’ve got a challenge for the RT community.

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]

It’s my hope that in the coming months, “RT Developer Challenges” will
become a regular feature here on rt-devel. If you’ve got ideas for
future challenges, please drop me a line off-list.

Ladies and Gentlemen, start your engines.

Jesse

[1] Tower of Hanoi -- from Wolfram MathWorld
[2] Fame and a beer or other beverage of your choice the next time I or
another Best Practical staffer passes through your town.

2

On Sat, 23 Oct 2004 03:33:20 -0400, “Jesse Vincent”
jesse@bestpractical.com said:

Perhaps it’s the fault of the delicious bottle of Port that a houseguest
brought me, but I’ve got a challenge for the RT community.

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’ve made a couple of them, but they suck for various reasons.
Basically
it’s hard to make them sort correctly, because it takes forever if you
put
a ‘sleep 1’ in, but otherwise (at least with Mysql’s dates) they don’t
sort
properly.

Anyway, here’s one that’s pretty chatty, but gets the moves in the
correct
order txn-wise.

The Scrip:

Condition: On Comment

Action: User Defined

Prepration Code: (<< EOF)
my $comment = $self->TransactionObj->Content();

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();

Find a third queue to use as temporary space for this move.

my $queues = RT::Queues->new($user);
$queues->UnLimit();
my $queue_items = $queues->ItemsArrayRef;

my %queue_names;
my $temp_queue_id;
my $new_queue_id;
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) {
# nothing to do
} elsif ($new_queue_match eq $matchname) {
$new_queue_id = $id;
} elsif (!$temp_queue_id) {
$temp_queue_id = $id;
}
}

make sure a move is actually required (the case of trying to move to

where

we already are will leave this blank as well)

return 0 unless $new_queue_id;

the next smaller disk is our member.

my $members = $self->TicketObj->Members->ItemsArrayRef;
if (@$members) {
# make sure there’s spare space to move this thing!
return 0 unless $temp_queue_id;
my $child_obj = RT::Ticket->new($user);
$child_obj->Load($members->[0]->LocalBase);
if ($child_obj->Queue != $temp_queue_id) {
$child_obj->Comment(Content => “move to
$queue_names{$temp_queue_id}”);
}
$self->TicketObj->SetQueue($new_queue_id);
$child_obj->Comment(Content => “move to
$queue_names{$new_queue_id}”);
} else {
# no children, just move ourselves!
$self->TicketObj->SetQueue($new_queue_id);
}
return 1;
}

return 0;
EOF

Cleanup Code: return 1;

Stage: TransactionCreate

How to use:

a) Have at least 3 queues available.
b) Create tickets with a Parent/Child relationship (Parent is the larger
disk)
c) Create a comment on the largest disk “move to ”.

All the other disks will be moved as appropriate.

NOTE: There is no concept of ‘stacking’ in RT queues, so the disks are
assumed to
be stacked correctly at the start since there’s no way of detecting
otherwise.

The script won’t move a disc until the immediately smaller disk is on
the a third
stack (not the source or destination of the first move) - and that
propagates up
to the top disk which has no children and hence can always move.

I still think this solution is rather ugly, but it works.

Bron.
Bron Gondwana
brong@fastmail.fm

3

I’m impressed :slight_smile: You win. May I add this to the Wiki?

Best,
JesseOn Oct 25, 2004, at 9:47 PM, Bron Gondwana wrote:

On Sat, 23 Oct 2004 03:33:20 -0400, “Jesse Vincent”
jesse@bestpractical.com said:

Perhaps it’s the fault of the delicious bottle of Port that a
houseguest
brought me, but I’ve got a challenge for the RT community.

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’ve made a couple of them, but they suck for various reasons.
Basically
it’s hard to make them sort correctly, because it takes forever if you
put
a ‘sleep 1’ in, but otherwise (at least with Mysql’s dates) they don’t
sort
properly.

Anyway, here’s one that’s pretty chatty, but gets the moves in the
correct
order txn-wise.

The Scrip:

Condition: On Comment

Action: User Defined

Prepration Code: (<< EOF)
my $comment = $self->TransactionObj->Content();

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();

Find a third queue to use as temporary space for this move.

my $queues = RT::Queues->new($user);
$queues->UnLimit();
my $queue_items = $queues->ItemsArrayRef;

my %queue_names;
my $temp_queue_id;
my $new_queue_id;
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) {
# nothing to do
} elsif ($new_queue_match eq $matchname) {
$new_queue_id = $id;
} elsif (!$temp_queue_id) {
$temp_queue_id = $id;
}
}

make sure a move is actually required (the case of trying to move

to
where

we already are will leave this blank as well)

return 0 unless $new_queue_id;

the next smaller disk is our member.

my $members = $self->TicketObj->Members->ItemsArrayRef;
if (@$members) {
# make sure there’s spare space to move this thing!
return 0 unless $temp_queue_id;
my $child_obj = RT::Ticket->new($user);
$child_obj->Load($members->[0]->LocalBase);
if ($child_obj->Queue != $temp_queue_id) {
$child_obj->Comment(Content => “move to
$queue_names{$temp_queue_id}”);
}
$self->TicketObj->SetQueue($new_queue_id);
$child_obj->Comment(Content => “move to
$queue_names{$new_queue_id}”);
} else {
# no children, just move ourselves!
$self->TicketObj->SetQueue($new_queue_id);
}
return 1;
}

return 0;
EOF

Cleanup Code: return 1;

Stage: TransactionCreate

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

How to use:

a) Have at least 3 queues available.
b) Create tickets with a Parent/Child relationship (Parent is the
larger
disk)
c) Create a comment on the largest disk “move to ”.

All the other disks will be moved as appropriate.

NOTE: There is no concept of ‘stacking’ in RT queues, so the disks are
assumed to
be stacked correctly at the start since there’s no way of detecting
otherwise.

The script won’t move a disc until the immediately smaller disk is on
the a third
stack (not the source or destination of the first move) - and that
propagates up
to the top disk which has no children and hence can always move.

I still think this solution is rather ugly, but it works.

Bron.

Bron Gondwana
brong@fastmail.fm

4

On Sat, 23 Oct 2004 03:33:20 -0400, “Jesse Vincent”
jesse@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 ”. 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 :slight_smile:

$self->TicketObj->Comment(Content => “Action Log for $comment:\n\n” .
join(“\n”, @notes));
}

return 1;
Bron Gondwana
brong@fastmail.fm