Submission 4a23fad3...

ChallengeRemove duplicate elements
Submitterhyszeth.eth
Submitted at2018-54-06
Gas used786321
/**
 * 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 {
    /**
     * @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 lookupLen = 11;
        uint[][11] memory lookup;// = new uint[][](lookupLen);

        uint[] memory uniqueList = new uint[](input.length);
        uint uniqueIndex;

        uint nDups;
        for(uint i = 0; i < input.length; ++i) {
            uint current = input[i];
            uint quickHash = current % lookupLen;
            uint[] memory currentLookup = lookup[quickHash];
            uint currentLookupLength = currentLookup.length;
            if(currentLookupLength > 0) {
                uint len = currentLookup[0] + 1;
                for(uint j = 1; j < len; ++j) {
                    if(currentLookup[j] == current) break;
                }
                if(j == len) {
                    // false positive
                    uniqueList[uniqueIndex++] = current;
                }
            } else {
                uniqueList[uniqueIndex++] = current;
                if(currentLookupLength == 0) {
                    currentLookup = lookup[quickHash] = new uint[](inputLength+1);
                    currentLookup[0] = 1;
                    currentLookup[1] = current;
                } else {
                    len = currentLookup[0]++;
                    currentLookup[len] = current;
                }
            }
        }
        ret = new uint[](uniqueIndex);
        for(i = 0; i < uniqueIndex; ++i) {
            ret[i] = uniqueList[i];
        }

        return ret;
    }
}