ZigZag Conversion Coding Challenge

Question

This is my solution for ZigZag Conversion, a coding challenge from LeetCode.

The challenge:

Write a program that takes two parameters, a string and a number of rows, that interprets the string as if it were displayed in a zigzag pattern and returns a line by line conversion of this interpretation in a final answer string.

Example:

Given the string 'PAYPALISHIRING', and 3 rows:

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

The program should output:

"PAHNAPLSIIGYIR"

My approach was to use a list of dictionaries, with the dictionaries as columns and their position in the list representing row positions. At the end of the control flow the list of dictionaries is unpacked and returned in the final output string.

My solution:

class Solution(object):
 def convert(self, s, numRows):
 row = numRows
 if row <= 1:
 return(s)
 else:
 a_lst = []
 a_dict = {}
 outer_count = 0
 loop_count = 0
 my_count = 0
 inner_count = row
 if row == 2:
 minus = 0
 else:
 minus = 2
 for i in s:
 loop_count+=1
 if outer_count < row:
 outer_count+=1
 a_dict[outer_count] = i
 if outer_count == row:
 my_count = 0
 inner_count = row
 dict_copy = a_dict.copy()
 a_lst.append(dict_copy)
 a_dict.clear()
 elif loop_count == len(s):
 dict_copy = a_dict.copy()
 a_lst.append(dict_copy)
 a_dict.clear()
 elif my_count < row - minus:
 my_count+=1
 if row == 2:
 inner_count = my_count
 else:
 inner_count-=1
 a_dict[inner_count] = i
 if my_count == row - minus:
 outer_count = 0
 dict_copy = a_dict.copy()
 a_lst.append(dict_copy)
 a_dict.clear()
 elif loop_count == len(s):
 dict_copy = a_dict.copy()
 a_lst.append(dict_copy)
 a_dict.clear()
 my_count = 1
 my_str = ''
 while my_count <= row:
 for d in a_lst:
 for key in d:
 try:
 my_str+=(d[my_count])
 break
 except KeyError:
 break
 my_count+=1
 return(my_str)

I would like any suggestions on improving code readability or conditional control logic. I would also like to know if I missed any edge cases. Thank you.

Answer 1

• DRY. Every path through the loop ends up in

   dict_copy = a_dict.copy()
   a_lst.append(dict_copy)
   a_dict.clear()
  

  Lift it out out of the conditionals. You will also immediately see that the branches oop_count == len(s) become no-ops, and could be safely removed, along with now irrelevant loop_count. The loop now looks a bit more manageable:

   for i in s:
   if outer_count < row:
   outer_count+=1
   a_dict[outer_count] = i
   if outer_count == row:
   my_count = 0
   inner_count = row
   elif my_count < row - minus:
   my_count+=1
   inner_count-=1
   a_dict[inner_count] = i
   if my_count == row - minus:
   outer_count = 0
   dict_copy = a_dict.copy()
   a_lst.append(dict_copy)
   a_dict.clear()
  

  Still, it is a textbook example of spaghetti. I must admit I failed to follow the control flow.

• Special casing of row==2 is extremely suspicious. I don't see why it should be a special case. If it should indeed, it is a trong indication that the algorithm is flawed.

• Speaking of the algorithm, it seems overcomplicated. As far as I can tell, the point of this exercise is to determine a pattern of indices. For example, consider a case of 5 rows. The zigzag table looks like

   0 8 16
   1 7 9 15 17
   2 6 10 14 18 ...
   3 5 11 13 19
   4 12 20
  

  Take e.g. a row 1 (1, 7, 9, 15, 19, ...). See that the differences alternate between 6 and 2.

  Prove (or at least convince yourself) that it is the case. Whatever numRows is, the indices' deltas in the row alternate between (numRows - row - 1) * 2 and row * 2. Once you do it, the construction of the output string is trivial, and does not require any heavy-weight structures like dictionaries (or the list of them).

• Tim_Jarvis99: Thanks! I should first look for a pattern, I just sort of eye-balled it and made an attack at the first idea that seemed to work. I should think these out much more. Any tips on how I could better approach such problems? Also what is DRY?