Submission 7fb0e8f6...

ChallengeRemove duplicate elements
Submitterhyszeth.eth
Submitted at2018-54-08
Gas used559785
/**
 * 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.
     */

// TRY THESE http://www.cse.yorku.ca/~oz/hash.html

    function uniquify(uint[] input) public pure returns(uint[] ret) {
        uint inputLength = input.length;
        if(inputLength == 0) return ret;
        uint lookupLen = 1051;
        //bool[1051] memory lookup;// = new uint[][](lookupLen);

        uint[1051] memory cache0;
        bool[733] memory cache1;

        uint uniqueIndex;

        uint nDups;
        for(uint i = 0; i < input.length; ++i) {
            uint current = input[i];
            uint16 quickHash = uint16(current % 1051);
            uint currentCache;
            if((currentCache=cache0[quickHash]) > 0) {
                if(currentCache != current+1) {
                    quickHash = uint16(current % 733);
                    if(cache1[quickHash]) {
                        for(uint j = 0; j < uniqueIndex; ++j) if(current == input[j]) break;
                        if(j == uniqueIndex) {
                            // false positive
                            if(uniqueIndex != i) input[uniqueIndex] = current;
                            uniqueIndex++;
                        }
                    } else {
                        if(uniqueIndex != i) input[uniqueIndex] = current;
                        uniqueIndex++;
                        cache1[quickHash] = true;
                    }
                }
            } else {
                if(uniqueIndex != i) input[uniqueIndex] = current;
                uniqueIndex++;
                cache0[quickHash] = current + 1;
                cache1[current % 733] = true;
            }
        }
        //emit E(r1);
        ret = new uint[](uniqueIndex);
        for(i = 0; i < uniqueIndex; ++i) {
            ret[i] = input[i];
        }
        return ret;
    }
}