Spatial Reasoning with Zigzag Patterns!
Today we’re continuing our study of Rust and Haskell solutions to basic coding problems. This algorithm is going to be a little harder than the last few we’ve done in this series, and it will get trickier from here!
For a complete study of problem solving techniques in Haskell, make sure to check out Solve.hs. This course runs the gamut from basic solving techniques to advanced data structures and algorithms, so you’ll learn a lot!
The Problem
Today’s problem is Zigzag Conversion. This is an odd problem that stretches your ability to think iteratively and spatially. The idea is that you’re given an input string and a number of “rows”. You need to then imagine the input word written as a zig-zag pattern, where you write the letters in order first going down, and then diagonally up to the right until you get back to the first row. Then it goes down again. Your output must be characters re-ordered in “row-order” after this zig-zag rearrangement.
This makes the most sense looking at examples. Let’s go through several variations with the string MONDAYMORNINGHASKELL. Here’s what it looks like with 3 rows.
M A R G K
O D Y O N N H S E L
N M I A LSo to get the answer, we read along the top line first (MARGK), then the second (ODYONNHSEL), and then the third (NMIAL). So the final answer is MARGKODYONNHSELNMIAL.
Now let’s look at the same string in 4 rows:
M M G L
O Y O N H E L
N A R I A K
D N SThe answer here is MMGLOYONHELNARIAKDNS.
Here’s 5 rows:
M R K
O O N S E
N M I A L
D Y N H L
A GThe answer here is MRKOONSENMIALDYNHLAG.
And now that we have the pattern, we can also consider 2 rows, which doesn’t visually look like a zig-zag as much:
M N A M R I G A K L
O D Y O N N H S E LThis gives the answer MNAMRIGAKLODYONNHSEL.
Finally, if there’s only 1 row, you can simply return the original string.
The Algorithm
So how do we go about solving this? The algorithm here is a bit more involved than the last few weeks!
Our output order is row-by-row, so for our solution we should think in a row-by-row fashion. If we can devise a function that will determine the indices of the original string that belong in each row, then we can simply loop over the rows and append these results!
In order to create this function, we have to think about the zig-zag in terms of “cycles”. Each cycle begins at the top row, goes down to the bottom row, and then up diagonally to the second row. The next element to go at the top row starts a new cycle. By thinking about cycles, we’ll discover a few key facts:
- With
nrows (n >= 2), a complete cycle has2n - 2letters. - The top and bottom row get one letter per cycle.
- All other rows get two letters per cycle.
Now we can start to think mathematically about the indices that belong in each row. It’s easiest to think about the top and bottom rows, since they only get one letter each cycle. Each of these has a starting index (0 and n - 1, respectively), and then we add the cycle length 2n - 2 to these starting indices until it exceeds the length.
The middle rows have this same pattern, only now they have 2 starting indices. They have the starting index from the “down” direction and then their first index going up and to the right. The first index for row i is obviously i - 1, but the second index is harder to see.
The easiest way to find the second index is backwards! The next cycle starts at 2n - 2. So row index 1 has its second index at 2n - 2 - 1, and row index 2 has its second index at 2n - 2 - 2, and so on! The pattern of adding the “cycle number” will work for all starting indices.
Once we have the indices for each row, our task is simple. We build a string for each row and combine them together in order.
So suppose we have our 4-row example.
M M G L
O Y O N H E L
N A R I A K
D N SThe “cycle num” is 6 (2 * 4 - 2). So the first row has indices [0, 6, 12, 18]. The fourth row starts with index 3, and so its indices also go up by 6 each time: [3, 9, 15].
The second row (index 1) has starting indices 1 and 5 (6 - 1). So its indices are [1, 5, 7, 11, 13, 17, 19]. Then the third row has indices [2, 4, 8, 10, 14, 16].
A vector input will allow us to efficiently use and combine these indices.
As a final note, the “cycle num” logic doesn’t end up working with only 1 row. The cycle length using our calculation would be 0, not 1 as it should. The discrepancy is because our “cycle num” logic really depends on having a “first” and “last” row. So if we only have 1 row, we’ll hardcode that case and return the input string.
Rust Solution
In our rust solution, we’ll accumulate our result string in place. To accomplish this we’ll do a few setup steps:
- Handle our base case (1 row)
- Get the string length and cycle number
- Make a vector of the input chars for easy indexing (Rust doesn’t allow string indexing)
- Initialize our mutable result string
pub fn convert(s: String, num_rows: i32) -> String {
if (num_rows == 1) {
return s;
}
let n = s.len();
let nr = num_rows as usize; // Convenience for comparison
let cycleLen: usize = (2 * nr - 2);
let sChars: Vec<char> = s.chars().collect();
let mut result = String::new();
...
}Now we have to add the rows in order. Since the logic differs for the first and last rows, we have 3 sections: first row, middle rows, and last row. The first and last row are straightforward using our algorithm. Each is a simple while loop.
pub fn convert(s: String, num_rows: i32) -> String {
if (num_rows == 1) {
return s;
}
let n = s.len();
let nr = num_rows as usize; // Convenience for comparison
let cycleLen: usize = (2 * nr - 2);
let sChars: Vec<char> = s.chars().collect();
let mut result = String::new();
// First Row
let mut i = 0;
while i < n {
result.push(sChars[i]);
i += cycleLen;
}
// Middle Rows
...
// Last Row
i = (nr - 1);
while i < n {
result.push(sChars[i]);
i += cycleLen;
}
return result;
}Now the middle rows section is similar. We loop through each of the possible rows in the middle. For each of these, we’ll do a while loop similar to the first and last row. These loops are different though, because we have to track two possible values, the “first” and “second” of each cycle.
If the “first” is already past the end of the vector, then we’re already done and can skip the loop. But even if not, we still need an “if check” on the “second” value as well. Each time through the loop, we increase both values by cycleLen.
pub fn convert(s: String, num_rows: i32) -> String {
if (num_rows == 1) {
return s;
}
let n = s.len();
let nr = num_rows as usize; // Convenience for comparison
let cycleLen: usize = (2 * nr - 2);
let sChars: Vec<char> = s.chars().collect();
let mut result = String::new();
// First Row
let mut i = 0;
while i < n {
result.push(sChars[i]);
i += cycleLen;
}
// Middle Rows
for row in 1..(nr - 1) {
let mut first = row;
let mut second = cycleLen - row;
while first < n {
result.push(sChars[first]);
if second < n {
result.push(sChars[second]);
}
first += cycleLen;
second += cycleLen;
}
}
// Last Row
i = (nr - 1);
while i < n {
result.push(sChars[i]);
i += cycleLen;
}
return result;
}And that’s our complete solution!
Haskell Solution
The Haskell solution follows the same algorithm, but we’ll make a few stylistic changes compared to Rust. In Haskell, we’ll go ahead and define specific lists of indices for each row. That way, we can combine these lists and make our final string all at once using concatMap. This approach will let us demonstrate the power of ranges in Haskell.
We start our defining our base case and core parameters:
zigzagConversion :: String -> Int -> String
zigzagConversion input numRows = if numRows == 1 then input
else ...
where
n = length input
cycleLen = 2 * numRows - 2
...Now we can define index-lists for the first and last rows. These are just ranges! We have the starting element, and we know to increment it by cycleLen. The range should go no higher than n - 1. Funny enough, the range can figure out that it should be empty in the edge case that our input is too small to fill all the rows!
zigzagConversion :: String -> Int -> String
zigzagConversion input numRows = if numRows == 1 then input
else ...
where
n = length input
cycleLen = 2 * numRows - 2
firstRow :: [Int]
firstRow = [0,cycleLen..n - 1]
lastRow :: [Int]
lastRow = [numRows - 1, numRows - 1 + cycleLen..n - 1]
...In Rust, we used a while-loop with two state values to calculate the middle rows. Hopefully you know from this series now that this while loop translates into a recursive function in Haskell. We’ll accumulate our list of indices as a tail argument, and keep the two stateful values as our other input parameters. We’ll combine all our lists together into one big list of int-lists, allRows.
zigzagConversion :: String -> Int -> String
zigzagConversion input numRows = if numRows == 1 then input
else ...
where
n = length input
cycleLen = 2 * numRows - 2
firstRow :: [Int]
firstRow = [0,cycleLen..n - 1]
lastRow :: [Int]
lastRow = [numRows - 1, numRows - 1 + cycleLen..n - 1]
middleRow :: Int -> Int -> [Int] -> [Int]
middleRow first second acc = if first >= n then reverse acc
else if second >= n then reverse (first : acc)
else middleRow (first + cycleLen) (second + cycleLen) (second : first : acc)
middleRows :: [[Int]]
middleRows = map (\i -> middleRow i (cycleLen - i) []) [1..numRows-2]
allRows :: [[Int]]
allRows = firstRow : middleRows <> [lastRow]
...Now we bring it all together with one final step. We make a vector from our input, and define a function to turn a single int-list into a single String. Then at the top level of our function (the original else branch), we use concatMap to bring these together into our final result String.
zigzagConversion :: String -> Int -> String
zigzagConversion input numRows = if numRows == 1 then input
else concatMap rowIndicesToString allRows
where
n = length input
cycleLen = 2 * numRows - 2
firstRow :: [Int]
firstRow = [0,cycleLen..n - 1]
lastRow :: [Int]
lastRow = [numRows - 1, numRows - 1 + cycleLen..n - 1]
middleRow :: Int -> Int -> [Int] -> [Int]
middleRow first second acc = if first >= n then reverse acc
else if second >= n then reverse (first : acc)
else middleRow (first + cycleLen) (second + cycleLen) (second : first : acc)
middleRows :: [[Int]]
middleRows = map (\i -> middleRow i (cycleLen - i) []) [1..numRows-2]
allRows :: [[Int]]
allRows = firstRow : middleRows <> [lastRow]
inputV :: V.Vector Char
inputV = V.fromList input
rowIndicesToString :: [Int] -> String
rowIndicesToString = map (inputV V.!)Conclusion
This comparison once again showed how while loops in Rust track with recursive functions in Haskell. We also saw some nifty Haskell features like ranges and tail recursion. Most of all, we saw that even with a trickier algorithm, we can still keep the same basic shape of our algorithm in a functional or imperative style.
To learn more about these problem solving concepts, take a look at Solve.hs, our comprehensive course on problem solving in Haskell. You’ll learn about recursion, list manipulation, data structures, graph algorithms, and so much more!