Submission 6c832b91...

ChallengeRemove duplicate elements
Submittermichaelsproul.eth
Submitted at2018-37-02
Gas used1462650
/**
 * 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 n = input.length;

        uint i;
        uint num_uniq;
        bool seen_zero;

        uint[] memory hashmap = new uint[](n);

        for (; i < n; i++) {
            uint val = input[i];

            if (val != 0) {
                // TODO: consider using a cheaper hash function
                uint hash_idx = uint(keccak256(abi.encodePacked(val)));

                for (uint j = 0; j < n; j++) {
                    uint idx = (hash_idx + j) % n;

                    uint bucket_val = hashmap[idx];

                    // Found our element => it's a duplicate, skip it and continue outer loop.
                    if (bucket_val == val) {
                        break;
                    }
                    // Found an empty slot => it's unique, store it and continue outer loop.
                    else if (bucket_val == 0) {
                        hashmap[idx] = val;
                        input[num_uniq] = val;
                        num_uniq = num_uniq + 1;
                        break;
                    }
                }
            } else if (!seen_zero) {
                seen_zero = true;
                input[num_uniq] = 0;
                num_uniq = num_uniq + 1;
            }
        }

        ret = new uint[](num_uniq);

        for (i = 0; i < num_uniq; i++) {
            ret[i] = input[i];
        }
    }
}