# Bug Byte puzzle from Jane Street

This is a puzzle from Jane Street.

Given this graph:

Fill in the edge weights in the graph with the numbers 1 through 24, using each number exactly once. Labeled nodes provide some additional constraints:

This solution below correctly solves the puzzle, but it takes around 5 minutes to complete on my laptop. I'm a bit rusty on algorithms, so I'm wondering if there is a more efficient way to solve it. Any feedback is appreciated.

After building the graph, this is the high level logic of the function solve:

1. Assign a (candidate) weight to an edge
2. Check if the state of the graph is correct (validation)
3. If the validation fails, backtrack and try with another weight
4. If the validation is correct proceed to the next edge recursively
5. When there are no more edges the solution is found

Note: running the code won't reveal the secret message, uncomment the last line if you want to see it.

Code:

from collections import deque
import networkx as nx
import string
import time

class Node:
def __init__(self, id, sum_edges, paths=[]):
self.id = id
self.sum_edges = sum_edges
self.paths = paths

def __eq__(self, other):
if isinstance(other, Node):
return self.id == other.id
return False

def __hash__(self):
return self.id

def __repr__(self):
return f"Node(id={self.id},sum_edges={self.sum_edges})"

class Graph:
def __init__(self, nodes):
self.g = {}
self.nodes = nodes
self.edges = {}
# Available weights
self.aw = {}
# Number of edges
self.E = 0
self.candidates = {}

"""
Adds an edge to the graph with an optional weight
"""
self.edges[(s_id, t_id)] = w
self.edges[(t_id, s_id)] = w
if s_id in self.g:
else:
self.g[s_id] = {t_id}

if t_id in self.g:
else:
self.g[t_id] = {s_id}

self.E = len(self.edges) // 2
self.update_aw()

def update_aw(self):
"""
Updates available weights (aw). Available weights are weights
not assigned to any edge.
"""
self.aw = {i + 1 for i in range(self.E)}
weights = {w for w in self.edges.values() if w}
self.aw = self.aw.difference(weights)

def update_candidates(self):
"""
Updates candidate weights for each edge. Candidate weights are available weights
that can be assigned to an edge according to the state of the graph.
"""
self.candidates = {}
for edge, w in self.edges.items():
if not w:
sid, tid = edge
ub = self.upper_bound(sid, tid)
candidates = [w for w in self.aw if w <= ub]
self.candidates[(sid, tid)] = candidates

def set_w(self, sid, tid, w):
"""
Set weight w to the edge identified by source node id (sid) and
target node id (tid). Then update available weights and candidates.
"""
self.edges[(sid, tid)] = w
self.edges[(tid, sid)] = w
self.update_aw()
self.update_candidates()

def unset_w(self, sid, tid):
"""
Unset weight w of the edge identified by source id (sid) and target id (tid).
Then update available weights and candidates.
"""
self.edges[(sid, tid)] = None
self.edges[(tid, sid)] = None
self.update_aw()
self.update_candidates()

def upper_bound(self, s_id, t_id):
"""
Determines the upper bound weight for the given edge according to the state of the graph.
"""
s = self.nodes[s_id]
t = self.nodes[t_id]

def upper_bound(s, t):
if not s.sum_edges:
return self.E
tot = 0
aw = self.aw.copy()
for neighbor_id in self.g[s.id]:
if neighbor_id != t.id:
if self.edges[(neighbor_id, s.id)]:
tot += self.edges[(neighbor_id, s.id)]
else:
tot += min(aw)
aw.remove(min(aw))
return min(self.E, s.sum_edges - tot)

return min(upper_bound(s, t), upper_bound(t, s))

def print_edges(self):
seen = set()
res = {}
for edge, weight in self.edges.items():
if edge in seen:
continue
a, b = edge
res[edge] = weight
print(res)

def validate(self):
"""
Validates the state of the graph:
- The sum of all edges directly connected to a node
- The paths (see function validate_paths)
"""
for node in self.nodes:
if node.sum_edges:
tot = 0
# if all direct edges set then has to equal to sum_edges
if all(
self.edges[(node.id, neighbor_id)]
for neighbor_id in self.g[node.id]
):
if (
sum(
self.edges[(node.id, neighbor_id)]
for neighbor_id in self.g[node.id]
)
!= node.sum_edges
):
return False
else:
for neighbor_id in self.g[node.id]:
if self.edges[(node.id, neighbor_id)]:
tot += self.edges[(node.id, neighbor_id)]
if tot > node.sum_edges:
return False
if not self.validate_paths():
return False
return True

def validate_paths(self):
for node in self.nodes:
if node.paths:
for N in node.paths:
if not self.validate_path(node, N):
return False
return True

def validate_path(self, root, N):
"""
Validates requirement:
- There exists a non-self-intersecting path starting from this node where N is the sum of the weights of the edges on that path
"""
seen = set()
q = deque([(root.id, N)])
while q:
node_id, limit = q.popleft()
if limit == 0:
return True
if limit < 0:
continue
for neighbor_id in self.g[node_id]:
if neighbor_id not in seen:
w = self.edges[(node_id, neighbor_id)]
if not w:
return True
q.append((neighbor_id, limit - w))
return False

def shortest_path(self, sid, tid):
"""
Finds the shortest path between the given nodes
"""
G = nx.Graph()
for edge, w in self.edges.items():
aid, bid = edge
return nx.shortest_path(G, source=sid, target=tid, weight="weight")

def decode_path(self, p):
"""
Converts a path to the secret message
"""
res_w = [self.edges[(p[i - 1], p[i])] for i in range(1, len(p))]
alp = [0] + list(string.ascii_uppercase)
message = [alp[w] for w in res_w]
return "".join(message)

def solve(self):
"""
Solves the graph by finding the configuration of weights that satisfies the requirements
"""
self.update_candidates()
progress = len(self.edges) // 2

def solve(edges):
nonlocal progress
if not edges:
return True
sid, tid = next(iter(edges))
remaining_edges = {
key: value
for key, value in edges.items()
if key != (sid, tid) and key != (tid, sid)
}
if len(remaining_edges) // 2 < progress:
progress = len(remaining_edges) // 2
print(f"Remaining edges to solve: {progress}...")
if edges[(sid, tid)]:
return solve(remaining_edges)
# Try every candidates for the given edge if there are any
if self.candidates[(sid, tid)]:
for w_candidate in self.candidates[(sid, tid)]:
self.set_w(sid, tid, w_candidate)
if self.validate() and solve(remaining_edges):
return True
# unset failed candidate
self.unset_w(sid, tid)
return False
return solve(self.edges)

def main():
nodes = [
Node(0, 17),
Node(1, 3),
Node(2, None, [19, 23]),
Node(3, None),
Node(4, None, [31]),
Node(5, 54),
Node(6, None, [6, 9, 16]),
Node(7, 49),
Node(8, None, [8]),
Node(9, 60),
Node(10, 79),
Node(11, None),
Node(12, 29),
Node(13, 75),
Node(14, None),
Node(15, 25),
Node(16, None),
Node(17, 39),
]
g = Graph(nodes)

print("Total number of edges: ", g.E)

start_time = time.time()
g.solve()
end_time = time.time()

running_time = end_time - start_time
print("Running time:", running_time, "seconds")
p = g.shortest_path(3, 16)
secret_message = g.decode_path(p)
# Uncomment to see the solution
#print(f"The secret message is: {secret_message}")

if __name__ == "__main__":
main()

• I don't understand the N constraint. There exists a non-self-intersecting path starting from this node... to where? Commented May 12 at 14:51
• @Reinderien to any node except the node itself. Yeah, that part is a bit confusing
– Marc
Commented May 12 at 15:01

This submission would benefit from the addition of profiling measurements.

# mutable default

This signature has well-defined semantics. But please don't do it. Human maintenance engineers in future will have difficulty reasoning about it.

class Node:
def __init__(self, ..., paths=[]):


Here, let me demonstrate:

>>> n1 = Node(1, 1)
>>> n2 = Node(2, 2)
>>> n1.paths.append('one')
>>>
>>> n2.paths
['one']


I confess that, in the course of trying to "begin again" for a clean demo, I accidentally assigned n2.paths = []. Uggh! Yeah, rookie mistake, do you see it? I meant to do n2.paths.clear(), which means something entirely different.

Standard idiom for this would be

    def __init__(self, ..., paths=None):
...
self.paths = paths or []


# equality

I don't understand what's going on with __eq__. It seems to suggest that e.g. Node(3, 20) == Node(3, 30). That's certainly feasible, there are business domain use cases where that would be desirable. But in this particular puzzle I'm just not seeing how that makes sense.

Also, it's not clear that you even use this and need to define it at all. Similarly for __hash__. Not sure why we would even want a pair of Node 3's to exist.

# signature

    def __init__(self, id, sum_edges, paths=[]):


When I read the constructor I thought I understood what was going on. I didn't.

Here is how I read it:

    def __init__(
self,
id: int,
sum_edges: int,
paths: list[Node] = [],
):


But it turns out later that sum_edges can be None instead of 0. Please don't surprise the Gentle Reader with such non-obvious assignments. Either spell it out in a """docstring""", or offer a hint via type annotation.

Also, consider giving sum_edges a default value, either 0 or perhaps None.

# abbreviations

        # Available weights
self.aw = {}
# Number of edges
self.E = 0


Thank you, thank you for that first comment, very helpful. I would never have guessed that on my own, but now I know how to mentally pronounce it, good.

That second item, for edges, is not so great. Better to elide the comment and simply assign self.num_edges = 0. As it stands, it's clear we have discarded the pep-8 convention, since E obviously isn't a class. But that leaves me to fall back on math naming conventions, yet $$\E\$$ obviously isn't a connectivity matrix or vector quantity. Please choose a more appropriate name for this concept. Or remove it entirely, as it doesn't seem to offer more than len(self.edges). You could offer that expression as a computed @property, if desired.

(Oh, I see later there's a surprising representation choice, where an undirected graph of N edges induces a corresponding digraph of 2 × N edges, ok.)

# doubled edge

    def add_edge(self, s_id, t_id, w=None):
"""
Adds an edge to the graph with an optional weight
"""
self.edges[(s_id, t_id)] = w
self.edges[(t_id, s_id)] = w


Thank you for the docstring, making it clear the last param is a weight. The problem statement doesn't speak of $$\s\$$ or $$\t\$$ nodes, so I started pronouncing them "src" and "to" (not "dst" and "from"?) and then noticed they model an undirected edge and decided they're just arbitrary letters. [edit: OIC, source and target.]

Doubling the edge seems inconvenient. For one thing, update_candidates() does everything twice twice. We could maybe exploit sort order to quickly find the out edges from $$\s\$$ or from $$\t\$$, but I don't notice any sorting happening.

Consider adopting the fairly conventional approach of assigning

        pair = tuple(sorted([s_id, t_id]))
self.edges[pair] = w


so that each undirected edge has a canonical name, in numeric order.

# defaultdict

This is inconvenient and needlessly distracting:

        self.g = {}
...
if s_id in self.g:
else:
self.g[s_id] = {t_id}


Prefer to let defaultdict worry about details irrelevant to your core algorithm.

        self.g = defaultdict(set)
...


# algorithm

update_aw() looks expensive, with work proportional to graph size. Consider making "self.aw is always accurate" a class invariant, and preferring incremental delta updates rather than rebuilding it from scratch each time.

Doing the update_candidates() work incrementally would be similarly attractive.

A tiny nit:

        self.aw = {i + 1 for i in range(self.E)}


Hoisting the + 1 out of the loop lets us accomplish that with fewer interpreted bytecodes:

        self.aw = {i for i in range(1, self.E + 1)}


or equivalently ... = list(range(1, self.E + 1)).

# correctness

        def upper_bound(s, t):
if not s.sum_edges:
return self.E


This seems to assign unit weight in the "unknown" None case. It's not clear to me how that would be correct. I would have expected an expression closer to self.E * max_edge_weight.

Also, I am troubled by the lack of symmetry with target node t. The relationship between s.sum_edges and t.sum_edges is not yet obvious to me. It warrants an assert, or at least a docstring remark or comment.

# graph representation

Modeling an undirected graph is not core to this code's contribution. Consider outsourcing that to networkX or similar graph library. They have already worked out the details for things like undirected graph vs digraph, with excellent documentation, which saves you some effort.

OIC, you do wind up using that library, to exploit its nx.shortest_path() routine, very good. But each call is a bit expensive, as you reproduce a new graph from scratch. Consider relying on an nx.Graph as your core representation.

# None vs empty container

    def validate_paths(self):
...
if node.paths:
for N in node.paths:


Consider simplifying it down to

            for n in node.paths or []:


Consider banishing None from your datastructure entirely, replacing it with an empty container. Often the None special case is just a distraction. Iterating over zero items is a natural way to say "do nothing".

And kudos for using a deque during validation, that looks great.

# nested function

I just don't even understand what's going on in here.

    def solve(self):
...
progress = len(self.edges) // 2

def solve(edges):
nonlocal progress


Is the nesting buying you anything? Certainly it has made it difficult to unit test this with the nested function inaccessible. Yes, it's a recursive approach, but that's no excuse.

This problem can be solved optimally in pseudo-polynomial time. This can be done by using k-sum. For every edge that has two connected M nodes we can compute k-sum on both vertices then take the intersection of the possible values that sum up to both nodes to drastically reduce the search space. This reduces the complexity of the problem down to $$\O(E * K^S)\$$ where $$\K\$$ is the possible values in this case $$\K\$$ is 20, and $$\S\$$ is the k-sum complexity of the vertex with the maximum amount of edges needed to be filled. In this case $$\S\$$ is 3, due to the fact that the highest number of unfilled edges in the graph is 4 meaning 4 sum is the highest complexity any edge will require which has an $$\O(N^3)\$$ complexity. That makes this solution $$\O(E * K^3)\$$.

I wrote a similar version to yours with this implementation and mine runs in about .3 seconds. Here is the code, it's far from perfect and could use some optimizations.

Note: This version handles edges in sorted order based off of the amount of valid options in the k-sum result, this is a slight heuristic approach as filling in edges with the least amount of possibilities first will reduce the complexity of the higher order edges at every step,this results in the algorithm pruning the search space drastically by reducing the k-sum complexity of the higher bounded edges in each recursive call.

import heapq
import time
from collections import defaultdict
from typing import List

def twoSum(nums: List[int], target: int) -> List[List[int]]:
res = []
s = set()

for i in range(len(nums)):
if len(res) == 0 or res[-1][1] != nums[i]:
if target - nums[i] in s:
res.append([target - nums[i], nums[i]])

return res

def threeSum(nums, target):
n = len(nums)
triplets = []
nums.sort()  # Sort the array in ascending order

for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue

left = i + 1
right = n - 1

while left < right:
current_sum = nums[i] + nums[left] + nums[right]

if current_sum == target:
triplets.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1

while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif current_sum < target:
left += 1
else:
right -= 1

return triplets

def fourSum(nums: List[int], target: int) -> List[List[int]]:
def kSumm(nums: List[int], target: int, k: int) -> List[List[int]]:
res = []

# If we have run out of numbers to add, return res.
if not nums:
return res

# There are k remaining values to add to the sum. The
# average of these values is at least target // k.
average_value = target // k

# We cannot obtain a sum of target if the smallest value
# in nums is greater than target // k or if the largest
# value in nums is smaller than target // k.
if average_value < nums[0] or nums[-1] < average_value:
return res

if k == 2:
return twoSum(nums, target)

for i in range(len(nums)):
if i == 0 or nums[i - 1] != nums[i]:
for subset in kSumm(nums[i + 1:], target - nums[i], k - 1):
res.append([nums[i]] + subset)

return res

nums.sort()
return kSumm(nums, target, 4)

def k_sum(nums, target, k):
if k == 1:
for num in nums:
if num == target:
return [[num]]
if k == 2:
return twoSum(nums, target)
if k == 3:
return threeSum(nums, target)
if k == 4:
return fourSum(nums, target)
return []

class Vertex():
def __init__(self, i, sum_edges=None, intersections=None):
self.i = i
self.se = sum_edges
self.intersections = intersections
self.edges = []
self.total_sum = 0

class Graph():
def __init__(self, nodes):
self.g = defaultdict(lambda: [])
self.filled_edges = defaultdict(lambda: 0)
self.nodes = nodes
self.valid_weights = set([i for i in range(1, 25)])
self.onstack = set()
for i in [7, 12, 20, 24]:
self.edges = {}
self.attempts = 0

self.edges[(v, w)] = c
self.edges[(w, v)] = c
self.g[v].append(w)
self.g[w].append(v)
self.nodes[v].edges.append(w)
self.nodes[w].edges.append(v)
if c is not None:
self.nodes[v].total_sum += c
self.nodes[w].total_sum += c
self.filled_edges[v] = self.filled_edges[v] + 1
self.filled_edges[w] = self.filled_edges[w] + 1

def has_non_intersecting_path(self, v, visited, cost, target):
if v in visited:
return cost == target
for w in self.nodes[v].edges:
c = self.edges[(v, w)]
if cost + c == target:
return True
elif cost + c < target:
if self.has_non_intersecting_path(w, visited, cost + c, target):
return True
return False

def valid(self):
visited = set()
used = set()
sums = defaultdict(lambda: 0)
for v, w in self.edges:
if (v, w) in visited:
continue
if self.edges[(v, w)] is None or self.edges[(v, w)] in used or self.edges[(v, w)] not in self.valid_weights:
return False
sums[v] += self.edges[(v, w)]
sums[w] += self.edges[(w, v)]
for v in self.nodes:
if self.nodes[v].se is None:
continue
if sums[v] != self.nodes[v].se:
return False
for v in self.nodes:
if self.nodes[v].intersections is None:
continue
for target in self.nodes[v].intersections:
if not self.has_non_intersecting_path(v, set(), 0, target):
return False
return True

def potential_vals(self, v, valids):
vals = set()

if self.nodes[v].se is not None:
total_v = len(self.nodes[v].edges)
found_edges = 0
v_sum = 0
for z in self.nodes[v].edges:
if self.edges[(v, z)] is not None:
found_edges += 1
v_sum += self.edges[(v, z)]
v_opts = k_sum(valids, self.nodes[v].se - v_sum, total_v - found_edges)
for opts in v_opts:
for i in opts:
return vals

def optimal_decisions(self, v, w, valids):

if self.nodes[v].se is not None and self.nodes[w].se is not None:
ws = self.potential_vals(w, valids)
vs = self.potential_vals(v, valids)
return vs & ws

elif self.nodes[v].se is not None:
return self.potential_vals(v, valids)
elif self.nodes[w].se is not None:
return self.potential_vals(w, valids)
return valids

def update_candidates(self, current_edges):
candidates = {}
valids = [i for i in range(1, 25) if i not in self.onstack]
for v, w in current_edges:
opts = self.optimal_decisions(v, w, valids)

if opts:
if (w, v) in candidates and candidates[(w, v)] == opts:
continue
candidates[(v, w)] = opts

ordered_dict = dict(sorted(candidates.items(), key=lambda x: len(x[1]), reverse=False))
return ordered_dict

def get_edges_to_solve(self, current_edges):

remaining_edges = {}
for v, w in current_edges:
if current_edges[(v, w)] is not None:
assert current_edges[(v, w)] == current_edges[(w, v)]
continue

assert current_edges[(v, w)] is None and current_edges[(w, v)] is None
remaining_edges[(v, w)] = None

return remaining_edges

def solve(self):
progress = len(self.edges) // 2

def solve_remainder(current_edges):
nonlocal progress

edges_to_solve = self.get_edges_to_solve(current_edges)
candidates = self.update_candidates(edges_to_solve)

if len(candidates) < len(edges_to_solve) // 2:
return False
if len(edges_to_solve) // 2 < progress:
progress = len(edges_to_solve) // 2
print(f"Remaining edges to solve: {progress}...")
for v, w in candidates:
self.attempts += len(candidates[(v, w)])
if current_edges[(v, w)] is not None:
assert current_edges[(v, w)] == current_edges[(w, v)]
continue

for candidate in candidates[(v, w)]:
current_edges[(v, w)] = candidate
current_edges[(w, v)] = candidate

self.nodes[w].total_sum += candidate
self.nodes[v].total_sum += candidate
self.filled_edges[v] = self.filled_edges[v] + 1
self.filled_edges[w] = self.filled_edges[w] + 1
if self.valid():
return True
if solve_remainder(current_edges):
return True
else:
current_edges[(v, w)] = None
current_edges[(w, v)] = None
self.onstack.remove(candidate)
self.nodes[w].total_sum -= candidate
self.nodes[v].total_sum -= candidate
self.filled_edges[v] = self.filled_edges[v] - 1
self.filled_edges[w] = self.filled_edges[w] - 1
if (w, v) not in candidates:
return False
if candidates[(w, v)] == candidates[(v, w)]:
return False

return solve_remainder(self.edges)

Nodes = {
0: Vertex(0, sum_edges=17),
1: Vertex(1, sum_edges=3),
2: Vertex(2, None, intersections=[19, 23]),
3: Vertex(3, None),
4: Vertex(4, None, intersections=[31]),
5: Vertex(5, sum_edges=54),
6: Vertex(6, None, intersections=[6, 9, 16]),
7: Vertex(7, sum_edges=49),
8: Vertex(8, None, intersections=[8]),
9: Vertex(9, sum_edges=60),
10: Vertex(10, sum_edges=79),
11: Vertex(11, None),
12: Vertex(12, 29),
13: Vertex(13, 75),
14: Vertex(14, None),
15: Vertex(15, 25),
16: Vertex(16, None),
17: Vertex(17, 39),
}
g = Graph(Nodes)

def dijkstra(graph, edges, start, end):
# Initialize distances, previous vertices, visited set, and path edges
distances = {vertex: float('inf') for vertex in graph}
distances[start] = 0
previous = {vertex: None for vertex in graph}
visited = set()
path_edges = []

# Initialize priority queue
pq = [(0, start)]

while pq:
# Get the vertex with the minimum distance
current_distance, current_vertex = heapq.heappop(pq)

# If the vertex has already been visited, skip it
if current_vertex in visited:
continue

# If the current vertex is the end vertex, break the loop
if current_vertex == end:
break

# Mark the vertex as visited

# Explore the neighbors of the current vertex
for neighbor in graph[current_vertex]:
# Get the edge weight between the current vertex and the neighbor
edge_weight = edges[(current_vertex, neighbor)]

# Calculate the distance to the neighbor through the current vertex
distance = current_distance + edge_weight

# If the calculated distance is smaller than the current distance, update it
if distance < distances[neighbor]:
distances[neighbor] = distance
previous[neighbor] = current_vertex
heapq.heappush(pq, (distance, neighbor))

# Build the shortest path and collect the edges
path = []
current_vertex = end
while current_vertex is not None:
path.append(current_vertex)
if previous[current_vertex] is not None:
path_edges.append((previous[current_vertex], current_vertex))
current_vertex = previous[current_vertex]
path.reverse()
path_edges.reverse()

# Return the shortest path, its length, and the edges along the path
return path, distances[end], path_edges

start = time.perf_counter()
g.solve()
end = time.perf_counter() - start
print(f"graph solved in {end}")
path, length, path_edges = dijkstra(graph=g.g, edges=g.edges, start=3, end=16)

def decode_to_letter(number):
if 1 <= number <= 24:
ascii_code = number + 64
letter = chr(ascii_code)
return letter
else:
return None

s = ""
for v, w in path_edges:
s += decode_to_letter(g.edges[(v, w)])

print(s)

• spent some days, worked on own solution in C#, it runs in ~0.6-0.7s, yours is faster, I know if I chose a different starting node (I went with nodes first approach), then time is (at least) like ~0.04s but I have to figure out how to optimize pre-sorting and not cherry pick, obviously. Also it is possible to optimize your approach from 0.3s to ~0.08s by cutting off an edge. Look at constraint node values and sum nodes values, try to find how they are similar yet exclusive. Let me know if you want details. Commented Jun 20 at 21:33

I solved this problem here, using python-constraint.

I modelled it as a set of linear equations with inequality constraints.

The code is ChatGPT generated and I adapted the constraints.

from constraint import Problem, AllDifferentConstraint

def solve_variables():
# Create a new problem object
problem = Problem()

# Possible values for variables
possible_values = [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24]

# Add variables with their possible values
for i in range(1, 21):

# All variables must have different values

# Define the equations
problem.addConstraint(lambda x2, x3, x7: x2 + x3 + x7 == 25, ("x_2", "x_3", "x_7")) # 1
problem.addConstraint(lambda x1, x4: x1 + x4 == 32, ("x_1", "x_4")) # 2
problem.addConstraint(lambda x3, x4, x5: x3 + x4 + x5 == 29, ("x_3", "x_4", "x_5")) # 3
problem.addConstraint(lambda x7, x8, x9: x7 + x8 + x9 == 55, ("x_7", "x_8", "x_9")) # 4
problem.addConstraint(lambda x9, x12, x16, x11: x9 + x12 + x16 + x11 == 36, ("x_9", "x_12", "x_16", "x_11")) # 5
problem.addConstraint(lambda x5, x6, x10: x5 + x6 + x10 == 48, ("x_5", "x_6", "x_10")) # 6
problem.addConstraint(lambda x12, x13, x14: x12 + x13 + x14 == 29, ("x_12", "x_13", "x_14")) # 7
problem.addConstraint(lambda x10, x11, x17, x18: x10 + x11 + x17 + x18 == 54, ("x_10", "x_11", "x_17", "x_18")) # 8
problem.addConstraint(lambda x19, x20: x19 + x20 == 17, ("x_19", "x_20")) # 9
problem.addConstraint(lambda x20, x15: x20 + x15 == 3, ("x_20", "x_15")) # 10
problem.addConstraint(lambda x16: x16 == 6, ["x_16"])
problem.addConstraint(lambda x13: x13 <= 8, ["x_13"])
# problem.addConstraint(lambda x13, x14, x12: (x13 + x14 <= 8) or (x13 + x12 <= 8),
#                       ["x_13", "x_14", "x_12"])

problem.addConstraint(lambda x16, x12, x11, x9: (x16 + x12 <= 16) or (x16 + x11 <= 16) or (x16 + x9 <= 16),
["x_16", "x_12", "x_11", "x_9"])

problem.addConstraint(lambda x17, x18, x11, x10: (x17 + x18 == 31) or (x17 + x11 == 31) or (x17 + x10 == 31),
["x_17", "x_18", "x_11", "x_10"])

# Get the solutions
solutions = problem.getSolutions()

# Printing all possible solutions
for solution in solutions:
print(solution)

print("Number of solutions found:", len(solutions))

# Execute the function
solve_variables()



After filling in the weights, the shortest path could be found using A* or Dijkstra algorithm.

def heuristic(a, b):
# Placeholder for actual heuristic
return 0

path = nx.astar_path(G, 'L', 'A', heuristic=heuristic)
print("Path:", path)

total_weight = 0
print("Edge Weights on Path:")
for i in range(len(path) - 1):
weight = G[path[i]][path[i+1]]['weight']
total_weight += weight
print(f"{path[i]} -> {path[i+1]} : Weight = {weight}")
print("Total weight of path:", total_weight)



Finally, transform each number shortest path weight to numbers like this to find secret path.

def number_to_letter_rotating(numbers):
# Initialize an empty string to store the decoded message
message = ''

# Iterate through the list of numbers
for number in numbers:
if number > 0:  # Check if the number is positive
# Convert number to a value between 1 and 26 using modulo
letter_number = (number - 1) % 26 + 1
# Convert adjusted number to corresponding letter and add to the message
message += chr(letter_number + 64)
else:
message += ' '  # Add a space for non-positive numbers

return message

# Example usage:
secret_numbers = [4,5,11,14,9,12]
secret_message = number_to_letter_rotating(secret_numbers)
print(secret_message)


As for the complexity of the solution, one needs to dig into the implementation of python-constraint CSP solver implementation, but I guess that the way the constraints are being fed to the algorithms could play a role in the runtime.

• Can you do this using scipy instead?
– Simd
Commented May 21 at 22:26
• @Simd: Would be interesting to map the problem into linear programming optimization problem and this is how I thought about it in the first place. If there's a mapping that does exist than it would be possible to use scipy linprog although I doubt, but I don't have a proof. Commented May 22 at 10:33
• @Simd Also LP is for optimization problem in real number space, and the problem is for bounded integer space (enumerator), which sounds simpler, but a mapping also to LP seems to make it even harder to use scipy. Commented May 22 at 19:18
• scipy has MIP support now. docs.scipy.org/doc/scipy/reference/generated/…
– Simd
Commented May 22 at 19:35