Deja Vu

[Hippo]

Here is mine ...

Code: Select all

Label	Addr	Code	Desired jmp
Start	0	882**0^0^*1-1^-00	
HashLoop	17	0^<0^0^5^/5^*-5^+1v2*1+1^<0^95*?	save
Nonzero	49	-57*?	found
Conflict	54	d0^<2^>1v1+1v	
Looping	67	1+0^4^-6?	HashLoopEnd
ToHashLoop	76	789*-g	HashLoop
HashLoopEnd	82	63*g	AfterHashLoop
	86	!!!	
Found	89	1^<p!	
Save	94	d1v>358*-g	Looping
AfterHashLoop	104	2v+2vd1^-0	
ClearLoop	114	01^<0^4^/4^*-4^+>1+0^3^-6?	ClearLoopEnd
	140	048*-g	ClearLoop
BackToHLoop	146	d000754**-g	HashLoop

I made it safe to be ready to hash several times in the case of unprobable conlicts.

How it works ... storing at (val mod (16384-size)+size) the value 2val+1, of course check there was 0 on the address. If there was nonzero equal to 2val+1 you are done, otherwise store val to the list of conflicted numbers to be processed once again.
Confliceted numbers are processed by the same method, just the size is decreased to the conflict size. To allow that you must ensure there are zeros at the addresses they will use.
... worst case is O(size^2) for the case all hashed to the same address, but as modulo changes, that would require astronomically high numbers. It seems to me the big conflict case is solved better by this method (than by sloving conflicts by standard hash techniques) thanks to the modulus change.
I don't think the size in the 2nd run would be bigger than 5.
I know it's overkill ... to pass tests, it would be probably sufficient to store 1 and report a conflict as a solution ... .

I dont think there is any reason the modulus to be prime number.

[yes-man]

Like I already hinted in the non-solver forum, I'm pretty impressed with the design of this challenge.

I, like others, used a hashing scheme to identify the duplicate. Good old memory-time trade-off. Glad I remember some of those university lessons ;-D

The author basically set up the test sets to mess with any attempt of just breezing through the challenge by including duplicates to have the same MOD for a whole lot of different prime numbers. Chapeau!

Some additional magic was needed to get around this one. Really liked it.

Here is my take on it. The spaces are for (my) readability. Too lazy to get them out after solving it^^

Code: Select all

882**0^88**1-1^  1-0^  <0^3^1^1^/*-  4^+0^  <65*8+?  0^<0^54*4+?2^:62*?1+054*8+-g  <p!  d>099*-g

A bit of explanation

Code: Select all

882**0^88**1-1^		preload (memory offset, mod hash value, counter for reading backwards)
1-0^				decrement main counter (iMem)
<0^3^1^1^/*-		read mem cell memory[iMem]; duplicate; calculate mod (see MOD challenge^^)
4^+0^				add mem offset to hash; duplicate
<65*8+?				check hash table for non-zero entry; if zero, jump directly to hash write
0^<0^54*4+?			get another copy of the hash value; is it zero, jump to hash write
2^:62*?				(if not) compare it to the number found; the same? jump to output
1+054*8+-g			(again, if not) increase iMem and check next bucket
<p!					done, output integer from mem cell
d>099*-g			hash write; (d is for stack correction on specific jumps); go back to dec main

[adum]

hi