Click here to Skip to main content
15,304,276 members
Articles / General Programming / Algorithms
Posted 4 Sep 2015


7 bookmarked


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 (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.


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.


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.


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));

Outputs four variants of zigzag-converted "PAYPALISHIRING"

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

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


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


About the Author

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 
As they say, Dictum - factum Big Grin | :-D
[for i in 1..numRows-1 do yield (numRows - i) * 2] |> List.replicate l |> List.concat

where l is the length of the input string. The last operator is necessary in such pipe since replicate returns the sequence of small lists.

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.