Ahhh, I see! I was conflating grouping with order of execution, and desperately trying to find a grouping that would get those examples to make sense to me. It's totally clear now, thank you both!
HappyCake
@HappyCake
Posts made by HappyCake

RE: Examples correct?

Examples correct?
I believe that examples 2 and 3 had typos, and I can't figure out the second column of example 3.
tl;dr  I think the second columns were included by mistake.
Example 2
Input: "F?1:T?4:5" Output: "4" Explanation: The conditional expressions group righttoleft. Using parenthesis, it is read/evaluated as: "(F ? 1 : (T ? 4 : 5))" "(F ? 1 : (T ? 4 : 5))" > "(F ? 1 : 4)" or > "(T ? 4 : 5)" > "4" > "4"
I think the top line of column 2 should read:
"((F ? 1 : T) ? 4 : 5)"
in order to get the next line in that column.
Example 3
Input: "T?T?F:5:3" Output: "F" Explanation: The conditional expressions group righttoleft. Using parenthesis, it is read/evaluated as: "(T ? (T ? F : 5) : 3)" "(T ? (T ? F : 5) : 3)" > "(T ? F : 3)" or > "(T ? F : 5)" > "F" > "F"
Again, I think that the top line of column 2 is a typo (it repeats the top line of column 1). Regardless, however, I don't see how it's possible to get the next line of column 2 at all. Does anyone see it?
In any case, I thought that "conditional expressions group righttoleft" was to avoid ambiguity. If, on the other hand, that rule still allows for some ambiguity (I don't think it does), can one prove that the answer is always the same?
...or maybe I'm missing something obvious!

RE: Cant pass test case "a","01"
Strictly speaking, the problem implies no leading zeros are allowed, because in the first given example, it lists all possible abbreviations, and none have leading zeros. Would be nice if that was stated clearly, though.
Anyway, to pass that case, just detect leading 0's and return False if you see any.

This is a baby version of the unsolved 3n+1 problem (aka the Collatz conjecture)
Just a little observation, this appears to be a baby version of the unsolved 3n+1 problem, whose conjectured answer is known as the Collatz Conjecture.
The only difference is that for odd numbers
n
you replace with3n+1
. It's conjectured that you can always get to 1 by following the rules, but to this day it remains unproved.Fortunately this one is much easier. :)

Python OO solution (42 ms) with some optimizations
A reasonably fast solution, which aims to make the logic fairly readable from the code using object oriented programming. The steps are simple:
 Build the digraph using the data given.
 Nodes have variable names as values, and edges have numerical values.
 For example, if we have
[x](a)>[y]
, this representsx/y = a
.  Automatically add "inverse" edges to represent
y/x = 1/a
.
 For each (start, end) pair, perform a DFS beginning at start.
 If a path is found, multiply every edge value along that path to get the answer.
 To speed up future searches, add a connection representing that calculation to the digraph (as well as the inverse connection).
For quick lookups, all lists of nodes are actually dictionaries, with variable names as keys and
Node
classes as values. Redundant, but quick!class Node(object): def __init__(self, name): self.name = name; self.outs = {}; def addConnection(self, node, value): """ Create an edge with value "value", and an edge in the reverse direction with value 1/"value". """ if node.name not in self.outs: self.outs[node.name] = (node, value) inverse = 1.0/value if inverse not in node.outs: node.outs[self.name] = (self, inverse) def dfs(self, end, visited = []): """ Attempts to find a path from this node to "end" nodes. """ newvisited = visited + [self.name] if self.name == end: return newvisited for outnode in self.outs: if self.outs[outnode] [0].name not in visited: # No loops in our path! result = self.outs[outnode] [0].dfs(end, newvisited) if result[1] == end: # Success was returned, continue to return it return result # Otherwise continue through the outnodes. return newvisited class Digraph(object): def __init__(self, equations, values): """ Build a digraph with appropriate named nodes and weighted edges. """ self.nodes = {} # Build the connections. for i in range(len(equations)): # Add 0, 1, or 2 nodes as needed eq = equations[i] if eq[0] not in self.nodes: self.nodes[eq[0]] = Node(eq[0]) if eq[1] not in self.nodes: self.nodes[eq[1]] = Node(eq[1]) # Add edges. (Automatically adds the inverse edge if it doesn't already exist.) self.nodes[eq[0]].addConnection(self.nodes[eq[1]], values[i]) def multiplyPath(self, path): """ Takes a connected path of nodes and returns the product of their edges. """ prod = 1 for i in range(len(path)1): prod *= self.nodes[path[i]].outs[ path[i+1] ] [1] return prod class Solution(object): def calcEquation(self, equations, values, queries): """ :type equations: List[List[str]] :type values: List[float] :type queries: List[List[str]] :rtype: List[float] """ # 1. Build the digraph dg = Digraph(equations, values) print "Built digraph:"; print dg.display() # 2. Do a DFS for each query. # 2.5 to optimize, add each answer as an edge after it's computed. answer = [] for (start, end) in queries: if start not in dg.nodes or end not in dg.nodes: answer.append(1) continue path = dg.nodes[start].dfs(end) if path[1] == end: prod = dg.multiplyPath(path) answer.append(prod) dg.nodes[start].addConnection(dg.nodes[end], prod) else: answer.append(1) return answer
 Build the digraph using the data given.

RE: If you're getting "ValueError: Unterminated string", here's why
Looks like it's been fixed, if you open the Custom Testcase, it's formatted properly. However, as pointed out in this post, some of the actual test cases have 4 spaces instead of tabs. Is it an edge case that was missed, or is the problem not stated fully?

If you're getting "ValueError: Unterminated string", here's why
If you're getting something like this
Line 42: ValueError: Unterminated string starting at: line 1 column 1 (char 0)
when clicking
Run Code
, LeetCode OJ has a problem. Open up the the Custom Testcase, and you'll see that OJ has converted\n
and\t
into whitespace, which is mucking things up. Copypaste the strings in the statement of the problem in, and it'll work.