j=input()
n=len(j)
Q=range(n*n)
L=N=[[{1<<i%n|1<<i/n}]*j[i/n][i%n]for i in Q]
for _ in Q:N=[[a|b for A,B in zip(N[i/n::n],N[i%n::n])for a in A for b in B if{1}>a&b]for i in Q];L=[L[i]+N[i]for i in Q]
1/all(L[i]*all(A&B|B&C|C&A for A in L[i]for B in L[i]for C in L[i])for i in Q if i%n<i/n)
Try it online! (simulates STDIN to run all test cases at once)
-10 bytes thanks to @ovs
Takes input as an adjacency matrix from STDIN.
Outputs by the presence of an error in accordance with a default output method. An IndexError represents non-cactus, and no error represents cactus.
Theory
A simple cycle can be thought of as two disjoint simple paths between a pair of vertices. Similarly, our conjoined cycles correspond to three distinct simple paths being present between a pair of vertices (better explanation near the bottom of the ungolfed code).
To detect these conjoined cycles, we:
- find all paths between all pairs of vertices, keeping track of the edges using Python sets.
- for each pair of vertices, if three paths are pairwise disjoint, then a conjoined cycle is present.
The first bullet has the side-benefit of making the connectedness easy to test: if a path exists between every pair of distinct vertices, then the graph is connected.
Potential improvements
If input could be taken via STDIN as n
followed by n*n
rows of boolean values, 13 bytes could be saved, but it doesn't feel right.
A lot of generator for-loop code is repeated, so surely there's a better way. I tried itertools.product
, but that ended up with a net cost of +9 bytes. I might have to go with exec/string-replacement abuse like in Baba, which could especially help with for i in Q
being used four times.
Ungolfed Code
Python 2 has two main benefits over Python 3 here:
input()
automatically parses the input
- Division is floor division by default.
j = input()
n = len(j)
Q = range(n * n)
# Replace each 0 in the adjacency matrix with []
# and each edge with a label such that the element of N representing the edge m→n has the
# same label as the element of N representing the edge n→m
L = N = [
# Each edge label is a 2-hot integer (easiest way to ensure ensure equality in both directions since the graph is undirected)
# Each path's edge sequence is stored as a set of edge labels
# N[i] is a list of paths from vertex i % n to vertex i / n
# N[i] starts out as all possible paths of length 1, i.e. edges
# L[i] starts as the same
[{1 << i%n | 1 << i/n}]
* j[i / n][i % n]
for i in Q
]
# Repeat this n**2 times:
# (In reality, only about log_2(n) times is needed, but there isn't a big performance loss)
for _ in Q:
# Update N from the list of all possible paths of length k to the list of all possible paths of length k+1
N = [
[
# The union of two paths is possible
a | b
# ... for every paths list in N
for A, B in zip(N[i / n :: n], N[i % n :: n])
# ... and for every pair of paths in each of these paths lists
for a in A
for b in B
# Limit the search to be through disjoint paths only
# equivalent to `{1}>a&b == not a&b` because a,b contain only tuples, not integers
if {1} > a & b
]
for i in Q
]
# Update L from being list of all possible paths of length at most k to the list of all possible paths of length at most k+1
# (It really seems like these two generator for-loops can be merged into one for loop, but I couldn't get it to work
# I might be able to store L and N in the same list, but that's super slow performance; hard to test)
L = [L[i] + N[i] for i in Q]
# Raises a ZeroDivisionError iff the result of the `all` call is False
1/all(
# L[i] is falsey ←→ L[i] is an empty list ←→
# no path exists between vertices i%n and i/n ←→ graph is not connected ←→ not cactus
L[i]
* all(
# `A & B | B & C | C & A` is falsey
# → A,B,C are three disjoint simple paths between vertices i%n and i/n
# → AB' and CB' are two cycles that share an edge
# → The graph is non-cactus
A & B | B & C | C & A
# using itertools.product is net +9 bytes last I checked
for A in L[i]
for B in L[i]
for C in L[i]
)
for i in Q
# L is symmetric, and we don't want to check the main diagonal
if i % n < i / n
)
Super-ungolfed code
def dot(r1, r2):
return [
path1 | path2
for paths1, paths2 in zip(r1, r2)
for path1 in paths1
for path2 in paths2
# simple paths, so exclude those that share edges
if len(path1 & path2) == 0
]
def mul(paths1, paths2):
return [[dot(row, col) for row in zip(*paths2)] for col in paths1]
def f(adj):
n = len(adj)
paths_length_1 = [
[
[{(min(x, y), max(x, y))}] if entry == 1 else []
for x, entry in enumerate(row)
]
for y, row in enumerate(adj)
]
all_paths = paths_length_1
paths_length_n = paths_length_1
for _ in range(n):
paths_length_n = mul(paths_length_1, paths_length_n)
for y in range(n):
for x in range(n):
all_paths[y][x].extend(paths_length_n[y][x])
for x, row in enumerate(all_paths):
for y, paths in enumerate(row):
# The graph is non-cactus if it is not conneted
if x != y and len(paths) == 0:
return False
# The graph is non-cactus if there exist three piecewise disjoint simple paths A,B,C
# between two nodes because A+B' forms one cycle and C+B' forms the other cycle
for A, B, C in itertools.combinations(paths, 3):
if len(A & B) == 0 and len(B & C) == 0 and len(A & C) == 0:
return False
return True
e
contain exactly one element AND doesv
contain exactly 2 AND isv
equal to the first element ofe
? 2) OR Isv
equal to the union set of the first elements of each element ine
? The second test case passes the first check (v=[1,2]=e[0]=[1,2]
) and the other test cases that should be true match the second, e.g. case#4:v=[1,2,3,4,5,6]=[e[0][0],e[1][0],e[2][0],e[4][0]]=[1,2,3,4,5,6]
. \$\endgroup\$console.log(f([1,2,3,4,5,6,7,8,9,10,11,12,13])([[1,2],[1,3],[3,4],[2,4],[3,5],[5,6],[6,7],[7,8],[8,5],[7,9],[9,10],[10,11],[11,7],[8,12],[8,13]]))
\$\endgroup\$true
orfalse
? \$\endgroup\$