ZigZag-Conversion-Problem

Download ZigZagConversion.zip (8 KB)

This article is an alternative to Graph is everywhere by Eric Z. Maybe you'd like to refer it, since he provides a very different Solution-Concept.

Problem

The ZigZag-Conversion-Problem is a fancy programmer-riddle:

see the string "PAYPALISHIRING" written in a zigzag-pattern on a given number of rows, eg like this (3 rows):

P   A   H   N
 A P L S I I G
  Y   I   R

Reading it in horizontal lines results to: "PAHNAPLSIIGYIR"
Now write a function for such conversion.

Solution-Concept

As my Original said, traditionally this is solved by searching a pattern among the index of the letters on the same row. And as a traditionallist this is exactly what I did ;-)

Compare zigzags with several row-count, and for each letter in the zigzag note down the stepsize to reach the next letter in the horizontal line:

(3 Rows)
P   A   H   N
 A P L S I I G
  Y   I   R
steps: 4,2,4,2,...

(4 Rows)
P     I     N
 A   L S   I G
  Y A   H R
   P     I
steps: 6,4,2,6,4,2,...

These two samples are actually sufficiant to recognize the pattern: Its a cyclic repetition of a small sequence.
The cycles size equals row-count - 1.

Code

static string ZigZagConvert(string input, int nRows) {
    var cycle = (nRows - 1).Times().From(nRows * 2 - 2).Step(-2); // nRows:3=>{4,2}, 4=>{6,4,2} ...
    var infinite = int.MaxValue.TimesRepeat(cycle).SelectMany(ccl => ccl);
    var map = infinite.Take(input.Length).ToArray();
    var result = new List<int>();
    for (var line = 0; line < nRows; line++) {
        for (var index = line; index < input.Length; index += map[index]) result.Add(index);
    }
    return new string(result.Select(i => input[i]).ToArray());
}

Let me try to explain the non-trivials of those few code-lines:

• var cycle = (nRows - 1).Times().From(nRows * 2 - 2).Step(-2);
  Defines the small sequence, mentioned before
  Note the use of my fancy int.Times() - Extension - normally the line would be expressed as:
  var cycle = Enumerable.Range(1, nRows - 1).Select(i => (nRows - i) * 2);
   
• var infinite = int.MaxValue.TimesRepeat(cycle).SelectMany(ccl => ccl);
  An (nearby) endless repetition of the cyclic sequence, with flattend hierarchy (achived by .SelectMany())
  Again one of my int-Extensions in use - you may consider it as:
  var infinite = Enumerable.Repeat(cycle, int.MaxValue).SelectMany(ccl => ccl);
   
• var map = infinite.Take(input.Length).ToArray();
  Create an arrray which maps each input-letter-index to a stepsize, where to find the next letter in horizontal line.
   
•  (skip two trivial lines)
   
• for (var index = line; index < input.Length; index += map[index]) result.Add(index);
  This code-line loops the horizontal-line-letters from one to the next - very similar to a Graph-Traversal:
  input-letter-indicees define nodes, and the mapping-array defines edges.

Using the code

static void Main() {
    for (var i = 2; i < 6; i++) Console.WriteLine(ZigZagConvert("PAYPALISHIRING", i));
    Console.ReadKey();
}

Outputs four variants of zigzag-converted "PAYPALISHIRING"

P Y A I H R N
 A P L S I I G

PYAIHRNAPLSIIG

P   A   H   N
 A P L S I I G
  Y   I   R

PAHNAPLSIIGYIR

P     I     N
 A   L S   I G
  Y A   H R
   P     I

PINALSIGYAHRPI

P       H
 A     S I
  Y   I   R
   P L     I G
    A       N

PHASIYIRPLIGAN

Points of Interest

As so often just looking at several input/output - samples leads to a convenient solution.

Extension-Functions, especially the Linq-stuff, bring up very brief code, quite intuitive to understand.

By the way a small Introducion to some of my int.Times()-Extensions (contained in the attached Source-File). I often need sequences, and i prefer to have them available as Extension to get rid of the little circuitous use of static Enumerable.Range().