4
\$\begingroup\$

Here is an implementation of Towers of Hanoi based on few observed patterns1 from the easier recursive solution:

function [] = myTowersOfHanoi(N, from, to, alt)
  % Accepts three integers: N - number of disks  
  % from - number of start tower, to - number of end tower, alt - free tower. 
  % Returs string outputs with succesive moves to complete the task of solving
  % the Towers of Hanoi with N disks moved from tower with number stored
  % in the second argument to one with number in third arg.

  totalNumberOfMoves = (2 ^ N) - 1;

  M = generateDiskMoves(totalNumberOfMoves);

  % These are the paths of disks if N is odd.
  path1 = [from, alt, to];  % Path of disk with odd number: from->alt->to 
  path2 = [from, to, alt];  % Path of disk with even number.

  currentPositions = ones(1, N); % index-disk number, value-number of moves

  len = numel(path1);

  % If N (numer of disks) is even the paths are swapped.
  if mod(N, 2) == 0
    [path2, path1] = swapArrays(path1, path2);  
  end  

  % Solve
  for i = M 
    from = -1;
    to = -1;

    if mod(i, 2) == 0  % if number of disk, i is even
      j = currentPositions(i); % j - number of moves for i-th disk

      % In C++ indexes: [0, size - 1] in Octave: [1, size] 
      % so: mod(j - 1, len) + 1, to avoid index = 0.
      from = path1( mod(j - 1, len) + 1); % Cycle over 1->2->3 

      j = j + 1; 

      to =  path1( mod(j - 1, len) + 1); 

      currentPositions(i) = j; % update moves of i-th disk

    else
      k = currentPositions(i);

      from = path2( mod(k - 1, len) + 1); 
      k = k + 1;  
      to =  path2( mod(k - 1, len) + 1); 

      currentPositions(i) = k;
    end  
      disp(sprintf('Move disk %d from %d to %d.', i, from, to))
  end  

end  

function [a2, a1] = swapArrays (a1, a2)
  [a2, a1] = deal(a1, a2);  
end  

% From: http://mathworld.wolfram.com/BinaryCarrySequence.html
function [M] = generateDiskMoves(N)
  % Accepts integer: N - total number of moves.
  % Returns a 1xN integer array with the first N consecutive disk moves
  % in Tower of Hanoi where the index is the move number 
  % and the value is the disk number. m - is discarded.

  [m, M] = Omega2(N); % Generate the first N terms of: "Binary Carry Sequence".

  M = M .+ 1;         % Add one and get moves of disk in Tower of Hanoi.

  if N < 2            % Get only the first move.
    M = M(1);       
  end    
end  

% From : https://oeis.org/A007814
function [m, M] = Omega2(n)
  % Accepts an integer: n.
  % Returns m: max power of 2 such that 2^m divides n, and
  % M: 1-by-K matrix where M(i) is the max power of 2 such 
  % that 2^M(i) divides n.

  M = NaN * zeros(1, n);

  M(1) = 0; 
  M(2) = 1;

  for k = 3 : n
    if M(k - 2) ~= 0
      M(k) = M(k - k / 2) + 1;
    else
      M(k) = 0;
    end
  end

  m = M(end);
end 

Input: Move 4 disks from 1st to 3rd peg, 2nd is free.

myTowersOfHanoi(4, 1, 3, 2)

Output:

Move disk 1 from 1 to 2.
Move disk 2 from 1 to 3.
Move disk 1 from 2 to 3.
Move disk 3 from 1 to 2.
Move disk 1 from 3 to 1.
Move disk 2 from 3 to 2.
Move disk 1 from 1 to 2.
Move disk 4 from 1 to 3.
Move disk 1 from 2 to 3.
Move disk 2 from 2 to 1.
Move disk 1 from 3 to 1.
Move disk 3 from 2 to 3.
Move disk 1 from 1 to 2.
Move disk 2 from 1 to 3.
Move disk 1 from 2 to 3.

I would appreciate your opinion and suggestions related to:

  • MATLAB / Octave coding style and readability.
  • thoughts on / possible improvements of the algorithm.

1. The observations were that firstly: the sequence of transitions could be described by a slightly modified formula: "Binary Carry Sequence" and secondly: individual disk transitions are following only two different cyclic paths which were based on the parity of the total number of the disks, N, and the parity of the number of the currently moving disk, i.e:

enter image description here

\$\endgroup\$
3
\$\begingroup\$

Wow. Some legible matlab code. I'm impressed. Too often matlab seems to be a "write only" language, in the sense that perl regex line noise or Iverson's APL can be write only.

No biggie, but I wouldn't mind seeing consistent comment formatting where (N, from, to, alt) appear in the left margin in each of four separate lines. Kudos for telling us about the args, anyway. In the matlab ecosystem this is maybe redundant, but speaking for myself I wouldn't mind seeing a reminder that there's no zero-origin going on here, by mentioning from > 0 or something. Saying it once would suffice - to & alt would clearly use the same convention. I see that later you spell this out in the "avoid index = 0" comment.

typo: Returs

Kudos on helpfully explaining that 2^N-1 is totalNumberOfMoves.

Your figure was helpful. The "from -> alt -> to" comment is on the redundant side.

Would you do the Gentle Reader a small favor, please, and bump the currentPositions and len assignments down slightly? Just a few lines. That way we have a full-line comment on the "odd" case, setting up dramatic tension for "what about even?", and the swapArrays immediately shows the even case.

Switching from j to k for the path2 case was maybe a little odd. Wouldn't hurt to stick with j, as we always assign it a value at top of loop. Switching to k made me wonder if variable value needs to survive until some subsequent iteration.

Renaming deal to swapArrays made sense, thank you.

Comment for generateDiskMoves is very nice. Except I'd delete that "m is discarded" remark, as that's not part of the public API.

Personally I view the comment for M .+ 1 as "% Convert to one-origin moves."

The "Get only the first move" comment is accurate and helpful, but consider something stronger: "% The trivial case requires just one move."

Omega2 accepts lowercase n. Consider using lowercase in the other functions. I had been thinking of upper as matrix and lower as scalar.

I wouldn't mind seeing a comment that spells out whether disk 1 is smallest or biggest disk.

As far as the algorithm goes, if results of a parity function were available, could you verify, or synthesize, the Omega2 results? Perhaps with less looping?

\$\endgroup\$
  • \$\begingroup\$ Thank you for the great answer! I've removed the redundant (mostly directed to myself comments), placed together lines of closely connected code, placed j = currentPositions(i); in the beginning of the for loop, and ` currentPositions(i) = j` is at the end; k is now j. The only thing that I couldn't quite get were the comments on the algorithm at the end. What I noticed is that the algorithm determines completely the sequences of moves of all the disks, from beginning to end, and in fact can be used to determine n-th move of k-th disk, independently. \$\endgroup\$ – Ziezi Sep 9 '17 at 14:00
2
\$\begingroup\$

I agree with J H regarding most of the comments. One thing to add though: If you restructure the comments on the top of the function, you can get help. This can be very helpful at times.

myTowersOfHanoi(N, from, to, alt)
% MYTOWERSOFHANOI  Implementation of Tower Of Hanoi
% Accepts three integers: 
%  N - number of disks  
%  from - number of start tower
%  to - number of end tower 
%  alt - free tower. 
% Displays string outputs with successive moves to complete the task of solving
% the Towers of Hanoi with N disks moved from tower with number stored
% in the second argument to one with number in third arg.

%   See also GENERATEDISCMOVES.

You don't need the dot when adding numbers a number to a vector / array. Use M = M + 1; instead of M = M .+ 1;.


NaN can take arguments, so M = NaN * zeros(1, n); is simply M = NaN(1, N).

I'd avoid it all and do M = zeros(1, n), and then skip the else part in the loop below.


I might come back to this and add more later on, but I don't have more time now.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the "help" detail, I've applied it, however, for some reason when I use it, the only thing that gets printed is the comment on the first line of the .m file, not the comments after the function keyword. Note: I'm using Octave. \$\endgroup\$ – Ziezi Sep 9 '17 at 14:02
  • 1
    \$\begingroup\$ @Ziezi You need to put all help lines together, either before or after the function command. The first continuous block of comments is shown for help. \$\endgroup\$ – Cris Luengo Jan 12 '18 at 2:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.