7
\$\begingroup\$

Given a list of integers a 2D graph has to be plotted taking 1st, 3rd, 5th, ... numbers as upward slope and 2nd, 4th, ... numbers as downward slope.

I have used a Python list to do it. Is there any further optimization possible with Python?

Sample input:

3, 1, 2, 3, 6, 2, 3, 6, 2, 3, 6, 3, 2, 3, 6, 2, 3, 4, 3, 2, 5, 4, 2, 1, 2, 1, 2, 3, 1, 2, 6, 2, 3, 6, 2, 3, 6, 3, 2, 3, 1, 5, 3, 2, 1, 2, 4, 2, 1, 8, 1, 2

My code:

data = [3, 1, 2, 3, 6, 2, 3, 6, 2, 3, 6, 3, 2, 3, 6, 2, 3, 4, 3, 2, 5, 4, 2, 1, 2, 1, 2, 3, 1, 2, 6, 2, 3, 6, 2, 3, 6, 3, 2, 3, 1, 5, 3, 2, 1, 2, 4, 2, 1, 8, 1, 2]
length = sum(data)
print_list=[]

def populate_list():
    top = -1             #to keep track of max x-axis of list
    x=0
    y=0
    for i in range(0,len(data)):
        if i % 2==0:
            for _ in range(0,data[i]):
                if x>top:
                    print_list.append([])
                    top=x
                    for _ in range(0,length):               #to initialize a new top list
                        print_list[x].append(" ")
                print_list[x][y]="/"
                x+=1
                y+=1
        else:
            for _ in range(0,data[i]):
                x-=1
                print_list[x][y]="\\"
                y+=1

populate_list()
for i in range(len(print_list)-1,-1,-1):                    #printing from bottom up since generated graph is inverted
    print(''.join(map(str,print_list[i])))

OUTPUT:

                                                                                                  /\
                                                                                             /\  /  \              /\
                                                                                            /  \/    \            /  \  /\
                                                                     /\          /\        /          \          /    \/  \
                                                                    /  \      /\/  \      /            \  /\    /          \/\
                                                       /\          /    \  /\/      \/\  /              \/  \  /              \              /\
                                                  /\  /  \    /\  /      \/            \/                    \/                \    /\      /  \/\
                   /\                            /  \/    \  /  \/                                                              \  /  \/\  /      \
              /\  /  \              /\          /          \/                                                                    \/      \/        \
             /  \/    \            /  \  /\    /                                                                                                    \
            /          \          /    \/  \  /                                                                                                      \
     /\    /            \  /\    /          \/                                                                                                        \
  /\/  \  /              \/  \  /                                                                                                                      \
 /      \/                    \/                                                                                                                        \/\
/                                                                                                                                                          \
\$\endgroup\$
5
\$\begingroup\$

Some simple things:

top and length could probably have better names (Top of what? Length of what?), maybe max_x, max_y? And print_list could be better as e.g. graph and populate_list as create_graph?

also print_list should probably be a local variable inside populate_list(), which can then return the list for you to print. Might also be better for it to take data as an argument.

Simplification

Instead of this:

if x>top:
    print_list.append([])
    top=x
    for _ in range(0,length):               #to initialize a new top list
        print_list[x].append(" ")

you could do:

if x+1 > len(graph):
    graph.append([" "] * length)

(top is only used once so len(graph) works just as well, but we need to +1 to x because 0-indexed lists!)

Your final print could be simplified a lot (using 'range' to then iterate over a list is a good sign you could do something with iterators):

for i in print_list[::-1]:                    #printing from bottom up since generated graph is inverted
    print("".join(i))

You can also see your main for loop could do something similar, but because we need to track the iterator as well as the value we can use enumerate to get both:

for i, n in enumerate(data):
        if i % 2==0:
            for _ in range(n):

and while I'm looking at that loop, I see that your two 'for _` loops are basically identical except one goes up, and one goes down. So with some refactoring we can combine them into one.

Putting it all together we get

def populate_graph(data):
    graph = []
    max_y = sum(data)
    x,y = 0,0
    
    for i, n in enumerate(data):
        for _ in range(data[i]):
            if i%2 == 0:
                if x+1 > len(graph):
                    graph.append([" "] * max_y)
                                        
                graph[x][y]="/"
                x += 1
              
            else:           
                x -= 1
                graph[x][y]="\\"  
            
            y+=1
        
    return graph[::-1] #polite to prove a right-way-up-graph

if __name__ == "__main__":
    
    data = [3, 1, 2, 3, 6, 2, 3, 6, 2, 3, 6, 3, 2, 3, 6, 2, 3, 4, 3, 2]
        
    for row in populate_graph(data):                   
        print("".join(row))
\$\endgroup\$
1
  • \$\begingroup\$ 1.len(graph) is inside two for loops, wouldn't it be better if max_x(top) is used in its place 2."Your final print could be simplified a lot (using 'range' to then iterate over a list is a good sign you could do something with iterators):" is it not a good sign? I didn't get it 3. I don't think enumerate has any added advantage \$\endgroup\$ Dec 12 '21 at 14:13
3
\$\begingroup\$

Global variables rarely needed. You have written most of the algorithm inside of a function, which is good; however, you are not really taking full advantage of what functions offer. In particular, they take arguments and return data. You aren't doing that; instead, your function operates on global variables, which is bad in nearly all cases.

Don't make the caller work too hard. I would describe the algorithm in your function as only partially implemented, because it forces the caller to engage in further machinations in order to print it. If the purpose of the function is to generate data that can easily be printed as an ASCII line graph, then the printing itself should be trivially easy.

Avoid tight algorithmic coupling with printing, when feasible.The algorithm is also tightly coupled to printing. On the one hand, that makes sense: we are solving a made-up programming challenge, so we should focus on the concrete challenge at hand. However, one can often develop better programming habits by broadening one's perspective. Instead of writing an algorithm that is narrowly targeted to printing, one can approach the problem like this: (1) convert the raw input data into some other type of data that contains the same information but in a more useful form; (2) convert the generally-more-useful data into what we need specifically for printing.

Test algorithms with a wider range of inputs. Finally, your algorithm is a bit fragile. It has some special case logic to add a new row to print_list whenever the line slopes upward. But what about when the line slopes downward? For example, consider a very simple case where the input data is [3, 7]. The code will add 3 rows on the upward direction, but then the big downward movement of 7 will require that we add rows on the lower portion of the graph. Your code blows up with an IndexError.

My thought process. In the rest of this reply, I'll describe the thought process I used in solving the problem. We begin with a solid program structure that uses functions, not global variables, and that will place no excessive burdens on the caller of our function when it comes time to print:

def main():
    input_data = [3, 1, ...]
    for row in ascii_line_graph(input_data):
        # Printing will be easy: no algorithmic logic required.
        print(row)

def ascii_line_graph(input_data):
    rows = []
    ...
    return rows

if __name__ == '__main__':
    main()

I decided first to convert the idiosyncratic input data into a more generally useful format: a list of Point objects, where each point knows its x-y coordinates and its marker style (up or down). This data conversion doesn't solve the real problem yet, but my intuition is that this generally useful way of storing the data will be amenable to further conversions that are needed for the ultimate printing.

from dataclasses import dataclass

def main():
    input_data = [3, 1, 2]
    for row in ascii_line_graph(input_data):
        print(row)

def ascii_line_graph(input_data):
    # Not fully implemented yet.
    # So far, we're just creating Point instances.
    for p in get_points(input_data):
        yield p

def get_points(input_data):
    x, y = (-1, 0)
    for i, nsteps in enumerate(input_data):
        slope = -1 if i % 2 else 1
        for _ in range(nsteps):
            x += 1
            y += slope
            yield Point(x, y, slope)
        y += slope

@dataclass(frozen = True)
class Point:
    x: int
    y: int
    slope: int

    @property
    def marker(self):
        return '/' if slope == 1 else '\\'

The only remaining step is to convert the list of Point instances into a row-oriented ASCII graph. That requires some sorting and grouping.

from operator import attrgetter
from itertools import groupby

def ascii_line_graph(input_data):
    # Sort the Points by their y values, in descending order.
    y_key = attrgetter('y')
    points = sorted(get_points(input_data), key = y_key, reverse = True)

    # Get the stop value for chart width.
    x_stop = 1 + max(p.x for p in points)

    # Process the points in groups, based on their y values.
    for y, group in groupby(points, y_key):
        # A dict of the marked points for the current row.
        markers = {p.x : p.marker for p in group}

        # Yield the full row.
        row = ''.join(markers.get(x, ' ') for x in range(x_stop))
        yield row.rstrip()
\$\endgroup\$
1
\$\begingroup\$
  • Move your data, etc. out of the global namespace into functions
  • Rather than doing an even/odd check on an index, consider doing the slightly more Pythonic thing of a slice [::2] and zip
  • Consider making a generator function that converts deltas to height values
  • Separate your rendering code that uses /\ from your logical code that calculates heights
  • Avoid your for i in range; changing iteration methods on an iterable is more Pythonic than manipulating indices
  • Use PEP484 type hints

Suggested

from typing import Collection, Iterator, List, Tuple, Iterable


def heights_with_end(start: int, n: int, direction: int) -> Tuple[range, int]:
    end = start + direction*n
    return range(start, end, direction), end - direction


def data_to_heights(data: Collection[int]) -> Iterator[Tuple[bool, range]]:
    ups = data[::2]
    downs = data[1::2]
    height = 0
    for up, down in zip(ups, downs):
        segment, height = heights_with_end(height, up, 1)
        yield True, segment
        segment, height = heights_with_end(height, down, -1)
        yield False, segment


def make_grid(deltas: Collection[int]) -> List[List[str]]:
    segments = tuple(data_to_heights(deltas))
    width = sum(deltas)
    flat = [y for is_up, segment in segments for y in segment]
    bottom = min(flat)
    height = max(flat) - bottom
    grid = [
       [' ']*width
       for _ in range(1 + height)
    ]

    x = 0
    for is_up, segment in segments:
        for y in segment:
            grid[height + bottom - y][x] = '/' if is_up else '\\'
            x += 1

    return grid


def print_grid(grid: Iterable[Iterable[str]]) -> None:
    print(
        '\n'.join(
            ''.join(line) for line in grid
        )
    )


def test() -> None:
    data = (
        3, 1, 2, 3, 6, 2, 3, 6, 2, 3, 6, 3, 2, 3, 6, 2, 3, 4, 3, 2, 5, 4, 2, 1,
        2, 1, 2, 3, 1, 2, 6, 2, 3, 6, 2, 3, 6, 3, 2, 3, 1, 5, 3, 2, 1, 2, 4, 2,
        1, 8, 1, 2,
    )
    grid = make_grid(data)
    print_grid(grid)


if __name__ == '__main__':
    test()
\$\endgroup\$
3
  • \$\begingroup\$ Plenty of good advice here, and in the useful answer from @JeffUK, but I think both fail in the same way the OP's code fails, with an IndexError if the line crosses below the initial point. (But it's possible I missed a detail outlawing such inputs.) \$\endgroup\$
    – FMc
    Dec 4 '21 at 21:15
  • \$\begingroup\$ @FMc You're right. Works for sample input but not for the scenario you describe. Will edit later. \$\endgroup\$
    – Reinderien
    Dec 4 '21 at 22:10
  • 1
    \$\begingroup\$ @FMc Should be fixed \$\endgroup\$
    – Reinderien
    Dec 4 '21 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.