Deja Vu

[ShardFire]

I was wondering if the rest of you solved this in a similar way to me. I used a radix sort in base-64 and checked for duplicates when adding a value into its bucket.

[snibril]

No, I used a hash function.

[m!nus]

a hash function? can you explain how that works?

i used radix aswell (ShardFire explained it to me) but maxed out the buckets to a number and each a size of 127 memory cells.
worst case 6344 cycles, average about 2500.
how many cycles did your hash function take, snibril?

[efe]

I think both of the methods use the same principle. Radix sort also makes use of a hash function to determine the bucket (i.e. the adress in memory).
I used the following hash function, which is applied to every input number:

h(n) = (n mod 16128) + 128

The result is a memory location between 128 and 16256.

In order to increase the success rate, I used linear probing for resolving hash collisions.
http://en.wikipedia.org/wiki/Linear_probing

[teebee]

I also used hashing with a little bit collision resolution (just in the case...). The remaining s := 16384-128 memory cells are used as hash table. The hash value for some number x is computed by v := x mod p where p is some prime. The hash table contains in cell v the number of hashed numbers for that hash value followed by the numbers themselves in the cells v+1, v+2,... p = 251, 599, 5417 worked for me.

[snibril]

I used the same hash function as efe, but you get better results if you use a prime number thats not to close to a power of 2.

[MerickOWA]

I used the exact same method as efe. At first I attempted to do the problem without resolving collisons. My method stored a "1" in memory to indicate that i'd seen that number and assumed no collisions happened. I tried using many different numbers to mod by without finding one passed all the tests. At best I passed all but one. Eventually I rewrote to store the number at the memory location and resolved collisions by simple incrementing (linear probing).

[Karian]

I found a sollution that would work without collision detection, but not from the first attempt. In general, it is the same as efe's algoritm. Only I first have put all values on the stack and resetting their memory value, and then I used the full range of the memory buffer.

[wrtlprnft]

I guess one could also just quicksort and then scan for duplicates. That's what I'd have done if I wasn't too lazy. I didn't even do linear probing (might have done, but my lazy test modulus of 9999*** just worked on my first try).

[Hamstaro]

Well, my first try was with quicksort. But i couldn't optimize it to bring results under 11000 cycles

I then used the solution with a hash table - without collision detection. We have here only 128 entries - so just be happy.

[blablaSTX]

remembering my old Lisp days, I used a hash into a collection of hashTableSize linked lists (cons pairs). I am hashing on (value MOD hashTableSize). The list is searched sequentially.

[arthur]

if lucky enough, you can pass all the test cases without collision detection

[kalunos]

here comes my simple solution:

first: load all numbers onto stack (while setting mem completly to zero)

882** 1-0^<1v01^>0^7?037*-g

then: create hashtable { mod 127 } to reduce overall compare-operations ...

d882**1- 1^1^/1^*2^1v-1^* 0^<0^54*0+?3^-2?4gddp!1+056*-g d2v1v> 088*1--g

happy coding!

[compudemon]

i used a big hash table 16111 prime probably overkill but all the work i did, i may as well go for least collisions its the biggest prime that i felt safely fit in the memory

79+g0^<2^1^-4?d1+$p!953**2557***8+95**1+882**1-0^<0^0^4^/4^*-4^+0^<8?4c09-4-g>0^6?259*-g!

[avrrobot]

Here is my solution:
00^<0^8888***3*/8888***3**-88*2*+0^<2^<:52*?1^<1v>1+1c1^<p!