The Rotation Braid
I started recording myself talking through the PEDAC method out loud, and it is a disaster. I know that I am not a verbal processor – I tend to write everything first or see it written in my mind’s eye. I even sometimes imagine that I’m writing a blog post as I speak. It takes me about 5 seconds longer than others to get my thoughts together and be able to verbalize them. The good news is that I have gotten better.
(As a teacher, I recognized this trait in my students, and usually made them take a minute to write first or talk to a partner before sharing their thoughts to the whole class – this way, I heard from more students. I also taught verbal processors how to record themselves as they spoke so that they could get their thoughts down on paper. One extreme case even ended up bringing a recorder to class to be able to write his in-class timed essays.)
The hardest part of these problems is understanding what they want you to do in the first place. It took me about fifteen minutes to fully understand the question I describe below, then 15 minutes to complete it once I had it planned. This after a 50-minute fiasco with the previous problem, where I incorrectly answered the problem due to not understanding it enough before starting. Since the problems build on each other, this problem took me less time to understand than it would have if I hadn’t spent so much time on the previous problem.
The problem asks us to take an integer and rotate through to find what they call the max rotation. The seemingly simple concept of rotation took me a while to wrap my head around, but practically it means to take one digit and move it to the end of the integer. For example, 1234 rotated would be 2341.
To find the max rotation, the first digit needs to move to the end, then the second to first digit needs to move to the end, and so on until all digits rotate through. The image that popped into my head was a braid, where you complete the braid using the remaining loose hair and leave the already braided hair in its place.
12345 => 23451 (digit located in first index position, 1, moves to back) => 24513 (digit 2 remains in place, digit located in second index position, 3, moves to back) => 24135 (digits 2 and 4 remain in place, digit located in third index position, 5, moves to back) => 24153 (2, 4, and 1 remain in place, and digit located in fourth index position, 3, is moved to back)
It’s confusing because the moving values can be values that have already been rotated to the back before.
The problem recommends using a method that we made in the previous problem called rotate_rightmost_digits. It takes two arguments, an integer and the digit number from the right it wants you to rotate to the back, called n.
def rotate_rightmost_digits(integer, n) ary = integer.digits.reverse new_ary = Array.new(ary) # avoids mutating the original argument new_ary << new_ary.delete_at(-n) new_ary.join('').to_i end
Without going too much into the inner workings of this method, I will give an example and explain the return value. Given the integer 12345 and the value 4 for n, my return value is the integer 13452. The digit 2 is four places from the right, so it rotates to the end.
So I build the method based on this existing method. First, I copy and paste this method into my file to have access to it. This method returns an integer. My new method needs to use an integer as its parameter.
Here is my plan:
# count number of digits in given integer. integer.to_s.chars.size # initialize variable n, set to size # initialize new variable called new_integer # start loop # call rotate_rightmost_digits using given integer and current n, set new_integer value to return value of this method # break out of loop when n == 0 => this was wrong, I'll discuss later # return new_integer
First, I initialize a new variable called n that is set to the value returned by the size method called on the provided integer. I want to figure out the size to see how many times we need to go through the rotation process. In order to get the size, I make the integer to an array and called size on that array. I make a guess that simply changing the integer into a string would suffice, but for now, I’m positive this will work, so I’ll refactor that later.
def max_rotation(integer) n = integer.to_s.chars.size end
Then, I need a space to save my return value for the newly rotated integer, but due to variable scope, I need to initialize it outside of the do…end block. I set my new variable to the given integer since that is what it will be the first time the methods inside the loop execute as I start “braiding”. Then I invoke the loop method using the do…end block.
def max_rotation(integer) n = integer.to_s.size new_integer = integer loop do end end
At this point, n is the size of the array. I invoke my rotate_rightmost_digits method by passing the values saved in the new_integer and n variables through the method.
def max_rotation(integer) n = integer.to_s.size new_integer = integer loop do new_integer = rotate_rightmost_digits(new_integer, n) end end
If I start out with 12345, n at this point is 5, and new_integer is now 23451, with the value at the index -5 rotated to the back of the number. At this point when writing the method, I had a choice of reducing the counting mechanism or creating a break. I initially chose to reduce the counting mechanism first. I reduced n by using the shorthand for n = n – 1, and decided to break if the n was equal to one (in my thinking, one value cannot be rotated – I’ll explain later an issue I had with this). Finally, I needed to return the last value saved in new_integer.
def max_rotation(integer) n = integer.to_s.size new_integer = integer loop do new_integer = rotate_rightmost_digits(new_integer, n) n -= 1 break if n == 1 end new_integer end
I ran the code using the test cases, and the first two worked:
p max_rotation(12345) == 24153 # => true p max_rotation(735291) == 321579 # => true p max_rotation(3) == 3 # => infinite loop!!!!!!!!
But the third value did not. This is what is called an “edge case” – should work technically (still within acceptable working parameters), but probably going to cause a problem. There are other edge cases for this problem, but I will not explain those in this blog post. In this case, because the size of this integer is only one digit, n = 1. In my code, I reduce n’s value by one, so it now == 0. However, my break happens when n == 1. I skipped the break condition! Ways to fix this:
Change n == 1 to n < 1
Change n == 1 to n == 0
Change the position of the break so it breaks before n is changed
def max_rotation(integer) n = integer.to_s.size new_integer = integer loop do new_integer = rotate_rightmost_digits(new_integer, n) break if n == 1 n -= 1 end new_integer end
Voila! More than anything for this problem, I am happy that I could explain this out loud before I even tried to write the code.