InnovatorsCode SubmissionsDeveloping Your Algorithm

Developing Your Algorithm

This is the step where you develop your algorithm. You can use the existing algorithms as a reference.

You can pick a challenge <challenge_name> to develop an algorithm for. Make a copy of tig-algorithms/<challenge_name>/template.rs or of an existing algorithm.

Adding a License Header

Make sure your file has the following notice in its header if you intend to submit it to TIG:

/*!
Copyright [year copyright work created] [name of copyright owner]
 
Identity of Submitter [name of person or entity that submits the Work to TIG]
 
UAI [UAI (if applicable)]
 
Licensed under the TIG Inbound Game License v2.0 or (at your option) any later
version (the "License"); you may not use this file except in compliance with the
License. You may obtain a copy of the License at
 
https://github.com/tig-foundation/tig-monorepo/tree/main/docs/licenses
 
Unless required by applicable law or agreed to in writing, software distributed
under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
CONDITIONS OF ANY KIND, either express or implied. See the License for the specific
language governing permissions and limitations under the License.
*/

UAI stand for Unique Algorithm Identifier. It is a unique identifier for your algorithm. If your implementation is based on an algorithmic method submitted to TIG, you must attribute your implementation to it (example UAI: c001_b001)

  • UAI of a method is detailed inside tig-breakthroughs/<challenge_name>/<method_name>.md.s
  • Methods should have a branch name like - <challenge_name>/method/<method_name>.

If your implementation is based on an algorithmic method outside of TIG, set the UAI to null.

Rename the file with your own <algorithm_name>

Edit tig-algorithms/<challenge_name>/mod.rs to export your algorithm and test it:

mod.rs
pub mod <algorithm_name>;
 
#[cfg(test)]
mod tests {
    use super::*;
    use tig_challenges::{<challenge_name>::*, *};
 
    #[test]
    fn test_<algorithm_name>() {
        let difficulty = Difficulty {
            // Uncomment the relevant fields.
            // Modify the values for different difficulties
 
            // -- satisfiability --
            // num_variables: 50,
            // clauses_to_variables_percent: 300,
 
            // -- vehicle_routing --
            // num_nodes: 40,
            // better_than_baseline: 250,
 
            // -- knapsack --
            // num_items: 50,
            // better_than_baseline: 10,
            
            // -- vector_search --
            // num_queries: 10,
            // better_than_baseline: 350,
        };
        let seed = [0u8; 32]; // change this to generate different instances
        let challenge = Challenge::generate_instance(seed, &difficulty).unwrap();
        match <algorithm_name>::solve_challenge(&challenge) {
            Ok(Some(solution)) => match challenge.verify_solution(&solution) {
                Ok(_) => println!("Valid solution"),
                Err(e) => println!("Invalid solution: {}", e),
            },
            Ok(None) => println!("No solution"),
            Err(e) => println!("Algorithm error: {}", e),
        };
    }
}

Use the above test to debug your algorithm:

cargo test -p tig-algorithms -- --nocapture

Notes for Developing Algorithms

  • Not all challenge instances have solutions. Algorithms that can detect such cases and exit early (return Ok(None)) will potentially have better performance than algorithms that don’t exit early.

  • To find out the the current qualifying difficulties, you can query the official API endpoint:

### To get the <block_id>
 
curl https://mainnet-api.tig.foundation/get-block
 
### For <qualifier_difficulties>
 
curl https://mainnet-api.tig.foundation/get-challenges?block_id=<block_id>

  • If you are copying and modifying an algorithm that has been submitted to TIG, make sure to use the innovator_outbound version.

  • Do not include tests in your algorithm file. TIG will reject your algorithm submission.

  • Only your algorithm’s rust code gets submitted. You should not be modifying Cargo.toml in tig-algorithms. Any extra dependencies you add will not be available when TIG compiles your algorithm

  • If you need to use random number generation, ensure that it is seeded so that your algorithm is deterministic. It is recommended to use let mut rng = SmallRng::from_seed(StdRng::from_seed(challenge.seed).gen()).

Setting up Dev EnvironmentCompiling Your Algorithm