15,038,237 members
Articles / General Programming / Algorithms
Alternative
Article
Posted 4 Sep 2015

13.6K views
7 bookmarked

# ZigZag-Conversion-Problem

Rate me:
4 Sep 2015CPOL2 min read
Usage of Linq and anonymous Methods help keep code briefly

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

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

## About the Author

 Germany
No Biography provided

## Comments and Discussions

 First Prev Next
 python list generator Vadim Kurochkin13-Sep-15 10:16 Vadim Kurochkin 13-Sep-15 10:16
 nice Mr.PoorEnglish13-Sep-15 21:23 Mr.PoorEnglish 13-Sep-15 21:23
 Re: nice Vadim Kurochkin14-Sep-15 7:36 Vadim Kurochkin 14-Sep-15 7:36
 Last Visit: 31-Dec-99 18:00     Last Update: 24-Sep-21 12:34 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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