Gothic 1 Remake Lockpicker

GothicLockpicker.cs

using System.Collections;
using System.Diagnostics;

namespace GothicLockpicker;


public enum MovementDirection
{
    Left,
    Right,
}

public enum DependencyDirection
{
    None = 0,
    Same,
    Opposite
}

internal abstract class Program
{
    // current pin positions from front to back
    private static readonly int[] GateStates = [0, 0, 1, 1, 5, 4];
    
    // how other gates move when one gate is moved 
    private static readonly DependencyDirection[][] Dependencies = [
        [ DependencyDirection.Same, 0, 0, 0, DependencyDirection.Same, DependencyDirection.Opposite ],
        [ DependencyDirection.Opposite, DependencyDirection.Same, 0, DependencyDirection.Opposite, DependencyDirection.Same, DependencyDirection.Opposite ],
        [ 0, 0, DependencyDirection.Same, 0, 0, 0 ],
        [ 0, 0, DependencyDirection.Same,DependencyDirection.Same, 0, 0 ],
        [ 0, DependencyDirection.Same, DependencyDirection.Same, DependencyDirection.Opposite, DependencyDirection.Same, 0 ],
        [ 0, 0, 0, 0, 0, DependencyDirection.Same ]
    ];
    
    private static async Task Main()
    {
        var solver = new Solver(new Lock(GateStates, Dependencies));

        try
        {
            using var cts = new CancellationTokenSource();
            cts.CancelAfter(TimeSpan.FromSeconds(5));
            
            var sw = Stopwatch.StartNew();

            var solution = await solver.SolveAsync(cts.Token);

            sw.Stop();

            Console.WriteLine($"Time elapsed: {sw.ElapsedMilliseconds} ms");

            foreach (var step in solution)
            {
                Console.WriteLine($"State: [{string.Join(", ", step.CurrentState.GatePositions)}]; Move: {step.GateToMove}; Direction: {step.MovementDirection}");
            }
        }
        catch (OperationCanceledException)
        {
            Console.WriteLine("Solving took too long.");
        }
        catch (ArgumentException ex)
        {
            Console.WriteLine(ex.Message);
        }
    }
}

public record Lock(int[] GatePositions, DependencyDirection[][] Dependencies)
{
    public virtual bool Equals(Lock? other) =>
        other is not null && (ReferenceEquals(this, other) || GetHashCode() == other.GetHashCode());

    public override int GetHashCode()
    {
        var hash = 0;
        
        for (var i = 0; i < NumGates; i++)
        {
            hash = hash * 10 + GatePositions[i];
        }

        return hash;
    }

    public int NumGates { get; } = GatePositions.Length;
    
    public bool IsSolved => GatePositions.All(d => d == 3);
    public bool IsValid => !GatePositions.Any(d => d is < 0 or > 6);

    // move the gate into the given direction and apply dependencies; does not check validity!
    public Lock DoStep(int gateNumber, MovementDirection direction)
    {
        var newPositions = new int[NumGates];

        for (var i = 0; i < NumGates; i++)
        {
            newPositions[i] = Dependencies[gateNumber][i] switch
            {
                DependencyDirection.None => GatePositions[i],
                DependencyDirection.Same => GatePositions[i] + (direction == MovementDirection.Left ? 1 : -1),
                DependencyDirection.Opposite => GatePositions[i] + (direction == MovementDirection.Right ? 1 : -1),
                _ => throw new ArgumentOutOfRangeException(nameof(direction), direction, null)
            };
        }

        return new Lock(newPositions, Dependencies);
    }
}

[DebuggerDisplay("State: [{string.Join(\", \", CurrentState.GatePositions)}]; Move: {GateToMove}; Direction: {MovementDirection}")]
public record SolveStep(SolveStep? PreviousStep, Lock CurrentState, int GateToMove, MovementDirection MovementDirection)
    : IEnumerable<SolveStep>
{
    // each step has a reference to the previous step; make this easier to handle
    private class SolveStepEnumerator(SolveStep step) : IEnumerator<SolveStep>
    {
        private SolveStep? _current;

        public bool MoveNext()
        {
            _current = _current is null ? step : _current.PreviousStep;

            return _current is not null;
        }

        public void Reset() => _current = null;

        SolveStep IEnumerator<SolveStep>.Current => _current ?? throw new InvalidOperationException();
        object? IEnumerator.Current => _current;

        public void Dispose()
        {
        }
    }
    
    public IEnumerator<SolveStep> GetEnumerator() => new SolveStepEnumerator(this);
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

public class Solver(Lock lck)
{
    // all gate positions we've already reached somehow; to prevent loops
    private HashSet<Lock> AlreadyFoundStates { get; } = [];

    // next steps to test
    private Queue<SolveStep> StepQueue { get; } = new();

    // each gate might be moved left or right; enqueue those steps
    private void EnqueueNextSteps(SolveStep? previousStep, Lock l)
    {
        var lastGate = previousStep?.GateToMove ?? 0;
        
        // we want to move between gates as little as possible, so order them by distance
        var gates = Enumerable.Range(0, l.NumGates).OrderBy(g => Math.Abs(lastGate - g));
        
        foreach (var gateToMove in gates)
        {
            StepQueue.Enqueue(new SolveStep(previousStep, l, gateToMove, MovementDirection.Left));
            StepQueue.Enqueue(new SolveStep(previousStep, l, gateToMove, MovementDirection.Right));
        }
    }

    public Task<IEnumerable<SolveStep>> SolveAsync(CancellationToken cancellationToken = default) =>
        Task.Run(() => Solve(cancellationToken), cancellationToken);

    private IEnumerable<SolveStep> Solve(CancellationToken ct)
    {
        if (lck.IsSolved)
        {
            // wtf
            return [];
        }

        AlreadyFoundStates.Add(lck);
        EnqueueNextSteps(null, lck);

        // while there are steps left that have not been tried
        while (StepQueue.TryDequeue(out var step))
        {
            ct.ThrowIfCancellationRequested();

            var (_, l, gateNumber, direction) = step;

            if (l.DoStep(gateNumber, direction) is not { IsValid: true } newLock)
            {
                // step wasn't possible
                continue;
            }

            if (AlreadyFoundStates.Contains(newLock))
            {
                // (shorter) path to same state found before
                continue;
            }

            if (newLock.IsSolved)
            {
                // each step knows its predecessor, so reverse the list to start from the beginning
                return step.Reverse();
            }

            AlreadyFoundStates.Add(newLock);
            EnqueueNextSteps(step, newLock);
        }

        throw new ArgumentException("No solution found.");
    }
}