# Question
Title: We're Spiralling out of control, Doctor!
The Doctor, in trying to escape from the Dalek forces has decided to send them in a spin by traveling in various pockets of space in a spiral motion.

Depending on the nature of the available space-time, The Doctor needs to enter into the TARDIS controls the height and width of the section of space and his entry point with which to begin the spiral.

The section of space can be envisioned as a *h* x *w* grid filled with sequential integers from left to right, top to bottom, starting with 1.

The starting position is provided as *r c* for the row and column... From this the TARDIS's software needs to spit out the ordered list of integers obtained by spiraling outward in an anti-clockwise direction from row *r* column *c*, starting upwards...

Your task, as the Doctor's companion is to program the TARDIS to take four numbers, in the format `height width row column` and have it determine which sector of space the TARDIS needs to travel to match the spiral movement described below...

**Input 1**

```
5 5 3 3

```

(5 x 5 grid, starting at position 3,3)

**Output 1**

```
13 8 7 12 17 18 19 14 9 4 3 2 1 6 11 16 21 22 23 24 25 20 15 10 5

```

**Explaining output**

Original grid

Generated spiral

**Input 2**

```
2 4 1 2

```

(2 x 4 grid starting at position 1,2)

**Output 2**

```
2 1 5 6 7 3 8 4

```

**Explaining output**

Slightly different as spiral now must circle around grid to generate respective output...

Original grid

Generated spiral

Rules:

1. This is code-golf, so shortest code length gets the tick of approval.
2. The above examples must be used to test your code. If it doesn't provide the respective output, there's something wrong...
3. Both golfed and in-golfed versions of code must be provided in your answer...

Good luck!

# Answer
> 3 votes
# JavaScript (ES6) 124 ~~163 177~~

**Edit** Totally different way, no need of an array to store visited cells. Using the fact that the side of the spiral increase of 1 after every 2 turns.

```
// New way
f=(h,w,y,x)=>
  (e=>{
    for(o=[],d=i=t=l=0;l<w*h;i<t?i+=2:[i,d,e]=[1,-e,d,++t])
      o[l]=y*w-w+x,l+=x>0&x<=w&y>0&y<=h,x+=d,y-=e
  })(1)||o

// Golfed
g=(h,w,y,x)=>
  (g=>{
    for(e=n=0;n<h*w;)g[[n%w+1,-~(n/w)]]=++n;
    for(o=[g[[x,y]]],l=d=1;l<n;l+=!!(o[l]=g[[x+=d,y+=e]]))
      g[[x,y]]=0,
      g[[x+e,y-d]]!=0&&([d,e]=[e,-d])
  })([])||o

// Not golfed
u=(h,w,y,x)=>{
  var i,j,dx,dy,kx,ky,o,n,
    g={} // simulate a 2dimensional array using a hashtable with keys in the form 'x,y'

  for(n=i=0; i++<h;) // fill grid (probably better done in a single loop)
    for(j=0; j++<w;)
      g[[j,i]] = ++n;
  o=[g[[x,y]]] // starting point in output
  dx=1, dy=0 // start headed right

  for(; !o[w*h-1]; ) // loop until all w*h position are put in output
  {
    g[[x, y]] = 0 // mark current position to avoid reusing
    kx=dy, ky=-dx // try turning left
    if(g[[x+kx, y+ky]] != 0) // check if position marked
    { // found a valid position
      dx=kx, dy=ky // change direction
    }
    x+=dx, y+=dy // move
    k=g[[x, y]] // get current value
    if (k) o.push(k) // put in output list if not 'undefined' (outside grid)
  }
  return o
}

// TEST - In FireFox

out=x=>O.innerHTML+=x+'\n';
[
 [[5,5,3,3],'13 8 7 12 17 18 19 14 9 4 3 2 1 6 11 16 21 22 23 24 25 20 15 10 5'],
 [[2,4,1,2],'2 1 5 6 7 3 8 4']
].forEach(t=>out(t[0] + '\n Result: ' + f(...t[0])+'\n Check:  ' + t[1]))

test=()=>
{
  var r, i=I.value.match(/\d+/g), h=i[0]|0, w=i[1]|0, y=i[2]|0, x=i[3]|0
  if (y>h||x>w) r = 'Invalid input'
  else r = f(h,w,y,x)
  out(i+'\n Reault: ' +r)
}
```

```
<pre id=O></pre>
Your test:<input id=I><button onclick="test()">-></button>
```

# Answer
> 2 votes
# Python 3, 191

Probably not a great score, but here it goes:

```
def f(b,a,d,c):
 p,r,l,s,h=c+1j*d,-1j,1,0,0
 for _ in [0]*((a+b)**2):x,y=p.real,p.imag;0<x<a+1and 0<y<b+1and print(int((y-1)*a+x),end=' ');p+=r;s=(s+1)%l;t=s==0;h=(h+t)%2;l+=h<t;r*=(-1j)**t

```

We move along the spiral by increasing side-length after every second turns. If our position is inside the given grid we print its corresponding number.

Variables are:

* p is complex position
* x and y are position coordinates
* r is direction
* s is position on current side
* l is current side length
* h is the parity of the current side's ordinal

---
Tags: code-golf
---


title: Sorting for Bozos

text:
# Question
Title: Sorting for Bozos
**Introduction**

This challenge is about three (bad) sorting algorithms: `Bogosort`, and two others variants that I came up with (but have probably been thought of by others at some point in time): `Bogoswap` (AKA Bozosort) and `Bogosmart`.

`Bogosort` works by completely shuffling the array randomly and checking if it becomes sorted (ascending). If not, repeat.

`Bogoswap` works by selecting two elements, randomly, and swapping them. Repeat until sorted (ascending).

`Bogosmart` works by selecting two elements, randomly, and only swapping them if it makes the array closer to being sorted (ascending), ie. if the element with the lower index was originally larger than the one with the higher. Repeat until sorted.

**The Challenge**

This challenge explores the efficiency (or lack of) of each of these three sorting algorithms. The golfed code will

1. generate a shuffled 8 element array of the integers 1-8 inclusive (keep reading to see how you should do this);
2. apply each algorithm to this array; and
3. display the original array, followed by the number of computations required for each algorithm, separated by one space (trailing space ok), in the format `<ARRAY> <BOGOSORT> <BOGOSWAP> <BOGOSMART>`.

The program will produce 10 test cases; you can generate all ten at the beginning or generate one at a time, whatever. Sample output below.

**Details:**

For `Bogosort`, it should record the number of times the array was shuffled.

For `Bogoswap`, it should record the number of swaps made.

For `Bogosmart`, it should record the number of swaps made.

**Example output:**

```
87654321 1000000 100 1
37485612 9050000 9000 10
12345678 0 0 0
28746351 4344 5009 5
18437256 10000 523 25
15438762 10000 223 34
18763524 58924 23524 5
34652817 9283 21 445
78634512 5748 234 13
24567351 577 24 34

```

I made up these numbers; of course, your program will print different output but in the same format.

**Rules**

* All randomness used in your program must come from pseudorandom number generators available to you, and otherwise not computed extensively by you. You don't have to worry about seeds.
* There is no time limit on the programs.
* The arrays are to be sorted ascendingly.
* Trailing spaces or an extra newline is no big deal.
* For `Bogosort`, the array is to be shuffled using any unbiased shuffling algorithm such as Fisher-Yates or Knuth Shuffling, explicitly specified in your explanation. Built-in shuffling methods are not allowed. Generate your test arrays in the same manner.
* If after shuffling or swapping the array remains the same, it still counts and should be included in the program's count. For example, shuffling the array to itself by coincidence counts as a shuffle, and swapping an element with itself counts as a swap, even though none of these operations change the array.
* If my memory serves me correctly, an 8 element array shouldn't take too long for any of the three algorithms. In fact, I think a few times for a 10 element array, when I tried it, `Bogoswap` only required a few thousand (or less) actual shuffles and well under 10 seconds.
* Your code must actually sort the arrays, don't just give expected values or mathematical calculations for an expected answer.
* This is a code-golf challenge, so shortest program in bytes wins.

Here are some sample steps for each sorting algorithm:

```
BOGOSORT
56781234
37485612
28471653
46758123
46758123
12685734
27836451
12345678

BOGOSWAP
56781234
16785234
17685234
12685734
12685743
12685734
12485763
12385764
12385764
12345768
12345678

BOGOSMART
56781234
16785234
12785634
12785364
12785364
12385764
12385674
12345678

```

In this case, the program would output `56781234 7 10 7`, and then do the same thing 10 times. You do not have to print the arrays while sorting is going on, but I gave the above sample steps so you can understand how each algorithm works and how to count computations.

# Answer
> 3 votes
# Pyth, ~~62~~ 60 bytes

```
VTjd[jkKJ=boO0=ZS8fqZ=KoO0K0fqZ=XJO.CJ2)0fqZ=Xb*>F=NO.Cb2N)0

```

This was quite fun. Not sure if this is valid, I'm probably using some unwritten loopholes.

A sample output would be:

```
23187456 22604 23251 110
42561378 125642 115505 105
62715843 10448 35799 69
72645183 7554 53439 30
61357428 66265 6568 77
62348571 1997 105762 171
78345162 96931 88866 241
17385246 51703 7880 80
74136582 36925 19875 100
26381475 83126 2432 25

```

### Explanation:

My shuffle function uses the built-function `order-by`. Basically I assign each element of the list a random number of the interval `[0-1)` and sort the list by them. This gives me an unbiased random shuffle.

**Outer loop**

The `VT` at the start repeats the following code 10 times.

**Preparation**

```
jkKJ=boO0=ZS8
           S8        create the list [1, 2, 3, 4, 5, 6, 7, 8]
         =Z          and store in Z
      oO0            shuffle
    =b               and store in b
   J                 and store in J
  K                  and store in K (3 copies of the same shuffled array)
jkK                  join K with ""

```

**Bogosort**

```
fqZ=KoO0K0
     oO0K            shuffle K
   =K                and store the result in K
f        0           repeat ^ until:
 qZ K                  Z == K
                     and give the number of repeats

```

**Bogoswap**

```
fqZ=XJO.CJ2)0
       .CJ2          give all possible pairs of elements of J
      O              take a random one
    XJ     )         swap these two elements in J
   =                 and store the result in J
f           0        repeat ^ until:
 qZ K                  Z == K
                     and give the number of repeats

```

**Bogosmart**

```
fqZ=Xb*>F=NO.Cb2N)0
            .Cb2     give all possible pairs of elements of b
           O         take a random one
         =N          assign it to N
       >F N          check if N[0] > N[1]
      *         N    multiply the boolean with N
    Xb           )   swap the two (or zero) values in b
   =                 and assign to b
f                 0  repeat ^ until:
 qZ                    Z == b
                     and give the number of repeats

```

**Printing**

```
jd[
  [                  put all 4 values in a list
jd                    join by spaces and print

```

# Answer
> 2 votes
# JavaScript (*ES6*), 319 ~~345~~

Unsurprisingly this is quite long.

For Random shuffle, credits to @core1024 (better than mine for the same chellenge)

Test running the snippet (Firefox only as usual)

```
// FOR TEST : redefine console
var console = { log: (...p)=>O.innerHTML += p.join(' ')+'\n' }
// END

// Solution
R=n=>Math.random()*n|0,
S=a=>(a.map((c,i)=>(a[i]=a[j=R(++i)],a[j]=c)),a), // shuffle
T=f=>{for(a=[...z];a.join('')!=s;)f(a)}, // apply sort 'f'  algorithm until sorted

s='12345678';
for(i=0;i<10;i++)
  z=S([...s]),
  n=l=m=0,
  T(a=>S(a,++n)),
  T(a=>(t=a[k=R(8)],a[k]=a[j=R(8)],a[j]=t,++m)),
  T(a=>(t=a[k=R(8)],u=a[j=R(8)],(t<u?j<k:k<j)&&(a[k]=u,a[j]=t,++l))),
  console.log(z.join(''),n,m,l)
```

```
<pre id=O></pre>
```

---
Tags: code-golf, random, sorting
---


title: Cryptographic hash golf

text:
# Question
Title: Cryptographic hash golf
> **This contest is over.**
>
> Due to the nature of challenges, the cops challenge becomes a lot easier when the interest in the associated robbers challenge has diminished. Therefore, while you can still post hash functions, your answer will not get accepted or form part of the leaderboard.

This challenge is a search for the shortest implementation of a hash function that is collision resistant, i.e., it should be infeasible to find two different messages with the same hash.

As a cop, you try to invent and implement a hash function finding the best compromise between code size and collision resistance. Use too many bytes and another cop will outgolf you!

As a robber, you try to foil the cops' attempts by cracking their functions, proving that they are unsuitable. This will force them to use more bytes to strengthen their algorithms!

## Cops challenge

### Task

Implement a cryptographic hash function **H : I -\> O** of your choice, where **I** is the set of all non-negative integers below 2230 and **O** is the set of all non-negative integers below 2128.

You can either implement **H** as an actual function that accepts and returns a single integer, a string representation of an integer or an array of integers or a full program that reads from STDIN and prints to STDOUT in base 10 or 16.

### Scoring

* **H** that it has to resist the *robbers challenge* defined below.

If a robber defeats your submission in the first 168 hours after posting it, it is considered *cracked*.
* The implementation of **H** should be as short as possible. *The shortest uncracked submission will be the winner of the cops challenge.*

### Additional rules

* If you implement **H** as a function, please provide a wrapper to execute the function from within a program that behaves as explained above.
* Please provide at least three test vectors for your program or wrapper (example inputs and their corresponding outputs).
* **H** can be your novel design (preferred) or a well-known algorithm, as long as you implement it yourself. It is forbidden to use any kind in-built hash function, compression function, cipher, PRNG, etc.

Any built-in commonly used to *implement* hashing functions (e.g., base conversion) is fair game.
* The output of your program or function must be deterministic.
* There should be a free (as in beer) compiler/interpreter that can be run on a x86 or x64 platform or from within a web browser.
* Your program or function should be reasonably efficient and has to hash any message in **I** below 2219 in less than a second.

For edge cases, the (wall) time taken on my machine (Intel Core i7-3770, 16 GiB of RAM) will be decisive.
* Given the nature of this challenge, it is forbidden to change the code of your answer in any way, whether it alters the output or not.

If your submission has been cracked (or even if it hasn't), you can post an additional answer.

If your answer is invalid (e.g., it doesn't comply with the I/O specification), please delete it.

### Example

> # Python 2.7, 22 bytes
>
> ```
> def H(M):
>  return M%17
>
> ```
>
> ### Wrapper
>
> ```
> print H(int(input()))
>
> ```

## Robbers challenge

### Task

Crack any of the cops' submissions by posting the following in the robbers' thread: two messages **M** and **N** in **I** such that **H(M) = H(N)** and **M ≠ N**.

### Scoring

* Cracking each cop submissions gains you one point. The robber with the most points wins.

In the case of a tie, the tied robber that cracked the longest submission wins.

### Additional rules

* Every cop submission can only be cracked once.
* If a cop submission relies on implementation-defined or undefined behavior, you only have to find a crack that works (verifiably) on your machine.
* Each crack belongs to a separate answer in the robbers' thread.
* Posting an invalid cracking attempt bans you from cracking that particular submission for 30 minutes.
* You may not crack your own submission.

### Example

> # Python 2.7, 22 bytes by user8675309
>
> ```
> 1
>
> ```
>
> and
>
> ```
> 18
>
> ```

# Leaderboard

### Safe submissions

1. CJam, 21 bytes by eBusiness
2. C++, 148 bytes by tucuxi
3. C++, 233(?) bytes by Vi.

### Uncracked submissions

You can use this Stack Snippet to get a list of not yet cracked answers.

```
function g(p){$.getJSON('//api.stackexchange.com/2.2/questions/51068/answers?page='+p+'&pagesize=100&order=desc&sort=creation&site=codegolf&filter=!.Fjs-H6J36w0DtV5A_ZMzR7bRqt1e',function(s){s.items.map(function(a){var h=$('<div/>').html(a.body).children().first().text();if(!/cracked/i.test(h)&&(typeof a.comments=='undefined'||a.comments.filter(function(b){var c=$('<div/>').html(b.body);return /^cracked/i.test(c.text())||c.find('a').filter(function(){return /cracked/i.test($(this).text())}).length>0}).length==0)){var m=/^\s*((?:[^,(\s]|\s+[^-,(\s])+)\s*(?:[,(]|\s-).*?([0-9]+)/.exec(h);$('<tr/>').append($('<td/>').append($('<a/>').text(m?m[1]:h).attr('href',a.link)),$('<td class="score"/>').text(m?m[2]:'?'),$('<td/>').append($('<a/>').text(a.owner.display_name).attr('href',a.owner.link))).appendTo('#listcontent');}});if(s.length==100)g(p+1);});}g(1);
```

```
table th, table td {padding: 5px} th {text-align: left} .score {text-align: right} table a {display:block}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><table><tr><th>Language</th><th class="score">Length</th><th>User</th></tr><tbody id="listcontent"></tbody></table>
```

# Answer
> 6 votes
# CJam, 21 bytes

```
1q3*{i+_E_#*^26_#)%}/

```

Takes a string of bytes as input.

In pseudocode:

```
hash = 1
3 times:
    for i in input:
        hash = hash + i
        hash = hash xor hash * 14^14
        hash = hash mod (26^26 + 1)
output hash

```

Example hashes:

"" (empty string) -\> 1
"Test" -\> 2607833638733409808360080023081587841
"test" -\> 363640467424586895504738713637444713

It may be a bit on the simple side, the output range is only a little more than 122 bits, the triple iteration strengthening is already a bit broken as it does exactly the same thing every time, so input that hash to 1 in the first iteration will be a full break. But it is short, and there is no fun in being too safe.

# Answer
> 7 votes
# Python, 109 bytes \[cracked, and again\]

```
def f(n,h=42,m=2**128):
 while n:h+=n&~-m;n>>=128;h+=h<<10;h^=h>>6;h%=m
 h+=h<<3;h^=h>>11;h+=h<<15;return h%m

```

I tried implementing Jenkins' one-at-a-time function as-is, with the only difference being the seed and the number of bits.

Fun fact: Apparently Perl used the Jenkins' hash at some point.

## Wrapper

```
print(f(int(input())))

```

## Examples

```
>>> f(0)
12386682
>>> f(1)
13184902071
>>> f(2**128-1)
132946164914354994014709093274101144634
>>> f(2**128)
13002544814292
>>> f(2**128+1)
13337372262951
>>> f(2**(2**20))
290510273231835581372700072767153076167

```

# Answer
> 6 votes
# C++, 148 bytes

```
typedef __uint128_t U;U h(char*b,U n,U&o){U a=0x243f6a8885a308d,p=0x100000001b3;for(o=a;n--;)for(U i=27;--i;){o=(o<<i)|(o>>(128-i));o*=p;o^=b[n];}}

```

\__uint128\_t is a GCC extension, and works as expected. The hash is based on iterating FNV hash (I've borrowed their prime, although `a` is the first digits of Pi in hex) with a sha1-like rotation at the start of each iteration. Compiling with `-O3`, hashing a 10MB file takes under 2 seconds, so there is still margin for upping the iterations in the inner loop - but I'm feeling generous today.

De-uglified (changed variable names, added comments, whitespace and a pair of braces) for your cracking pleasure:

```
typedef __uint128_t U;
U h(char* input, U inputLength, U &output){
    U a=0x243f6a8885a308d,p=0x100000001b3;
    for(output=a;inputLength--;) {   // initialize output, consume input
        for(U i=27;--i;) {                          // evil inner loop
            output = (output<<i)|(output>>(128-i)); // variable roll
            output *= p;                            // FNV hash steps
            output ^= input[inputLength];
        }
    }
    // computed hash now available in output
}

```

Golfing suggestions are welcome (even if I don't get to improve the code based on them).

**edit:** fixed typos in de-uglified code (golfed version remains unchanged).

# Answer
> 5 votes
## C++, 182 characters (+ about 51 characters of boilerplate)

```
h=0xC0CC3051F486B191;j=0x9A318B5A176B8125;char q=0;for(int i=0;i<l;++i){char w=buf[i];h+=((w<<27)*257);j^=(h+0x5233);h+=0xAA02129953CC12C3*(j>>32);j^=(w+0x134)*(q-0x16C552F34);q=w;}

```

Boilerplate:

```
void hash(const unsigned char* buf, size_t len, unsigned long long *hash1, unsigned long long *hash2)
{
    unsigned long long &h=*hash1;
    unsigned long long &j=*hash2;
    size_t l = len;
    const unsigned char* b = buf;

    // code here
}

```

## Runnable program with a golfed function

```
#include <stdio.h>

// The next line is 227 characters long
int hash(char*b,int l,long long&h,long long&j){h=0xC0CC3051F486B191;j=0x9A318B5A176B8125;char q=0;for(int i=0;i<l;++i){char w=b[i];h+=((w<<27)*257);j^=(h+0x5233);h+=0xAA02129953CC12C3*(j>>32);j^=(w+0x134)*(q-0x16C552F34);q=w;}}

int main() {
    char buf[1024];
    int l  = fread(buf, 1, 1024, stdin);
    long long q, w;
    hash(buf, l, q, w);
    printf("%016llX%016llX\n", q, w);
}

```

# Answer
> 5 votes
# CJam, 44 bytes \[cracked\]

```
lW%600/_z]{JfbDbGK#%GC#[md\]}%z~Bb4G#%\+GC#b

```

Input is in base 10.

CJam is slow. I hope it runs in 1 second in some computer...

### Explanations

```
lW%600/            e# Reverse, and split into chunks with size 600.
_z                 e# Duplicate and swap the two dimensions.
]{                 e# For both versions or the array:
    JfbDb          e# Sum of S[i][j]*13^i*19^j, where S is the character values,
                   e# and the indices are from right to left, starting at 0.
    GK#%GC#[md\]   e# Get the last 32+48 bits.
}%
z~                 e# Say the results are A, B, C, D, where A and C are 32 bits.
Bb4G#%             e# E = the last 32 bits of A * 11 + C.
\+GC#b             e# Output E, B, D concatenated in binary.

```

Well, the two dimensional things seemed to be a weakness... It was intended to make some slow calculations faster at the beginning. But it cannot run in a second no matter what I do, so I removed the slow code finally.

It should be also better if I have used binary bits and higher bases.

## C version

```
__uint128_t hash(unsigned char* s){
    __uint128_t a=0,b=0;
    __uint128_t ar=0;
    __uint128_t v[600];
    int l=0,j=strlen(s);
    memset(v,0,sizeof v);
    for(int i=0;i<j;i++){
        if(i%600)
            ar*=19;
        else{
            a=(a+ar)*13;
            ar=0;
        }
        if(i%600>l)
            l=i%600;
        v[i%600]=v[i%600]*19+s[j-i-1];
        ar+=s[j-i-1];
    }
    for(int i=0;i<=l;i++)
        b=b*13+v[i];
    a+=ar;
    return (((a>>48)*11+(b>>48))<<96)
        +((a&0xffffffffffffull)<<48)
        +(b&0xffffffffffffull);
}

```

# Answer
> 4 votes
# Pyth, 8 Cracked

```
sv_`.lhQ

```

Try it online

A bit of a silly answer, I'll explain how it works because most people can't read Pyth. This takes the natural log of one plus the input, and then converts that to a string. That string is reversed, and then evaluated and then converted to an integer.

A python translation would look like:

```
import math
n = eval(input()) + 1
rev = str(math.log(n))[::-1]
print(int(eval(rev)))

```

# Answer
> 4 votes
# Python 3, 216 bytes \[cracked\]

```
def f(m):
 h=1;p=[2]+[n for n in range(2,102)if 2**n%n==2];l=len(bin(m))-2;*b,=map(int,bin((l<<(l+25)//26*26)+m)[2:])
 while b:
  h*=h
  for P in p:
   if b:h=h*P**b.pop()%0xb6ee45a9012d1718f626305a971e6a21
 return h

```

Due to an incompatibility with the spec I can think of at least one *slight* vulnerability, but other than that I think this is at least brute-force proof. I've checked the first 10 million hashes, among other things.

In terms of golf this would be shorter in Python 2, but I've sacrificed some bytes for efficiency (since it's probably not going to win anyway).

Edit: This was my attempt at implementing the Very Smooth Hash, but unfortunately 128-bits was far too small.

## Wrapper

```
print(f(int(input())))

```

## Examples

```
>>> f(0)
2
>>> f(123456789)
228513724611896947508835241717884330242
>>> f(2**(2**19)-1)
186113086034861070379984115740337348649
>>> f(2**(2**19))
1336078

```

## Code explanation

```
def f(m):
 h=1                                             # Start hash at 1
 p=[2]+[n for n in range(2,102)if 2**n%n==2]     # p = primes from 2 to 101
 l=len(bin(m))-2                                 # l = bit-length of m (input)
 *b,=map(int,bin((l<<(l+25)//26*26)+m)[2:])      # Convert bits to list, padding to
                                                 # a multiple of 26 then adding the
                                                 # bit-length at the front

 while b:                                        # For each round
  h*=h                                           # Square the hash
  for P in p:                                    # For each prime in 2 ... 101
   if b:h=(h*P**b.pop()                          # Multiply by prime^bit, popping
                                                 # the bit from the back of the list
           %0xb6ee45a9012d1718f626305a971e6a21)  # Take mod large number

 return h                                        # Return hash

```

An example of the padding for `f(6)`:

```
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0]

(len 3)(------------------ 23 zeroes for padding -------------------------)(input 6)
       (---------------------------- length 26 total ------------------------------)

```

# Answer
> 4 votes
# C, 87 bytes \[cracked\]

This is the complete program; no wrapper required. Accepts binary input via stdin, and outputs a hexadecimal hash to stdout.

```
c;p;q;main(){while((c=getchar())+1)p=p*'foo+'+q+c,q=q*'bar/'+p;printf("%08x%08x",p,q);}

```

This only calculates a 64-bit hash, so I'm taking a bit of a gamble here.

In case anyone's wondering, the two constants `'foo+'` and `'bar/'` are the prime numbers 1718578987 and 1650553391.

---

### Examples:

Ignores leading zeroes:

```
echo -ne '\x00\x00\x00\x00' |./hash
0000000000000000

```

Single-byte inputs:

```
echo -ne '\x01' |./hash
0000000100000001
echo -ne '\xff' |./hash
000000ff000000ff

```

Multi-byte inputs:

```
echo -ne '\x01\x01' |./hash
666f6f2dc8d0e15c
echo -ne 'Hello, World' |./hash
04f1a7412b17b86c

```

# Answer
> 3 votes
# J - 39 bytes - cracked

Function taking a string as input and returning an integer \< 2128. I am assuming we have to name our function to be valid, so drop another 3 chars from the count if we can submit anonymous functions.

```
H=:_8(".p:@+5,9:)a\(a=.(2^128x)&|@^/@)]

```

For those of you that don't read hieroglyphics, here's a rundown of what I'm doing.

* `a=.(2^128x)&|@^/@` This is a subroutine\* which takes an array of numbers, and then treats it as a power tower, where exponentiation is taken mod 2128. By "power tower", I mean if you gave it the input `3 4 5 6`, it would calculate `3 ^ (4 ^ (5 ^ 6))`.
* `(".p:@+5,9:)a` This function takes a string, converts it to the number *N*, and then calculates the (*n*+5)-th and (*n*+9)-th prime numbers, and then throws the `a` from before on it. That is, we find `p(n+5) ^ p(n+9)` mod 2128 where `p(k)` is the `k`-th prime.
* `H=:_8...\(a...)]` Perform the above function on 8-character subblocks of the input, and then `a` all the results together and call the resulting hash function `H`. I use 8 characters because J's "`k`-th prime" function fails when `p(k)` \> 231, i.e. `k=105097564` is the largest safe `k`.

Have some sample outputs. You can try this yourself online at tryj.tk, but I really recommend doing this at home by downloading the interpreter from Jsoftware.

```
   H=:_8(".p:@+5,9:)a\(a=.(2^128x)&|@^/@)]
   H '88'
278718804776827770823441490977679256075
   H '0'
201538126434611150798503956371773
   H '1'
139288917338851014461418017489467720433
   H '2'
286827977638262502014244740270529967555
   H '3'
295470173585320512295453937212042446551
   30$'0123456789'  NB. a 30 character string
012345678901234567890123456789
   H 30$'0123456789'
75387099856019963684383893584499026337
   H 80$'0123456789'
268423413606061336240992836334135810465

```

* Technically, it's not a function in and of itself, it attaches to other functions and acts on their output. But this is a semantic issue of J, not a conceptual difference: the program flow is as I described it above.

# Answer
> 2 votes
# Java, ~~299~~ ~~291~~ 282 bytes, cracked.

```
import java.math.*;class H{public static void main(String[]a){BigInteger i=new java.util.Scanner(System.in).nextBigInteger();System.out.print(BigInteger.valueOf(i.bitCount()*i.bitLength()+1).add(i.mod(BigInteger.valueOf(Long.MAX_VALUE))).modPow(i,BigInteger.valueOf(2).pow(128)));}}

```

Does some operations on BigIntegers, then takes the result modulo 2128.

# Answer
> 2 votes
# Python 3, 118 bytes \[cracked\]

```
def H(I):
    o=0;n=3;M=1<<128
    for c in I:i=ord(c);o=(o<<i^o^i^n^0x9bb90058bcf52d3276a7bf07bcb279b7)%M;n=n*n%M
    return o

```

Indentation is a single tab. Simple hash, haven't really tested it thoroughly yet.

Call as follows:

```
print(H("123456789"))

```

result: `73117705077050518159191803746489514685`

# Answer
> 2 votes
# C++, 239 bytes

My very first code golf! \[*Please be gentle*\]

```
#define r(a,b) ((a<<b)|(a>>(64-b)))
typedef uint64_t I;I f(I*q, I n, I&h){h=0;for(I i=n;--i;)h=r(h^(r(q[i]*0x87c37b91114253d5,31)*0x4cf5ad432745937f),31)*5+0x52dce729;h^=(h>>33)*0xff51afd7ed558ccd;h^=(h>>33)*0xc4ceb9fe1a85ec53;h^=(h>>33);}

```

Ungolfed version:

```
I f(I* q, I n, I& h) // input, length and output
{
    h = 0; // initialize hashes
    for (I i=n;--i;)
    {
        q[i] *= 0x87c37b91114253d5;
        q[i]  = rotl(q[i], 31);
        q[i] *= 0x4cf5ad432745937f;

        h ^= q[i]; // merge the block with hash

        h *= rotl(h, 31);
        h = h * 5 + 0x52dce729;
    }
    h ^= h>>33;
    h *= 0xff51afd7ed558ccd;
    h ^= h>>33;
    h *= 0xc4ceb9fe1a85ec53; // avalanche!
    h ^= h>>33;
}

```

Not the best hash, and definitely not the shortest code in existence. Accepting golfing tips and hoping to improve!

## Wrapper

Probably not the best in the world, but a wrapper nonetheless

```
I input[500];

int main()
{
    string s;
    getline(cin, s);
    memcpy(input, s.c_str(), s.length());
    I output;
    f(input, 500, output);
    cout << hex << output << endl;
}

```

# Answer
> 2 votes
# C, 128 bytes \[cracked\]

```
p;q;r;s;main(c){while((c=getchar())+1)p=p*'foo+'+s^c,q=q*'bar/'+p,r=r*'qux3'^q,s=s*'zipO'+p;printf("%08x%08x%08x%08x",p,q,r,s);}

```

This is more or less the same algorithm as my last effort (cracked by Vi.), but now has enough hamster wheels to generate proper 128-bit hashes.

The four prime constants in the code are as follows:

```
'foo+' = 1718578987
'bar/' = 1650553391
'qux3' = 1903523891
'zipO' = 2053730383

```

As before, this is a complete program with no need for a wrapper. The integer **I** is input via stdin as raw binary data (big-endian), and the hash **O** is printed in hex to stdout. Leading zeroes in **I** are ignored.

## Examples:

```
echo -ne '\x00' |./hash
00000000000000000000000000000000
echo -ne '\x00\x00' |./hash
00000000000000000000000000000000
echo -ne '\x01' |./hash
00000001000000010000000100000001
echo -ne 'A' |./hash
00000041000000410000004100000041
echo -ne '\x01\x01' |./hash
666f6f2dc8d0e15cb9a5996fe0d8df7c
echo -ne 'Hello, World' |./hash
da0ba2857116440a9bee5bb70d58cd6a

```

# Answer
> 2 votes
# C, 122 bytes \[cracked\]

```
long long x,y,p;main(c){for(c=9;c|p%97;c=getchar()+1)for(++p;c--;)x=x*'[3QQ'+p,y^=x^=y^=c*x;printf("%016llx%016llx",x,y);}

```

Nested loops, half-assed LCGs, and variable swapping. What's not to love?

Here's a ungolf'd version to play around with:

```
long long x,y,p;

int main(int c){
    // Start with a small number of iterations to
    //   get the state hashes good and mixed because initializing takes space
    // Then, until we reach the end of input (EOF+1 == 0)
    //   and a position that's a multiple of 97
    for (c=9;c|p%97;c=getchar()+1) {

        // For each input c(haracter) ASCII value, iterate down to zero
        for (++p;c--;) {

            // x will act like a LCG with a prime multiple
            //   partially affected by the current input position
            // The string '[3QQ' is the prime number 0x5B335151
            x=x*'[3QQ'+p;

            // Mix the result of x with the decrementing character
            y^=c*x;

            // Swap the x and y buffers
            y^=x^=y;
        }
    }

    // Full 128-bit output
    printf("%016llx%016llx",x,y);
    return 0;
}

```

This is a fully self-contains program that reads from STDIN and prints to STDOUT.

Example:

```
> echo -n "Hello world" | ./golfhash
b3faef341f70c5ad6eed4c33e1b55ca7

> echo -n "" | ./golfhash
69c761806803f70154a7f816eb3835fb

> echo -n "a" | ./golfhash
5f0e7e5303cfcc5ecb644cddc90547ed

> echo -n "c" | ./golfhash
e64e173ed4415f7dae81aae0137c47e5

```

In some simple benchmarks, it hashes around 3MB/s of text data. The hash speed depends on the input data itself, so that should probably be taken into consideration.

# Answer
> 1 votes
# **C, 134 bytes, Cracked**

This is complete C program.

```
long long i=0,a=0,e=1,v,r;main(){for(;i++<323228500;r=(e?(scanf("%c",&v),e=v>'/'&&v<':',v):(a=(a+1)*7)*(7+r)));printf("0x%llx\n", r);}

```

What it does: The idea is to take input as byte array and append pseudo random (but deterministic) bytes at the end to make the length equal to about 2230 (a bit more). The implementation reads input byte by byte and starts using pseudo random data when it finds the first character that isn't a digit.

As builtin PRNG isn't allowed I implemented it myself.

There is undefined/implementation defined behavior that makes the code shorter (the final value should be unsigned, and I should use different types for different values). And I couldn't use 128 bit values in C. Less obfuscated version:

```
long long i = 0, prand = 0, notEndOfInput = 1, in, hash;

main() {
    for (; i++ < 323228500;) {
        if (notEndOfInput) {
            scanf("%c", &in);
            notEndOfInput = in >= '0' && in <= '9';
            hash = in;
        } else {
            prand = (prand + 1)*7;
            hash = prand*(7 + hash);
        }
    }
    printf("0x%llx\n", hash);
}

```

# Answer
> 1 votes
# PHP 4.1, 66 bytes \[cracked\]

I'm just warming up.

I hope you find this insteresting.

```
<?for($l=strlen($b.=$a*1);$i<40;$o.=+$b[+$i]^"$a"/$a,$i++);echo$o;

```

I've tried it numbers as large as 999999999999999999999999999.
The output seemed to be within the 2128 range.

---

PHP 4.1 is required because of the `register_globals` directive.

It works by automatically creating local variables from the session, POST, GET, REQUEST and cookies.

It uses the key `a`. (E.G.: access over `http://localhost/file.php?a=<number>`).

If you want to test it with PHP 4.2 and newer, try this:

```
<?for($l=strlen($b.=$a=$_REQUEST['a']*1);$i<40;$o.=+$b[+$i]^"$a"/$a,$i++);echo$o;

```

This version only works with POST and GET.

---

Example output:

```
0 -> 0000000000000000000000000000000000000000
9 -> 8111111111111111111111111111111111111111
9999 -> 8888111111111111111111111111111111111111
1234567890 -> 0325476981111111111111111111111111111111
99999999999999999999999999999999999999999999999999999999999999999999999999999999 -> 0111191111111111111111111111111111111111

```

(I assure you that there are numbers that produce the same hash).

# Answer
> 1 votes
**Python 2.X - 139 bytes** \[\[Cracked\]\]

This is quite similar to all the other (LOOP,XOR,SHIFT,ADD) hashes out here. Come get your points robbers ;) I'll make a harder one after this one is solved.

```
M=2**128
def H(I):
 A=[1337,8917,14491,71917];O=M-I%M
 for z in range(73):
  O^=A[z%4]**(9+I%9);O>>=3;O+=9+I**(A[z%4]%A[O%4]);O%=M
 return O

```

Wrapper (expects one argument in base-16 also known as hexadecimal):

```
import sys
if __name__ == '__main__':
 print hex(H(long(sys.argv[1], 16)))[2:][:-1].upper()

```

# Answer
> 1 votes
**Python 2.7 - 161 bytes \[\[Cracked\]\]**

Well since I managed to change my first hash function into an useless version before posting it, I think I will post another version of a similar structure. This time I tested it against trivial collisions and I tested most of the possible input magnitudes for speed.

```
A=2**128;B=[3,5,7,11,13,17,19]
def H(i):
 o=i/A
 for r in range(9+B[i%7]):
  v=B[i%7];i=(i+o)/2;o=o>>v|o<<128-v;o+=(9+o%6)**B[r%6];o^=i%(B[r%6]*v);o%=A
 return o

```

Wrapper (not counted in the bytecount)

```
import sys
if __name__ == '__main__':
 arg = long(sys.argv[1].strip(), 16)
 print hex(H(arg))[2:][:-1].upper()

```

Run example (input is always a hexadecimal number):

```
$ python crypt2.py 1
3984F42BC8371703DB8614A78581A167
$ python crypt2.py 10
589F1156882C1EA197597C9BF95B9D78
$ python crypt2.py 100
335920C70837FAF2905657F85CBC6FEA
$ python crypt2.py 1000
B2686CA7CAD9FC323ABF9BD695E8B013
$ python crypt2.py 1000AAAA
8B8959B3DB0906CE440CD44CC62B52DB

```

# Answer
> 1 votes
# Ruby, 90 Bytes

```
def H(s);i=823542;s.each_byte{|x|i=(i*(x+1)+s.length).to_s.reverse.to_i%(2**128)};i;end

```

A highly random hash algorithm I made up without looking at any real hashes...no idea if it is good. it takes a string as input.

### Wrapper:

```
def buildString(i)
  if(i>255)
    buildString(i/256)+(i%256).chr
  else
    i.chr
  end
end
puts H buildString gets

```

# Answer
> 0 votes
# Mathematica, 89 bytes, cracked

```
Last@CellularAutomaton[(a=Mod)[#^2,256],{#~IntegerDigits~2,0},{#~a~99,128}]~FromDigits~2&

```

Not the shortest.

# Answer
> 0 votes
# PHP, 79 Bytes (cracked. With a comment):

```
echo (('.'.str_replace('.',M_E*$i,$i/pi()))*substr(pi(),2,$i%20))+deg2rad($i);

```

This does alot of scary things via type-conversions in php, which makes it hard to predict ;) (or at least I hope so). It's not the shortest or most unreadable answer, however.

To run it you can use PHP4 and register globals (with ?i=123) or use the commandline:

```
php -r "$i = 123.45; echo (('.'.str_replace('.',M_E*$i,$i/pi()))*substr(pi(),2,$i%20))+deg2rad($i);"

```

# Answer
> 0 votes
# C# - 393 bytes cracked

```
using System;class P{static void Main(string[]a){int l=a[0].Length;l=l%8==0?l/8:l/8+1;var b=new byte[l][];for(int i=0;i<l;i++){b[i]=new byte[8];};int j=l-1,k=7;for(int i=0;i<a[0].Length;i++){b[j][k]=Convert.ToByte(""+a[0][i],16);k--;if((i+1)%8==0){j--;k=7;}}var c=0xcbf29ce484222325;for(int i=0;i<l;i++){for(int o=0;o<8;o++){c^=b[i][o];c*=0x100000001b3;}}Console.WriteLine(c.ToString("X"));}}

```

Ungolfed:

```
using System;
class P
{
    static void Main(string[]a)
    {
      int l = a[0].Length;
      l = l % 8 == 0 ? l / 8 : l / 8 + 1;
      var b = new byte[l][];
      for (int i = 0; i < l; i++) { b[i] = new byte[8]; };
      int j = l-1, k = 7;
      for (int i = 0; i < a[0].Length; i++)
      {
        b[j][k] = Convert.ToByte(""+a[0][i], 16);
        k--;
        if((i+1) % 8 == 0)
        {
          j--;
          k = 7;
        }
      }
      var c = 0xcbf29ce484222325;
      for (int i = 0; i < l; i++)
      {
        for (int o = 0; o < 8; o++)
        {
          c ^= b[i][o];
          c *= 0x100000001b3;
        }
      }
      Console.WriteLine(c.ToString("X"));
    }
}

```

I have never touched cryptography or hashing in my life, so be gentle :)

It's a simple implementation of an FNV-1a hash with some array pivoting on the input. I am sure there is a better way of doing this but this is the best I could do.

It might use a bit of memory on long inputs.

# Answer
> 0 votes
# Python 2, 115 bytes \[Cracked already!\]

OK, here's my last effort. Only 115 bytes because the final newline isn't required.

```
h,m,s=1,0,raw_input()
for c in[9+int(s[x:x+197])for x in range(0,len(s),197)]:h+=pow(c,257,99**99+52)
print h%4**64

```

This is a complete program that inputs a decimal integer on stdin and prints a decimal hash value on stdout. Extra leading zeroes will result in different hash values, so I'll just assume that the input doesn't have any.

This works by stuffing 197-digit chunks of the input number through a modular exponentiation. Unlike some languages, the `int()` function always defaults to base 10, so `int('077')` is 77, not 63.

### Sample outputs:

```
$ python hash.py <<<"0"
340076608891873865874583117084537586383

$ python hash.py <<<"1"
113151740989667135385395820806955292270

$ python hash.py <<<"2"
306634563913148482696255393435459032089

$ python hash.py <<<"42"
321865481646913829448911631298776772679

$ time python hash.py <<<`python <<<"print 2**(2**19)"`
233526113491758434358093601138224122227

real    0m0.890s   <-- (Close, but fast enough)
user    0m0.860s
sys     0m0.027s

```

---
Tags: code-golf, cryptography, cops-and-robbers, hashing
---


title: Cryptographic hash golf (robbers)

text:
# Question
Title: Cryptographic hash golf (robbers)
> **This contest is over.**
>
> There are no remaining crackable answer in the cops challenge.

# Companion thread of Cryptographic hash golf

As a reminder, here are the rules for robbers from the main challenge:

> ### Task
>
> Crack any of the cops' submissions by posting the following in the robbers' thread: two messages **M** and **N** in **I** such that **H(M) = H(N)** and **M ≠ N**.
>
> ### Scoring
>
> Cracking each cop submissions gains you one point. The robber with the most points wins.
>
> In the case of a tie, the tied robber that cracked the longest submission wins.
>
> ### Additional rules
>
> * Every cop submission can only be cracked once.
> * If a cop submission relies on implementation-defined or undefined behavior, you only have to find a crack that works (verifiably) on your machine.
> * Each crack belongs to a separate answer in the robbers' thread.
> * Posting an invalid cracking attempt bans you from cracking that particular submission for 30 minutes.
> * You may not crack your own submission.
>
> ### Example
>
> > # Python 2.7, 22 bytes by user8675309
> >
> > ```
> > 1
> >
> > ```
> >
> > and
> >
> > ```
> > 18
> >
> > ```

### Leaderboard

1. eBusiness: 3 cracks, 393 bytes
2. Martin Büttner: 3 cracks, 299 bytes
3. jimmy23013: 3 cracks, 161 bytes
4. Sp3000: 3 cracks, 44 bytes
5. tucuxi: 2 cracks, 239 bytes
6. Vi.: 2 cracks, 87 bytes
7. feersum: 1 crack, 216 bytes
8. mathmandan: 1 crack, 139 bytes
9. squeamish ossifrage: 1 crack, 134 bytes

# Answer
# C, 122 bytes - by: Mr. Llama

```
bmaj8PCosFLAJjeHaevvvchnJedmg2iujpePOPivI2x2asw0yKa2eA15xvFJMFe82RGIcdlvxyaAPRuDuJhFjbh78BFsnCufJkarwEyKa0azHxccw5qegpcP9yaO0FKoohanxgiAfK1Lqwba51bKtjacbvdjMmcBkiv8kd62sBd98c4twa98sgj3iPh7nkP4
rlaejTPrua1DhBdg0jrIoDBi8fc1GIJAigivIGaxs1OmfPcctNadK3HErvzPLCeDPD8fkMNPCBcIwuoGfEHegOfk9k9pwktslqaBenaati1uNthMiyk9ndpy7gdIz88iot6A09cbNeIMheyjBvbeegL7aGp7mCb91hCxnvgV5abfImrPfLbrbraAsN6loJgh

```

Both strings hash to `bb66000000000000d698000000000000`

Just like "C, 128 bytes - by: squeamish ossifrage" the higher order bits never influence the lower order bits, this can be exploited.

### Code

Visual C++, uses "unsafe" string operations

```
#include "stdafx.h"
#include <string>
#include <iostream>
#include <fstream>

long long x, y;

//Original hash function (not used for cracking).
void h(char inp[]){
    long long c;
    int index = 0;
    int len = strlen(inp);
    x = 0;
    y = 0;
    long long p = 0;
    for (c = 9; c ; c = (index<len?inp[index++]:-1) + 1) {
        for (++p; c--;) {
            x = x*'[3QQ' + p;
            y ^= c*x;
            y ^= x ^= y;
        }
    }
    printf("%016llx%016llx\n", x, y);
}

//Partial hash, takes a string and a starting point in the stream.
//The byte 0x08 must be prepended to a string in order to produce a full legal hash.
void hp(char inp[],long long p){
    long long c;
    int index = 0;
    int len = strlen(inp);
    x = 0;
    y = 0;
    for (index = 0; index<len; index++) {
        c = inp[index] + 1;
        for (++p; c--;) {
            x = x*'[3QQ' + p;
            y ^= c*x;
            y ^= x ^= y;
        }
    }
}

//Reverse partial hash, backtracks the inner state.
void hprev(char inp[], long long p){
    long long c;
    long long clim;
    int index = 0;
    int len = strlen(inp);
    p += len + 1;
    x = 0;
    y = 0;
    for (index = len-1; index>=0; index--) {
        clim = inp[index] + 1;
        c = 0;
        for (--p; c<clim;c++) {
            y ^= x;
            x ^= y;
            y ^= c*x;
            x -= p;
            x = x * 17372755581419296689;
            //The multiplicative inverse of 1530089809 mod 2^64.
        }
    }
}
const int rows = 163840;
const int maprows = 524288;

//Store for intermediate input strings, row 0 contains 64 columns with 3-char strings,
//row 1 contain 32 columns with 6-char strings and so forth, the final strings will
//contain one string from each column, in order.
char store[7][rows][512];

//Storage for a hashmap, used for matching n strings with n string in O(n) time.
char map[maprows][512];

int _tmain(int argc, _TCHAR* argv[])
{
    char alpha[] = "abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    int row;
    int col;
    int layer;
    int a=0, b=0, c=0;
    int colzero;
    //Produce some starting strings.
    for (row = 0; row < rows; row++){
        //All column 0 strings begin with 0x08 in order to imitate the hash.
        store[0][row][0] = 8;
        colzero = 1;
        for (col = 0; col < 64; col++){
            store[0][row][col * 8 + colzero] = alpha[a];
            store[0][row][col * 8 + colzero + 1] = alpha[b];
            store[0][row][col * 8 + colzero + 2] = alpha[c];
            store[0][row][col * 8 + colzero + 3] = 0;
            colzero = 0;
        }
        a++;
        if (a >= 52){
            b++;
            a = 0;
            if (b >= 52){
                c++;
                b = 0;
            }
        }
    }
    //Layer for layer, column for column, build strings that preserve successively
    //more zero bits. Forward calculated partial hashes are matched with backwards
    //calculated partial hashes.
    for (layer = 1; layer < 7; layer++){
        int slayer = layer - 1;
        int swidth = 1 << (slayer + 3);
        int width = 1 << (layer + 3);
        int slen = 3 << slayer;
        int len = 3 << layer;
        int colnum;
        int layershift=slayer*8;
        for (col = 0,colnum=0; col < 512; col+=width,colnum++){
            printf("Layer: %i, column: %i\n",layer,colnum);
            memset(map, 0, sizeof map);
            int col2 = col + swidth;
            for (row = 0; row < rows; row++){
                hprev(store[slayer][row] + col2, 1 + slen*(1 + colnum * 2));
                x = (x >> layershift) & 255;
                y = (y >> layershift) & 255;
                int index = (x << 3) | (y << 11);
                for (a = 0; a < 8; a++){
                    if (map[index + a][0] == 0){
                        strcpy_s(map[index + a], store[slayer][row] + col2);
                        break;
                    }
                }
            }
            int destrow = 0;
            for (row = 0; row < rows && destrow < rows; row++){
                hp(store[slayer][row] + col, !!colnum + slen*(colnum * 2));
                x = (x >> layershift) & 255;
                y = (y >> layershift) & 255;
                int index = (x << 3) | (y << 11);
                for (a = 0; a < 8 && destrow < rows; a++){
                    if (map[index + a][0]){
                        strcpy(store[layer][destrow] + col, store[slayer][row] + col);
                        strcat(store[layer][destrow] + col, map[index + a]);
                        destrow++;
                    }
                }
            }
        }
    }
    memset(map, 0, sizeof map);
    char temp[1000];
    std::ofstream myfile;
    myfile.open("hashout.txt");
    for (row = 0; row < rows; row++){
        hp(store[6][row], 0);
        sprintf(temp, "%016llx%016llx", x, y);
        myfile << store[6][row] <<" " << temp << "\n";
    }
    myfile << "\n";
    //The final hash set has 96 of 128 output bits set to 0, I could have gone all
    //the way, but this is enough to find a collision via the birthday paradox.
    for (row = 0; row < rows; row++){
        hp(store[6][row], 0);
        long long xc = x;
        long long yc = y;
        int pos = (xc >> 45 | ((yc >> 48) & 7)) & (maprows-1);
        while (map[pos][0]!=0){
            hp(map[pos], 0);
            if (x == xc && y == yc){
                myfile << store[6][row] << "\n" << map[pos] << "\n";
                sprintf(temp,"%016llx%016llx", x, y);
                myfile << temp << "\n\n";
            }
            pos = (pos + 1) % maprows;
        }
        strcpy_s(map[pos], store[6][row]);
    }
    myfile.close();
    printf("done");
    getchar();
    return 0;
}

```
> 5 votes

# Answer
# Python, 109 bytes by Sp3000

Note that Martin cracked first, so I'm not sure if this deserves points. On the other hand, I did make a preimage attack rather than a simple collision - a much stronger result. This means that you can give it an arbitrary hash value, and it will construct an input that generates that hash value.

```
M = 2**128

# The hash to crack.
def jenkins(n):
    h = 42
    while n:
        h += n & (M - 1)
        n >>= 128
        h *= 1025
        h ^= h >> 6
        h %= M

    h *= 9
    h ^= h >> 11
    h *= 32769

    return h % M

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def invxorshift(h, s):
    r = h >> s
    while r:
        h ^= r
        r >>= s
    return h

def moddiv(a, b):
    return (a * modinv(b, M)) % M

def jenkins_crack(h):
    h = moddiv(h, 32769)
    h = invxorshift(h, 11)
    h = moddiv(h, 9)
    h = invxorshift(h, 6)
    h = moddiv(h, 1025)
    h -= 42
    return h

```

And to show that it works:

```
>>> from crack import *
>>> n = 2**128 + 1337
>>> h = jenkins(n)
>>> n2 = jenkins_crack(h)
>>> h2 = jenkins(n2)
>>> n != n2
True
>>> h == h2
True

```

And to give a particular set of numbers that collide:

```
N: 2**128
M: 43617

```
> 13 votes

# Answer
# Python, 109 bytes by Sp3000

```
340282366920938463463374607431768211414

```

and

```
113982837842983129870077688367927159293402923522160868689804433865221255200726

```

both yield

```
132946164914354994014709093261515948032

```

The algorithm splits the input into chunks of 128 bits, and repeatedly modifies the hash (seeded to `42`) with each chunk, before doing some extra hashing at the end. To find a collision, our goal is to find two numbers that yield the same result after running the following pseudo code on each chunk:

```
hash += chunk
hash += (hash << 10)
hash ^= (hash >> 6)
hash %= 2**128

```

Since the hash is taken mod 2128 we want to look for numbers that shift all the interesting stuff outside of this bit range. But the hash is seeded to `42` so it has some not-so-significant bits set to begin with:

```
000000000000000000000000 ... 000000000000000000101010

```

My idea was to get rid of those bits when adding the first chunk. So let's try 2128-42:

```
           000000000000000000000000 ... 000000000000000000101010     hash = 42
           111111111111111111111111 ... 111111111111111111010110     chunk = 2**128 - 42
          1000000000000000000000000 ... 000000000000000000000000     hash += chunk
10000000001000000000000000000000000 ... 000000000000000000000000     hash += hash << 10
10000010001000001000000000000000000 ... 000000000000000000000000     hash ^= hash >> 6
           000001000000000000000000 ... 000000000000000000000000     hash %= 2**128

```

That's fairly simple so let's try to use that as one of the two numbers. (Indeed, the first number of the collision I used is 2128-42.

Now how do we find another number with the same result? Well after one iteration the hash isn't `42` any more, but `2**122` as we've just shown. Now by adding a second chunk to our input number, we can run another iteration. We can choose the second chunk by the same argument as this one, i.e. we want 2128-2122. Then the intermediate result after `hash += chunk` will be identical and we end up with the same result at the end.

So we can compute the two numbers of the collision:

```
>>> 2**128-42
340282366920938463463374607431768211414L
>>> 2**128-42 + ((2**128-2**122)<<128)
113982837842983129870077688367927159293402923522160868689804433865221255200726L

```

We can easily generate many more collisions like this.
> 9 votes

# Answer
# Mathematica, 89 bytes by LegionMammal978

```
0

```

and

```
16

```

Both yield `0`.

The principle of this cop is to evolve a "random" binary 1-D cellular automaton from a "random" initial condition for a "random" number of steps, and then interpret the first 128 cells of the result as an integer.

The problem is that the rule is determined simply by `Mod[#^2,256]`, such that any multiple of 16 gives rule `0`, which is the trivial rule where all cells are always zero. If the input is not divisible by 99 then we will evolve at least 1 step, so the output is always zero. So any two multiples that aren't multiples of 99 definitely collide. However, input `0` *also* gives 0 (despite never using the rule), because the initial condition is just the binary representation of the input (which is all zeroes in this case).

As an aside, we can find other collisions that are completely independent of the rule. As noted above, any multiple of 99 means that the cellular automaton isn't evolved at all, so the result is simply the first (most significant) 128 bits of the initial condition... which is itself just the input number. So if we take two multiples that don't differ in the first 128 bits (padded to the right with zeroes), we also get a collision. The simplest example of this is `M = 99`, `N = 99*2 = 198`.
> 8 votes

# Answer
# J, 39 bytes

The first number is:

```
10000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000

```

That is, `10000000` repeated 64 times. The second number is that plus one, i.e.

```
10000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000001

```

Both yield

```
322124197561777885386414076216564234267

```

## Explanation

Let's start with `x := H 10000000 = 146018215378200688979555343618839610915`, and `y := 2^128`. Rather than finding `a, b` such that `a == b mod y`, we'll look for `a, b` such that `x^a == x^b mod y`, making use of the power towers in the algorithm.

But there must be some `k` such that `x^k == 1 mod y`, since `x, y` are coprime, and for that `k` we must have `a == b mod k`. So we can find the discrete logarithm of 1 mod `y`, and for the first step we get

```
x ^ (k = 85070591730234615865843651857942052864) == 1 mod 2^128

```

So now we want to find two numbers `a, b` such that `a == b mod k`. To do this, we set `y` to be `k` and try to find `a, b` such that `x^a == x^b mod y` again. Using the same logic, we take the discrete logarithm again and get

```
x ^ (k = 21267647932558653966460912964485513216) == 1 mod 85070591730234615865843651857942052864

```

We repeat this until we get to a small `y`, at which point it is trivial to find two numbers which hash to the same thing modulo `y`. After 63 iterations `y = 4`, at which point basically any two numbers work.

Here's the Mathematica code to generate the discrete log chain:

```
k = 0; x = 146018215378200688979555343618839610915; y = 2^128; While[y > 10, y = MultiplicativeOrder[x, y]; k++; Print[k, " ", y]];

```

This gives the following output.
> 8 votes

# Answer
## Pyth, 8 bytes by FryAmTheEggman

```
99999999999999999999999999

```

and

```
99999999999999999999999998

```

Floating point precision isn't big enough for this.
> 7 votes

# Answer
# CJam, 44 bytes, ~~user~~ jimmy23013

The numbers are too big to post, so here they are on Pastebin: num 1, num 2.

The first number is `600^2 = 360000` ones. The second number is the same, except for the following changes:

```
Positions to change to "2": 605, 1811, 3001, 6603
Positions to change to "4": 1805, 3003, 57348, 208895
Positions to change to "5": 602, 1201, 2405, 3004
Positions to change to "6": 1203, 1802
Positions to change to "7": 12, 609, 5401, 7200
Positions to change to "8": 1, 2, 4, 6, 600, 1200, 1808, 2400, 3600, 4803

```

Both hash to `271088937720654725553339294593617693056`.

## Explanation

Let's take a look at the first half of the code:

```
lW%                e#  Read input number as string, and reverse
600/               e#  Split every 600 digits, forming a 2D array
_z                 e#  Duplicate and zip, swapping rows and columns
{           }%     e#  For both arrays...
 JfbDb             e#  Find sum of S[i][j]*13^i*19^j, where S are the character values
                   e#  and the indices are from right to left, starting at 0.
      GK#          e#  Take modulo 16^20

         ...  ...  e#  (Rest of code irrelevant)

```

So if we can find two input numbers so that the sums of `S[i][j]*13^i*19^j` are the same modulo `16^20` for both the initial 600-wide array and the zipped array, then we're done.

To make things a little easier, we'll consider only `600^2 = 360000`-digit input numbers, so that the 600-wide array is just a 600 by 600 square of digits. This makes things easier to visualise, and is valid since `10^360000 ~ 2^(2^20.19) < 2^(2^30)`. To simplify things even further, we'll only consider such input strings whose digit square is symmetric along the main diagonal, so that the original array and the zipped array are the same. This also allows us to ignore the initial string reversal and the right-to-left index numbering, which cancel each other out.

To start us off, we can take the first number to be `360000` ones. To get the second number, we want to modify this by changing some of the digits so that the sums are the same modulo `16^20`, while preserving the digit square's symmetry. We accomplish this by finding a list of triples `(i, j, k)` so that

```
sum of k*(13^i 19^j + 19^i 13^j) == 0 mod 16^20

```

where `1 <= k <= 8` is the amount to increase the digit 1 by (i.e. changing to a digit from 2 to 9 – we could have included 0 but we didn't need it) and `0 <= i < j < 600` are index pairs.

Once we have the `(i, j, k)` triplets, we change the digits at `(i, j)` and `(j, i)` to `1+k` to get the second number. The triplets were found using a greedy backtracking algorithm, and for the second number above the digit square looks like:

```
188181811111711 ...
815112111711111 ...
851611111111111 ...
116114118112111 ...
811115111111111 ...
121451111111111 ...
811111111111111 ...
111111111111111 ...
111811111111111 ...
171111111111111 ...
111111111111111 ...
111211111111111 ...
711111111111111 ...
111111111111111 ...
111111111111111 ...

............... .
...............  .
...............   .

```

For example, `(i, j, k) = (0, 1, 7)` corresponds to changing the digits `(0, 1)` (position `600*0 + 1 = 1`) and `(1, 0)` (position `600*1 + 0 = 600`) to `1 + 7 = 8`.

---

Here's the backtracker in Python 3, although closer inspection revealed that we were pretty lucky, as no backtracking actually happened:

```
n = 16**20
L = [(k *(pow(13,i,n)*pow(19,j,n) + pow(19,i,n)*pow(13,j,n)) % n, i, j, k)
     for i in range(600) for j in range(600) for k in range(1, 9) if i < j]

L.sort(reverse=True)
stack = [(n, 0, [])]

while stack:
    k, index, result = stack.pop()

    if k == 0:
        print(result)
        break

    if index == len(L):
        continue

    stack.append((k, index+1, result)) # Don't include triplet

    if L[index][0] <= k:
        stack.append((k - L[index][0], index+1, result + [L[index][1:]])) # Include

```

For a bonus, here's a not-so-efficient port of the hash in Python 3. It was useless.
> 6 votes

# Answer
# PHP 4.1, 66 bytes by Ismael Miguel

```
$ A=0111129112911291111111111111111111111111 php hash.php 2> /dev/null ; echo
0100038003800381129111111111111111111111
$ A=0111129112911291129111111111111111111111 php hash.php 2> /dev/null ; echo
0100038003800381129111111111111111111111
$ cat hash.php
<? $a = getenv("A"); for($l=strlen($b.=$a*1);$i<40;$o.=+$b[+$i]^"$a"/$a,$i++);echo$o;

```

Found using simple iterated hashing, starting from 1:

```
$ i=1; while true; do i=$(A=$i php hash.php  2> /dev/null); echo $i; done | head -n 10
0111111111111111111111111111111111111111
0100000000000001129111111111111111111111
0111129111111111111111111111111111111111
0100038000000001129111111111111111111111
0111129112911111111111111111111111111111
0100038003800001129111111111111111111111
0111129112911291111111111111111111111111
0100038003800381129111111111111111111111
0111129112911291129111111111111111111111
0100038003800381129111111111111111111111

```
> 5 votes

# Answer
# Python 3 (216) by Sp3000

My messages are

```
5012053369354645637214643587103597313576086380250249302980438772005248488380915054746146050001036696049972235875591571028140916001206596142280971107479334216535925703480968283657357930602076844092875640359192729378384507238123245417656548512647301639542279794868512420586823155070914644206130805893968511673770843170450832829657206145931885656157628306896903719624729809643572222159364893644113710867223921580178741177106141068298067479650611992859787419779579962211254029169589775046869542029842374359998053713002047081002506346875804341770199884355810931652447801492691887376948615365487982834690942054717077615539311699691010938426302886867891090301248321702485904291177813145565144089044261424329155436660979948932491709511914065619715728353376578192548334780893602675684085757434059540582004872746967999949306946618036846307799677491651967418565531672392468089533111553281620101129322575737949904022139471688252420467041529301533363008476437812216585923822571793353317799365005036029476865
5012053369354645637214643587103103086948976188724715498910865650846170784131001427390927276355140411160919276493388206817700368694224128444524223814513348177926532982330730066315320819293979046126543806115318009892783577432467861426768883700930779409885418980853424256180864755881414774514084197887594253752179391098292488771920695965135791582218083012144604515253506370334133858904659263953147111654656123599460222236152128559750436960308887683690915261431659087040402402092795259541564130228515353133867041828417398395559815392177084002004583988047406317670433664624642858480970640416500369367395538257341309676777745698712896295462462064271676447460293684100001583256400774270688958051470568447233589146620275159126426142305307007744396679875427883384557759778766330566230012377845843842097372663092379922300568052486301863154557664156185573021849420011058607321977550938866119133331529852821217331665195832442542012455132139770813510559894254061471149750738447764616026512400623344132554752

```

I used this Python 2 code to generate them:

```
a,b = 14460445391122031029,16815296360833931837 #http://www.numberempire.com/numberfactorizer.php
pr = ~-a * ~-b

m0 = reduce(long.__or__, [long(b) << 26*i for i,b in enumerate(bin(pr)[2:])])
m1 = 1 << 26*i-1
m0 |= m1

#print m0, m1
print f(m0), f(m1)

```

The big modulus was a product of two primes `a` and `b`. I guess the hope was that it would be NP-impossible for us to factor the semiprime, but I guess 128 bits is too small as some webpage gave me the answer right away.

The multiplicative group modulo `ab` will have order *(a - 1)(b - 1)* which means if we raise any number to that power it will have to result in 0 or (usually) 1. So I put 1 bits in places that resulted in *2(a-1)(b-1)* being multiplied into the hash. Then the other message is basically 0, but I set one other bit in each number to make the lengths the same.

I think it would have been more annoying were the hash squared on every bit, rather than only after using all the primes. Then it wouldn't have been so simple to build arbitrary exponents for them.
> 5 votes

# Answer
# C, 128 bytes - by: squeamish ossifrage

The following two strings both hash to all zeroes:

```
dddl|lddH4|@dhxdxXdh0TXPdhhdx(dTxtlpdd@4Lhd|hdDpdhDdXLdXP4(PdddL|ldXdD(lddX4|0hddp4|ddP4Lxdp0dP@dhpTxPdhXdXxdhHDxHdllLttdhPT8pd(pT8Pdd0TL8dlLLTtddPtl8dP@DPPdhhDxhd804(pdh0Txpd@DDpLdhL4xtdXXdHXdd04lXht40dlddh4|@ddPTLXdhhDXHhtPH40dh0t8pd(pt80dhPtX0dhLtXtdhLT8thlLplTdhpt80dh0txpdhHDX(hdX8txdhhdxHdp|d@tdhlTx4dlptdxdh0T8PdT@t|Hdd@tL(ht(8DhdhHD8(hpHHP8dhLtXtdX8dhxdhpt8Pd@(D@Hdd@tLhdtxTLPdd0tlxhhL8X|dd8t|0dT04|Xddxt|phxxxhhdhpt8PhhxX8hdhlTX4dd4l||dd@TLHdXlTHtdhHd8hdX0THPdh(D8(d8xdh8dhp4xPd0HDp(dhl4xTdxlthtdhlTx4d8lT(TdhhdXHdphdP(dhp4x0d0Xd0XddTl||d88DH8dhhdxhdx|tHDdhLT8Thll0lTddPTlXdxXd(xdd0Tlxdhp480dhp4x0dd|LltdhPt80dtll|dddPTlXdxXd(xdd0Tlxdhp480dhp4x0dd|LltdhPt80dtll|dddP4Lxd|ptT8dhddxldH|4xDdhp4x0dDdl|LdhtD8|hhHx88ddpTL8hhphx@dhtd8|dphDP(dh0tx0hhDHx4dhpt8Pd@(D@HddLLLDhh|xxldhl4xTdhL4x4dhPt8Pd(HDx(dh(D8Hd4PT|8ddH4|@hh4H8ddhxd8XdDP4lxdhHd8hdl04d8ddXT|phdh8Thdd@TlHdhXdxxdllL44dD@4lHdhxdxXhd8XtxddLlLddT@T|(dhxdXXd|P44Xdhpt8pdlHDT0dhL4Xtd@ldpDdddl|LdXP4h0dhltXtdX8d(Xdh|tXdhhLXX|dhxd8XdP@D0PdhXDxXhtpHtPdd84|pddtl||dh(dx(d88Dh8ddx4|PhtT0DLdd@tL(hdX8Txdhp480d08d08dlll44d4dLLldhTdX|hh8Xxhdh048pd08d08ddPtL8d4H4l@dhhdxHd|pt4Xddp4lXhp(hPxdh|48DdxhDh(ddLlldd8XdH8dddl|LdLHDT0dhpt8pdlHDT0dh(d8hdTHtl@ddptl8dt84LPdh8dxxdlptD8dd04lxhhH8XxddDl|ldP|D@4ddTl||d|ptT8dh(dXhhd8X48dhPtXpd(8DxXdh@TX@dDP4L8dhpTX0d4@4|hdhHdxHdX8DHxdhPT8PhllplTdh0TXPhlXHLXddp4lXhtHXD(dhP4X0htH8dhdhLTx4hpxHPHdhhd8(dX8DHxdhpt80hhdHxTdlll44d@Hd@(dhhDxhdh0t8Pddh4|@ddh4|@dhptx0dpPD0@ddPtlxdhPT8pdhhdX(htTpDLdd@4L(dLHDtpdhxd8xdt84lPdlpTdxdDPTLXddLLLDdxlThtdlhd4PdXLTh4ddptLxd|@44(dhhd8HdtDLLlddxt|pd|hDd0ddPtLXhl@H|pdhDD8ld8dDhLdhXDXxdDxT|PdhHD8hdp8dpxdhp480d@XD@xddpTLXdHhD8(ddllLDdD|LL4dhpt80d@LdPDdh|4xDdP8dpXddLllddl8d4@dhptXpdd(4|@dhltx4d0Dd@LdhptxphdPHdpdhl4xTdxlthtdhHD8HdTdllldhLtX4dXP4(PdhLTxTd4X4LpddlllDdlpTD8dllltTdL(dtPdhDDxLdhLTx4dhptx0d|0T4Xdhl4xTdHL4XtdhpTXpdLp4dxddHt|@dHL484dhHDXHdHLtxtdhDdXldxL4H4dh|TxDhh8xX(dhLt8td8Lt(TdhHDx(d4DlLlddXT|PdHHD8(dlll44dlP4dxdd@tL(dL@4dhdd0tLxd4X4l0dhhdxhdDlLldddLLlddD04l8ddPtlxd(hd8hdd(T|@hdDp4|ddP4Lxdp0dP@dhptXpd(p4X0dhhd8(d8pT(0dh8d8Xhd(XT(dhddxLd@XD@8dd@tlhd@ld0ddhTD8|hhPH8@ddtl||dH0Tx0ddLlLddhp480dhHdxhd4lL|DdhXD8xdhhDX(dh048pd4Ll|ddddl|LdXP4h0dlll4thhdhxtddP4LXdhXdxXdhpTX0hdXXtxddlLLddx0Th0ddTl||hlhhlHdd|Ll4dHDdXldhhDX(hpxh0HdhDDXLdXDDhLdlhDTpht8Xdxdhpt8phhHXX8dd(t|@dHl4xtddp4LXhxhXH8dhDDxldDXt|PdhTDX|d|0ttxdhdDXLdDLLLddd84|PdT84LpdlhDTphl8hlxdhXD8xdHpt8Pdlhd40ddHT|@dhxdX8dhlT84dh|T8dhlXHLxdhxDxXdT4lL|dlllttd@xd@xdhhDXHhtXXD8dh(d8(d4p4|8dd04lxdxPThpdhHD8Hhdhx4hdhl4xthl|pLDdhltX4dhP4XPdd0Tlxdl@tDhddP4lXd0xD0xdhHD8Hd@8D@xdh0T8Pd0XDpxddPtl8dP@DPPdhhDxhd804(pdd04L8hpxHphdhDdxLdppD0@dd@tl(d88dHXdh0txpdXhDhHdd@Tlhdx8DHXdh0tXPdxxdH8dhPT8Pd484LPdlhD4pdxxdHxdd|Lltdhptx0dhlTx4hp8HPhdhPt8pdt4lL|ddtl||dH0Tx0dhxd8xhl@H|pddLllDhldP||dhdD8ldXLTHTdlhDTpddllLddd04lxhhH8Xxdh|48DdP8d0XddLLldd|@44hdhhd8hd4x4L0dhltXthh4H8Ddh4DX|dD@Tlhdh0tXpd8|T(ddhtDX|dlhdTPdd@tLhdThTl@dh8D8xdT(TL@dd@Tl(d8Hd(hdhXdxxhtHXdhdd0tl8d|HDDPdd8T|PdH04xPdd@Tl(d|@4t(dd(4|@dHp4xpdhpt80dh0txpdhp48phdXxTxdhhDXHhtPH40dh0t8pd(pt80dd8T|pdlxdt@dhp48PdD0TLXdh0t8Pd|lldTdh|t8DhphHp8

ddTl||d4|L|4dhptX0d4dllLddxT|pdxXdH8dlhDtPhlpH|@dd|Lltdhptx0dhlTx4hp8HPhdhPt8pdt4lL|ddtl||dH0Tx0ddLLLDd8tdH|dhDD8LdtxtLpdhxD8Xhd8xtxdhPt8Pd(8DX8dhddxLd0xd08dd0Tlxdxdd(Lddh4|@dXpt(Pdh048pd0xd0xdhhDX(d8p4Hpdh0480d(8DX8dhL4x4d4PT|XddPTLXdPDd@Ldddl|ld(P4X0ddDL|lht88DXdhPtxpd((Dx(dh0tx0dxXd(8dhpT8Pd0xD0XdlhD4pdT0T|8dh04XPht0H40dlhDtpdpHDP(dhlTXtdPHdpHdhXDxXhpPH0pddDl|lhltp|Ldh04x0dtXTL0ddLLLDdLhdtpdhL4xtdHDdXLddxt|0d4X4l0dh(Dxhdx04h0ddllLDd0PD0@dhXDxxhdx848dhDDxldpXDpXdhPt8pdhltxTdd04lxhhH8Xxdh|48DdP8d0XddLLldd|@44hdhhd8hd4x4L0dhltXthh4H8Ddh4DX|dD@Tlhdh0tXpd8|T(ddhtDX|dlhdTPdhlTXtdTX4L0dd@Tlhhh8xXHdhPt80d|XdD@dhp4xphd4Ptldd|LL4dL|ltDdhPTx0d80T(pdhpt8pd|pTtXdhpTX0hhth8Ddhxd8xdphdP(dh8D88dp(DPhdhHD8(htxXdXdh8dXXdXpTH0ddx4|PdpXDPxdhXDXXdxxdhXdhlt8Td@xD@8dhP4XPdhltX4dd@tlHdhXDxxdhPtXPd(8Dxxdh0t8PhdpHd0dh(D8HdX(D(Hdd@tLhht|@4Tdd@4lHdttll|dd0tlXhh|xxldd@TLHdlHdTPdd|LL4dt@T|hddx4|PdlHdtPddTl||d88DH8dlhdTpd40t|xddht|@dpPDP@dhHDxHhxthHDdhddxldxtDH|dhltx4d8Dd(ldd|LLthp0H0Pdhl4x4d|0T4Xdd|ll4dt8tLPdd@4lhd|0TTXddPtLXd(8d8xdhPTxPdHxd8xdhHDX(ddLllddhp48Pd0@d0PdhptxpdX(DhHdd0TlXhtPHTPddh4|@dTDlLldhDDxLhp(hPxdhdD8ldXLTHTddPtLXdTh4L@dhLtxTdlpTd8dhPtXpdhLtX4ddPTlXdxxdhXdhhd8(d404|8dhTd8|dhL4Xtddp4l8d4X4LpdhL4Xtd@ldpDdddl|LdXP4h0dhpTX0htXxDxdhpt8pddLlLddhp4XPhp0H00dh4Dx|dlp4D8dhPtxpd((Dx(dh0tx0dxXd(8dhDDxlhlL0ltdhhDxHd@|d0TdhHdxhdL0tD8dhhD8hhl|pLdddxt|pd|hDd0ddPtLXhl@H|pdhxDXxd8DdhldlhdtphpphppdhpT8PdH8dxXdlhd40dtXtlPdhTd8|dXlthtdhTDX|dx|4HDddxT|pdHDd8ldhL4X4dhP4XpdhtDx|ddXt|Pdh|T8DdHhdxhddLLLDhlxHl8dh0tXPd|(ddPddDL|LdHhdxhdhp4x0dl8dT@ddXT|phdh8Thdh(DXhd0HDP(dddl|lhd(xT(dhXdXxdTxtl0dd|lLtd8|4hddd4l||dXLTh4dd04lxdP8DP8ddxT|0dXXdh8ddP4lxd0@DpPdh8dXxddp4lxdhLt8tdHTdx|dh4Dx|dxLTHtdhhd8hd@DDpldd04LXdXlT(tdhXdXxdhPT8pdh(DXHdP@dp0ddP4LXdXpThPdllL4td((D8(dh0tXpd|(ddpdh(DxhhdL@DDdhHDx(dxL4(tdhLtXtdl@4dHdhxd8xdTh4L@dhXDXXhhdH8Tdd8T|PdH04xPdlllT4hllpLtdhhDXHhxxXhhdhXDxXdPDd@Ldd0TlXdHLtX4ddDL|ldXLT(4dhPtXPdXXd(8dhpt8phdH8thddxT|pd(ptXpddP4LxdLXDT@dhpT80dLptDxddxt|pdP@Dp0dhptx0d|0T4XdlpTdxdxpt(PdhHD8(d4TlL|dhHDx(d@hD@(dd@tl(d88dHXdh(Dx(d4pT|xddPtl8dP@DPPdhhDxhd804(pdhHD8Hhdhx4hddP4lxhdhXt(dhxdX8dp@DppdlllT4dP0dp@dddl|ldH8DXXdllLT4dPXdp8dd@tLHdlPTd8ddtL||d8PtHpddHt|@hd|@d4dh(dX(hdhXT(dhpT80hdHX4(dlpTdxdtDlLlddxT|pd(ptXpddP4LxdLXDT@dhpT80dLptDxddxt|pdP@Dp0dhptx0d|0T4XdlpTdxdxpt(PdhHD8(d4TlL|dhHDx(d@hD@(dddL|lhtph40dhpTxPdlp4dXdhDDxldpxD08dh(dX(dHlTxTdd|ll4d40t|Xdh0480ht@hT@dhptXphdHxT(dh(D8Hd4PT|8dhpt8pd88dhXddDl|LhxdHHtddPtlXd|pt4Xdd0Tl8d0(D0hdhhd8hdppd0@ddPTlXd8P4hpdhlTx4d8dDhLdd@TLhhllplTddXT|0dH|4XDdh|4xDht8XD8ddptl8dH8d88dd|LLTdh(DXhddHt|@hpXhp(dhdDxLdDhT|@dhP4X0dXhDHhdh0T8Pd((dxhdhhDx(hdx8Txddp4LXd8xDH8dhPTXpdlPtD8dh(DxHd@8D@Xdhl48Td00Dp@dhLT8Tdp(d0(dhhd8(d404|8dhhdx(dx0T(pdd|lL4ddXt|Pdd0TlXhxdH(4ddllLDhhLXX|dhXDx8hl8hLxdhpT80dLPtDXdhptX0dPXd0XddP4lxd0@DpPdlptd8dl(dTPdhxDx8d(ptX0dhpT80htxxdXdhhDxhdXltHtddh4|@d@|dPTdhdDXLhpph0Pdhp48Pdt4lL|dh04xpdLpTD8dd@4lhdl8dt@ddhT|@dPxDp8dd04lXd40t|xdd0TLxdTdlLLddpTLXd|pTT8dd04lxhhH8XxdhddxlhddPT|dd04LXdlhd4pdh8d8xhh|8XLdhxd8xd(8d8xdhp48pd(8DX8dhhDXHd4dllLddx4|0d8PTH0ddPtlxd|P44XdlpTdxd(XDXXddpTlxdHltX4dhLTxtd|HDD0

```

The hash function is built so that higher order bits never influence lower order bits, therefore I can generate a collection of strings where all of the `x` lower order bits are zero, then I can try concatenated combinations of these strings to find some where more of the lower bits are zero etc. I'm pretty sure that there are more ways of breaking this, and also ways that produce significantly shorter strings, but this way I avoided doing a lot of maths.
> 5 votes

# Answer
# Python 3, 118 bytes

```
int(H("9"+"0"*400))

```

and

```
int(H("9"+"0"*4000))

```

(that is: 9E400 and 9E4000)

Both produce

```
83909358607540647658718900164058931893

```

Digging somewhat deeper, it seems that any integer followed by k repeated digits such that k \> 128 and (k%4 == 0) will return the same hash. For example, `H("1"+"1"*32*4)` and `H("1"+"1"*33*4)` are both `13493430891393332689861502800964084413`. Hmmm, 128...
> 4 votes

# Answer
# Python 2, 161 bytes, by Puzzled

```
340282366920938463463374607431768211456 (decimal)
100000000000000000000000000000000 (hexadecimal)

```

and

```
340282366920938468780317283222139437056 (decimal)
100000000000001203B66F94300000000 (hexadecimal)

```

Both have the output:

```
83F172CC3D050D131F64FD04B8181DC2

```

The numbers are 2^128 and 2^128 + (3\*5\*7\*11\*13\*17)^2\*19\*2^32.
> 4 votes

# Answer
# Java, 299 bytes by SuperJedi224

Pastebin for `M`. In binary, `M` has 65535 `1`s, followed by 2 `0`s.

Pastebin for `N`. In binary, `N` has 21845 `1`s, followed by 174766 `0`s.

Both yield `0`.

Note that the basis of the algorithm is `i.bitCount()*i.bitLength()+1` and ultimately, we take the result to the power of `i` and take it mod 2128. So the idea was just to find two `i` that are divisible by four, but where the first expression gives 232. That was easily done by factoring 232-1 and picking two factors for the count of 1s and total bit width of the number.

**Edit:** Actually, there's a bit more to why `M` yields zero, but we can easily find more numbers that yield zero because of my explanation by using other factors of 232-1 such that there are at least 64 zeroes at the end.
> 3 votes

# Answer
# C, 134 bytes (by Barteks2x)

```
10

```

and

```
20

```

both hash to

```
0xa609779942cb9ef1

```

because the algorithm only hashes the last digit!
> 3 votes

# Answer
## C, 87 bytes

```
$ echo B075343F9832CD60 | ./hash6_ ; echo
fc2e9f02bd284bd1
$ echo 5914BD1B71164C77 | ./hash6_ ; echo
fc2e9f02bd284bd1

```

Found using my collision bruteforcer.
> 3 votes

# Answer
# Python 2, 115 bytes, by squeamish ossifrage

```
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111122222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222

```

and

```
2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

```

The hash value had nothing to do with the order of blocks.
> 3 votes

# Answer
# Python 2.x, 139 bytes by Puzzled

`H(2)`

and

`H(128)`

both return

`16645614427504350476847004633262883518`.
> 2 votes

# Answer
# C++, 239 bytes by SpelingMistake

Using the provided "main" program, the following two inputs produce the same hash:

```
echo -n "dog" | ./h
481c27f26cba06cf

```

and

```
echo -n "fog" | ./h
481c27f26cba06cf

```

The *first 8 bytes of input are never processed*, due to this bug in the code:

```
 for(I i=n;--i;) // and then we use q[i] for this iteration

```

because `--i` evaluates to false when `i==1`, `q[0]` (the first 8 bytes: `I` is an `int64`). Replacing the loop condition with `for(I i=n;i--;)` would have fixed this.
> 2 votes

# Answer
# Ruby, 90 Bytes, by MegaTom

```
4271974071841820164790043412339104229205409044713305539894083215644439451561281100045924173873152

```

and

```
23495857395130010906345238767865073260629749745923180469417457686044416983587046050252582956302336

```

which are 2 and 11 followed by 40 zero bytes. So they both have 41 bytes. The hash value is added by the input length for each byte, and then it is reversed in decimal. A input length ending with `1` can make sure the hash value will end with a `0` pretty quickly. Then reversing it reduces the length of the hash value by 1.

Both have the hash value `259`.
> 2 votes

# Answer
# C# - 393 bytes - by: Logan Dam

`70776e65642062792031333337206861786f72` and `70776e65642062792031333337206861786f7200` both hash to `18E1C8E645F1BBD1`.
> 2 votes

---
Tags: code-golf, cryptography, cops-and-robbers, hashing
---


# Question
Title: Create a basic autocorrecting spell checker
In this challenge, you have to implement a basic spell checker and autocorrector. Your program will use the first input as a source for a dictionary of words, and will use that to autocorrect the second input, finding a close match to some incorrectly spelt words, outputting the result

## Specifications

* You will receive two inputs, one is a sentence/paragraph you use as a source for your spell checker, and the other includes wrong words (they can be correct too) which you have to correct using the first input.
* Possible mistakes: Missing one letter (e.g. helo), one extra letter (e.g. heello), substitution of one character (e.g. hilp instead of help), transposition of two adjacent characters (e.g. hlep instead of help).
* In other words, the mistake and the original word have to have a Damerau–Levenshtein distance of one.
* You can separate the inputs in any reasonable format. For example, instead of using a newline, you can use a pipe sign to separate them. (|) However, watch out so you don't use something like letters because they are used in the 1st input.
* It's possible for a word to have neither an identical word nor a word with 1 distance from the first input. You will have to leave them unchanged.
* You don't need to do anything with punctuation. That is, I won't test words that are followed by a punctuation. (E.g. From the first example, I won't ask the correction of 'blod')
* Challenge is case insensitive, both the input and output. Meaning that if 'The' is used in the 1st input and the 2nd input is 'teh' you can change it to 'The', 'teh', 'teH', and similar cases.
* If a word is in the first input, but also has a distance of 1 with one of the other words, do not correct it.
* If there are two words with the same distance, you can output either of them. (E.g. 'en' can change into 'on' and 'in' if the words are both in the first input.) You can also output both of them, but you'll have to use a slash between them. (E.g. 'en' can be corrected into 'in/on')
* You can assume words are just sequences of letters separated by spaces.
* You can use STDIN or the closest alternative in your language.
* Standard loophole rules apply.
* This is , so the shortest code wins.

## Examples

Input:

```
A criminal strain ran in his blood, which, instead of being modified, was increased and rendered infinitely more dangerous by his extraordinary mental powers.

increasd mnetal

```

Output:

```
increased mental

```

Input:

```
The fact is that upon his entrance I had instantly recognized the extreme personal danger in which I lay.

I recognizid dnger en

```

Output:

```
I recognized danger in

```

# Answer
# CJam, ~~90~~ 87 bytes

```
qelN%Sf%~f{1$:W,,_:_2ewWf{\~e\}\Wf{' t_S-}W,),Wf{1$m<S\+m>}++Sf/26,'af+\ff*:+\&\a+0=}S*

```

Try it online in the CJam interpreter.
> 3 votes

---
Tags: code-golf, string
---


# Question
Title: Shortest undefined behavior sample in C++
What's the shortest, well-formed C++ code that exhibits undefined behavior?

# Answer
```
int main(){main;}

```

> ### 3.6.1 Main function \[basic.start.main\]
>
> 3 - \[...\] The function main shall not be used within a program.

Edit: this is diagnosable, so not UB.

---

```
int main(){for(;;);}

```

> ### 1.10 Multi-threaded executions and data races \[intro.multithread\]
>
> 24 - The implementation may assume that any thread will eventually do one of the following: — terminate, — make a call to a library I/O function, — access or modify a volatile object, or — perform a synchronization operation or an atomic operation.

---

```
int main(){int i=i;}

```

> ### 4.1 Lvalue-to-rvalue conversion \[conv.lval\]
>
> 1 - \[...\] If the object to which the glvalue refers is \[...\] uninitialized, a program that necessitates this conversion has undeﬁned behavior.

---

```
//^L.

```

Here `^L` is the form feed character, which is part of the basic character set. 4 characters (a newline is not required per 2.2:2). Undefined behaviour is per

> ### 2.8 Comments \[lex.comment\]
>
> 1 - If there is a form-feed or a vertical-tab character in \[a `//`-style\] comment, only white-space characters shall appear between it and the new-line that terminates the comment; no diagnostic is required.
> 12 votes

# Answer
```
\u\
0000

```

This has eight characters, and has undefined behaviour, according to §2.2/1.

> Each instance of a backslash character (`\`) immediately followed by a new-line character is deleted, splicing physical source lines to form logical source lines. Only the last backslash on any physical source line shall be eligible for being part of such a splice. If, as a result, a character sequence that matches the syntax of a universal-character-name is produced, the behavior is undefined.
> 5 votes

# Answer
```
int main(){int i=1>>-1;}

```

Explanation:

C++98 and C++11 §5.8/1 both state that

> The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.
> 2 votes

# Answer
```
#include. /*Imagine a new-line right after the dot*/

```

§16.2/4:

> A preprocessing directive of the form
>
> `#include` *pp-tokens new-line*
>
> (that does not match one of the two previous forms) is permitted. \[..\] If the directive resulting after all replacements does not match one of the two previous forms, the behavior is undefined.
> 2 votes

# Answer
If one is to believe wikipedia, here's a few:

Modifying strings is said to cause undefined behavior. It's always worked for me.

```
int main(int c,char*v){v[0]='.';}

```

A non-void function with no return causes undefined return values.

```
int a(){}
int main(){return a();}

```

Division (of int?) by zero is supposedly undefined. All I know is that it crashes.

```
int main(int c){c/0;}

```
> 1 votes

# Answer
```
int main() { int* a; return a[0]; }

```
> -1 votes

---
Tags: code-challenge, c++
---


title: Find nearest number in a given array

text:
# Question
Title: Find nearest number in a given array
This is inspired by a real world problem I had. I'm curious to see if there is any clever way to go about this.

You are given two unsorted arrays, A and B, each containing an arbitrary number of floats. A and B don't necessarily have the same lengths. Write a function that takes the elements of A sequentially and finds the nearest value in array B. The result has to be contained in a new array.

**Win condition**

Shortest code wins (as usual).

# Answer
> 17 votes
# APL, 13 ~~17~~

(21 byte in UTF-8)

```
B[{↑⍋|⍵-B}¨A]

```

If you want true lambda (A as left argument and B as right):

```
{⍵[⍺{↑⍋|⍺-⍵}¨⊂⍵]}

```

## How it works:

`{...}¨A` invokes lambda function `{...}` with every A value (instead of invoking with A as array), gathering results to array of same shape

`|⍵-B` computes absolute values of difference between argument ⍵ and all in B (- is subtraction, | is abs).

`↑⍋` takes index of least element (⍋ sorts array returning indices, ↑ get first element)

`B[...]` is just fetching element(s) by index(es).

The solution is quite strightforward, altough it uses wonderful feature of APL's sorting function returning permutation vector (sorted element's indices in original array) rather than sorted array itself.

# Answer
> 17 votes
## Mathematica - 17

```
#&@@@Nearest@A/@B

```

How does it work? Yes, I admit that there's a bit of cheating here because Mathematica has built-in nearest functionality. The rest is straightforward and is concerned with arranging the result in a 1D array. It looks ugly only because of the extra effort to make it short.

# Answer
> 6 votes
# C# - 103 97 87 Bytes

I'm not quite sure if I understood this question correctly but here is my solution anyway. I used Lists instead of arrays, because it allows me to write shorter code.

A integer array is shorter than a integer list.

**Input:**

```
t(new int[] { 0, 25, 10, 38 }, new int[] { 3, 22, 15, 49, 2 });

```

**Method:**

```
void t(int[]a,int[]b){var e=a.Select(c=>b.OrderBy(i=>Math.Abs(c-i)).First()).ToArray();

```

**Output:**

```
2, 22, 15, 49

```

If my answer isn't correct, please leave a comment below it.

**EDIT:** AS @grax pointed out, the question is now about floats. Therefore I'd like to include his answer too.

# 95 Bytes(Grax's answer)

```
float[]t(float[]a,float[]b){return a.Select(d=>b.OrderBy(e=>Math.Abs(e-d)).First()).ToArray();}

```

# Answer
> 5 votes
## R, 41 chars

```
B[apply(abs(outer(A,B,`-`)),1,which.min)]

```

Explanation:

`outer(A,B,`-`)` computes for each element x of A the difference `x-B` and outputs the result as a matrix (of dimension length(A) x length(B)).
`which.min` picks the index of the minimal number.
`apply(x, 1, f)` applies function `f` on each row of matrix `x`.
So `apply(abs(outer(A,B,`-`)),1,which.min)` returns the indices of the minimal absolute difference between each element of A and the elements of vector B.

Usage:

```
> A <- runif(10,0,50)
> B <- runif(10,0,50)
> A
[1] 10.0394987 23.4564467 19.6667152 36.7101256 47.4567670 49.8315028  2.1321263 19.2866901  0.7668489 22.5539178
> B
[1] 44.010174 32.743469  1.908891 48.222695 16.966245 23.092239 24.762485 30.793543 48.703640  6.935354
> B[apply(abs(outer(A,B,`-`)),1,which.min)]
[1]  6.935354 23.092239 16.966245 32.743469 48.222695 48.703640  1.908891 16.966245  1.908891 23.092239

```

# Answer
> 5 votes
# CJam - 14

```
q~
f{{1$-z}$0=\;}
p

```

The main code is on the second line, the rest is for using the standard input and pretty output.

Try it at http://cjam.aditsu.net/

**Explanation:**

`q~` reads and evaluates the input
`f{...}` executes the block for each element of the first array and the next object (which is the second array), collecting the results in an array
`{...}$` sorts the second array using the block to calculate a key for each item
`1$` copies the current item from the first array
`-z` subtracts then takes the absolute value
`0=` takes the first value of the sorted array (the one with the minimum key)
`\;` discards the item from the first array
`p` prints the string representation of the result

**Examples** (inspired from other answers):

Input: `[10.1 11.2 12.3 13.4 9.5] [10 12 14]`
Output: `[10 12 12 14 10]`

Input: `[0 25 10 38] [3 22 15 49 2]`
Output: `[2 22 15 49]`

# Answer
> 4 votes
# Python 3.x - 55 chars

```
f=lambda a,b:[min((abs(x-n),x)for x in b)[1]for n in a]

```

`a` and `b` are the input arrays, and the desired array is the expression's result.

# Answer
> 4 votes
# Javascript (E6) 54 ~~56 59~~

Minimize distance. Using square instead of abs just so save chars.
**Edit** algebra ...
**Edit** fix useless assignment (a remainder of a test w/o the function definition)

```
F=(A,B)=>A.map(a=>B.sort((x,y)=>x*x-y*y+2*a*(y-x))[0])

```

Was `F=(A,B)=>D=A.map(a=>B.sort((x,y)=>((x-=a,y-=a,x*x-y*y))[0])`

**Test**

```
F([10.1, 11.2, 12.3, 13.4, 9.5],[10, 12, 14])

```

Result: `[10, 12, 12, 14, 10]`

# Answer
> 3 votes
## PowerShell - 44

```
$a|%{$n=$_;($b|sort{[math]::abs($n-$_)})[0]}

```

**Example**

With `$a` and `$b` set to:

```
$a = @(36.3, 9, 50, 12, 18.7, 30)
$b = @(30, 10, 40.5, 20)

```

Output is

```
40.5, 10, 40.5, 10, 20, 30

```

# Answer
> 3 votes
# Haskell, 55

```
c a b=[[y|y<-b,(y-x)^2==minimum[(z-x)^2|z<-b]]!!0|x<-a]

```

At first, I thought to use `minimumBy` and `comparing`, but since those aren't in Prelude, it took a ton of characters to qualify them. Also stole the squaring idea from some other answers to shave off a character.

# Answer
> 2 votes
# Ruby, 40

```
f=->a,b{a.map{|x|b.min_by{|y|(x-y)**2}}}

```

Same as the Python answer, but squaring is a little terser than any way I could think of to take absolute value.

# Answer
> 2 votes
# TI-BASIC, 24

```
∟A+seq(min(∟B+i²∟A(N)),N,1,dim(∟A

```

Doesn't come close to APL, but uses less powerful functions-- this uses no "sorted by" or "index of least" function. The disadvantage of TI-BASIC here is its lack of those functions and multidimensional arrays.

Ungolfed:

```
seq(       ,N,1,dim(∟A           #Sequence depending on the Nth element of list A
    ∟A(N)+min(   +0i)            #Number with minimum absolute value, add to ∟A(N)
              ∟B-∟A(N)           #Subtracts Nth element of ∟A from all elements of B

```

The min( function has two behaviors: when used with real numbers or lists, it gives the smallest value; however, when used with complex numbers or lists, it gives the value with the smallest absolute value. Adding `0i` or multiplying by `i^2` causes the interpreter to use the second behavior, so `min(1,-2)` returns `-2` whereas `min(1+0i,-2+0i)` returns `1`.

# Answer
> 2 votes
# Pyth - 12 11 bytes

## Note: Pyth is much younger than this challenge, so this answer is not eligible to win.

Simple method, uses `o` order function to get minimal distance and `m`aps it over list `a`.

```
mho.a-dNQvz

m    vz    Map over evaled first input and implicitly print
 ho Q      Minimal mapped over evaled second input
  .a-      Absolute difference
   d       Lambda param 1
   b       Lambda param 2

```

Try it online here.

# Answer
> 1 votes
# Fortran 90: 88

```
function f();integer::f(size(a));f(:)=[(b(minloc(abs(a(i)-b))),i=1,size(a))];endfunction

```

This requires it to be `contain`ed within a full program:

```
program main
   real :: a(5), b(3)
   integer :: i(size(a))
   a = [10.1, 11.2, 12.3, 13.4, 9.5]
   b = [10, 12, 14]
   i = f()
   print*,i
 contains
   function f()
     integer :: f(size(a))
     f(:)=[(b(minloc(abs(a(i)-b))),i=1,size(a))]
   end function
end program main

```

The square braces declare an array while `(...,i=)` represents an implied `do` loop; I then return the value of `b` for which element `a(i)-b` is minimized.

# Answer
> 1 votes
# Matlab: 48

```
f=@(a)B(abs(B-a)==min(abs(B-a)));C=arrayfun(f,A)

```

Assumes that `A` and `B` are 1D matrices in the workspace, Final result is `C` in the workspace. This would likely also work in Octave as well. Conditional indexing makes doing this fairly trivial.

# Answer
> 0 votes
# C 144 163

```
#define f float
f T, *C, m;
f *q(f *A, f *B, int S, f s)
{
    if(m)
        return abs(T - *A) - abs(T - *B);
    for (
        C = malloc(S * 4);
        m = S--;
        C[S] = *B
    )
        T = A[S],
        qsort(B, s, 4, q);
    return C;
}

```

Okay... I think this little code needs explanation.

At first i tried to do the job with two level of for loop finding the min difference and set the current value to min of B's value. That's very basic.

The same thing can be reached with qsort and a comparator function. I make it sort B by the difference instead of B's elements. Too many functions for such a little algorithm. So the function q now serves two purposes. At first, it's the algorithm itself, secondly (when qsort calls it) a comparator. For communication between the two states, I had to declare globals.

**m** stands for whether it's in comparator state or the *main* one.

**example:**

```
float A[] = {1.5, 5.6, 8.9, -33.1};
float B[] = {-20.1, 2.2, 10.3};
float *C;

C = q(A, B, sizeof(A)/sizeof(*A), sizeof(B)/sizeof(*B));
// C holds 2.2,2.2,10.3,-20.1

```

# Answer
> 0 votes
# GolfScript, 49 bytes

*Note: this is a partial solution. I'm working on making it a complete solution*

```
{{\.@\.[.,,\]zip@{[\~@-abs]}+%{~\;}$0=0==}%\;}:f;

```

Yes. GolfScript does support floating point. Try it out here. Example:

```
# B is [-20.1 2.2 10.3]
[-201 10 -1?*
22 10 -1?*
103 10 -1?*]

# A. No floating point numbers allowed here.
# This is because 1.5{}+ (where the 1.5 is a
# single floating point number, not 1.5,
# which would be 1 1 5) results in the block
# {1.5 }, which leads to 1 1 5 when executed
[1 5 9 -30]

```

Output:

```
[2.2 2.2 10.3 -20.1]

```

# Answer
> 0 votes
## C# 262

Program finds min differences and saves closest value from Array B. I'll work on the golfing shortly.

```
List<float> F(List<float> a, List<float> b)
{
List<float> c = new List<float>();
float diff,min;
int k;
for(int i=0; i<a.Count;i++)
{
diff=0;
min=1e6F;
k = 0;
for(int j=0; j<b.Count;j++)
{
diff = Math.Abs(a[i] - b[j]);
if (diff < min)
{
min = diff;
k = j;
}
}
c.Add(b[k]);
}
return c;
}

```

Full program with test code

```
using System;
using System.Collections.Generic;
public class JGolf
{
    static List<float> NearestValues(List<float> a, List<float> b)
    {
        List<float> c = new List<float>();
        float diff,min;
        int k;
        for(int i=0; i<a.Count;i++)
        {
            diff=0;
            min=1e6F;
            k = 0;
            for(int j=0; j<b.Count;j++)
            {
                diff = Math.Abs(a[i] - b[j]);
                if (diff < min)
                {
                    min = diff;
                    k = j;
                }
            }
            c.Add(b[k]);
        }
        return c;
    }

    public static void Main(string[] args)
    {
        List<float> A = RandF(8413);
        Console.WriteLine("A");
        Print(A);
        List<float> B = RandF(9448);
        Console.WriteLine("B");
        Print(B);

        List<float> d = JGolf.NearestValues(A, B);
        Console.WriteLine("d");
        Print(d);
        Console.ReadLine();
    }

    private static List<float> RandF(int seed)
    {
        Random r = new Random(seed);
        int n = r.Next(9) + 1;
        List<float> c = new List<float>();
        while (n-- > 0)
        {
            c.Add((float)r.NextDouble() * 100);
        }
        return c;
    }

    private static void Print(List<float> d)
    {
        foreach(float f in d)
        {
            Console.Write(f.ToString()+", ");
        }
    }
}

```

# Answer
> 0 votes
# C#: 120

Linq is awesome:

```
float[] t(float[] A, float[] B){return A.Select(a => B.First(b => Math.Abs(b-a) == B.Min(c=>Math.Abs(c-a)))).ToArray();}

```

---
Tags: code-golf, function
---