Znalezienie impasu

Podczas programowania aplikacji wielowątkowej należy zachować ostrożność, aby uniknąć zakleszczenia różnych wątków podczas uzyskiwania dostępu do zasobów współużytkowanych. Impas występuje podczas próby nitki uzyskać dostęp do zasobu, który jest zamknięty w innym wątku w tym samym czasie, gdy inny wątek próbuje uzyskać dostęp do zasobu zablokowane przez pierwszą. Jest to prosty przypadek, ale może stać się bardziej złożony z dłuższymi łańcuchami zasobów.

Wyzwanie

Powinieneś napisać program lub funkcję, która może wykryć możliwą sytuację zakleszczenia na liście zasobów dostępnych dla każdego wątku. To jest golf golfowy, więc wygrywa najkrótsza odpowiedź w bajtach.

Każdy wątek jest uruchamiany w tym samym czasie, ale potem mogą działać przy dowolnej kombinacji przeplatania. W przypadku 2 gwinty 4 akcji każdy może być uruchamiany jako (z których każda jest to działanie podejmowane przez nić z tym ID) 1,1,1,1,2,2,2,2, 2,2,2,2,1,1,1,1, 1,2,1,2,1,2,1,2, 1,1,2,2,2,2,1,1, albo jakąkolwiek inną możliwą kombinacją.

Wejście

Otrzymasz, poprzez STDIN, parametr funkcji lub najbliższą alternatywę, listę ciągów. Każdy ciąg będzie w formacie +a -b. Każdy z tych ciągów reprezentuje blokowanie ( +) / odblokowywanie ( -) zasobu przez wątek. Pomiędzy każdym wątkiem będzie ---separator. Gwarantujemy, że wątek nie będzie próbował zablokować zasobu, który już zablokował, i że wszystkie wątki jawnie odblokują wszystkie zasoby, które zablokowały przed wyjściem. Oto przykład do zademonstrowania:

+a    # Lock resource a
+b    # Lock resource b
-a    # Unlock resource a
-b    # Unlock resource b
---   # Thread separator
+b    # Lock resource b
-b    # Unlock resource b

Wynik

Dane wyjściowe powinny być fałszywe, jeśli dane wejściowe nie zawierają żadnej możliwości zakleszczenia, a prawdą jest, jeśli zawiera możliwe zakleszczenie. Na przykład:

• true
• false
• 1
• 0

wszystkie prawidłowe dane wyjściowe, ale wszystko, co jest jasno określone jako prawda / fałsz, zostanie zaakceptowane.

Przykłady

+a
-a
---
+a
-a

Wynik: false

+a
+b
-b
-a
---
+b
+a
-a
-b

Wynik true

Zakleszczenie przy próbie uzyskania b,aodpowiednio dla wątków1,2

+a
+b
-a
-b
---
+a
+b
-b
-a

Wynik false

+a
+b
-b
-a
---
+b
+c
-c
-b
---
+c
+a
-a
-c

Wynik: true

Zakleszczenie w wątkach 1,2,3 podczas próby uzyskania b,c,aodpowiednio.

http://pastebin.com/vMYRZxtW

Wynik false

http://pastebin.com/V5MVgNgS

Wynik true

Zakleszczenie w wątkach 1,2,3 podczas próby uzyskania b,d,aodpowiednio.

Oczywiście może to stać się znacznie bardziej złożone, z większą liczbą wątków, większą ilością zasobów dla każdego z nich i tak dalej, ale uważam, że te testy obejmują podstawy.

Premia

Ponieważ jest to bardzo smutne, gdy znajdziesz sytuacje impasu pisząc program, istnieje -8 bajt bonus do odpowiedzi transmitują :(i :)jak truthy / falsy odpowiednio.

Python 2 - 227

Zasadniczo upewnia się, że nie ma pętli „pierwszeństwa”. Na przykład w drugim teście pierwszy wątek ma a(b)pierwszeństwo, a drugi wątek ma b(a)pierwszeństwo.

Myślałem o przepisaniu tego w Pyth, ponieważ myślę, że dobrze by to działało ze wszystkimi operacjami itertools, ale konwersja wyrażenia regularnego zajmie trochę pracy, więc na razie opublikuję to i może spróbuję przekonwertować to i opublikować kolejną odpowiedź później.

from itertools import*
import re
f=lambda t:any(re.search(r"(.)((.)\3)+\1",''.join(p))for i in product(*[[m.group(1)+m.group(2)for m in re.finditer(r"(\w).*(\w).*\2.*\1",e,16)]for e in t.split('---')])for p in permutations(i))

Python - 586 539 524 501 485 bajtów - 8 = 477

Poziomy wcięć:

1: 1 space
2: 1 tab
3: 1 tab + 1 space
4: 2 tabs

-

import sys
V=set()
t=[[[]]]
for r in sys.stdin:
 r=r.strip()
 if'---'==r:t.append([[]])
 else:v=r[1:];V.add(v);l=t[-1][-1];t[-1].append(l+[v]if'+'==r[0]else filter(lambda x:x!=v,l))
s=lambda l:s(l[1:])+map(lambda x:(l[0],x),l[1:])if 1<len(l)else[]
E=reduce(set.union,map(lambda x:set(sum(map(s,x),[])),t),set())
for v in V:
 k=set();q=[v]
 while 0<len(q):
    u=q.pop(0)
    if u in k:continue
    k.add(u)
    for x,y in E:
     if u==x:
        if y in k:print':(';sys.exit()
        else:q.append(y)
print':)'