# Submission 53dccaa9...

Challenge Remove duplicate elements zac.creditmint.eth 2018-56-10 413164
``````/**
* This file is part of the 1st Solidity Gas Golfing Contest.
*
*/

pragma solidity ^0.4.23;

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) {
// derp version
assembly {
if eq(calldatasize, 0x44) {
mstore(0x00, 0x20)
return(0x00, 0x40)
}
let arrayPointer := 0x00
let nextIndex := 0x00
let end := add(sub(calldatasize, 0x44), 0x140) // todo, optimize

calldatacopy(0x00, 0x44, sub(calldatasize, 0x44))

for {} lt(nextIndex, end) {} {
let not_unique := 0
for {let j := 0} or(lt(j, end), not_unique) {j := add(j, 0x20)} {
if and(eq(val, mload(j)), iszero(eq(j, nextIndex))) {
not_unique := 1
}
}
if iszero(not_unique) {
mstore(arrayPointer, val)
}
}
}
}

// hmm how can i improve.
// what about using the bloom filter as a 1st pass
// if the bloom filter does not return negative, we , hmm
*/
// bloom filters, can I get a ghetto 512 bit filter?
// e.g. third byte determines whether first or second byte is used
function uniquify(uint[] input) public view returns(uint[] ret) {

assembly {
// hash map
if eq(calldatasize, 0x44) {
mstore(0x00, 0x20)
return(0x00, 0x40)
}
mstore(0x0, 1)
mstore(0x20, 2)
mstore(0x40, 4)
mstore(0x60, 8)
mstore(0x80, 16)
mstore(0xa0, 32)
mstore(0xc0, 64)
mstore(0xe0, 128)

let nextIndex := 0x400
let arrayPointer := 0x400
let end := add(sub(calldatasize, 0x44), 0x400) // todo, optimize
/* let bloomFilterA := 0x00
let bloomFilterB := 0x00
let bloomFilterC := 0x00
let bloomFilterD := 0x00
let bloomFilterE := 0x00 */
calldatacopy(0x400, 0x44, sub(calldatasize, 0x44))
// 2453 bits and 4 hash functions
// let's try with 8 possible limbs
// 100 = end of hash lookup
// 100 - 120 = keccak256 scratch space
// 120 - 140 = bloom limb 1
// 140 - 160
// 160 - 180
// 180 - 1a0
// 1a0 - 1c0
// 1c0 - 1e0
// 1e0 - 200
// 200 - 220 = bloom limb 8
// 220 - rest = return data
let basicBloom := 0x00
let anotherBloom := 0x00
for {} lt(nextIndex, end) {} {
mstore(0x120, i)
let h1 := keccak256(0x120, 0x20)
let limbA := and(h1, 0xf)
let limbB := and(byte(30, h1), 0xf)
let indexA := add(mul(limbA, 0x20), 0x140)
let indexB := add(mul(limbB, 0x20), 0x140)
if or(
) {
mstore(arrayPointer, i)
switch eq(limbA, limbB)
case 1 {
}
default {
}
basicBloom := or(basicBloom, bitsC)
anotherBloom := or(anotherBloom, bitsD)
}
// let h1 := mulmod(i, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F, not(0)) //totally not overkill // keccak256(0x120, 0x20)
/* let b1 := mload(and(i, 0xff))
if or(
iszero(and(bloomFilterA, b1)),
or(
iszero(and(bloomFilterB, b2)),
or(
iszero(and(bloomFilterC, b3)),
or(
iszero(and(bloomFilterD, b4)),
iszero(and(bloomFilterE, b5))
)
)
)
) {
mstore(arrayPointer, i)
bloomFilterA := or(bloomFilterA, b1)
bloomFilterB := or(bloomFilterB, b2)
bloomFilterC := or(bloomFilterC, b3)
bloomFilterD := or(bloomFilterD, b4)
bloomFilterE := or(bloomFilterE, b5)
} */