Submission 346bfb04...

ChallengeRemove duplicate elements
Submitterhyszeth.eth
Submitted at2018-32-22
Gas used622257
/**
 * This file is part of the 1st Solidity Gas Golfing Contest.
 *
 * This work is licensed under Creative Commons Attribution ShareAlike 3.0.
 * https://creativecommons.org/licenses/by-sa/3.0/
 */

pragma solidity 0.4.24;

contract Unique {
    event E(uint);
    /**
     * @dev Removes all but the first occurrence of each element from a list of
     *      integers, preserving the order of original elements, and returns the list.
     *
     * The input list may be of any length.
     *
     * @param input The list of integers to uniquify.
     * @return The input list, with any duplicate elements removed.
     */

    function uniquify(uint[] input) public pure returns(uint[] ret) {
        uint inputLength = input.length;
        if(inputLength == 0) return ret;

        uint inputLen = input.length;
        uint[] memory cache = new uint[](inputLen);

        uint uniqueIndex;

        uint nDups;
        for(uint i = 0; i < inputLen; ++i) {
        	uint current = input[i];
	        uint currentOffset = current + 0xfaccf431;
        	uint quickHash = 33 * current % inputLen; // do we need a multiple? Like input * 33?
            uint elem;
    		do {
    			if(currentOffset == 0x0) {
    				// Worst case
    			}
    			if((elem=cache[quickHash]) == currentOffset) {
    				break; // duplicate
    			} else if(elem == 0) {
    				if(uniqueIndex != i) input[uniqueIndex] = current;
    				uniqueIndex++;
    				cache[quickHash] = currentOffset;
    				break; // we have an original

    			}
    			quickHash = (quickHash+1)%inputLen;
    		} while(true);
        }
        //emit E(r1);
        ret = new uint[](uniqueIndex);
        for(i = 0; i < uniqueIndex; ++i) {
            ret[i] = input[i];
        }
        return ret;
    }
}