# Kata Task 

Connect the dots in order to make a picture!

# Notes

* There are 2-26 dots labelled  `a` `b` `c` ...
* The line char is `*`
* Use only straight lines - vertical, horizontal, or diagonals of a square
* The paper is rectangular - `\n` terminates every line
* All input is valid

# Examples


InputExpected

 
 a       b 
 e         
            
 d       c 
 



          
 *********
 *       *
 *       *
 *********
 



InputExpected

 
    a
   e
      
 d     b
  
         
    c
 

     
    *
   * *
  *   *
 *     *
  *   *
   * *
    *

Difficulty: introductory

Starter code:

def connect_the_dots(paper):
	

Solutions:
def connect_the_dots(paper):
    Y    = paper.find("\n")+1
    lst  = list(paper)
    pts  = {c: i for i,c in enumerate(paper) if c.isalpha() }
    chrs = sorted(pts)
    
    for i in range(len(pts)-1):
        a,b = sorted((pts[chrs[i]], pts[chrs[i+1]]))
        (x,y),(u,v) = divmod(a,Y), divmod(b,Y)
        dx, dy = Y * ( (u>x)-(u<x) ), (v>y)-(v<y)
    
        for j in range(a,b+1,dx+dy): lst[j]='*'
    
    return ''.join(lst)


def connect_the_dots(s):
    s = list(map(list, s.splitlines()))
    arr = sorted((v,i,j) for i,row in enumerate(s) for j,v in enumerate(row) if v.isalpha())
    for (_,y1,x1),(_,y2,x2) in zip(arr,arr[1:]):
        py,px = y1,x1
        s[py][px] = '*'
        while (py,px) != (y2,x2):
            py += (1 if y2>py else -1 if y2<py else 0)
            px += (1 if x2>px else -1 if x2<px else 0)
            s[py][px] = '*'        
    return '\n'.join(map(''.join,s))+'\n'

def connect_the_dots(paper):
    dots = {c: (i, j) for i, row in enumerate(paper.split("\n")) for j, c in enumerate(row) if c != " "}
    points = sorted(dots.keys())
    coords = sum((link(dots[a], dots[b]) for a, b in zip(points, points[1:])), list(dots.values()))
    return "\n".join("".join("*" if (i, j) in coords else " " for j, _ in enumerate(row)) for i, row in enumerate(paper.split("\n")))
    
def link(a, b):
    dx, dy = (-1 if a[i] > b[i] else 1 if a[i] < b[i] else 0 for i in (0, 1))
    return [(a[0] + dx*i, a[1] + dy*i) for i in range(1, abs(a[0] - b[0]) or abs(a[1] - b[1]))]
    
# Not very proud of that, so ugly and antipythonic.


def connect_the_dots(paper):
    board = list(map(list, paper.splitlines(keepends=True)))
    alphabets = {
        x: (i, j)
        for i, row in enumerate(board)
        for j, x in enumerate(row)
        if not x.isspace()
    }
    coords = [coord for _, coord in sorted(alphabets.items())]
    for (r1, c1), (r2, c2) in zip(coords, coords[1:]):
        dr = 0 if r1 == r2 else (r2 - r1) // abs(r2 - r1)
        dc = 0 if c1 == c2 else (c2 - c1) // abs(c2 - c1)
        while True:
            board[r1][c1] = '*'
            if r1 == r2 and c1 == c2:
                break
            r1 += dr
            c1 += dc
    return ''.join(map(''.join, board))

def connect_the_dots(paper):
    paper_list = list(paper)
    lines = paper.split('\n')
    len_line = len(lines[0]) + 1
    coords = []
    for letter in 'abcdefghijklmnopqrstuvwxyz':
        found = False

        for row_index in range(len(lines)):
            try:
                column_index = lines[row_index].index(letter)
                found = True
                coords.append((row_index, column_index))
            except:
                pass

        if not found:
            break

    for i in range(1, len(coords)):
        from_x = coords[i-1][0]
        to_x = coords[i][0]
        from_y = coords[i-1][1]
        to_y = coords[i][1]

        step_x = 1
        step_y = 1

        if from_x == to_x:
            step_x = 0
        if from_x > to_x:
            step_x = -1
        if from_y == to_y:
            step_y = 0
        if from_y > to_y:
            step_y = -1

        for _ in range(1 + max(from_x-to_x, to_x-from_x,from_y-to_y,to_y-from_y)):
            paper_list[from_y + (from_x * len_line)] = '*'
            from_x += step_x
            from_y += step_y


    return "".join(paper_list)

from string import ascii_lowercase as lu
def connect_the_dots(li):
    li = [[j for j in i] for i in li.splitlines()]
    
    find_char = lambda c: next(([i,k] for i,j in enumerate(li) for k,l in enumerate(j) if l==c), 0) # find next char from string/array
    
    lower = iter(lu)
    
    char, chars = find_char(next(lower)), []
    
    while char:
        chars.append(char)
        char = find_char(next(lower))
    
    A = lambda s, se, see, e, ee, eee: list(zip(list(range(s, se + 1, see)), list(range(e, ee + 1, eee)))) # for diagonals
    
    for h, g in zip(chars, chars[1:]):
        i, j = h ; k, l = g
        m, m1, n, n1 = min(i, k), min(j, l), max(i, k), max(j, l)
        if i == k:                      # horizontal
            while m1 <= n1 : 
                li[i][m1] = '*' ; m1 += 1
        elif j == l:                    # verical
            while m <= n : 
                li[m][j] = '*' ; m += 1
        else:                           # diagonals
            B,C = i > k, j > l
            for o, p in A(i, k - (2 if B else 0), (1 if not B else -1), j, l - (2 if C else 0),(1 if not C else -1)) : 
                 li[o][p] = '*'
        i, j = k, l
    return "\n".join(["".join(i) for i in li])+"\n"

def connect_the_dots(paper):
    
    laliste = paper[:-1].split("\n")
    tablo = [[' ' for i in range(len(laliste[0]))] for j in range(len(laliste)) ]
    lesPositions = []
    
    for i, ligne in enumerate(laliste):
        listeCar = list(ligne)
        #listeCar.pop()
        for j, car in enumerate(listeCar):
            if 97<=ord(car)<=122:
                lesPositions.append((car, i, j))
    lesPositions.sort(key = lambda x:x[0])
    pointA = lesPositions.pop()
    while lesPositions:
        pointB = lesPositions.pop()
        if pointA[1] == pointB[1]: #ligne verticale
            ext = [pointB[2], pointA[2]]
            for y in range(min(ext), max(ext)+1):
                tablo[pointA[1]][y] = '*'
                
        elif pointA[2] == pointB[2]: #ligne horizontale
            ext = [pointB[1], pointA[1]]
            for x in range(min(ext), max(ext)+1):
                tablo[x][pointA[2]] = '*'
        else :
            dx = 1 if pointA[1]<pointB[1] else -1
            dy = 1 if pointA[2]<pointB[2] else -1
            y = pointA[2]
            for x in range(pointA[1], pointB[1]+dx, dx):
                tablo[x][y]='*'
                y += dy
        pointA = pointB
                
    tablo2 = [''.join(ligne)+'\n' for ligne in tablo]
    return ''.join(tablo2)

def connect_the_dots(paper: str) -> str:
    res = list(map(list, paper.splitlines()))
    d = [v for _, v in sorted({c: (i, j) for i, row in enumerate(res) for j, c in enumerate(row) if c != ' '}.items())]

    for (prev_i, prev_j), (i, j) in zip(d, d[1:]):
        if prev_i == i:  # same row
            for x in range(min(j, prev_j), max(j, prev_j) + 1):
                res[i][x] = '*'

        elif prev_j == j:  # same column
            for x in range(min(i, prev_i), max(i, prev_i) + 1):
                res[x][j] = '*'

        else:  # diagonal
            di, dj = [1, -1][prev_i > i], [1, -1][prev_j > j]
            for x in range(abs(prev_j - j) + 1):
                res[prev_i + x * di][prev_j + x * dj] = '*'

    return '\n'.join(map(''.join, res)) + "\n"


def connect_the_dots(paper):
    letters_input = [l for l in "abcdefghijklmnopqrstuvwxyz" if l in paper]
    table = [list(row) for row in paper.split("\n")[:-1:]]
    coordinates = [(row.index(letter), indx) for letter in letters_input for indx, row in enumerate(table) if letter in row]
    print(coordinates)
    for indx, coord in enumerate(coordinates[:-1:]):
        if coord[1] == coordinates[indx+1][1]:
            for x in range(min(coord[0], coordinates[indx+1][0]), max(coord[0], coordinates[indx+1][0]) + 1):
                table[coord[1]][x] = "*"
        elif coord[0] == coordinates[indx + 1][0]:
            for y in range(min(coord[1], coordinates[indx + 1][1]), max(coord[1], coordinates[indx + 1][1]) + 1):
                table[y][coord[0]] = "*"
        else:
            step_x = (coordinates[indx+1][0] - coord[0]) / abs(coord[0] - coordinates[indx+1][0])
            lst_x = [int(coord[0] + step_x * k) for k in range(abs(coord[0] - coordinates[indx+1][0]) + 1)]
            step_y = (coordinates[indx + 1][1] - coord[1]) / abs(coord[1] - coordinates[indx + 1][1])
            lst_y = [int(coord[1] + step_y * k) for k in range(abs(coord[1] - coordinates[indx + 1][1]) + 1)]
            for x, y in zip(lst_x, lst_y):
                table[y][x] = "*"
    res = "\n".join(["".join(row) for row in table]) + "\n"
    return res

def abs(x):
    if x<0:
        return -x
    else:
        return x

def norm(x):
    if x == 0:
        return 0
    else:
        return abs(x)//x

def string_to_grid(string):
    return [list(x) for x in string.split('\n')][0:-1]

def grid_to_string(grid):
    result = ''
    for y in range(0,len(grid)):
        result += ''.join(grid[y]) + '\n'
    return result
def connect_two_points(p1,p2,grid):
    ydiff = p2[0] - p1[0]
    xdiff = p2[1] - p1[1]
    ystep = norm(ydiff)
    xstep = norm(xdiff)
    
    step = (ystep,xstep)
    
    for i in range(0,max(abs(ydiff),abs(xdiff))+1):
        y_coord = p1[0] + ystep*i
        x_coord = p1[1] + xstep*i
        
        grid[y_coord][x_coord] = '*'

def generate_point_dictionary(grid):
    D = {}
    for y in range(0,len(grid)):
        for x in range(0, len(grid[y])):
            if grid[y][x] != ' ':
                D[grid[y][x]] = [y,x]
    return D
    
def connect_the_dots(inp):
    grid = string_to_grid(inp)
    D = generate_point_dictionary(grid)
    alph = 'abcdefghijklmnopqrstuvwxyz'
    for x in range(0,len(alph)):
        try:
            connect_two_points(D[alph[x]],D[alph[x+1]],grid)
        except:
            return grid_to_string(grid)