Problem:


Strange Key

Professor Tsukuba invented a mysterious jewelry box that can be opened
with a special gold key whose shape is very strange. It is composed
of gold bars joined at their ends.  Each gold bar
has the same length and is placed parallel to one of the three
orthogonal axes in a three dimensional space, 
i.e., x-axis, y-axis and z-axis.

The locking mechanism of the jewelry box
is truly mysterious, but the shape of the key is known.
To identify the key of the jewelry box, he gave a way to describe 
its shape.

The description 
indicates a list of connected paths that completely defines the shape
of the key: the gold bars of the key are arranged along the paths and 
joined at their ends.
Except for the first path, 
each path must start from an end point of a gold bar on a previously
defined path.
Each path is represented by a sequence of elements, each of which is one
of six symbols (+x, -x, +y, -y, +z and -z) or a positive integer.
Each symbol indicates the direction from an end point to the other end
point of a gold bar along the path.  Since each gold bar is
parallel to one of the three orthogonal axes, the 6 symbols are enough to
indicate the direction.  Note that a description of a path has
direction but the gold bars themselves have no direction.

An end point of a gold bar can have a label, which is a positive integer.
The labeled point may be referred to as the beginnings of other paths.
In a key description, the first occurrence of a positive integer 
defines a label of a point and each subsequent occurrence of the same
positive integer indicates the beginning of a new path at the point.

An example of a key composed of 13 gold bars is depicted 
in Figure 1.  

 

 

The following sequence of lines

      19
      1 +x 1 +y +z 3 +z 
      3 +y -z +x +y -z -x +z 2 +z  
      2 +y

is a description of the key in Figure 1.
Note that newlines have the same role as space characters in the
description, so that "19 1 +x 1 +y +z 3 +z 3 +y -z +x +y -z -x +z
2 +z 2 +y" has the same meaning.

The meaning of this description is quite simple.
The first integer "19" means the number of
the following elements in this description.
Each element is one of the 6 symbols or a positive integer.

The integer "1" at the head of the second line 
is a label attached to the starting point of the first path.
Without loss of generality, 
it can be assumed that the starting point of the first path is the
origin, i.e., (0,0,0), and that the length of each gold bar is 1.
The next element "+x" indicates that the first gold bar
is parallel to the x-axis, 
so that the other end point of the gold bar is at (1,0,0).
These two elements "1" and "+x" indicates
the first path consisting of only one gold bar.
The third element of the second line in the description is the positive
integer "1", meaning that the point with the label "1", i.e., the
origin (0,0,0) is the beginning of a new path.
The following elements "+y", "+z", "3", and "+z" indicate the second
path consisting of three gold bars. Note that this "3" is its first
occurrence so that the point with coordinates (0,1,1) is labeled "3". 
The head of the third line "3" indicates
the beginning of the third path and so on.
Consequently, there are four paths by which the shape of the key in
Figure 1 is completely defined.

Note that there are various descriptions of the same key since there
are various sets of paths that cover the shape of the key.
For example,
the following sequence of lines

      19  
      1 +x 1 +y +z 3 +y -z +x +y -z -x +z 2 +y  
      3 +z 
      2 +z

is another description of the key in Figure 1, since
the gold bars are placed in the same way.

Furthermore, the key may be turned 90-degrees around 
x-axis, y-axis or z-axis several times and may be moved parallelly.
Since any combinations of rotations and parallel moves don't change
the shape of the key, a description of a rotated and moved key also
represent the same shape of the original key. For example, a
sequence

      17 
      +y 1 +y -z +x
      1 +z +y +x +z +y -x -y 2 -y
      2 +z

is a description of a key in Figure 2 that represents the same key 
as in Figure 1.
Indeed, they are congruent under a rotation around x-axis and 
a parallel move.

Your job is to write a program to
judge whether or not the given two descriptions define the same key.

Note that paths may make a cycle.
For example, "4 +x +y -x -y" and "6 1 +x 1 +y +x -y"
are valid descriptions. However, two or more gold bars must not be placed at the same position.
For example, key descriptions
"2 +x -x" 
and
"7 1 +x 1 +y +x -y -x" are invalid.

Input

An input data is a list of pairs of key descriptions followed by
a zero that indicates the end of the input.
For p pairs of key descriptions, the input is given in the
following format.

key-description1-a

key-description1-b

key-description2-a

key-description2-b

...

key-descriptionp-a

key-descriptionp-b

0

Each key description (key-description) has the following format.

n 
e1    e2   
...  
ek  
...  
en

The positive integer n indicates the number of the following elements 
e1, ...,
en .
They are separated by one or more space characters and/or newlines.
Each element ek is 
one of the six symbols
(+x, -x, +y, -y, +z and -z)
or a positive integer.

You can assume that each label is a positive integer that is less than 51,
the number of elements in a single key description is less than 301,
and the number of characters in a line is less than 80.
You can also assume that the given key descriptions are valid and 
contain at least one gold bar.

Output

The number of output lines should be equal to that of
pairs of key descriptions given in the input.
In each line, you should output one of two words "SAME",
when the two key descriptions represent the same key, and 
"DIFFERENT", when they are different.
Note that the letters should be in upper case.

Sample Input

19
  1 +x 1 +y +z 3 +z 
  3 +y -z +x +y -z -x +z 2 +z  
  2 +y
19
  1 +x 1 +y +z 3 +y -z +x +y -z -x +z 2 +y  
  3 +z 
  2 +z
19
  1 +x 1 +y +z 3 +z 
  3 +y -z +x +y -z -x +z 2 +y  
  2 +z
18
  1 -y
  1 +y -z +x
  1 +z +y +x +z +y -x -y 2 -y
  2 +z
3 +x +y +z
3 +y +z -x
0

Output for the Sample Input

SAME
SAME
DIFFERENT



Sample input:
19
  1 +x 1 +y +z 3 +z
  3 +y -z +x +y -z -x +z 2 +z
  2 +y
19
  1 +x 1 +y +z 3 +y -z +x +y -z -x +z 2 +y
  3 +z
  2 +z
19
  1 +x 1 +y +z 3 +z
  3 +y -z +x +y -z -x +z 2 +y
  2 +z
18
  1 -y
  1 +y -z +x
  1 +z +y +x +z +y -x -y 2 -y
  2 +z
3 +x +y +z
3 +y +z -x
0


Sample output:
SAME
SAME
DIFFERENT

Submission status: Time Limit Exceeded

Solution code:
def main():
    while True:
        line = raw_input().split()
        if line[0] == "0":
            break
        N = int(line[0])
        s = line[1:]
        while len(s) < N:
            s += raw_input().split()
        original = make_graph(s)
        line = raw_input().split()
        M = int(line[0])
        t = line[1:]
        while len(t) < M:
            t += raw_input().split()
        for k in rotate_all_iter(make_graph(t)):
            if check(original, k):
                print "SAME"
                break
        else:
            print "DIFFERENT"

def check(key1, key2):
    def dfs(n1, n2):
        f1 = n1 in used1
        f2 = n2 in used2
        if f1 != f2:
            return False
        if f1 == f2 == True:
            return True
        used1[n1] = used2[n2] = True
        for k in n1.edges.keys():
            if n1.edges[k] is None:
                if n2.edges[k] is not None:
                    return False
            elif n2.edges[k] is None:
                return False
            elif not dfs(n1.edges[k], n2.edges[k]):
                return False
        return True
    for n in key2:
        used1 = {}
        used2 = {}
        if dfs(key1[0], n):
            return True
    return False

def make_graph(seq):
    D = {"+x": (1, 0, 0), "-x": (-1, 0, 0),
         "+y": (0, 1, 0), "-y": (0, -1, 0),
         "+z": (0, 0, 1), "-z": (0, 0, -1),}
    R = {"+x": "-x", "-x": "+x",
         "+y": "-y", "-y": "+y",
         "+z": "-z", "-z": "+z",}
    labels = {}
    pre = Node([0, 0, 0])
    nodes = {pre: pre}
    for s in seq:
        if s.isdigit():
            if s in labels:
                pre = labels[s]
            else:
                labels[s] = pre
        else:
            n = Node([pre[i] + D[s][i] for i in xrange(3)])
            if n in nodes:
                n = nodes[n]
            else:
                nodes[n] = n
            pre.add_edge(s, n)
            n.add_edge(R[s], pre)
            pre = n
    return Node.traverse(pre)

def rotate_all_iter(nodes):
    schedule = (Node.roll_x, Node.roll_x, Node.roll_x, Node.roll_x, 
                Node.roll_y, Node.roll_z, Node.roll_z, Node.roll_z, Node.roll_z,
                Node.roll_y, Node.roll_z, Node.roll_z, Node.roll_z, Node.roll_z,
                Node.roll_y, Node.roll_z, Node.roll_z, Node.roll_z, Node.roll_z,
                Node.roll_x, Node.roll_y, Node.roll_y, Node.roll_y, Node.roll_y,
                Node.roll_x, Node.roll_y, Node.roll_y, Node.roll_y, Node.roll_y,
                Node.roll_x, Node.roll_y, Node.roll_y, Node.roll_y, Node.roll_y,)
    for f in schedule:
        f(nodes[0])
        yield nodes

class Node(tuple):
    def __init__(self, li):
        if len(li) != 3:
            raise ValueError
        tuple.__init__(self, li)
        self.edges = dict((k, None) for k in ["+x", "-x", "+y", "-y", "+z", "-z"])
        
    def add_edge(self, edge, node):
        if not edge in self.edges:
            raise ValueError
        self.edges[edge] = node

    @classmethod
    def roll_x(cls, node, memo=[]):
        if node in memo:
            return []
        node.edges["+y"], node.edges["+z"], node.edges["-y"], node.edges["-z"] = \
            node.edges["-z"], node.edges["+y"], node.edges["+z"], node.edges["-y"]
        for n in node.edges.values():
            if n is not None:
                cls.roll_x(n, memo+[node])

    @classmethod
    def roll_y(cls, node, memo=[]):
        if node in memo:
            return []
        node.edges["+x"], node.edges["+z"], node.edges["-x"], node.edges["-z"] = \
            node.edges["-z"], node.edges["+x"], node.edges["+z"], node.edges["-x"]
        for n in node.edges.values():
            if n is not None:
                cls.roll_y(n, memo+[node])

    @classmethod
    def roll_z(cls, node, memo=[]):
        if node in memo:
            return []
        node.edges["+x"], node.edges["+y"], node.edges["-x"], node.edges["-y"] = \
            node.edges["-y"], node.edges["+x"], node.edges["+y"], node.edges["-x"]
        for n in node.edges.values():
            if n is not None:
                cls.roll_z(n, memo+[node])

    @classmethod
    def traverse(cls, node, memo=[]):
        if node in memo:
            return []
        ret = [node]
        for n in node.edges.values():
            if n is not None:
                ret += cls.traverse(n, memo+[node])
        return ret

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    while True:
        line = raw_input().split()
        while line == []:
            line = raw_input().split()
        if line[0] == "0":
            break
        N = int(line[0])
        s = line[1:]
        while len(s) < N:
            s += raw_input().split()
        original = make_graph(s)
        line = raw_input().split()
        while line == []:
            line = raw_input().split()
        M = int(line[0])
        t = line[1:]
        while len(t) < M:
            t += raw_input().split()        
        for k in rotate_all_iter(make_graph(t)):
            if check(original, k):
                print "SAME"
                break
        else:
            print "DIFFERENT"        

def check(key1, key2):
    def dfs(n1, n2):
        f1 = n1 in used1
        f2 = n2 in used2
        if f1 != f2:
            return False
        if f1 == f2 == True:
            return True
        used1[n1] = used2[n2] = True
        for k in n1.edges.keys():
            if n1.edges[k] is None:
                if n2.edges[k] is not None:
                    return False
            elif n2.edges[k] is None:
                return False
            elif not dfs(n1.edges[k], n2.edges[k]):
                return False
        return True
    for n in key2:
        used1 = {}
        used2 = {}
        if dfs(key1[0], n):
            return True
    return False

def make_graph(seq):
    D = {"+x": (1, 0, 0), "-x": (-1, 0, 0),
         "+y": (0, 1, 0), "-y": (0, -1, 0),
         "+z": (0, 0, 1), "-z": (0, 0, -1),}
    R = {"+x": "-x", "-x": "+x",
         "+y": "-y", "-y": "+y",
         "+z": "-z", "-z": "+z",}
    labels = {}
    pre = Node([0, 0, 0])
    nodes = {pre: pre}
    for s in seq:
        if s.isdigit():
            if s in labels:
                pre = labels[s]
            else:
                labels[s] = pre
        else:
            n = Node([pre[i] + D[s][i] for i in xrange(3)])
            if n in nodes:
                n = nodes[n]
            else:
                nodes[n] = n
            pre.add_edge(s, n)
            n.add_edge(R[s], pre)
            pre = n
    return nodes.values()

def rotate_all_iter(nodes):
    schedule = (Node.roll_x, Node.roll_x, Node.roll_x, Node.roll_x, 
                Node.roll_y, Node.roll_z, Node.roll_z, Node.roll_z, Node.roll_z,
                Node.roll_y, Node.roll_x, Node.roll_x, Node.roll_x, Node.roll_x,
                Node.roll_y, Node.roll_z, Node.roll_z, Node.roll_z, Node.roll_z,
                Node.roll_x, Node.roll_y, Node.roll_y, Node.roll_y, Node.roll_y,
                Node.roll_x, Node.roll_z, Node.roll_z, Node.roll_z, Node.roll_z,
                Node.roll_x, Node.roll_y, Node.roll_y, Node.roll_y, Node.roll_y,)
    for f in schedule:
        f(nodes[0], {})
        yield nodes

class Node(tuple):

    def __init__(self, li):
        if len(li) != 3:
            raise ValueError
        tuple.__init__(self, li)
        self.edges = dict((k, None) for k in ["+x", "-x", "+y", "-y", "+z", "-z"])
        
    def add_edge(self, edge, node):
        if not edge in self.edges:
            raise ValueError
        self.edges[edge] = node

    @classmethod
    def roll_x(cls, node, memo={}):
        if node in memo:
            return []
        memo[tuple(node)] = node
        node.edges["+y"], node.edges["+z"], node.edges["-y"], node.edges["-z"] = \
            node.edges["-z"], node.edges["+y"], node.edges["+z"], node.edges["-y"]
        for n in node.edges.values():
            if n is not None:
                cls.roll_x(n, memo)

    @classmethod
    def roll_y(cls, node, memo={}):
        if node in memo:
            return []
        memo[tuple(node)] = node
        node.edges["+x"], node.edges["+z"], node.edges["-x"], node.edges["-z"] = \
            node.edges["-z"], node.edges["+x"], node.edges["+z"], node.edges["-x"]
        for n in node.edges.values():
            if n is not None:
                cls.roll_y(n, memo)

    @classmethod
    def roll_z(cls, node, memo={}):
        if node in memo:
            return []
        memo[tuple(node)] = node
        node.edges["+x"], node.edges["+y"], node.edges["-x"], node.edges["-y"] = \
            node.edges["-y"], node.edges["+x"], node.edges["+y"], node.edges["-x"]
        for n in node.edges.values():
            if n is not None:
                cls.roll_z(n, memo)

    @classmethod
    def traverse(cls, node, memo={}):
        if node in memo:
            return []
        memo[tuple(node)] = node
        ret = [node]
        for n in node.edges.values():
            if n is not None:
                ret += cls.traverse(n, memo+[node])
        return ret

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 実際に判定を行う
def solve(key1, key2):
    key2 = Normalization(key2)
    for _ in range(4):
        key1 = x_rotate(key1)
        for __ in range(4):
            key1 = y_rotate(key1)
            for ___ in range(4):
                key1 = z_rotate(key1)
                ans = True
                for line in key2:
                    if line not in key1 and [line[1], line[0]] not in key1:
                        ans = False
                if ans:
                    return True
    return False

def x_rotate(key):
    tmpkey = []
    for pos in key:
        tmppos = []
        for i in pos:
            tmppos.append([i[0], i[2], -i[1]])
        tmpkey.append(tmppos)

    return Normalization(tmpkey)

def y_rotate(key):
    tmpkey = []
    for pos in key:
        tmppos = []
        for i in pos:
            tmppos.append([-i[2], i[1], i[0]])
        tmpkey.append(tmppos)

    return Normalization(tmpkey)

def z_rotate(key):
    tmpkey = []
    for pos in key:
        tmppos = []
        for i in pos:
            tmppos.append([i[1], -i[0], i[2]])
        tmpkey.append(tmppos)

    return Normalization(tmpkey)


# +xとかの判定
def check_pn_xyz(pn_xyz):
    if pn_xyz[0]== '+':
        if pn_xyz[1] == 'x':
            return [1, 0, 0]
        elif pn_xyz[1] == 'y':
            return [0, 1, 0]
        else:
            return [0, 0, 1]
    else:
        if pn_xyz[1] == 'x':
            return [-1, 0, 0]
        elif pn_xyz[1] == 'y':
            return [0, -1, 0]
        else:
            return [0, 0, -1]

# 同じ長さのリスト同士の足し算
def add(lista, listb):
    ret = []
    for i in range(len(lista)):
        ret += [lista[i] + listb[i]]
    return ret

# 鍵を正規化する (基準を[0, 0, 0]に)
def Normalization(key):
    x, y, z = float('inf'), float('inf'), float('inf')
    for pos in key:
        for i in pos:
            x, y, z = min(x, i[0]), min(y, i[1]), min(z, i[2])
    tmpkey = []

    for pos in key:
        tmppos = []
        for i in pos:
            tmppos.append([i[0] - x, i[1] - y, i[2] - z])
        tmpkey.append(tmppos)
    return tmpkey

# こっからメイン
past_key, now_key = [], []
while True:
    # 入力とか
    isneed_input = True
    if not past_key:
        past_key, now_key, i = now_key, [], 0
    else:
        past_key, now_key, i = [], [], 0
    makekey_pos, now_pos = {'0': (0, 0, 0)}, [0, 0, 0]
    N = False
    while not N:
        N = input()

    # 1行に集約されていた場合
    if not N.isdecimal():
        N, *string = N.split()
        isneed_input = False

    N = int(N)
    if not N:
        break

    # 鍵の部分の入力
    while i < N:
        if isneed_input:
            string = input().split()  # stringという名称だがlist, 命名ミス
        for num in range(len(string)):
            if string[num].isdecimal():
                if string[num] not in makekey_pos.keys():
                    makekey_pos[string[num]] = now_pos
                else:
                    now_pos = makekey_pos[string[num]]
            else:
                now_key.append([now_pos])
                now_pos = add(check_pn_xyz(string[num]), now_pos)
                now_key[-1].append(now_pos)
            i += 1

    # 一個前のやつと比較
    if past_key:
        print('SAME' if solve(now_key, past_key) else 'DIFFERENT')

Submission status: Accepted

Solution code:
def solve(sentence):
    now = [0, 0, 0]  # x,y,z
    num_p = {}
    positions = []
    for s in sentence:
        if s.isdecimal():
            if s in num_p:
                now = num_p[s]
            else:
                num_p[s] = now
        else:
            sign = 1 if s[0] == "+" else -1
            if s[1] == "x":
                positions.append([now.copy(), [now[0] + sign, now[1], now[2]]])
                now = [now[0] + sign, now[1], now[2]]
            if s[1] == "y":
                positions.append([now.copy(), [now[0], now[1] + sign, now[2]]])
                now = [now[0], now[1] + sign, now[2]]
            if s[1] == "z":
                positions.append([now.copy(), [now[0], now[1], now[2] + sign]])
                now = [now[0], now[1], now[2] + sign]
    return positions


def rotateX(positions):
    miny = float("inf")
    minz = float("inf")
    for i in range(len(positions)):
        for j in range(2):
            positions[i][j][1], positions[i][j][2] = -positions[i][j][2], positions[i][j][1]
            if positions[i][j][1] < miny:
                miny = positions[i][j][1]
            if positions[i][j][2] < minz:
                minz = positions[i][j][2]
    # シフト
    for i in range(len(positions)):
        for j in range(2):
            positions[i][j][1] -= miny
            positions[i][j][2] -= minz
        positions[i].sort()
    return positions


def rotateY(positions):
    minx = float("inf")
    minz = float("inf")
    for i in range(len(positions)):
        for j in range(2):
            positions[i][j][0], positions[i][j][2] = -positions[i][j][2], positions[i][j][0]
            if positions[i][j][0] < minx:
                minx = positions[i][j][0]
            if positions[i][j][2] < minz:
                minz = positions[i][j][2]
    # シフト
    for i in range(len(positions)):
        for j in range(2):
            positions[i][j][0] -= minx
            positions[i][j][2] -= minz
        positions[i].sort()
    return positions


def rotateZ(positions):
    minx = float("inf")
    miny = float("inf")
    for i in range(len(positions)):
        for j in range(2):
            positions[i][j][0], positions[i][j][1] = -positions[i][j][1], positions[i][j][0]
            if positions[i][j][0] < minx:
                minx = positions[i][j][0]
            if positions[i][j][1] < miny:
                miny = positions[i][j][1]
    # シフト
    for i in range(len(positions)):
        for j in range(2):
            positions[i][j][0] -= minx
            positions[i][j][1] -= miny
        positions[i].sort()
    return positions


def normal(positions):
    minx = float("inf")
    miny = float("inf")
    minz = float("inf")
    for i in range(len(positions)):
        if positions[i][0][0] < minx:
            minx = positions[i][0][0]
        if positions[i][1][0] < minx:
            minx = positions[i][1][0]

        if positions[i][0][1] < miny:
            miny = positions[i][0][1]
        if positions[i][1][1] < miny:
            miny = positions[i][1][1]

        if positions[i][0][2] < minz:
            minz = positions[i][0][2]
        if positions[i][1][2] < minz:
            minz = positions[i][1][2]

    for i in range(len(positions)):
        for j in range(2):
            positions[i][j][0] -= minx
            positions[i][j][1] -= miny
            positions[i][j][2] -= minz
        positions[i].sort()
    return positions


def check(position1, position2):
    if len(position1) != len(position2):
        return False

    position1.sort()
    position2.sort()
    for i in range(len(position1)):
        if position1[i][0] not in position2[i] or position1[i][1] not in position2[i]:
            return False
    return True


while True:
    string = input()
    if string != "":
        n, *S = string.split()
    else:
        continue
    n = int(n)
    if n == 0:
        break
    while len(S) < n:
        S += input().split()
    position1 = normal(solve(S))

    n, *S = input().split()
    n = int(n)
    while len(S) < n:
        S += input().split()
    position2 = normal(solve(S))

    # 入力ここまで

    end = False
    for z in range(4):
        for y in range(4):
            for x in range(4):
                if check(position1, position2):
                    end = True
                    break
                position2 = rotateX(position2)
            if end:
                break
            position2 = rotateY(position2)
        if end:
            break
        position2 = rotateZ(position2)

    if end:
        print("SAME")
    else:
        print("DIFFERENT")