Submission 8fb9caa7...

ChallengeRemove duplicate elements
Submitterricmoo.firefly.eth
Submitted at2018-09-31
Gas used419550
/**
 * 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/
 *
 *  Author: Richard Moore <[email protected]>
 *  Date:   May 24, 2018
 */

pragma solidity 0.4.24;

contract Unique {
    function uniquify(uint[] input) public pure returns(uint[] ret) {
        uint256 length = input.length;
        if (length <= 1) { return input; }

        uint[256] memory filter;

        uint256 outputIndex = 0;
        for (uint256 i = 0; i < length; i++) {
            uint v = input[i];

            if (v <= 0xff) {
                if (filter[v] & 0x01 == 0x01) { continue; }
                filter[v] |= 0x01;

            } else {
                uint index = uint(v & 0xff);
                uint check = uint(v & 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe);
                if (uint(filter[index]) & check != check) {
                    // Unique!
                } else {
                    check = 1;
                    for (uint j = 0; j < outputIndex; j++) {
                        if (input[j] == v) {
                            // Unique!
                            check = 0x00;
                            break;
                        }
                    }
                    if (check == 0x00) { continue; }
                }
                filter[index] |= check;
            }

            input[outputIndex++] = v;
        }

        ret = new uint[](outputIndex);
        for(i = 0; i < outputIndex; i++) {
            ret[i] = input[i];
        }
    }
}