Logic maths problem

C

Cags

Contributor
Joined
Feb 19, 2004
Messages
695
Location
Melton Mowbray, England
I've recently been coding various logic puzzles and I've ran into a tricky problem. I need to take a number between 1 & 45 and work out which (unique) numbers between 1 & 9 can be added up to achieve this number. For example 17 can only be made using 8 & 9. Unfortunately I can't think of an efficient way of doing it.
 
C#: 
List<int> FindCrazyNumbers(int solution)
{
    if (solution < 1 || solution > 45) return null;
    List<int> ret = new List<int>();
    int sum = 0, add = 10;
    while (sum != solution)
        if (sum + --add <= solution)
        {
            sum += add;
            ret.Add(add);
        }
    return ret;
}
 
Thanks for the suggestion, thats an interesting solution however not quite appropriate. I guess its my fault really as I neglected to mention a critical part that was causing me trouble. Your method will alwas find the solution using the least amount of numbers wheras what I need is to find a solution with a specified amount of values. Using the example I gave before what I meant to say was that 17 with 2 values must be 8 + 9. But I might also need to produce 17 in 3 values (which could be quite a few things, (9,1,7),(9,2,6).... etc...
 
A solution

Just add a button and a listbox to your project and you can try this out.

Visual Basic: 
    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

        FindFactors(17, 3)

    End Sub


    Private Sub FindFactors(ByVal Sum As Integer, ByVal NumberOfFactors As Integer)

        Dim Factors(NumberOfFactors + 1) As Integer
        Dim i As Integer, j As Integer
        For i = 1 To NumberOfFactors Step 1
            Factors(i) = 9
        Next
        Factors(0) = 2
        Factors(NumberOfFactors) = 10

        Do While Factors(0) = 2
            If Factors(1) = 1 Then
                Exit Do
            End If
            For i = 1 To NumberOfFactors Step 1
                If Factors(i) = 1 Then
                    Factors(i - 1) -= 1
                    For j = i To NumberOfFactors Step 1
                        Factors(j) = Factors(i - 1)
                    Next
                    Exit For
                Else
                    If i = NumberOfFactors Then
                        Factors(i) -= 1
                    End If
                End If
            Next

            'Print correct answers
            Dim Suggestion As String = ""
            Dim AddUp As Integer = 0
            For j = 1 To NumberOfFactors Step 1
                AddUp = AddUp + Factors(j)
                Suggestion = IIf(j = 1, "", Suggestion & "+") & Factors(j)
                If j = NumberOfFactors Then
                    Suggestion = Suggestion & "=" & AddUp
                End If
            Next
            If AddUp = Sum Then
                ListBox1.Items.Add(Suggestion)
                Application.DoEvents()
            End If

        Loop


    End Sub

If you wanna see how it works you can comment out these two lines at the end and the program will print out all the possibilities it tries.

Visual Basic: 
            'If AddUp = Sum Then
            ListBox1.Items.Add(Suggestion)
            Application.DoEvents()
            'End If
 
Back
Top