# 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
 

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

Source: codewars | Difficulty: EASY
Tags: Fundamentals

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]))]


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)
	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 (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:
			while m1 <= n1:
				li[i][m1] = '*'
				m1 += 1
		elif j == l:
			while m <= n:
				li[m][j] = '*'
				m += 1
		else:
			(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)
		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]:
			ext = [pointB[2], pointA[2]]
			for y in range(min(ext), max(ext) + 1):
				tablo[pointA[1]][y] = '*'
		elif pointA[2] == pointB[2]:
			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:
			for x in range(min(j, prev_j), max(j, prev_j) + 1):
				res[i][x] = '*'
		elif prev_j == j:
			for x in range(min(i, prev_i), max(i, prev_i) + 1):
				res[x][j] = '*'
		else:
			(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)