Call for participation: An On-Chain Sorting Program Contest

Write the most gas efficient pure sorting function and win a prize!

Info Sheet

• Network: Polygon Mainnet.
• Prize: Any Matic or ERC20 stored in the contract. Superfluid has funded $500 USDC!
• Period: Contest period ends by Fri Aug 19 2022 10:01:14 GMT+0000. Plus one more week of challenge period.
• Contest Address (SortProgramContest): https://polygonscan.com/address/0xb64a8f57b46df3f303d72204accf4f8f680d6dcf#readContract
• Baseline Program (SuccinctQuicksort): https://polygonscan.com/address/0x0c9002d3e520d1cb47136d9d78576793e3ab10e9#code
• Entrance Fee: 10 Matic.
• Detailed Rules: In the next section.
• Code Repository: https://github.com/hellwolf/quickhiring-sol

Qualifying Programs

Qualifying Steps

• Implement a contract with the interface:

interface ISortProgram {
     function sort(uint256[] calldata input) external view returns (uint256[] memory result);
}

• sort function should do what one would expect it to do, it should stand any random sequences of 256bits uint256 up to 500 elements.
• Deployed on Polygon Mainnet.
• Call `SortProgramContest.qualify` attaching a msg.value of 10 Matic.
• For prepared input, it should produce same result as the baseline program.
• For random input, producing a different result than the baseline program can be “busted” and lose the entrance .

Detailed Rules

// Sorting Program Contest:
//
// Objective: the most gas efficient pure sorting function
// Rules:
// - The contest lasts for `CONTEST_PERIOD`, and an additional `CHALLENGE_PERIOD` for challenge time.
// - During the contest period, anyone can use the `qualify` function to submit a new porgram.
// - There is an entrance fee of `ENTRANCE_FEE` for the qualification.
// - The program that uses less gas than the previous program is the new "top gun".
//   - There is a gas limit of `GAS_LIMIT` of how much gas the sorting function can use.
//   - The gas improvement has to be at least more than `MINIMUM_GAS_IMPROVEMENT`, due to gas measurement inaccuracy
// - The test input for the program is always the same.
// - The contest starts with a baseline pure recursive succinct quicksort algorithm as the "top gun".
// - The top gun can be challenged with a counter example, to prevent spams of any non general solutions.
//   - The top gun busted will cede the top gun position to the previous top gun.
// - The challenge examples are limited to `SAMPLE_LIMIT`, so that `GAS_LIMIT` could be met.
// Result:
// - After the `CONTEST_PERIOD`, there is still a `CHALLENGE_PERIOD`.
// - After the `CHALLENGE_PERIOD`, the top gun application can collect both coins and erc20 tokens in the contract.
// Note:
// - There are myriads of view functions for testing purpose, read the source code!

Parameters:

// if you burn more gas than this, I don't know what are you doing with your life!
    uint public constant GAS_LIMIT = 4e6;
uint public constant MINIMUM_GAS_IMPROVEMENT = 10e3;
// let's prevent challenge from unfair difficult problems.
    uint public constant SAMPLE_LIMIT = 500;
// no spam, bust it!
    uint public constant ENTRANCE_FEE = 0.01e18;
// time is limited!
    uint public constant CONTEST_PERIOD = 2 weeks;
// it's time to bust as many bad topguns as possible!
    uint public constant CHALLENGE_PERIOD = 1 weeks;