Getting Intersection Between 2 Lists in Python 3

Question

I have an application which has a list of objects (answers), each of which contains a list of tuples called spaces. I am trying to write a function which generates a list of common items between all spaces list. Each record in this list should be [(answer,index), (answer, index)] (This is a crossword-style program, requiring identification of common spaces between all the answers).

Currently, I have the code as follows:

for answer in answers:
    for compareAnswer in answers:
        if( answer != compareAnswer ):
            for compareSpace in compareAnswer.spaces:
                if compareSpace in answer.spaces:
                    intersect.append( [( answer, answer.spaces.index(compareSpace) ), ( compareAnswer, compareAnswer.spaces.index(compareSpace) ) ] );

This code works as intended; however, I feel there is probably an easier way to get where I'm headed. Is there a more pythonic (or at least easier to read) way of doing this? Thanks.

Full program code:

import os
import random

def printList( toPrint ):
    for line in toPrint:
        print( line )
    print("---------------------")

#
#
#
class Answer:
    def __init__( self, num, ad, length, y, x ):
        self.num = num
        self.ad = ad
        self.length = length
        self.spaces = []
        if( ad == 'A' ):
            for occupied in range(length):
                self.spaces.append( (y,x) )
                x += 1
        if( ad == 'D' ):
            for occupied in range(length):
                self.spaces.append( (y,x) )
                y += 1              
        self.domain = []
        self.intersect = []
        self.value = " " * length

    def SetDomain( self, dictionary ):
        for poss in dictionary:
            if( len( poss ) == self.length ):
                self.domain.append( poss )

#
#
#
puzPath = os.getcwd() + "\input.txt"
dictPath = os.getcwd() + "\dictionary.txt"

puzzle = []
dictionary = []
count = 0
answers = []
intersect = []

#Read files for puzzle and dictionary
with open(puzPath,'r') as puzFile:
    puzzle = [list(line.strip()) for line in puzFile]

with open(dictPath,'r') as dictFile:
    dictionary = [line.strip() for line in dictFile]

#Add border to eliminate out of bounds errors
size = len(puzzle[0])
border = ['X']*size
puzzle.insert(0, border)
puzzle.append(border)
puzzle = [['X'] + line + ['X'] for line in puzzle]

#Number board and set variables
for y in range(1, len(puzzle)-1):
    for x in range(1, len(puzzle[0])-1):
        if ( puzzle[y][x] == 'O' ):
            downStart = False
            acrossStart = False
            if ( puzzle[y-1][x] == 'X' and puzzle[y+1][x] != 'X' ):
                downStart = True
            if ( puzzle[y][x-1] == 'X' and puzzle[y][x+1] != 'X' ):
                acrossStart = True
            if ( downStart or acrossStart ):
                count+=1

            if( acrossStart ):
                puzzle[y][x] = count
                length = 1
                while( puzzle[y][x+length] != 'X' ):
                    length += 1
                answers.append( Answer( count, "A", length, y, x ) )
            if( downStart ):
                puzzle[y][x] = count
                length = 1
                while( puzzle[y+length][x] != 'X' ):
                    length += 1
                answers.append( Answer( count, "D", length, y, x ) )

#Set domain & contstraints for all variables
for answer in answers:
    answer.SetDomain( dictionary )
    for compareAnswer in answers:
        if( answer.ad != compareAnswer.ad ):
            for compareSpace in compareAnswer.spaces:
                if compareSpace in answer.spaces:
                    intersect.append( [( answer, answer.spaces.index(compareSpace) ), ( compareAnswer, compareAnswer.spaces.index(compareSpace) ) ] );

Sample answers.spaces:

[(1, 1), (1, 2), (1, 3), (1, 4)]
---------------------
[(1, 1), (2, 1), (3, 1)]
---------------------
[(1, 3), (2, 3), (3, 3)]
---------------------
[(1, 6), (1, 7), (1, 8), (1, 9)]
---------------------
[(1, 7), (2, 7), (3, 7)]
---------------------
[(1, 9), (2, 9), (3, 9)]
---------------------
[(3, 1), (3, 2), (3, 3), (3, 4)]
---------------------
[(3, 2), (4, 2), (5, 2), (6, 2), (7, 2)]
---------------------
[(3, 4), (4, 4), (5, 4), (6, 4), (7, 4)]
---------------------
[(3, 6), (3, 7), (3, 8), (3, 9)]
---------------------
[(3, 6), (4, 6), (5, 6), (6, 6), (7, 6)]
---------------------
[(3, 8), (4, 8), (5, 8), (6, 8), (7, 8)]
---------------------
[(4, 4), (4, 5), (4, 6)]
---------------------
[(5, 1), (5, 2), (5, 3), (5, 4)]
---------------------
[(5, 6), (5, 7), (5, 8), (5, 9)]
---------------------
[(6, 4), (6, 5), (6, 6)]
---------------------
[(7, 1), (7, 2), (7, 3), (7, 4)]
---------------------
[(7, 1), (8, 1), (9, 1)]
---------------------
[(7, 3), (8, 3), (9, 3)]
---------------------
[(7, 6), (7, 7), (7, 8), (7, 9)]
---------------------
[(7, 7), (8, 7), (9, 7)]
---------------------
[(7, 9), (8, 9), (9, 9)]
---------------------
[(9, 1), (9, 2), (9, 3), (9, 4)]
---------------------
[(9, 6), (9, 7), (9, 8), (9, 9)]

Answer 1

If n is the number of answers and m is the number of spaces in each answer then the time complexity of your code is O(n*n*m*m*m) that can be improved e.g., here's O(n*m) algorithm:

from collections import defaultdict

spaces = defaultdict(list) # space -> [(answer1, index1), (answer2, index2), ...]
for answer in answers:
    for i, space in enumerate(answer.spaces): 
        spaces[space].append((answer, i)) 
intersections = [occurrences for occurrences in spaces.values()
                 if len(occurrences) > 1]

As well as your code, it assumes that each space occurs once in an answer. Unlike your code, all occurrences in different answers for a space are grouped together in the intersections list.

Answer 2

You can use sets and intersection in python3 to get intersection of two lists. An example is given below:

listed = [(1, 1), (1, 2), (1, 3), (1, 4)]
listed1=[(1, 1), (2, 1), (3, 1)]
set(listed1)&set(listed)
>>>{(1, 1)}