dont ask me why, i dont know

knuth-plass.ps1

add-type -TypeDefinition @'
/// knuth plass c# implementation
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Knuth;
public static class LB
{
    // Efficient line length calculation (no 2D array)
    private static int GetLineLength(string[] words, int start, int end)
    {
        int len = -1;
        for (int i = start; i < end; i++)
            len += 1 + words[i].Length;
        return len;
    }

    // True Knuth-Plass: O(n^2) DP, but no 2D array, always produces output
    private static int[] FindBreaksKnuthPlass(string[] words, int width)
    {
        int n = words.Length;
        var cost = new double[n + 1];
        var breaks = new int[n + 1];
        for (int i = 0; i <= n; i++)
        {
            cost[i] = double.PositiveInfinity;
            breaks[i] = -1;
        }
        cost[0] = 0;
        for (int j = 1; j <= n; j++)
        {
            for (int i = 0; i < j; i++)
            {
                int lineLen = GetLineLength(words, i, j);
                bool singleLongWord = (j - i == 1) && (lineLen > width);
                double badness;
                if (lineLen > width && !singleLongWord)
                {
                    // Huge penalty for overfull lines (except for single long word)
                    badness = double.PositiveInfinity;
                }
                else if (lineLen > width && singleLongWord)
                {
                    // Allow single long word to overflow
                    badness = 0;
                }
                else
                {
                    badness = (j == n) ? 0 : Math.Pow(width - lineLen, 3);
                }
                if (cost[i] + badness < cost[j])
                {
                    cost[j] = cost[i] + badness;
                    breaks[j] = i;
                }
            }
        }
        // Always produce output, even if some breaks are -1
        for (int j = 1; j <= n; j++)
            if (breaks[j] == -1) breaks[j] = j - 1;
        return breaks;
    }

    // True Knuth-Plass: O(n^2) DP with 2D array for line lengths
    private static int[] FindBreaksKnuthPlass2D(string[] words, int width)
    {
        int n = words.Length;
        var cost = new double[n + 1];
        var breaks = new int[n + 1];
        for (int i = 0; i <= n; i++)
        {
            cost[i] = double.PositiveInfinity;
            breaks[i] = -1;
        }
        cost[0] = 0;
        // Precompute all line lengths
        int[,] lineLengths = new int[n, n];
        for (int i = 0; i < n; i++)
        {
            int len = -1;
            for (int j = i; j < n; j++)
            {
                len += 1 + words[j].Length;
                lineLengths[i, j] = len;
            }
        }
        for (int j = 1; j <= n; j++)
        {
            for (int i = 0; i < j; i++)
            {
                int lineLen = lineLengths[i, j - 1];
                bool singleLongWord = (j - i == 1) && (lineLen > width);
                double badness;
                if (lineLen > width && !singleLongWord)
                {
                    badness = double.PositiveInfinity;
                }
                else if (lineLen > width && singleLongWord)
                {
                    badness = 0;
                }
                else
                {
                    badness = (j == n) ? 0 : Math.Pow(width - lineLen, 3);
                }
                if (cost[i] + badness < cost[j])
                {
                    cost[j] = cost[i] + badness;
                    breaks[j] = i;
                }
            }
        }
        for (int j = 1; j <= n; j++)
            if (breaks[j] == -1) breaks[j] = j - 1;
        return breaks;
    }

    // Forced break at width (greedy, not justified, never overfull except for single long word)
    private static int[] FindBreaksForceWidth(string[] words, int width)
    {
        int n = words.Length;
        var breaks = new int[n + 1];
        breaks[0] = 0;
        int i = 0;
        while (i < n)
        {
            int lineLen = words[i].Length;
            int j = i + 1;
            if (lineLen > width) // single long word
            {
                breaks[i + 1] = i;
                i = i + 1;
                continue;
            }
            while (j < n && lineLen + 1 + words[j].Length <= width)
            {
                lineLen += 1 + words[j].Length;
                j++;
            }
            breaks[j] = i;
            i = j;
        }
        // Only fill missing breaks if not already set
        for (int k = 1; k <= n; k++)
            if (breaks[k] == 0 && k != 0) breaks[k] = breaks[k - 1];
        return breaks;
    }

    // Build lines from breakpoints
    private static List<(int start, int end)> BuildLines(int[] breaks, int n)
    {
        var lines = new List<(int, int)>();
        int k = n;
        while (k > 0)
        {
            int i = breaks[k];
            if (i < 0 || i > k) i = k - 1; // Defensive: never throw
            lines.Add((i, k));
            k = i;
        }
        lines.Reverse();
        return lines;
    }

    // Justify a line using indices, only if line is very close to width
    private static void JustifyLine(string[] words, int start, int end, int width, StringBuilder sb)
    {
        int totalWordLen = 0;
        for (int i = start; i < end; i++) totalWordLen += words[i].Length;
        int lineLen = totalWordLen + (end - start - 1); // spaces between words
        int gaps = end - start - 1;
        // Only justify if line is at least 95% of width and has more than 1 word
        if (gaps > 0 && lineLen >= width * 0.95)
        {
            int spacesNeeded = width - totalWordLen;
            int minSpaces = spacesNeeded / gaps;
            int extra = spacesNeeded % gaps;
            for (int i = start; i < end; i++)
            {
                sb.Append(words[i]);
                if (i < end - 1)
                {
                    int spaces = 1 + minSpaces + ((i - start) < extra ? 1 : 0);
                    sb.Append(' ', spaces);
                }
            }
        }
        else
        {
            // Ragged: single space between words
            for (int i = start; i < end; i++)
            {
                sb.Append(words[i]);
                if (i < end - 1) sb.Append(' ');
            }
        }
    }

    // Output a line with single spaces between words (no justification)
    private static void OutputLine(string[] words, int start, int end, StringBuilder sb)
    {
        for (int i = start; i < end; i++)
        {
            sb.Append(words[i]);
            if (i < end - 1) sb.Append(' ');
        }
    }

    // True Knuth-Plass, justified
    public static string KnuthPlassJustified(string input, int width)
    {
        var words = input.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
        int n = words.Length;
        var breaks = FindBreaksKnuthPlass(words, width);
        var lines = BuildLines(breaks, n);
        var sb = new StringBuilder();
        for (int lineNum = 0; lineNum < lines.Count; lineNum++)
        {
            var (start, end) = lines[lineNum];
            if (lineNum < lines.Count - 1)
                JustifyLine(words, start, end, width, sb);
            else
                sb.Append(string.Join(" ", words[start..end]));
            sb.AppendLine();
        }
        return sb.ToString().TrimEnd();
    }

    // True Knuth-Plass, justified, using 2D array
    public static string KnuthPlassJustified2D(string input, int width)
    {
        var words = input.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
        int n = words.Length;
        var breaks = FindBreaksKnuthPlass2D(words, width);
        var lines = BuildLines(breaks, n);
        var sb = new StringBuilder();
        for (int lineNum = 0; lineNum < lines.Count; lineNum++)
        {
            var (start, end) = lines[lineNum];
            if (lineNum < lines.Count - 1)
                JustifyLine(words, start, end, width, sb);
            else
                sb.Append(string.Join(" ", words[start..end]));
            sb.AppendLine();
        }
        return sb.ToString().TrimEnd();
    }

    // True Knuth-Plass, no justification (single spaces only)
    public static string KnuthPlassNoJustify(string input, int width)
    {
        var words = input.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
        int n = words.Length;
        var breaks = FindBreaksKnuthPlass(words, width);
        var lines = BuildLines(breaks, n);
        var sb = new StringBuilder();
        foreach (var (start, end) in lines)
        {
            OutputLine(words, start, end, sb);
            sb.AppendLine();
        }
        return sb.ToString().TrimEnd();
    }

    public static string KnuthPlass2DNoJustify(string input, int width)
    {
        var words = input.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
        int n = words.Length;
        var breaks = FindBreaksKnuthPlass2D(words, width);
        var lines = BuildLines(breaks, n);
        var sb = new StringBuilder();
        foreach (var (start, end) in lines)
        {
            OutputLine(words, start, end, sb);
            sb.AppendLine();
        }
        return sb.ToString().TrimEnd();
    }

    // Forced break at width, ragged right
    public static string ForceWidthBreaks(string input, int width)
    {
        var words = input.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
        int n = words.Length;
        var breaks = FindBreaksForceWidth(words, width);
        var lines = BuildLines(breaks, n);
        var sb = new StringBuilder();
        foreach (var (start, end) in lines)
        {
            sb.Append(string.Join(" ", words[start..end]));
            sb.AppendLine();
        }
        return sb.ToString().TrimEnd();
    }

    // Backward compatibility: main entry point
    public static string KnuthPlass(string input, int width, bool allowOverflow = true)
    {
        if (allowOverflow)
            return KnuthPlassJustified(input, width);
        else
            return ForceWidthBreaks(input, width);
    }

    // Main entry point with 2D array option
    public static string KnuthPlass2D(string input, int width, bool allowOverflow = true)
    {
        if (allowOverflow)
            return KnuthPlassJustified2D(input, width);
        else
            return ForceWidthBreaks(input, width);
    }
}
'@

function Test-KnuthPlass {
    [CmdletBinding()]
    param(
        [string]$Text,
        [int]$Width,
        [int]$TestRuns = 1000,
        [switch] $ShowOutput
    )
    $br = '-' * $Width
    $tests = @(
        @{ Name = 'KnuthPlass'; Script = { [Knuth.LB]::KnuthPlass($Text, $Width) } }
        @{ Name = 'KnuthPlassNoOverflow'; Script = { [Knuth.LB]::KnuthPlass($Text, $Width, $false) } }
        @{ Name = 'KnuthPlass2D'; Script = { [Knuth.LB]::KnuthPlass2D($Text, $Width) } }
        @{ Name = 'KnuthPlass2DNoOverflow'; Script = { [Knuth.LB]::KnuthPlass2D($Text, $Width, $false) } }
        @{ Name = 'KnuthPlassNoJustify'; Script = { [Knuth.LB]::KnuthPlassNoJustify($Text, $Width) } }
        @{ Name = 'KnuthPlass2DNoJustify'; Script = { [Knuth.LB]::KnuthPlass2DNoJustify($Text, $Width) } }
    )
    $results = foreach ($test in $tests) {
        $output = $null
        $times = foreach ($i in 1..$TestRuns) {
            (Measure-Command { $output = & $test.Script }).TotalMilliseconds
        }
        [PSCustomObject]@{
            Method    = $test.Name
            AvgTimeMs = [math]::Round(($times | Measure-Object -Average).Average, 2)
            Output    = $output
        }
    }

    $results | Sort-Object AvgTimeMs -Descending | Format-Table Method, AvgTimeMs
    if ($ShowOutput) {
        "`n--- Output Preview ---"
        foreach ($result in $results) {
            Write-Host "`n$($result.Method) [$($result.AvgTimeMs) ms]`n" -ForegroundColor Cyan
            Write-Host $br
            Write-Host $result.Output
            Write-Host $br
        }
    }
}
$str = 'Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industrys standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book. It has survived not only five centuries, but also the leap into electronic typesetting, remaining essentially unchanged.'

Test-KnuthPlass -Text $str -Width 80 -ShowOutput