Decentralized Online Judge provides a pioneering solution for establishing a decentralized provable online judging platform for competitive programming.
Our primary objective is to ensure the transparency and justice of programming contests, attract more OIers/ACMers to participate in web3 and improve the efficiency of blockchain networks through more extensive application of algorithms and data structures.
This project is developed based on Foundry, which is an incredibly easy-to-use smart contract development kit.
If you haven't install foundry, you can run
foundryup
After the installation, you can run
foundry install qpdk777/DOJ --no-commit
forge init
Then open foundry.toml
in the root folder of your project, insert the code below and save
remappings = [
'@qpdk777/DOJ=lib/DOJ/src',
]
Now you can create your smart contract problems in ./src
.
To create a problem, you need to:
- write the content of you problem and encode it with
base64
to generate an URI - inherit
SolutionInterface
interface, which defines the functions that an solution contract must implement - inherit
Judge
contract and overridejudge()
function, in which you can test whether a solution is right or wrong - write a script to deploy everything, where you can set the
testCaseNumber
,gasLimit
and other parameters.
To provide a solution, you need to:
- implement the
SolutionInterface
of that problem - design and implement an excellent algorithm to solve this problem
- write a script to deploy your solution
- call
enterJudge
with the address of your solution and get the result of the judge
For Quick Sort problem, I write three solutions - quick sort, merge sort and bubble sort, whose time complexities are
Here comes their gas usage comparison. As the scale of the array grows, their performances become extremely distinct.
Gas Usage in linear | Gas Usage in logarithm |
---|---|
![]() |
![]() |
The gas usage of quick sort and merge sort, which are of the same time complexity, grows together slowly, while that of bubble sort pumps up rapidly.
This proves that we can use the time complexity to distinguish which one is a better solution. It also allows some linear spare time to avoid unexpected and unpleasant TLE (GLE in DOJ, which means Gas Limit Exceeded).