Check if a set of points described a triangle

Question

I tried to solve this question but couldn't find a simple solution without passing all rows and find which numbers are on the same line.

Is there a simple way to find triangles?

this is my solution for finding a triangle:

How can I change it to be more "pythonic"? (or even better method for solving it)

from sympy.solvers import solve
from sympy import Symbol
from collections import Counter

vals = [8,17,19] # the triangle
dicl = []   #list of dics
for v in vals:
    dic = {}
    dic['val'] = v
    v1 = v
    done = 0
    stepsb = 0
    while done == 0:  #going backword untill reaching the big triabgle edges
        x = Symbol('x')
        k = solve((x**2 + x)/2 +1 - v1, x)
        k = list(filter(lambda x:x>0, k))
        if k[0]%1 == 0:               
            done = 1
        else:
            v1 -= 1
            stepsb += 1

    dic['line'] = k[0]
    dic['stepsb'] = stepsb  #dist from the left edge
    dic['stepsf'] = (k[0]**2 + 3*k[0] + 2)/2 - v  #dist from the right edge
    dicl.append(dic)
    print(dic)


lines = [l['line'] for l in dicl]
mc = Counter(lines).most_common(1)[0][0]   #finding the numbers on the same line

minv = min([l['val'] for l in dicl if l['line'] == mc])
maxv = max([l['val'] for l in dicl if l['line'] == mc])
stb = [l['stepsb'] for l in dicl if l['val'] == minv][0]
stf = [l['stepsf'] for l in dicl if l['val'] == maxv][0]
for k in dicl:
    if k['stepsb'] == stb and k['stepsf'] == stf:
        print("good")
        break

Answer 1

A first step could be to search for a formula that translates the one-dimensional point number t to an x,y coordinate.

So, search for an n such that n*(n+1)/2 < t:

from sympy import solve, Eq
from sympy.abc import n, t

f = Eq(n * (n + 1), 2 * t)
print(solve(f, n))  

This shows as positive root: (sqrt(8*t + 1) - 1)/2. To be strict smaller, a formula that copes with small approximation errors, could be:

floor((sqrt(8*t + 1) - 1)/2 - 0.0000001

The following idea is, given a list of indices:

• convert them to xy coordinates
• find their center (sum and divide by the length of the list)
• find the distances of each xy to the center
• check that all distances are equal

To convert to an xy position, note that the height of an equilateral triangle with base 1 is sqrt(3)/2, so the distances between the y-positions should be multiplied by that factor. The x-positions need to be centered which can be achieved by subtracting n/2.

import math

def find_xy(t):
    # convert the numerical position into an xy coordinate in the plane
    # first find largest n such that n*(n+1)/2 < t
    n = math.floor((math.sqrt(8 * t + 1) - 1) / 2 - 0.0000001)
    return (n + 1) * math.sqrt(3) / 2, t - n * (n + 1) // 2 - n/2

def sq_dist(p, q):
    return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2

def center(points):
    # find the center of a list of points
    l = len(points)
    x = sum(p[0] for p in points)
    y = sum(p[1] for p in points)
    return x / l, y / l

def is_regular(tri_points):
    points = [find_xy(t) for t in tri_points]
    cent = center(points)
    dists = [sq_dist(cent, p) for p in points]
    return max(dists) - min(dists) < 0.000001

Note that this code finds geometric figures for which all the points lie on a circle. This doesn't work for the parallelogram. The actual question also has some extra criteria: all edges should follow the grid lines, and all edges need to be equal in length.

Therefore, it is useful to have 3 coordinates for each point: the row, the column and the diagonal (the 3 directions of the grid).

The length in each direction, is just the maximum minus the minimum for that direction. These lengths are called d_r, d_c and d_d in the code below.

Checking for a valid triangle, the 3 lengths need to be equal. One way to check this, is to check that the minimum of the lengths is equal to the maximum.

For a valid parallelogram, two lengths need to be equal, and the third should be the double. Checking that the maximum length is twice the minimum length should cover this. But, because this can already be reached using 3 points, we should also check that for a given direction, there are exactly 2 points at the minimum and 2 at the maximum. Summing all points and comparing twice the sum of maximum and minimum should accomplish this.

For a valid hexagon, the 3 lengths should be equal. So, the same test as for the triangle: the minimum of the lengths equal to the maximum. And also the test on the sums is needed, as 4 points can already fulfil the length conditions.

import math

def find_row_col_diag(t):
    # convert the numerical position into an row,col,diag coordinate in the plane
    # first find largest n such that n*(n+1)/2 < t
    n = math.floor((math.sqrt(8 * t + 1) - 1) / 2 - 0.0000001)
    row, col = n + 1, t - n * (n + 1) // 2
    return row, col, row - col

def check_valid_figure(tri_points):
    points = [find_row_col_diag(t) for t in tri_points]
    rs = [r for (r, c, d) in points]
    cs = [c for (r, c, d) in points]
    ds = [d for (r, c, d) in points]
    sum_r = sum(rs)
    min_r = min(rs)
    max_r = max(rs)
    d_r = max_r - min_r
    sum_c = sum(cs)
    min_c = min(cs)
    max_c = max(cs)
    d_c = max_c - min_c
    sum_d = sum(ds)
    min_d = min(ds)
    max_d = max(ds)
    d_d = max_d - min_d
    if len(points) == 3:
        is_ok = max(d_r, d_c, d_d) == min(d_r, d_c, d_d)
    elif len(points) == 4:
        is_ok = max(d_r, d_c, d_d) == 2 * min(d_r, d_c, d_d) \
                and sum_r == 2 * (min_r + max_r) and sum_c == 2 * (min_c + max_c) and sum_d == 2 * (min_d + max_d)
    elif len(points) == 6:
        is_ok = max(d_r, d_c, d_d) == min(d_r, d_c, d_d) \
                and len(set(rs)) == 3 and len(set(cs)) == 3 and len(set(ds)) == 3
    else:
        is_ok = False
    print(" ".join([str(t) for t in tri_points]), end=" ")
    if is_ok:
        print("are the vertices of a",
              "triangle" if len(points) == 3 else "parallelogram" if len(points) == 4 else "hexagon")
    else:
        print("are not the vertices of an acceptable figure")

tri_point_lists = [[1, 2, 3],
                   [11, 13, 22, 24],
                   [11, 13, 29, 31],
                   [11, 13, 23, 25],
                   [26, 11, 13, 24],
                   [22, 23, 30],
                   [4, 5, 9, 13, 12, 7]]
for lst in tri_point_lists:
    check_valid_figure(lst)

The last code can be further compressed using list comprehensions:

def check_valid_figure_bis(tri_points):
    points = [find_row_col_diag(t) for t in tri_points]
    rs, cs, ds = [[p[i] for p in points] for i in range(3)]
    sums = [sum(xs) for xs in (rs, cs, ds)]
    mins = [min(xs) for xs in (rs, cs, ds)]
    maxs = [max(xs) for xs in (rs, cs, ds)]
    lens = [ma - mi for mi, ma in zip(mins, maxs)]
    if len(points) == 3:
        is_ok = max(lens) == min(lens)
    elif len(points) == 4:
        is_ok = max(lens) == 2 * min(lens) and all([su == 2 * (mi + ma) for su, mi, ma in zip(sums, mins, maxs)])
    elif len(points) == 6:
        is_ok = max(lens) == min(lens) and all([len(set(xs)) == 3 for xs in (rs, cs, ds)])
    else:
        is_ok = False
    return is_ok