<commit_before>﻿using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace Genetic.Problems
{
    /*
    * I would like to have an evolution algorithm solving sudoku problem.
    * Will use empty 9x9 sudoku board.
    * 
    * Chromosome is using sequence of numbers from 1 to 9 as a gene allowed values.
    * Length of genome will be fixed to number of slots in the 9x9 sudoku board.
    * Fitness will be calculated as a number of valid rows + number of valid cells + number of valid squares.
    * All standard sudoku rules apply (numbers must be distinct in each row, column and subsquare)
    * Mutation rate should be 0.5% and double-cut crossing should be applied.
    * For selection I would like to use 'tournament' strategy.
    * I would like population to be not bigger than 250 chromosomes per step.
    * 
    * It is expected that it will find sudoku solution before 100 evolution step.
    */
    [TestClass]
    public class SudokuProblem
    {
        [TestMethod]
        public void SolveSudokuProblem()
        {
        }
    }
}<commit_msg>Sudoku problem defined and added stub implementation of it proposing usage of the library<commit_after>﻿using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace Genetic.Problems
{
    /*
    * I would like to have an evolution algorithm solving sudoku problem.
    * Will use empty 9x9 sudoku board.
    * 
    * Chromosome is using sequence of numbers from 1 to 9 as a gene allowed values.
    * Length of genome will be fixed to number of slots in the 9x9 sudoku board.
    * Fitness will be calculated as a number of valid rows + number of valid cells + number of valid squares.
    * All standard sudoku rules apply (numbers must be distinct in each row, column and subsquare)
    * Mutation rate should be 0.5% and double-cut crossing should be applied.
    * For selection I would like to use 'tournament' strategy.
    * I would like population to be not bigger than 250 chromosomes per step.
    * 
    * It is expected that it will find sudoku solution before 100 evolution step.
    */
    [TestClass]
    public class SudokuProblem
    {       

        [TestMethod]
        public void SolveSudokuProblem()
        {
            var random = new RandomNumberGenerators.Default();

            var genePool = GenePool<int>();
            genePool.AddRange(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 });

            var chromosomeFactory = Chromosomes.SequentialChromosomeFactory<int>(random, genePool, 81); // chromosome as a sequence with 81 1-9 numbers
            var fitnessCalc = new SudokuFitnessCalculator();
            var mutationStrategy = MutationStrategies.SingleGeneMutation(random, 0.005); // mutation rate fixed to 0.5%
            var crossoverStrategy = CrossoverStrategies.DoubleCut(random);
            var selectionStrategy = SelectionStrategies.Tournament();
            var populationStrategy = PopulationStrategies.SinglePopulation(250); // size fixed to 250

            var evolution = new Evolution(random,
                chromosomeFactory,
                populationStrategy,
                mutationStrategy,
                crossoverStrategy,
                selectionStrategy);

            do
            {
                evolution.Step();
                if (evolution.TopFitness == 1.0)
                {
                    return;
                }
            }
            while (evolution.Generation < 100);
            Assert.Fail();
        }

        [TestMethod]
        public void ValiadateSudokuFitnessCalculator_WithSolvedSudoku()
        {
            SudokuFitnessCalculator calculator = new SudokuFitnessCalculator();
            int[] solvedSudokuNumbers = new int[] {
                8,3,5,   4,1,6,   9,2,7,
                2,9,6,   8,5,7,   4,3,1,
                4,1,7,   2,9,3,   6,5,8,

                5,6,9,   1,3,4,   7,8,2,
                1,2,3,   6,7,8,   5,4,9,
                7,4,8,   5,2,9,   1,6,3,

                6,5,2,   7,8,1,   3,9,4,
                9,8,1,   3,4,5,   2,7,6,
                3,7,4,   9,6,2,   8,1,5
            };
            var chromosome = Chromosomes.SequentialChromosome<int>(solvedSudokuNumbers);
            Assert.AreEqual(1.0, calculator.Calculate(chromosome));
        }

        [TestMethod]
        public void ValiadateSudokuFitnessCalculator_WithUnsolvedSudoku()
        {
            SudokuFitnessCalculator calculator = new SudokuFitnessCalculator();
            int[] unsolvedSudokuNumbers = new int[] {
                1,1,1,   1,1,1,   1,1,1,
                1,1,1,   1,1,1,   1,1,1,
                1,1,1,   1,1,1,   1,1,1,

                1,1,1,   1,1,1,   1,1,1,
                1,1,1,   1,1,1,   1,1,1,
                1,1,1,   1,1,1,   1,1,1,

                1,1,1,   1,1,1,   1,1,1,
                1,1,1,   1,1,1,   1,1,1,
                1,1,1,   1,1,1,   1,1,1
            };
            var chromosome = Chromosomes.SequentialChromosome<int>(unsolvedSudokuNumbers);
            Assert.AreEqual(0.0, calculator.Calculate(chromosome));
        }
    }

    private class SudokuFitnessCalculator : IFitnessCalculator<ISequentialChromosome<int>>
    {
        public double Calculate(ISequentialChromosome<int> chromosome)
        {
            if (chromosome.Length != 81)
            {
                throw new ArgumentOutOfRangeException("chromosome");
            }

            int targetSum = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9;
            int targetMul = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9;
            int[] columnSum = new int[9];
            int[] rowSum = new int[9];
            int[] squareSum = new int[9];
            int[] columnMul = new int[9];
            int[] rowMul = new int[9];
            int[] squareMul = new int[9];
            for (int i = 0; i < 9; i++)
            {
                columnMul[i] = 1;
                rowMul[i] = 1;
                squareMul[i] = 1;
            }

            int column = 0;
            int row = 0;
            int square = 0;
            for (int i = 0; i < chromosome.Length; i++)
            {
                column++;
                if (column >= 9)
                {
                    column = 0;
                    row++;
                }

                square = 3 * row % 3 + column % 3;
                
                rowSum[row] += chromosome[i];
                columnSum[row] += chromosome[i];
                squareSum[square] += chromosome[i];
                rowMul[row] *= chromosome[i];
                columnMul[row] *= chromosome[i];
                squareMul[square] *= chromosome[i];
            }

            int score = 0;
            foreach (int sum in columnSum)
                if (sum == targetSum)
                    score++;
            foreach (int sum in rowSum)
                if (sum == targetSum)
                    score++;
            foreach (int sum in squareSum)
                if (sum == targetSum)
                    score++;
            foreach (int mul in columnMul)
                if (mul == targetMul)
                    score++;
            foreach (int mul in rowMul)
                if (mul == targetMul)
                    score++;
            foreach (int mul in squareMul)
                if (mul == targetMul)
                    score++;
            double maxScore = 2 * (9 + 9 + 9);
            return score / maxScore;
        }
    }
}
{'fraction_non_alphanumeric': 0.09357277882797732, 'fraction_numerical': 0.03659195247096948, 'mean_word_length': 1.5763478260869566, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1986860', 'n_tokens_mistral': 2331, 'n_tokens_neox': 2073, 'n_words': 637}