Hash collision: "NO" means "YES"

Question

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.

Answer 1

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!¹

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 installed².

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.

---

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

Answer 2

Perl, 53 49 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}$/
addcache '';
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 $".

Answer 3

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(26^{n − k} · a_k; k = 1 .. n), where n is the number of characters in the input and a_k 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.

Answer 4

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.

Answer 5

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
$

Answer 6

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)

Answer 7

Javascript (ES6) 54 bytes

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

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

Answer 8

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?

Answer 9

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

Answer 10

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.

Answer 11

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.

Answer 12

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

Answer 13

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;
  }
}

Answer 14

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

Answer 15

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".

Answer 16

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 *.

Answer 17

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.

Answer 18

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.

Answer 19

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 _;
}

Answer 20

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.