5
\$\begingroup\$

It is a single-player game. In the beginning, there is a row of integers. In one move the player can take a certain amount of adjacent numbers (let's denote it T). Then the player's points increase with the sum of the chosen numbers. The player can take S moves at most. The goal is to determine the maximum points that can be reached and we have to give the specific moves to reach it.

Example

The numbers: 1 6 8 7 6 2 1 8
S = 2 (max moves)
T = 3 (adjacent numbers to take in one move)

The max points is 32, it can be done like this: 1 6 8 7 6 2 1 8 (we take the bold numbers)
So the two moves are 2 and 6 (they indicate start indexes in the row)
I wrote a recursive code in c# that works if we have few numbers, but takes too long if e.g. has 3000 numbers, 100 max moves and T = 20.

My idea is to first count the points we will get for each number. Then try every possible combination, and store the one that gives me the most points.
So my question is how it can be made it faster?

class Value
{
    public int idx = -1;
    public int num = -1;
    public Value(int idx, int num)
    {
        this.idx = idx;
        this.num = num;
    }
}

class Program
{
    const int N = 8;
    static int S = 2;
    static int T = 3;
    static int[] numbers = new int[N] { 1, 6, 8, 7, 6, 2, 1, 8 };
    static List<Value> values = new List<Value>();
    static int maxPoint = -1;
    static List<Value> result;

    static void Main(string[] args)
    {
        CountInitValues();
        Solve(values, new List<Value>(), 0, T);
    }

    static void Solve(List<Value> remaining, List<Value> numSoFar, int pointSoFar, int StepsRemain)
    {
        if (remaining.Count == 0 || StepsRemain == 0)
        {
            if (pointSoFar > maxPoint)
            {
                maxPoint = pointSoFar;
                result = new List<Value>(numSoFar);
            }
        }
        else
        {
            List<Value> newNum = new List<Value>(numSoFar);
            for (int i = 0; i < remaining.Count; i++)
            {
                List<Value> newRemaining = new List<Value>();
                newNum.Add(remaining[i]);
                newRemaining.AddRange(remaining.Take(i - T));
                newRemaining.AddRange(remaining.Skip(i + T));
                int ujPont = pointSoFar + remaining[i].num;
                int ujLepes = StepsRemain - 1;
                Solve(newRemaining, newNum, ujPont, ujLepes);
                newNum.RemoveAt(newNum.Count - 1);
            }
        }
    }

    static void CountInitValues()
    {
        for (int i = 0; i < N - T + 1; i++)
        {
            int newValue = 0;
            for (int j = 0; j < T; j++)
            {
                newValue += numbers[i + j];
            }
            Value ee = new Value(i, newValue);
            values.Add(ee);
        }
    }
}
\$\endgroup\$
4
\$\begingroup\$

Some general points

The code looks good, and the steps you take to calculate the result are sound. I would like to mention a few general points for reviewing the code, then move on to some tips that could improve the code.

Include usings

This helps others when reviewing the code.

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

Include the results when you run the program

This also helps reviewing, but more importantly: it helps you testing. Pressing "Run" and seeing what the results are is quicker than attaching the debugger and needing a break point to check.

class Value
{
    // ...
    public override string ToString() { return $"({idx}, {num})"; }
}

static void Main(string[] args)
{
    CountInitValues();
    Solve(values, new List<Value>(), 0, T);
    System.Console.Out.WriteLine ("The result is: {0}", string.Join(", ", result.Select(i => i.ToString())));
}

Names

Use descriptive names for fields and variables with large scopes

Example: N, S and T are clear if you have the problem description at hand, but not when you are looking at them in the code itself. You could change them to numbers, maxMoves and numbersToTake, so that their meaning is clear at one glance.

Write smaller functions

This helps readability, and especially in the case of Solve(), this could make it more clear what the code is doing. An example:

Split CountInitValues()

static void CountInitValues()
{
    for (int i = 0; i < N - T + 1; i++)
    {
        Value ee = new Value(i, CountValuesFrom(i));
        values.Add(ee);
    }
}

static int CountValuesFrom(int startIndex)
{
    int newValue = 0;
    for (int j = 0; j < T; j++)
    {
        newValue += numbers[startIndex + j];
    }
}

Bug

You use T for the number of steps, instead of S

This gives no different result in the example, because after 2 steps, you can't take another set of 3 values any more. But in different sets, this will give false results.

Solve(values, new List<Value>(), 0, T);

should be

Solve(values, new List<Value>(), 0, S);

An Object Oriented issue

Solver can be a separate class with non-static fields

If you extract a class Solver, and use non-static fields, you can create more of them in a testing method (or in Main()), give them different values to calculate results, and test those results.

class Solver
{
    int N;
    int S;
    int T;
    int[] numbers;

    List<Value> values = new List<Value>();
    int maxPoint = -1;
    List<Value> result;

    public Solver(int N, int S, int T, int[] numbers)
    {
        this.N = N;
        this.S = S;
        this.T = T;
        this.numbers = numbers;
    }

    public List<Value> Run()
    {
        CountInitValues();
        Solve(values, new List<Value>(), 0, S);
        return result;
    }

    void Solve(List<Value> remaining, List<Value> numSoFar, int pointSoFar, int StepsRemain)
    {
        // ...
    }

    void CountInitValues()
    {
        // ...
    }
}

You can call the test like this, then:

class Program
{
    const int N = 8;
    static int S = 2;
    static int T = 3;
    static int[] numbers = new int[N] { 1, 6, 8, 7, 6, 2, 1, 8 };

    static void Main(string[] args)
    {
        var result = new Solver(N, S, T, numbers).Run();
        System.Console.Out.WriteLine ("The result is: {0}", string.Join(", ", result.Select(i => i.ToString())));
    }
}

But also like this:

class Program
{
    const int N = 8;
    static int S = 2;
    static int T = 3;
    static int[] numbers = new int[N] { 1, 6, 8, 7, 6, 2, 1, 8 };

    static void Main(string[] args)
    {
        var result = new Solver(N, S, T, numbers).Run();
        System.Console.Out.WriteLine ("The result for S = 2, T = 3 is: {0}", string.Join(", ", result.Select(i => i.ToString())));
        result = new Solver(N, 3, 2, numbers).Run();
        System.Console.Out.WriteLine ("The result for S = 3, T = 2 is: {0}", string.Join(", ", result.Select(i => i.ToString())));
    }
}

Optimizing the algorithm

It does not matter in which order you take groups

If you pick numbers from indices (2, 3, 4), and then from indices (6, 7, 8), you will get the same result as when you first pick (6, 7, 8) and then (2, 3, 4). Also, when picking (1, 2, 3) then (4, 5, 6), you already have the same number of points as when picking (2, 3, 4) and then (1, 5, 6).

Knowing this, you can skip tests that try to take numbers from the left of where you took numbers:

void Solve(/*...*/)
{
    List<Value> newRemaining = new List<Value>();
    newNum.Add(remaining[i]);
    newRemaining.AddRange(remaining.Take(i - T));
    newRemaining.AddRange(remaining.Skip(i + T));
}

can now be

void Solve(/*...*/)
{
    List<Value> newRemaining = new List<Value>();
    newNum.Add(remaining[i]);
    newRemaining.AddRange(remaining.Skip(i + T));
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.