<commit_before>﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace npuzzle
{
    class Program
    {
        private const string timerFormat = @"hh\:mm\:ss\.fff";
        private static Stopwatch timer;
        static ulong nodesEvaluated = 0;
        static ulong nodesExpanded = 1;

        static void Main(string[] args)
        {
            byte[] goalBytes = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
            ulong goal = GetStateKey(goalBytes);
            //byte[] initialBytes = { 14, 13, 15, 7, 11, 12, 9, 5, 6, 0, 2, 1, 4, 8, 10, 3 };
            byte[] initialBytes = { 14,1,9,6,4,8,12,5,7,2,3,0,10,11,13,15 };
            ulong initial = GetStateKey(initialBytes);
            timer = Stopwatch.StartNew();
            //var solution = AStar(initial, goal, ManhattanDistance);
            var solution = IDAStarDriver(initial, goal, ManhattanDistance);
            timer.Stop();
            if (solution.Length > 0)
            {
                PrintSolution(solution, Console.Out);
                if (args.Length > 0)
                {
                    using (var writer = new StreamWriter(args[0]))
                    {
                        PrintSolution(solution, writer);
                    }
                }
            }
            else
            {
                Console.WriteLine("\nNo solution possible.");
            }
        }

        static ulong GetStateKey(byte[] tiles)
        {
            ulong value = 0;
            for (int i = 0; i < 16; i += 1)
            {
                int shift = i * 4;
                ulong part = (ulong)tiles[i] << shift;
                value |= part;
            }
            return value;
        }

        static void PrintSolution(ulong[] solution, TextWriter writeLocation)
        {
            writeLocation.WriteLine("\nSolution found in {0} with a solution length of {1} steps!", timer.Elapsed.ToString(timerFormat), solution.Length - 1);
            foreach (var step in solution)
            {
                PrintState(step, writeLocation);
            }
        }

        static void PrintState(ulong state, TextWriter writeLocation)
        {
            const ulong mask = 0xf;
            for (int shift = 0; shift < 64; shift += 4)
            {
                ulong position = (state >> shift) & mask;
                writeLocation.Write("{0} ", position);
            }
            writeLocation.WriteLine();
        }

        private static readonly Stack<ulong> noSolution = new Stack<ulong>(); 
        private static uint nextBest;
        static ulong[] IDAStarDriver(ulong initialState, ulong goal, Func<ulong, uint> h)
        {
            nextBest = h(initialState);
            var bestPath = noSolution;
            while (bestPath == noSolution && nextBest != uint.MaxValue)
            {
                uint threshold = nextBest;
                nextBest = uint.MaxValue;
                bestPath = IDAStar(initialState, goal, 0u, threshold, h);
                Console.WriteLine();
            }
            return bestPath.ToArray();
        }
        static Stack<ulong> IDAStar(ulong current, ulong goal, uint cost, uint upperbound, Func<ulong, uint> h)
        {
            nodesEvaluated += 1;
            if (current == goal) return new Stack<ulong>(new[] { current });
            var successors = ExpandState(current);
            foreach (var successor in successors)
            {
                var newCost = cost + 1;
                var newF = newCost + h(current);
                if (newF > upperbound)
                {
                    if (newF < nextBest) nextBest = newF;
                }
                else
                {
                    var p = IDAStar(successor, goal, newCost, upperbound, h);
                    if (p != noSolution)
                    {
                        p.Push(current);
                        return p;
                    }
                }
            }
            var nextBestDisplay = nextBest == uint.MaxValue ? "inf" : nextBest.ToString();
            Console.Write("\rtime: {0}, upperbound: {1}, nextBest: {2}, eval: {3}     ", timer.Elapsed.ToString(timerFormat), upperbound, nextBestDisplay, nodesEvaluated);
            return noSolution;
        }

        static ulong[] AStar(ulong initialState, ulong goal, Func<ulong, uint> h)
        {
            var g = new Dictionary<ulong, uint> {{initialState, 0u}};
            var closed = new HashSet<ulong>();
            var open = new SimplePriorityQueue<ulong>();
            open.Push(initialState, g[initialState], h(initialState));
            var cameFrom = new Dictionary<ulong, ulong> {{ initialState, 0ul }};
            while (open.Count > 0)
            {
                nodesEvaluated += 1;
                var minCost = open.GetMinCost();
                var maxDistance = g.Max(m => m.Value);
                var current = open.Pop();
                if (current == goal)
                {
                    return ReconstructPath(cameFrom, goal);
                }
                closed.Add(current);
                uint successorGScore = g[current] + 1;
                var successors = ExpandState(current);
                foreach (var successor in successors)
                {<commit_msg>add breaks to show progress at improvements<commit_after>﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace npuzzle
{
    class Program
    {
        private const string timerFormat = @"hh\:mm\:ss\.fff";
        private static Stopwatch timer;
        static ulong nodesEvaluated = 0;
        static ulong nodesExpanded = 1;

        static void Main(string[] args)
        {
            byte[] goalBytes = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
            ulong goal = GetStateKey(goalBytes);
            //byte[] initialBytes = { 14, 13, 15, 7, 11, 12, 9, 5, 6, 0, 2, 1, 4, 8, 10, 3 };
            byte[] initialBytes = { 14,1,9,6,4,8,12,5,7,2,3,0,10,11,13,15 };
            ulong initial = GetStateKey(initialBytes);
            timer = Stopwatch.StartNew();
            //var solution = AStar(initial, goal, ManhattanDistance);
            var solution = IDAStarDriver(initial, goal, ManhattanDistance);
            timer.Stop();
            if (solution.Length > 0)
            {
                PrintSolution(solution, Console.Out);
                if (args.Length > 0)
                {
                    using (var writer = new StreamWriter(args[0]))
                    {
                        PrintSolution(solution, writer);
                    }
                }
            }
            else
            {
                Console.WriteLine("\nNo solution possible.");
            }
        }

        static ulong GetStateKey(byte[] tiles)
        {
            ulong value = 0;
            for (int i = 0; i < 16; i += 1)
            {
                int shift = i * 4;
                ulong part = (ulong)tiles[i] << shift;
                value |= part;
            }
            return value;
        }

        static void PrintSolution(ulong[] solution, TextWriter writeLocation)
        {
            writeLocation.WriteLine("\nSolution found in {0} with a solution length of {1} steps!", timer.Elapsed.ToString(timerFormat), solution.Length - 1);
            foreach (var step in solution)
            {
                PrintState(step, writeLocation);
            }
        }

        static void PrintState(ulong state, TextWriter writeLocation)
        {
            const ulong mask = 0xf;
            for (int shift = 0; shift < 64; shift += 4)
            {
                ulong position = (state >> shift) & mask;
                writeLocation.Write("{0} ", position);
            }
            writeLocation.WriteLine();
        }

        private static readonly Stack<ulong> noSolution = new Stack<ulong>(); 
        private static uint nextBest;
        static ulong[] IDAStarDriver(ulong initialState, ulong goal, Func<ulong, uint> h)
        {
            nextBest = h(initialState);
            var bestPath = noSolution;
            while (bestPath == noSolution && nextBest != uint.MaxValue)
            {
                uint threshold = nextBest;
                nextBest = uint.MaxValue;
                bestPath = IDAStar(initialState, goal, 0u, threshold, h);
                Console.WriteLine();
            }
            return bestPath.ToArray();
        }
        static Stack<ulong> IDAStar(ulong current, ulong goal, uint cost, uint upperbound, Func<ulong, uint> h)
        {
            nodesEvaluated += 1;
            if (current == goal) return new Stack<ulong>(new[] { current });
            var successors = ExpandState(current);
            foreach (var successor in successors)
            {
                var newCost = cost + 1;
                var newF = newCost + h(current);
                if (newF > upperbound)
                {
                    if (newF < nextBest) nextBest = newF;
                }
                else
                {
                    var p = IDAStar(successor, goal, newCost, upperbound, h);
                    if (p != noSolution)
                    {
                        p.Push(current);
                        return p;
                    }
                }
            }
            var nextBestDisplay = nextBest == uint.MaxValue ? "inf" : nextBest.ToString();
            Console.Write("\rtime: {0}, upperbound: {1}, nextBest: {2}, eval: {3}     ", timer.Elapsed.ToString(timerFormat), upperbound, nextBestDisplay, nodesEvaluated);
            return noSolution;
        }

        private static uint lastMinCost = 0;
        static ulong[] AStar(ulong initialState, ulong goal, Func<ulong, uint> h)
        {
            var g = new Dictionary<ulong, uint> {{initialState, 0u}};
            var closed = new HashSet<ulong>();
            var open = new SimplePriorityQueue<ulong>();
            open.Push(initialState, g[initialState], h(initialState));
            var cameFrom = new Dictionary<ulong, ulong> {{ initialState, 0ul }};
            while (open.Count > 0)
            {
                nodesEvaluated += 1;
                var minCost = open.GetMinCost();
                if (minCost > lastMinCost)
                {
                    Console.WriteLine();
                    lastMinCost = minCost;
                }
                var maxDistance = g.Max(m => m.Value);
                var current = open.Pop();
                if (current == goal)
                {
                    return ReconstructPath(cameFrom, goal);
                }
                closed.Add(current);
                uint successorGScore = g[current] + 1;
                var successors = ExpandState(current);
                foreach (var successor in successors)
                {
{'fraction_non_alphanumeric': 0.10350813082404531, 'fraction_numerical': 0.0179974419879408, 'mean_word_length': 1.4165562913907286, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 40, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2606119', 'n_tokens_mistral': 3108, 'n_tokens_neox': 2809, 'n_words': 785}