Click here to Skip to main content
15,067,335 members
Articles / General Programming / Algorithms
Alternative
Article
Posted 4 Sep 2015

Stats

13.7K views
73 downloads
7 bookmarked

ZigZag-Conversion-Problem

Rate me:
Please Sign up or sign in to vote.
4.74/5 (11 votes)
4 Sep 2015CPOL2 min read
Usage of Linq and anonymous Methods help keep code briefly

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

C#
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

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

Outputs four variants of zigzag-converted "PAYPALISHIRING"

ZigZag Output
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().

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Mr.PoorEnglish
Germany Germany
No Biography provided

Comments and Discussions

 
Suggestionpython list generator Pin
Vadim Kurochkin13-Sep-15 10:16
MemberVadim Kurochkin13-Sep-15 10:16 
Generalnice Pin
Mr.PoorEnglish13-Sep-15 21:23
MemberMr.PoorEnglish13-Sep-15 21:23 
AnswerRe: nice Pin
Vadim Kurochkin14-Sep-15 7:36
MemberVadim Kurochkin14-Sep-15 7:36 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.