How to resolve the algorithm Minimal steps down to 1 step by step in the C# programming language

Published on 12 May 2024 09:40 PM
#C_Sharp

How to resolve the algorithm Minimal steps down to 1 step by step in the C# programming language

Table of Contents

Problem Statement

Given: The goal is find the minimum number of steps necessary to reduce N down to one. At any step, the number may be:

There may be many ways to reduce the initial N down to 1. Your program needs to:

No divisors, D. a single subtractor of 1. Single divisor of 2; single subtractor of 1: Divisors 2 and 3; subtractor 1: Using the possible divisors D, of 2 and 3; together with a possible subtractor S, of 1: Using the possible divisors D, of 2 and 3; together with a possible subtractor S, of 2:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Minimal steps down to 1 step by step in the C# programming language

Overview:

This program solves a mathematical problem related to finding the minimum number of steps needed to reach a target number (goal) using only a set of divisors and subtractors. It generates a lookup table that stores the optimal steps for each number up to a specified limit, and prints out the results for various scenarios.

Key Concepts:

  • Divisors: Numbers that divide the target number without any remainder.
  • Subtractors: Numbers that can be subtracted from the target number.
  • Lookup Table: An array that stores the optimal step count and operation (division or subtraction) for each number up to a certain limit.

Implementation Details:

1. Initialization:

  • The program starts by defining the divisors and subtractors arrays, which contain specific numbers that will be used for the operations.
  • It creates a lookup table of length goal + 1, where goal is the specified limit.

2. Lookup Table Creation:

  • The CreateLookup method populates the lookup table with the optimal steps and operations for each number up to goal.
  • It iterates through each number from 2 to goal, starting with the values already in the table.
  • For each number n, it checks if division or subtraction using any of the given divisors or subtractors would lead to a smaller step count.
  • If so, it updates the lookup table entry for the target number with the new operation and step count.

3. Printing Results:

  • The PrintRange method prints out the optimal steps and operations for a specified range of numbers.
  • The PrintMaxMins method finds and prints the numbers that require the maximum and minimum number of steps.

4. Main Function:

  • The Main function calls CreateLookup with different goal limits and divisor/subtractor combinations.
  • It prints out the results and statistics for each scenario.

5. Helper Methods:

  • Delimit is a helper method that joins a collection of items into a comma-separated string.

Example Output:

Divisors: [2, 3], Subtractors: [1]
1 takes 0 steps:
2 takes 1 step: 2,/2=> 1
3 takes 1 step: 3,/3=> 1
4 takes 2 steps: 4,/2=> 2,/2=> 1
5 takes 2 steps: 5,/5=> 1
6 takes 2 steps: 6,/2=> 3,/2=> 1
7 takes 2 steps: 7,/7=> 1
8 takes 3 steps: 8,/2=> 4,/2=> 2,/2=> 1
9 takes 3 steps: 9,/3=> 3,/3=> 1
10 takes 3 steps: 10,/2=> 5,/2=> 2,/2=> 1
11 takes 3 steps: 11,/11=> 1

There are 6 numbers below 2000 that require 3 steps: 8, 9, 10, 11, 12, 18

Divisors: [2, 3], Subtractors: [2]
...
There is one number below 2000 that requires 3 steps: 6

Source code in the csharp programming language

using System;
using System.Collections.Generic;
using System.Linq;

public static class MinimalSteps
{
    public static void Main() {
        var (divisors, subtractors) = (new int[] { 2, 3 }, new [] { 1 });
        var lookup = CreateLookup(2_000, divisors, subtractors);
        Console.WriteLine($"Divisors: [{divisors.Delimit()}], Subtractors: [{subtractors.Delimit()}]");
        PrintRange(lookup, 10);
        PrintMaxMins(lookup);
        lookup = CreateLookup(20_000, divisors, subtractors);
        PrintMaxMins(lookup);
        Console.WriteLine();

        subtractors = new [] { 2 };
        lookup = CreateLookup(2_000, divisors, subtractors);
        Console.WriteLine($"Divisors: [{divisors.Delimit()}], Subtractors: [{subtractors.Delimit()}]");
        PrintRange(lookup, 10);
        PrintMaxMins(lookup);
        lookup = CreateLookup(20_000, divisors, subtractors);
        PrintMaxMins(lookup);
    }

    private static void PrintRange((char op, int param, int steps)[] lookup, int limit) {
        for (int goal = 1; goal <= limit; goal++) {
            var x = lookup[goal];
            if (x.param == 0) {
                Console.WriteLine($"{goal} cannot be reached with these numbers.");
                continue;
            }
            Console.Write($"{goal} takes {x.steps} {(x.steps == 1 ? "step" : "steps")}: ");
            for (int n = goal; n > 1; ) {
                Console.Write($"{n},{x.op}{x.param}=> ");
                n = x.op == '/' ? n / x.param : n - x.param;
                x = lookup[n];
            }
            Console.WriteLine("1");
        }
    }

    private static void PrintMaxMins((char op, int param, int steps)[] lookup) {
        var maxSteps = lookup.Max(x => x.steps);
        var items = lookup.Select((x, i) => (i, x)).Where(t => t.x.steps == maxSteps).ToList();
        Console.WriteLine(items.Count == 1
            ? $"There is one number below {lookup.Length-1} that requires {maxSteps} steps: {items[0].i}"
            : $"There are {items.Count} numbers below {lookup.Length-1} that require {maxSteps} steps: {items.Select(t => t.i).Delimit()}"
        );
    }

    private static (char op, int param, int steps)[] CreateLookup(int goal, int[] divisors, int[] subtractors)
    {
        var lookup = new (char op, int param, int steps)[goal+1];
        lookup[1] = ('/', 1, 0);
        for (int n = 1; n < lookup.Length; n++) {
            var ln = lookup[n];
            if (ln.param == 0) continue;
            for (int d = 0; d < divisors.Length; d++) {
                int target = n * divisors[d];
                if (target > goal) break;
                if (lookup[target].steps == 0 || lookup[target].steps > ln.steps) lookup[target] = ('/', divisors[d], ln.steps + 1);
            }
            for (int s = 0; s < subtractors.Length; s++) {
                int target = n + subtractors[s];
                if (target > goal) break;
                if (lookup[target].steps == 0 || lookup[target].steps > ln.steps) lookup[target] = ('-', subtractors[s], ln.steps + 1);
            }
        }
        return lookup;
    }

    private static string Delimit<T>(this IEnumerable<T> source) => string.Join(", ", source);
}

You may also check:How to resolve the algorithm Gamma function step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Determinant and permanent step by step in the J programming language
You may also check:How to resolve the algorithm Higher-order functions step by step in the Efene programming language
You may also check:How to resolve the algorithm Total circles area step by step in the Python programming language
You may also check:How to resolve the algorithm Sum of squares step by step in the Ruby programming language