0

I'm trying to write the code to draw n diagonals in an m by m square such that they do not touch each other.

For example, for m=2 and n=3:

enter image description here

I tried to approach it by creating a list of pairs of points by generating the permutations and checking the solution before proceeding. Therefore, I have (m+1)*(m+1) points that create the cells of an m by m square.



def dist(a,b):
  return ((a[0] - b[0])**2 + (a[1] - b[1])**2)**.5

def can_be_extended_to_solution(perm):
  i = len(perm) - 1
  for j in range(i):
    for k in range(2):
      for l in range(2):
        if dist(perm[i][k],perm[j][l]) == 0:
          return False
  return True


def diagonal(perm,n,m):
  if len(perm)==n:
    print(perm)
    return
    

  temp =[]
  for k in range(m):
    for i in range(m):
      if [k,i] not in perm:
        for j in [+1,-1]:
          if [k+j,i+j] not in perm and (k+j<m and i+j<m) and (0<k+j and 0<i+j):
            temp = [[k,i],[k+j,i+j]]
            perm.append(temp)

            if can_be_extended_to_solution(perm):
              diagonal(perm,n,m)
            perm.pop()
m=2
n=3

diagonal([],m+1,n)

The output:

enter image description here

The code works and I'm getting the expected result. However, it's very slow. I'm trying to learn to improve my coding skills and do it more efficiently. So, I'd appreciate it if someone reviews my code and tells me what I can do better and what mistakes I'm making. I see that I have many loops and that's the reason for the slow speed, but I can't figure out any other way to implement those loops or avoid them.

BlueEliS
  • 21
  • 4
  • the timing study on the `diagona(perm,m,n)` shows that the recursion in the code is the resource drag. Have you looked `yield` based definition? – sudhish Jan 02 '21 at 10:37
  • [class VPTree(MetricTree)](https://well-adjusted.de/~jrspieker/mspace/) – sudhish Jan 02 '21 at 10:40
  • [What is the use of the yield keyword in Python, and what does it do?](https://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do) – sudhish Jan 02 '21 at 10:41

1 Answers1

0

Unique Diagonals

An algorithmic map of the unique diagonals

Probably, the code can improve if you try using the algorithm based on this pattern. I am using 1 as positive diagonal, -1 as negative (slope=-45deg) diagonal.

My impression on the pattern is that based on the starting cell and neighbouring cells will get selected based on this. An algorithmic map of a 3x3 matrix

I may update this answer with some code if possible. Does this help?
More inputs may help. let me know.

sudhish
  • 98
  • 5
  • 1
    Thank you this sure is a better (less complicated) algorithm to approach the problem. I'll try to write the code for this and get back here. However, my main objective here is to learn to code more efficiently (although it is important to design the algorithm more efficiently). So if you have any comments on my code, it could be helpful. – BlueEliS Jan 01 '21 at 16:25