# Hash collision: “NO” means “YES”

This Code Golf was inspired by the recent Daily WTF article You Can't Handle the True!, which features a string comparison written as:

String yes = "YES";
if ((delay.hashCode()) == yes.hashCode())


Imagine the trouble it would have caused for Steve's team if Java's String.hashCode method just happened to be implemented in a way that "YES".hashCode() == "NO".hashCode(). So, the challenge I propose here is:

Write, in as few characters as possible, a hash function (I'll call it h) with a string parameter and integer return value, such that h("YES") is equal to h("NO").

Of course, this would be trivial to do with a function like def h(s): return 0, which makes a hash collision for every string. To make this challenge more interesting, you must abide by the following additional rule:

Of the other 18 277 possible strings consisting of three or fewer uppercase ASCII letters (^[A-Z]{0,3}$), there must be no hash collisions. Clarification (pointed out by Heiko Oberdiek): The input string may contain characters other than A-Z, and your code must be able to hash arbitrary strings. (You may, however, assume that the input is a character string rather than a null pointer or an object of some other data type.) However, it does not matter what the return value is for strings that do not match ^[A-Z]{0,3}$, as long as it's an integer.

Furthermore, to obfuscate the intent of this function:

Your code must not include any of the letters 'Y', 'E', 'S', 'N', or 'O' (in either upper- or lowercase) within character or string literals.

Of course, this restriction doesn't apply to language keywords, so else, return, etc. are fine.

• It kind of doesn't help that we can still use the numeric ASCII values of YESNO to check for this specific exception. – Joe Z. Apr 25 '14 at 2:22
• Reading the article one can't not remember the "for reasons" comic: threewordphrase.com/pardonme.gif – Antonio Ragagnin Apr 26 '14 at 10:46

# GolfScript: 19 chars (24 chars for named function)

26base.2107=59934*+


This is the body of the function. Assigning it to a named function h takes five more chars:

{26base.2107=59934*+}:h;


(The final semicolon can be omitted, if you don't mind leaving a copy of the code lying on the stack.)

The core of the hash function is 26base, which calculates sum(26nk · ak; k = 1 .. n), where n is the number of characters in the input and ak denotes the ASCII code of the k-th input character. For inputs consisting of uppercase ASCII letters, this is a collision-free hash function. The rest of the code compares the result to 2107 (the hash code of NO) and, if they're equal, adds 59934 to yield 2701 + 59934 = 62041, the hash code of YES.

For example output, see this online demo with test cases.

• How did you test this? I just found a bunch of collisions. Example: h('DXP') == h('KK') == 65884. – nneonneo May 6 '14 at 19:36
• (Python equivalent of what you wrote, for my testing purposes: lambda w:sum(ord(c)*26**i for i,c in enumerate(reversed(w*9)))%102983) – nneonneo May 6 '14 at 19:39
• @nneonneo: Obviously, not well enough. I thought I generated the full set of three-letter-or-less inputs, hashed all of them and checked that the set of hashes had one element less than the set of inputs. Clearly, my test harness had a bug somewhere. :-( I'll revert to the original 19-char version until/unless I can fix the shorter one. – Ilmari Karonen May 6 '14 at 19:48

# 32-bit Python 2.x (19)

hash(w*9)%537105043


RSA uses a semiprime modulus, and that makes it secure, so using one with my hash algorithm should surely make it even better!1

This is a pure math function, works for all strings (hell, works for any hashable Python object), and doesn't contain any conditionals or special-casing! 32-bit Python can typically be called as python-32 on most systems that have both installed2.

I've tested this, and it returns 18,278 different values for the 18,279 3-letter-or-less uppercase strings. Assigning this to a function takes 11 more bytes:

h=lambda w:hash(w*9)%537105043


and h('YES') == h('NO') == 188338253.

# 64-bit Python 2.x (19)

hash(w*2)%105706823


Same deal as above.

To come up with these numbers, a little bit of modular math was used. I was looking for a function f and a modulus n such that hash(f('YES')) % n == hash(f('NO')) % n. This is equivalent to testing that n divides d = hash(f('YES')) - hash(f('NO')), i.e. we only have to check the factors of d for suitable values of n.

The ideal n is in the neighbourhood of 20000**2 to reduce the chance of a birthday paradox collision. Finding a suitable n turns out to be a bit of trial and error, playing with all the factors of d (there usually aren't many) and different choices for the function f. Notice though that the trial and error is only needed because I wanted to make n as small as possible (for golfing). If that wasn't a requirement, I could just choose d as my modulus, which is usually sufficiently large.

Note too that you can't pull this trick off using just f(s) = s (the identity function) because the rightmost character of the string has essentially a linear relationship (actually an XOR relationship) with the final hash (the other characters contribute in a much more nonlinear way). The repetition of the string therefore ensures that the differences between the strings are amplified to eliminate the effect of changing only the rightmost character.

1 This is patent nonsense.
2 Python string hashing depends on major version (2 vs 3) and bitness (32-bit vs 64-bit). It does not depend on platform AFAIK.

• You've got my vote. :D – cjfaure Apr 25 '14 at 21:02
• Unfortunately, this doesn't work on recent versions of Python due to the new hash randomization feature. – dan04 Apr 26 '14 at 2:33
• @dan04: Odd, I thought I'd specified that this was for Python 2.x only. I've edited it in again. – nneonneo Apr 26 '14 at 2:34
• May I know how you found these magic numbers? I see hash('YES'*9) has 34876679 as a factor, while hash('NO'*9) has 34876679+537105043 as a factor. But how do you knew that 537105043 was a good modulus? i.e. it didn't make other collisions? – Antonio Ragagnin Apr 26 '14 at 7:37
• @AntonioRagagnin: Added that to the answer. – nneonneo Apr 26 '14 at 7:52

# Perl, 5349 40 bytes

sub h{hex(unpack H6,pop)-20047||5830404}


Test:

h('YES') = 5830404
h('NO')  = 5830404
Keys:   18279
Values: 18278


The hash values for YES and NO are the same and there are 18279 strings ^[A-Z]{0,3}$, which are collision free except for the only collision for YES and NO. Ungolfed: sub h { hex(unpack("H6", pop())) - 20047 || 5830404; # The argument is the first and only element in the argument array @_. # "pop" gets the argument from array @_ (from the end). # The first three bytes of the argument or less, if the argument # is shorter, are converted to a hex string, examples: # "YES" -> "594553" # "NO" -> "4e4f" # Then the hex string is converted to a number by function "hex": # 0x594553 = 5850451 # 0x4e4f = 20047 # The value for "NO" is subtracted, examples: # case "YES": 5850451 - 20047 = 5830404 # case "NO": 20047 - 20047 = 0 # If the argument is "NO", the subtraction is zero, therefore # 5830404 is returned, the result of "YES". } # Test my %cache; sub addcache ($) {$cache{$_[0]} = h($_[0])} # Check entries 'YES' and 'NO' addcache 'YES'; addcache 'NO'; print "h('YES') =$cache{'YES'}\n";
print "h('NO')  = $cache{'NO'}\n"; # Fill cache with all strings /^[A-Z]{0-3}$/
for my $one (A..Z) { addcache$one;
for (A..Z) {
my $two = "$one$_"; addcache$two;
for (A..Z) {
my $three = "$two$_"; addcache$three;
}
}
}
# Compare number of keys with number of unique values
my $keys = keys %cache; my %hash; @hash{values %cache} = 1 x$keys;
$values = keys %hash; print "Keys:$keys\n";
print "Values: $values\n";  # Older version, 49 bytes Since the new algorithm is slightly different, I keep the old version. sub h{($_=unpack V,pop."\0"x4)==20302?5457241:$_}  Test: h('YES') = 5457241 h('NO') = 5457241 Keys: 18279 Values: 18278  Ungolfed: sub h {$_ = unpack('V', pop() . ($" x 4); # pop(): gets the argument (we have only one). #$" x 4: generates the string "    " (four spaces);
#   adding the four spaces ensures that the string is long
#   enough for unpack's template "V".
# unpack('V', ...): takes the first four bytes as
#   unsigned long 32-bit integer in little-endian ("VAX") order.
$_ == 20302 ? 5457241 :$_;
# If the hash code would be "NO", return the value for "YES".
}


Edits:

• Using "\0" as fill byte saves 4 bytes in comparison to $". • Where do 5457241 and 20047 come from? How do you calculate these numbers? Thanks in advance. – A.L Apr 26 '14 at 3:02 • @n.1: YES in hex is 594553. 0x594553 = 5850451. NO in hex is 4e4f. 0x4e4f = 20047. – nneonneo Apr 26 '14 at 4:27 # Python: 63 An incredibly lame solution: def h(s): try:r=int(s,36) except:r=0 return(r,44596)[r==852]  It works by interpreting alphanumeric strings as base-36 numbers, and returning 0 for everything else. There's an explicit special case to check for a return value of 852 (NO), and return 44596 (YES) instead. • Unless I misunderstand: It's code golf, you're allowed to assume the input is accurate. You can ditch try: and the entire third line. You can also save a few bites by having every logical line on the same actual line, separated by semicolons (def h(s):r=int(s,36);return(r,44596)[r==852]) – undergroundmonorail Apr 25 '14 at 4:31 • @undergroundmonorail: The string parameter for the hash function is not restricted in the question. For a certain class of strings (up to three uppercase letters) there is a restriction regarding the return values of the hash function. However it does not matter, what is returned for other strings, if the return value is an integer. – Heiko Oberdiek Apr 25 '14 at 9:21 • I like the boolean-indexing of your array there – kratenko Apr 25 '14 at 15:28 # Pure Bash, 29 bytes (function body) h()(echo$[n=36#$1,n-852?n:44596])  This simply treats the input string as a base 36 number and converts to decimal, then deals with the special NO case. Output: $ h A
10
$h B 11$ h CAT
15941
$h NO 44596$ h YES
44596
$h ZZZ 46655$


# Ruby, 51 bytes

h=->s{d=s.unpack('C*').join;d=~/896983|^7879$/?0:d}  testing code : h=->s{d=s.unpack('C*').join;d=~/896983|^7879$/?0:d}

puts 'YES : '+h.call('YES').to_s # 0
puts 'NO : '+h.call('NO').to_s # 0
puts 'NOX : '+h.call('NOX').to_s # 787988
puts 'FNO : '+h.call('FNO').to_s # 707879
puts ''

values = Hash[]
n = 0
('A'..'Z').each{|c|
values[c] = h.call(c)
('A'..'Z').each{|c2|
values[c+c2] = h.call(c+c2)
('A'..'Z').each{|c3|
values[c+c2+c3] = h.call(c+c2+c3)
n += 1
}
}
}
puts 'tested '+n.to_s
duplicate = Hash.new()

values.each{|k, e|
if duplicate.has_key?(e)
puts 'duplicate : "'+k+'" = "'+duplicate[e].to_s+'" ('+e.to_s+')'
else
duplicate[e] = k
end
}


output :

YES : 0
NO : 0
NOX : 787988
FNO : 707879

tested 17576
duplicate : "YES" = "NO" (0)


# Javascript (ES6) 54 bytes

f=s=>[x.charCodeAt()for(x of s)].join('')^7879||897296

f('YES'); // 897296
f('NO'); // 897296
f('MAYBE'); // -824036582


# Java - 94 77

int h=new BigInteger(s.getBytes()).intValue();return Math.abs(h-(h^5835548));


Unrolled:

int hashCode(String s) {
int h = new BigInteger(s.getBytes()).intValue();
return Math.abs(h - (h ^ 5835548));
}


Narrative - for f(s) = BigInteger(s.getBytes()):

• f("YES") xor f("NO") = 5835548
• So f("YES") xor 5835548 = f("NO")
• So f("YES") - (f("YES") xor 5835548) = f("NO") - (f("NO") xor 5835548) am I right?
• Can't you inline the BigInteger? – mafu Apr 26 '14 at 22:01
• @mafutrct - YES!!! Thank you. – OldCurmudgeon Apr 26 '14 at 22:25

# CJam, 15 bytes

q42b_*81991617%


Works as the GolfScript solution below. Try it online.

# GolfScript, 17 bytes

42base.*81991617%


This approach builds on the answers of nneonneo and Ilmari Karonen.

### How it works

42base    # Interpret the input string as a base 42 number.
# "YES" is [ 89 69 83 ] in ASCII, so it becomes 42 * (42 * 89 + 69) + 83 = 159977.
# "NO" is [ 78 79 ] in ASCII, so it becomes 42 * 78 + 79 = 3355.
#
.*        # Square. "YES" becomes 25592640529, "NO" becomes 11256025.
#
81991617% # "YES" becomes 11256025.


### Choosing an algorithm

We start with {b base}:h, i.e., the input string is considered a base-b number. As long as b > 25, h is inyective.

We get a collision for strings "YES" and "NO" if we modify h in the following way: {x base n}:h, where n is a divisor of "YES" h "NO" h -.

Unfortunately, this means we'll also get a collision for, e.g., YET and NP. To prevent this, we have to modify the base-b number in a non-linear fashion before taken the modulus.

The shortest way to accomplish this in GolfScript is to multiply the base-b number with itself (i.e., squaring it). h is now {base b .* n %}:h.

All that remains to do is finding suitable values for b and n. We can accomplish this by brute force:

for((b=26;b<100;b++)){
P=($(golfscript <<< "['YES' 'NO']{$b base.*}/-" | factor | cut -d\  -f 2-))

for n in $(for((i=0;i<2**${#P[@]};i++)){
for((n=1,j=0;j<${#P[@]};n*=${P[j]}**((i>>j)&1),j++)){ :;};echo $n;} | sort -nu);{ [[$n -ge 18277 && $(echo -n '' {A..Z}{,{A..Z}{,{A..Z}}} | golfscript <(echo "' '/[{$b base.*$n%}/].&,")) = 18278 ]] && echo$b $n && break } }  The shortest possible values for b n are: 37 92176978 42 81991617  ### Testing $ echo -n '' {A..Z}{,{A..Z}{,{A..Z}}} |
golfscript <(echo '{42base.*81991617%}:h;" "/{."\t"+\h+puts}/') |
sort -k 2n |
uniq -Df 1
"NO"    11256025
"YES"   11256025


# JavaScript (ES6) - 38 characters (33 char function body)

h=s=>(a=btoa(s))=="WUVT"|a=="Tk8="||+s


### Test Cases:

var l = console.log;
l(  h("YES")  );                // 1
l(  h("NO")  );                 // 1
l(  h("ABC")  );                // NaN
l(  h("WIN")  );                // NaN
l(  h("YES") === h("NO")  );    // true
l(  h("ABC") === h("WIN")  );   // false
l(  h("WIN") === h("YES")  );   // false

l(  NaN === NaN  );             // false


### Explanation:

First of all, let me introduce you to NaN - "Not A Number" - in JavaScript. It is a number:

typeof NaN  // number


Just like:

typeof 42   // number


Its special property is that it never equals itself. My function returns 1 if the string is YES or NO, and NaN for any other string.

So, this doesn't break the rules, because there would be no hash collision for any other string ;) ( NaN !== NaN shown above in test cases).

And my dream comes true: beating Bash, Perl and Ruby in code length!

### Ungolfed Code:

h =  // h is a function
s => // s = string argument

( ( a = btoa(s) )  ==  "WUVT" | a == "Tk8=" )
^-- returns some value stored in a


If that value is "WUVT" or "Tk8=", return 1. Else, return

+s // parseInt(s, 10)


which would be NaN.

• NaN might be a number, but it is not an "integer" in any sense of the word. – Paŭlo Ebermann Apr 26 '14 at 8:59
• @PaŭloEbermann From wiki, "An integer is a number that is written without a fractional component". The question does not explicitly say that the integer has to be ^\d+$. And JS does treat NaN as a number. You can multiply it by a number, add, divide, subtract just as with numbers. It is a special property of JavaScript. There's no harm in using it. That's what we call bending of rules ;) – Gaurang Tandon Apr 26 '14 at 9:04 • I could use Object.is() and claim it's still a collision… – user2428118 Apr 26 '14 at 11:24 • @user2428118 Thanks for bringing Object.is to my knowledge. I never knew it. But I would like you to note that the OP uses the equality operator (==) for comparison, which will guarantee no hash collision happens for any string apart from "YES" or "NO". – Gaurang Tandon Apr 26 '14 at 11:31 • Ignoring the fact that claiming NaN doesn't count as collision seems cheap, this solution has collisions with strings NA through NP and YEQ through YET – nderscore Apr 27 '14 at 17:36 # Python 92 n=int("".join(map(str,map(ord,raw_input())))) # hashing function print n if 1+(n**2-904862*n)/7067329057 else-1 # input validation  The hashing function concatenates the ordinal values of the ASCII characters, the print statement ensures that the two desired inputs collide. # ECMAScript 6 (30 bytes) I've tried to avoid variable assignment, return, and function keyword, and this looks like a great way to avoid all that nonsense (it also looks like functional programming, in a way). Unlike other solutions, it doesn't depend on btoa or atob, which isn't ECMAScript 6, but HTML5. 0+ is needed, so it could parse arbitrary strings. a=>parseInt(0+a,36)-852||43744  • Nice! I didn't know they added other bases for parseInt. You can cut a lot of bytes though. :) a=>parseInt(0+a,36)-852||43744 – nderscore Apr 28 '14 at 14:17 • @nderscore: Thanks for suggestion. It really improved my script a lot. – Konrad Borowski Apr 28 '14 at 16:16 # Java - 45 (or 62?) I have no idea how to fairly score given what one needs to run a program in Java, do I need to include the function definition? Feel free to edit and adjust my score appropriately. Currently I'm scoring the same way as the @OldCurmudgeon answer. Add 17 for int h(String t){} if it's required: int h=t.hashCode();return h*h*3%1607172496;  Ungolfed with test harness: import static org.junit.Assert.*; import java.util.*; import org.junit.Test; public class YesNo { @Test public void testHashValue() { YesNo yesNo = new YesNo(); Set<Integer> set = new HashSet<>(); assertEquals(yesNo.hash("YES"), yesNo.hash("NO")); set.add(yesNo.hash("")); for(char i = 'A'; i <= 'Z'; i++) { set.add(yesNo.hash("" + i)); for(char j = 'A'; j <= 'Z'; j++) { set.add(yesNo.hash("" + i + j)); for(char k = 'A'; k <= 'Z'; k++) { set.add(yesNo.hash("" + i + j + k)); } } } assertEquals(18278, set.size()); } int hash(String toHash) { int hashValue=toHash.hashCode(); return hashValue*hashValue*3%1607172496; } }  And the looser is... # Conveyor, 145 chars  I >#< 26*)2**\88 >========* ^ \ \+- ^=====#==< 5**222P: 5======< 5***26*)*(\P\:@e25*:*)4*,F >==============#========= P,F  Basically this program does some kind of base 26 thing on the chars. After that it checks if the hash is equal to 12999 (The hash code of YES) and if so print 404 (the hashcode of NO), else it will just print the hashcode. Conveyor is a language made by me that is currently in beta-stages but an interpreter along with some examples and source code can be found here: https://github.com/loovjo/Conveyor # C# 4.5 (112 bytes) int h(string s){int code=s.Select((v,i)=>((int)v)<<(2*(i-1))).Sum();return(code|1073742225)|(code|-2147483569);}  Working (?) version of undergroundmonorail's attempt, in C#. Concats the bytes in the string into a 32-bit integer (only works up to 4 characters), then ORs the result against the result for "YES" and "NO" respectively, then ORs those together. While it may collide at some point, it shouldn't happen for any ^[A-Z]{2,3}$ other than "YES" and "NO".

• You hash function will have many more collisions. Your "hash function" is essentially ignoring many bits in the concatenation. All string pairs which only differ in those bits will have the same hash code. – Paŭlo Ebermann Apr 26 '14 at 9:07

# No Comment - 31 (function content: 26)

'=|*==|,,|+|"#|[|,  |+|-%3|]*|:


Pretty simple solution. ;) Works for any and all UTF-8 strings.

EXPLANATION: ' is, obviously, the function. First, it checks whether * (it's input) is equal to |,,|+|"#| (|NO|). If it is, it returns |, |+|-%3| (|YES|) - otherwise, it just returns *.

• I've never worked with No Comment, would it be possible for you to explain your solution like is often done with opaque Golfscript, J, or APL answers? – Kaya Apr 25 '14 at 19:34
• @Kaya Oh, yes, sorry, I'll edit the post. – cjfaure Apr 25 '14 at 19:35
• No apologies necessary, I was just curious how it worked. – Kaya Apr 25 '14 at 19:45

C 54

h(char *c){int d=*(int*)c-20302;return d*(d-5436939);}


Convert string to integer -"NO" and multiply that by by same value + "NO"-"YES" to get 0 for "NO" and "YES" and non-zero for any other string in the range specified.

All values on Windows 7 machine if there are any endian concerns.

# Stax, 12 11 bytes

ì≤ïøZ‼kESa←


Run and debug it

Translates input as base-36, subtracts 852, then replaces 0 with 43744. It's a port of Konrad's excellent solution.

# CoffeeScript - 36

Should return 1 for YES and NO, and whatever garbled nonsense atob produces for everything else that's not a base64 string.

h=(s)->_=atob s;_ in["D","4"]&&1||_


The JavaScript equivalent (not the JS code from the CS compiler):

function h( s ) {
var _ = atob( s );

if( _ === "D" || _ === "4" )
return 1;
else
return _;
}

• "The function should have an integer return value" - I suppose yours returns the _ when the input is not "YES" or "NO". – Gaurang Tandon Apr 25 '14 at 5:03

Here's a super lame one. SO LAME IT DOESN'T EVEN WORK

# Python 2.7 - 79 bytes

def h(s):n=sum(100**i*ord(c)for i,c in enumerate(s));return (n-7978)*(n-836989)


First we get the sum of (each character's ascii value) * 100^(that character's position in the string). Then we multiply (that result - 7978) and (that result - 836989) to get our final answer. 7978 and 836989 are the results for "YES" and "NO" of the first bit, so for YES and NO we're multiplying by 0.

This shouldn't have any collisions? I don't feel like testing against 18000 possible counterexamples, but if there was an unintended collision I can throw another 0 on that 100 and then there really shouldn't be any collisions.

Disappointed that I couldn't use a lambda` for this, but I didn't want to do the whole calculation twice so I had to save it to a variable.

Please don't let this win. It's super lame and I don't deserve it.

• Doesn't meet the "no other collisions" requirement: There are only 18012 unique hashes out of the 18277-string set that shouldn't have collisions. – dan04 Apr 25 '14 at 2:41
• @dan Damn, give me a second – undergroundmonorail Apr 25 '14 at 2:43
• @dan I can't get it to work. Maybe there's something inherently wrong with the algorithm. I don't want to delete it because someone else might know what's wrong, but I'll put up a note – undergroundmonorail Apr 25 '14 at 2:54
• This works for me, h=lambda s:(hash(s)+997192582)*(hash(s)-480644903) – Lucas Apr 25 '14 at 4:10
• as did defining a hash function similar to yours but with 99**i*int(c,36) – Lucas Apr 25 '14 at 4:11