djfz-2019-s426197/TaskB05/run.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import re
import sys
# Regex pattern for reading atandt format
atandt_desc_pattern = re.compile(r"^([0-9]+)[ \t]([0-9]+)[ \t](\S+)") #^([0-9]+)\t([0-9]+)\t(\S+)$ regex for tab separated columns
atandt_accepted_state_pattern = re.compile(r"^[0-9]+$")

current_state = 0
accept_states = set()
state_move = set()

# function that filters set by starting node and returns all edges that starts in that node 
def filter_set(xs, filtered_value):
    return set(filter(lambda x: x[0] == filtered_value, xs)) 


def dfs(graph, start):
    visited = set()
    stack = []
    for el in filter_set(state_move, 0):
        stack.append(el)
    while stack:
        edge = stack.pop()
        #print('Current edge: {edge}'.format(edge = edge))
        #return immediately if cycle is detected
        if edge[0] == edge[2]:
            return [-1]
        if edge[2] in accept_states:
            visited = set()
        if edge not in visited:
            visited.add(edge)
            children = set()
            for val in filter_set(state_move, edge[2]):
                stack.append(val)
            #print('Stack: {stack}'.format(stack = stack))
            #print('Visited: {visited}'.format(visited = visited))
        else:
            return [-2]
    return visited
    
#print("Start program")
# load atand format from stdin
for line in sys.stdin:
    line = line.replace('\n', '')
    #print(line)
    move = atandt_desc_pattern.match(line)
    succes = atandt_accepted_state_pattern.match(line)
    if move:
        node = str(move.group(3))
        state_move.add((int(move.group(1)), node, int(move.group(2))))
    if succes:
        accept_states.add(int(line))
#print('Moves: {state_move}'.format(state_move = state_move))
#print('Accept states: {accept_states}'.format(accept_states = accept_states))

vis = dfs(state_move, 0)
#print(vis)
# if edge start and end node is the same
if -1 in vis:
    print("TAK")
# if edge is in visited 
elif -2 in vis:
    print("TAK")
else:
    print("NIE")