15,309,768 members
Articles / General Programming / Algorithms
Alternative
Article
Posted 4 Sep 2015

14.6K views
7 bookmarked

# ZigZag-Conversion-Problem

Rate me:
Usage of Linq and anonymous Methods help keep code briefly

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

## Share

 Germany
No Biography provided

 As they say, Dictum - factum F#Copy Code `[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.