Is it a prefix code?

Question

In information theory, a "prefix code" is a dictionary where none of the keys are a prefix of another. In other words, this means that none of the strings starts with any of the other.

For example, {"9", "55"} is a prefix code, but {"5", "9", "55"} is not.

The biggest advantage of this, is that the encoded text can be written down with no separator between them, and it will still be uniquely decipherable. This shows up in compression algorithms such as Huffman coding, which always generates the optimal prefix code.

Your task is simple: Given a list of strings, determine whether or not it is a valid prefix code.

Your input:

• Will be a list of strings in any reasonable format.

• Will only contain printable ASCII strings.

• Will not contain any empty strings.

Your output will be a truthy/falsey value: Truthy if it's a valid prefix code, and falsey if it isn't.

Here are some true test cases:

["Hello", "World"] 
["Code", "Golf", "Is", "Cool"]
["1", "2", "3", "4", "5"]
["This", "test", "case", "is", "true"] 
["111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011", 
 "0110", "11001", "00110", "10011", "11000", "00111", "10010"]

Here are some false test cases:

["4", "42"] 
["1", "2", "3", "34"] 
["This", "test", "case", "is", "false", "t"]
["He", "said", "Hello"]
["0", "00", "00001"]
["Duplicate", "Duplicate", "Keys", "Keys"]

This is code-golf, so standard loopholes apply, and shortest answer in bytes wins.

• Martin Ender: Do you want a consistent truthy value or could it be e.g. "some positive integer" (which might vary between different inputs).
• DJMcMayhem: @MartinBüttner Any positive integer is fine.
• Martin Ender: @DrGreenEggsandHamDJ I don't think that answer is meant to address the consistency of outputs at all, hence the question. ;)
• Joba: Just out of curiosity: The challenge says: "The biggest advantage of this, is that the encoded text can be written down with no separator between them, and it will still be uniquely decipherable.". How would something like 001 be uniquely decipherable? It could be either 00, 1 or 0, 11.
• DJMcMayhem: @Joba It depends on what your keys are. If you have 0, 00, 1, 11 all as keys, this is not a prefix-code because 0 is a prefix of 00, and 1 is a prefix of 11. A prefix code is where none of the keys starts with another key. So for example, if your keys are 0, 10, 11 this is a prefix code and uniquely decipherable. 001 is not a valid message, but 0011 or 0010 are uniquely decipherable.

Answer 1

Pyth, 8 bytes

.AxM.PQ2

Test suite

Take all 2 element permutations of the input, map each to the index of one string in the other (0 for a prefix) and return whether all results are truthy (non-zero).

Answer 2

Haskell, 37 bytes

f l=[x|x<-l,y<-l,zip x x==zip x y]==l

Each element x of l is repeated once for every element that it's a prefix of, which is exactly once for a prefix-free list, giving the original list. The prefix property is checked by zipping both lists with x, which cuts off elements beyond the length of x.

• Michael Klein: This is an elegant solution (+1)

Answer 3

Java, (削除) 128 (削除ここまで) (削除) 127 (削除ここまで) (削除) 126 (削除ここまで) (削除) 125 (削除ここまで) (削除) 124 (削除ここまで) 121 bytes

(Thanks @Kenny Lau, @Maltysen, @Patrick Roberts, @Joba)

Object a(String[]a){for(int i=0,j,l=a.length;i<l;i++)for(j=0;j<l;)if(i!=j&a[j++].startsWith(a[i]))return 1<0;return 1>0;}

Ungolfed

Object a(String[] a) {
 for (int i = 0, j, l = a.length; i < l; i++) 
 for (j = 0; j < l;) 
 if (i != j & a[j++].startsWith(a[i])) return 1<0;
 return 1>0;
}

Output

[Hello, World]
true
[Code, Golf, Is, Cool]
true
[1, 2, 3, 4, 5]
true
[This, test, case, is, true]
true
[111, 010, 000, 1101, 1010, 1000, 0111, 0010, 1011, 0110, 11001, 00110, 10011, 11000, 00111, 10010]
true
[4, 42]
false
[1, 2, 3, 34]
false
[This, test, case, is, false, t]
false
[He, said, Hello]
false
[0, 00, 00001]
false
[Duplicate, Duplicate, Keys, Keys]
false

• Maltysen: idk bout java, but would & work instead of &&?
• Marv: Right, saves another byte. In Java, using bitwise operators with boolean operands behave just like normal logical operators, except they don't short circuit which isn't needed in this case.
• Patrick Roberts: Couldn't you just change the return type of the function to int and return 0 and 1? That would save several bytes. Also I forget if this is valid in Java but if you declare i, j, and l inside the outer for loop that would save one byte from one less semicolon.
• Marv: @PatrickRoberts Maltysen suggested this before, but this is not valid according to the most upvoted definition of truthy/falsey. Putting the declarations in the loop however is perfectly valid and pretty obvious now that I think about it. Thats what you get for golfing at 4 in the morning :^)
• Pokechu22: @Joba Pretty sure that isn't valid since indexOf returns -1 when the string isn't found; it would need to be indexOf(a[i])==0 in which case there are no savings.

Answer 4

Python 2, 48 (削除) 51 (削除ここまで) bytes

lambda l:all(1/map(a.find,l).count(0)for a in l)

For each element a of l, the function a.find finds the index of the first occurrence of a in the input string, giving -1 for an absence. So, 0 indicates a prefix. In a prefix-free list, mapping this function returns only a single 0 for a itself. The function checks that this is the case for every a.

---

51 bytes:

lambda l:[a for a in l for b in l if b<=a<b+'~']==l

Replace ~ with a character with ASCII code 128 or higher.

For each element a in l, a copy is included for each element that's a prefix of it. For a prefix-free list, the only such element is a itself, so this gives the original list.

Answer 5

CJam, 14 bytes

q~$W%2ew::#0&!

Test suite.

Explanation

q~ e# Read and evaluate input.
$ e# Sort strings. If a prefix exists it will end up directly in front 
 e# of a string which contains it.
W% e# Reverse list.
2ew e# Get all consecutive pairs of strings.
::# e# For each pair, find the first occurrence of the second string in the first.
 e# If a prefix exists that will result in a 0, otherwise in something non-zero.
0& e# Set intersection with 0, yielding [0] for falsy cases and [] for truthy ones.
! e# Logical NOT.

Answer 6

JavaScript ES6, (削除) 65 (削除ここまで) (削除) 43 (削除ここまで) 40 bytes

a=>!/(.*)1円/.test(''+a.sort().join``)
 ^ ^ ^ embedded NUL characters

My previous solution, which handled string arrays of all UTF-8 characters:

a=>!/[^\\]("([^"]*\\")*[^\\])",1円/.test(JSON.stringify(a.sort()))

I was able to avoid JSON.stringify since the challenge specifies printable ASCII characters only.

Test

f=a=>!/(0円.*)1円/.test('0円'+a.sort().join`0円`) // since stackexchange removes embedded NUL characters
O.textContent += 'OK: '+
[["Hello", "World"] 
,["Code", "Golf", "Is", "Cool"]
,["1", "2", "3", "4", "5"]
,["This", "test", "case", "is", "true"] 
,["111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011", 
 "0110", "11001", "00110", "10011", "11000", "00111", "10010"]
].map(a=>f(a)) 
O.textContent += '\nKO: '+
[["4", "42"] 
,["1", "2", "3", "34"] 
,["This", "test", "case", "is", "false", "t"]
,["He", "said", "Hello"]
,["0", "00", "00001"]
,["Duplicate", "Duplicate", "Keys", "Keys"]
].map(a=>f(a))

<pre id=O></pre>

Answer 7

Haskell, 49 bytes

g x=[1|z<-map((and.).zipWith(==))x<*>x,z]==(1<$x)

This has a couple parts:

-- Are two lists (or strings) equal for their first min(length_of_1,length_of_2) elements, i.e. is one the prefix of the other?
(and.).zipWith(==)
-- Check whether one element is the prefix of the other, for all pairs of elements (including equal pairs)
map((and.).zipWith(==))x<*>x
-- This is a list of 1's of length (number of elements that are the prefix of the other)
[1|z<-map((and.).zipWith(==))x<*>x,z]
-- This is the input list, with all the elements replaced with 1's
(1<$x)

If the two lists are equal, then an element is only the prefix of itself, and it's valid.

Answer 8

Retina, 19 bytes

Byte count assumes ISO 8859-1 encoding.

O`.+
Mm1`^(.+)¶1円
0

The input should be linefeed-separated. Output is 0 for falsy and 1 for truthy.

Try it online! (Slightly modified to support multiple space-separated test cases instead.)

Explanation

O`.+

Sort the lines in the input. If a prefix exists it will end up directly in front of a string which contains it.

Mm1`^(.+)¶1円

Try to match (M) a complete line which is also found at the beginning of the next line. The m activates multiline mode such that ^ matches line beginnings and the 1 ensures that we only count at most one match such that the output is 0 or 1.

0

To swap 0 and 1 in the result, we count the number of 0s.

Answer 9

Java, 97 bytes

Object a(String[]a){for(String t:a)for(String e:a)if(t!=e&t.startsWith(e))return 1<0;return 1>0;}

Uses most of the tricks found in @Marv's answer, but also makes use of the foreach loop and string reference equality.

Unminified:

Object a(String[]a){
 for (String t : a)
 for (String e : a)
 if (t != e & t.startsWith(e))
 return 1<0;
 return 1>0;
}

Note that, as I said, this uses string reference equality. That does mean that the code can behave oddly due to String interning. The code does work when using arguments passed from the command line, and also when using something read from the command line. If you want to hardcode the values to test, though, you'd need to manually call the String constructor to force interning to not occur:

System.out.println(a(new String[] {new String("Hello"), new String("World")}));
System.out.println(a(new String[] {new String("Code"), new String("Golf"), new String("Is"), new String("Cool")}));
System.out.println(a(new String[] {new String("1"), new String("2"), new String("3"), new String("4"), new String("5")}));
System.out.println(a(new String[] {new String("This"), new String("test"), new String("case"), new String("is"), new String("true")}));
System.out.println(a(new String[] {new String("111"), new String("010"), new String("000"), new String("1101"), new String("1010"), new String("1000"), new String("0111"), new String("0010"), new String("1011"), new String("0110"), new String("11001"), new String("00110"), new String("10011"), new String("11000"), new String("00111"), new String("10010")}));
System.out.println(a(new String[] {new String("4"), new String("42")}));
System.out.println(a(new String[] {new String("1"), new String("2"), new String("3"), new String("34")}));
System.out.println(a(new String[] {new String("This"), new String("test"), new String("case"), new String("is"), new String("false"), new String("t")}));
System.out.println(a(new String[] {new String("He"), new String("said"), new String("Hello")}));
System.out.println(a(new String[] {new String("0"), new String("00"), new String("00001")}));
System.out.println(a(new String[] {new String("Duplicate"), new String("Duplicate"), new String("Keys"), new String("Keys")}));

• Pokechu22: @Jo King See the second half of my answer; it's a bit complicated and depends on how input is specified. I don't remember actually writing this, though

Answer 10

PostgreSQL, (削除) 186 (削除ここまで), 173 bytes

WITH y AS(SELECT * FROM t,LATERAL unnest(c)WITH ORDINALITY s(z,r))
SELECT y.c,EVERY(u.z IS NULL)
FROM y LEFT JOIN y u ON y.i=u.i AND y.r<>u.r AND y.z LIKE u.z||'%' GROUP BY y.c

Output:

enter image description here

No live demo this time. http://sqlfiddle.com supports only 9.3 and to run this demo 9.4 is required.

How it works:

1. Split string array with number and name it y
2. Get all y
3. LEFT OUTER JOIN to the same derived table based on the same i(id), but with different oridinal that start with prefix y.z LIKE u.z||'%'
4. Group result based on c (initial array) and use EVERY grouping function. If every row from second table IS NULL it means there is no prefixes.

---

Input if someone is interested:

CREATE TABLE t(i SERIAL,c text[]);
INSERT INTO t(c)
SELECT '{"Hello", "World"}'::text[]
UNION ALL SELECT '{"Code", "Golf", "Is", "Cool"}'
UNION ALL SELECT '{"1", "2", "3", "4", "5"}'
UNION ALL SELECT '{"This", "test", "case", "is", "true"}' 
UNION ALL SELECT '{"111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011","0110", "11001", "00110", "10011", "11000", "00111", "10010"}'
UNION ALL SELECT '{"4", "42"}'
UNION ALL SELECT '{"1", "2", "3", "34"}' 
UNION ALL SELECT '{"This", "test", "case", "is", "false", "t"}'
UNION ALL SELECT '{"He", "said", "Hello"}'
UNION ALL SELECT '{"0", "00", "00001"}'
UNION ALL SELECT '{"Duplicate", "Duplicate", "Keys", "Keys"}';

EDIT:

SQL Server 2016+ implementation:

WITH y AS (SELECT *,z=value,r=ROW_NUMBER()OVER(ORDER BY 1/0) FROM #t CROSS APPLY STRING_SPLIT(c,','))
SELECT y.c, IIF(COUNT(u.z)>0,'F','T')
FROM y LEFT JOIN y u ON y.i=u.i AND y.r<>u.r AND y.z LIKE u.z+'%' 
GROUP BY y.c;

LiveDemo

Note: It is comma separated list, not real array. But the main idea is the same as in PostgreSQL.

---

EDIT 2:

Actually WITH ORDINALITY could be replaced:

WITH y AS(SELECT *,ROW_NUMBER()OVER()r FROM t,LATERAL unnest(c)z)
SELECT y.c,EVERY(u.z IS NULL)
FROM y LEFT JOIN y u ON y.i=u.i AND y.r<>u.r AND y.z LIKE u.z||'%' GROUP BY y.c

SqlFiddleDemo

Answer 11

Brachylog, 8 bytes

¬(⊇pa0d)

Try it online!

Outputs through predicate success/failure. Takes more than 60 seconds on the last truthy test case ["111","010","000","1101","1010","1000","0111","0010","1011","0110","11001","00110","10011","11000","00111","10010"] but passes it quickly with an added byte which eliminates a large number of possibilities earlier than the program does otherwise (Ċ before checking permutations rather than d after checking permutations, to limit the length of the sublist to two).

¬( ) It cannot be shown that
 p a permutation of
 ⊇ a sublist of the input
 d is a pair of values [A,B] such that
 a0 A is a prefix of B.

Less trivial 9-byte variants than ¬(⊇Ċpa0d) which run in reasonable time are ¬(⊇o1a0d), ¬(⊇o↔a0d), and ¬(⊇oa0d1).

• Unrelated String: If this challenge used "two distinct and consistent values" instead of "truthy/falsy", this would only take 5 bytes.

Answer 12

Perl 6, 24 bytes

{.all.starts-with(.one)}

Try it online!

Wow, surprisingly short while using a long built-in.

Explanation

{ } # Anonymous code block taking a list
 .all # Do all of the strings
 .starts-with( ) # Start with
 .one # Only one other string (i.e. itself)

• bb94: I wrote a 50 byte answer but yours just blew mine out of the water.
• Jo King: @bb94 Yeah, I started with a similar answer but ran into the same problem as yours with sets with duplicated keys returning truthy. Writing this answer was incredibly satisfying

Answer 13

Racket, 70 bytes

(λ(l)(andmap(λ(e)(not(ormap(curryr string-prefix? e)(remv e l))))l))

Answer 14

JavaScript (ES6), 52 (削除) 54 (削除ここまで)

Edit 2 bytes saved thx @Neil

a=>!a.some((w,i)=>a.some((v,j)=>i-j&&!w.indexOf(v)))

Test

f=a=>!a.some((w,i)=>a.some((v,j)=>i-j&&!w.indexOf(v)))
O.textContent += 'OK: '+
[["Hello", "World"] 
,["Code", "Golf", "Is", "Cool"]
,["1", "2", "3", "4", "5"]
,["This", "test", "case", "is", "true"] 
,["111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011", 
 "0110", "11001", "00110", "10011", "11000", "00111", "10010"]
].map(a=>f(a)) 
O.textContent += '\nKO: '+
[["4", "42"] 
,["1", "2", "3", "34"] 
,["This", "test", "case", "is", "false", "t"]
,["He", "said", "Hello"]
,["0", "00", "00001"]
,["Duplicate", "Duplicate", "Keys", "Keys"]
].map(a=>f(a))

<pre id=O></pre>

• Neil: !w.indexOf(v)?

Answer 15

Mathematica (削除) 75 69 (削除ここまで) 68 bytes

Loquacious as usual. But Martin B was able to reduce the code by 7 bytes.

Method 1: Storing output in an Array

(68 bytes)

f@a_:=!Or@@(Join@@Array[a~Drop~{#}~StringStartsQ~a[[#]]&,Length@a])

---

f@{"111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011", "0110", "11001", "00110", "10011", "11000", "00111", "10010"}

True

---

f@{"He", "said", "Hello"}

False

---

Method 2: Storing output in a List

(69 bytes)

f@a_:=!Or@@Flatten[a~Drop~{#}~StringStartsQ~a[[#]]&/@Range@Length@a]

• Martin Ender: The precedence rules should make a~Drop~{#}~StringStartsQ~a[[#]] work. Also Array should save some bytes over Length, especially because it will allow you to use Join@@ instead of Flatten@ (provided, you're using Flatten only for a single level).
• DavidC: Thanks for the suggestion. I'll look into Array later.

Answer 16

Mathematica, 41 bytes

!Or@@StringStartsQ@@@Reverse@Sort@#~Subsets~{2}&

Answer 17

APL (Dyalog Unicode), 13 bytes ^SBCS

-2 bytes:

≢=∘≢∘⍸∘.(⊃⍷)⍨

Try it online!

Explanation:

≢=∘≢∘⍸∘.(⊃⍷)⍨ ⍝ Monadic function train
 ⍷ ⍝ "Find": Convert the right argument into a boolean vector,
 ⍝ where ones correspond to instances of the left argument
 ⊃ ⍝ Take the first item of the above vector (i.e., only prefixes)
 ∘.( )⍨ ⍝ Commutative outer product: take the above function and apply
 ⍝ it for each possible pair of elements in the input
 ⍝ If the input is a prefix code, the above should have a number of ones
 ⍝ equal to the length of the input (i.e., each item is a prefix of only itself)
 ⍝ To test this...
 ⍸ ⍝ Find the location of all ones in the above
 ≢∘ ⍝ Take the length of the above
≢=∘ ⍝ Compare to the length of the input

• ngn: ~2∊+\⊃¨∘.⍷⍨⎕­

Answer 18

J, 17 bytes

#=1#.1#.{.@E.&>/~

Try it online!

Note: I actually wrote this before looking at the APL answer, to approach it without bias. Turns out the approaches are almost identical, which is interesting. I guess this is the natural "array thinknig" solution

Take boxed input because the strings are of unequal length.

Create a self-function table /~ of each element paired with each element and see if there is a match at the start {.@E.. This will produce a matrix of 1-0 results.

Sum it twice 1#.1#. to get a single number representing "all ones in the matrix", and see if that number is the same as the length of the input #=. If it is, the only prefix matches are self matches, ie, we have a prefix code.

sorting solution, 18 bytes

0=1#.2{.@E.&>/\/:~

Attempt at different approach. This solution sorts and looks at adjacent pairs.

Try it online!

Answer 19

R, 48 bytes

function(s)sum(outer(s,s,startsWith))==length(s)

Try it online!

Explanation: outer(s,s,startsWith) outputs a matrix of logicals checking whether s[i] is a prefix of s[j]. If s is a prefix code, then there are exactly length(s) TRUE elements in the result, corresponding to the diagonal elements (s[i] is a prefix of itself).

• Giuseppe: I've found a bunch of other 48 byte alternatives, like function(s)all(colSums(outer(s,s,startsWith))<2) but it remains that startsWith is a function I didn't know about! Nice find.
• Robin Ryder: @Giuseppe I tried several ways of checking whether the matrix is an identity matrix, but couldn't get it under 48 bytes either. I thought this way was the easiest to understand, but I'm sure someone will golf it down!
• Giuseppe: 47 bytes by inverting TRUE and FALSE...
• Robin Ryder: @Giuseppe Is that allowed? The rules explicitly ask for truthy when the input is a valid prefix code. (Also your link is to the 48 byte version, but I am guessing that your suggestion is to replace == with >. :-) )

Answer 20

Pyth - (削除) 13 (削除ここまで) 12 bytes

!ssmm}d._k-Q

Try it online here.

Answer 21

Ruby, 48 bytes

Uses arguments as input and stdout as output.

p !$*.map{a,*b=$*.rotate!
a.start_with? *b}.any?

Answer 22

Python, (削除) 58 (削除ここまで) 55 bytes

lambda l:sum(0==a.find(b)for a in l for b in l)==len(l)

• user45941: a.index(b)==0 is a bit shorter. Alternatively, you could do 0**sum(a.index(b)for a in l for b in l).
• DJMcMayhem: @Mego That doesn't work because index throws an exception when b isn't found. And because it should be ==, not >=. However, find works. (And it's shorter too!)
• user45941: Whoops, I meant to type find. Sleepy brain is sleepy. The second version should also work with find.
• DJMcMayhem: @Mego I'm not sure if I get the second version. Wouldn't that always return 0?
• DJMcMayhem: @Mego That only works if every string is the same. The reason we compare it to len(l) is since we're iterating through all bs on each a, there will always be at least one match per a. So we check if the number of matches is the same as the number of elements.

Answer 23

Scala, 71 bytes

(s:Seq[String])=>(for{x<-s;y<-s}yield x!=y&&x.startsWith(y)).forall(!_)

Answer 24

Racket 130 bytes

(define g #t)(for((n(length l)))(for((i(length l))#:unless(= i n))(when(string-prefix?(list-ref l i)(list-ref l n))(set! g #f))))g

Ungolfed:

(define(f l)
 (define g #t)
 (for ((n (length l)))
 (for ((i (length l)) #:unless (= i n))
 (when (string-prefix? (list-ref l i) (list-ref l n))
 (set! g #f))))g)

Testing:

(f [list "Hello" "World"]) 
(f [list "Code" "Golf" "Is" "Cool"])
(f [list "1" "2" "3" "4" "5"])
(f [list "This" "test" "case" "is" "true"]) 
(f [list "111" "010" "000" "1101" "1010" "1000" "0111" "0010" "1011" 
 "0110" "11001" "00110" "10011" "11000" "00111" "10010"])
(f [list "4" "42"]) 
(f [list "1" "2" "3" "34"]) 
(f [list "This" "test" "case" "is" "false" "t"])
(f [list "He" "said" "Hello"])
(f [list "0" "00" "00001"])
(f [list "Duplicate" "Duplicate" "Keys" "Keys"])

Output:

#t
#t
#t
#t
#t
#f
#f
#f
#f
#f
#f

Answer 25

C (gcc), 93 bytes

p(r,e,f,i,x)char**r;{for(f=i=0;i<e;++i)for(x=0;x<e;++x)f|=x!=i&&strstr(r[i],r[x])==r[i];r=f;}

Try it online!

Simple double for loop using strstr(a,b)==a to check for prefices. Mainly added since there doesn't seem to be a C answer yet.

• ceilingcat: 85 bytes

Answer 26

05AB1E, 13 bytes

2.ÆDí«ε`Å?}O_

Too long.. Initially I had a 9-byte solution, but it failed for the duplicated key test case.

Try it online or verify all test cases.

Explanation:

2.Æ # Get all combinations of two elements from the (implicit) input-list
 Dí # Duplicate and reverse each pair
 « # Merge the lists of pairs together
 ε # Map each pair to:
 ` # Push both strings to the stack
 Å? # And check if the first starts with the second
 }O # After the map: sum to count all truthy values
 _ # And convert it to truthy if it's 0 or falsey if it's any other integer
 # (which is output implicitly as result)

Answer 27

Japt, 8 bytes

á2 ËrbÃe

Try it

á2 ËrbÃe :Implicit input of array
á2 :Permutations of length 2
 Ë :Map each pair
 r : Reduce by
 b : Get the index of the second in the first - 0 (falsey) if it's a prefix
 Ã :End map
 e :All truthy (-1 or >0)

Answer 28

C# (Visual C# Interactive Compiler), 70 bytes

l=>!l.Any(x=>l.Where((y,i)=>l.IndexOf(x)!=i).Any(z=>z.StartsWith(x)));

Try it online!

Answer 29

Stax, 6 bytes

å·↑↑¶Ω

Run and debug it

This produces non-zero for truthy.

The general idea is to consider every pair of strings in the input. If the substring index of one in the other is ever zero, then it's not a valid prefix code. In stax, index of a non-existing substring yields -1. This way, all the pair-wise substring indices can be multiplied together.

This is the same algorithm as isaacg's pyth solution, but I developed it independently.