none
Automating a math assignment from school RRS feed

  • Question

  • Today I got a very time consumimng math assignment. Here is the assignment:

    Let's say that a whole number is accepted if all of its numbers are in 2018. (For example: 22882800 is accepted, but 24 is not). How many positive whole numbers are accepted and less than or equal to 2018?

    Sorry if I transelated it poorly but I'm almost certain that that is what it would be like in english. But just in case I there are any swedish programmers out there that are willing to help out here is the original swedish version.

     Säg att ett heltal är aktuellt om alla dess siffror finns med i 2018 (t.ex. ¨ar 22882800 aktuellt, men 24 ¨ar inte aktuellt). Hur många positiva aktuella heltal är ≤ 2018?

    So basicaly to solve this problem on paper there is a lot of writing and I just whanted to see if I could solve it through a program that I wrote so that I didn't have to write too much. (Just a disclamer, I did solve the problem on paper and the correct answer is 135).

    The problem I'm having with writing this is that I don't know how to check if any of the numbers 1,2,8,0 are in the generated number. My idea was to just make a for loop that would add one number every time and if that number contained 1,2,8 or 0 it would be accepted and one would be added onto a variable. Kind of like this:

    namespace ConsoleApp1
    {
        class Program
        {
            static void Main(string[] args)
            {
                int HowManyNumbers;
    
                for (int i = 0, i < 2018,)
                {
                    i++;
    
                    if (i=__________)
                    {
                        HowManyNumbers++
    
                    }
                }
    
                Console.WriteLine(HowManyNumbers);
    
            }
        }
    }
    

    As you might have realised I'm pretty new to programming.   

    Tuesday, November 6, 2018 3:27 PM

All replies

  • This is not a programming task. It is a simple combinatorics question. It does not require enumerating all values and testing them.

    Hint: It's a kind of place-value system with a restricted set of symbols.


    Tuesday, November 6, 2018 5:11 PM
  • While Stefan is right, I do believe that it is still an interesting question and I wouldn't discount it.

    You do seem to be on the right track (at least as far as solving it in a brute force manner -- which given the restricted size of the input should be valid).

    There are many approaches, and this is probably not the fastest, but again, we are dealing with small numbers here.

                    if (TestNumber(i))
                    {
                        HowManyNumbers++
    
                    }
    private bool TestNumber(int i) {
        char[] chars i.ToString().ToCharArray();
        const string _2018 = "2018";
    
        foreach (char c in chars){
            if (!_2018.Contains(c))
                return false
        }
        return true;
    }
    (Note -- there are shorter solutions that use LINQ, but I am guessing you probably want more basics under you before you start LINQ).



    • Edited by SimonRev Tuesday, November 6, 2018 7:12 PM
    Tuesday, November 6, 2018 7:11 PM
  • To correct approach would be generating all possible numbers by the given alphbet and filtering for numbers smaller than 2018.

    This is even pretty simple, cause zero is part of the alphabet. Thus all permutations with redraw do it.

    Or a more computational approach as I already posted: position-valued system over an alphabet of four digits. Which is a simple map of 0->4^4 to the appropriate space.

    Tuesday, November 6, 2018 8:14 PM
  • @Stefan

    This is not a programming task. It is a simple combinatorics question. It does not require enumerating all values and testing them.

    Hint: It's a kind of place-value system with a restricted set of symbols.

     

    Ridiculous! How do you dare to say it is not a programming question?

    Do you happen to "calculate" all combinations by hand? If so, someone should tell you about a very very new electronic machine called... computer!   :S)

    P.S.: "hone" your fingers, and post some code...!


    • Edited by ritehere44 Thursday, November 8, 2018 2:47 AM missing image
    Tuesday, November 6, 2018 11:08 PM
  • @Stefan

    To correct approach would be generating all possible numbers by the given alphbet and filtering for numbers smaller than 2018.

    This is even pretty simple, cause zero is part of the alphabet. Thus all permutations with redraw do it.

    Or a more computational approach as I already posted: position-valued system over an alphabet of four digits. Which is a simple map of 0->4^4 to the appropriate space.

    >> To correct approach would be generating all possible numbers by the given alphbet and filtering for numbers smaller than 2018. 

    REALLY?

    So, "hone" your fingers and post some code...


    • Edited by ritehere44 Thursday, November 8, 2018 2:48 AM missing image
    Tuesday, November 6, 2018 11:11 PM
  • I believe Stefan is correct; the correct number of ints meeting the requirements stated above can be determined analytically,

    I THINK that can be determined by observing that
    a) the format is up to 4 digits.
    b) the range is 0 - 2018, inclusive.

    Consequently, I THINK that can be expressed as 0.4^3 * 2018 + 0.4 * 18;

    However, AinP mentioned that he knew, and had found, the answer analytically, but wanted to see how it might look as code.   I suggest the following …..

                int count = 0;
                for (int i = 0; i < 2019; i++)   // 2019 'cuz the range is 0 - 2018, inclusive
                   if (!Regex.IsMatch(i.ToString(), "[^2018]")) count++;

    Wednesday, November 7, 2018 3:47 AM
  • Hi AinP,

    Thank you for posting here.

    For your question, please try the code below.

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace test1
    {
        class Program
        {
            static void Main(string[] args)
            {
                string n2018 = "2018";
                int m1 = 0;
                for (int i = 0; i < 2018; i++)
                {
                    char[] m = i.ToString().ToCharArray();
                    int count = 0;
                    
                    for (int j = 0; j < m.Length; j++)
                    {
                        if(!n2018.Contains(m[j]))
                        {
                            break;
                        }
                        else
                        {
                            count++;
                        }
                        if(m.Length==count)
                        {
                            Console.WriteLine(i);   //You can output all the eligible numbers here.
                            m1++;
                        }                    
                    }
                    
                }
                Console.WriteLine(m1);     //You can output the count of eligible conditions
                Console.ReadKey();
            }
           
    
        }
    }
    

    Best Regards,

    Wendy


    MSDN Community Support
    Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com.

    Wednesday, November 7, 2018 7:38 AM
    Moderator
  • Hi Wendy.

    Just a quickie comment if I may .…

    I can't help but wonder if, in your "for" statement, that the clause "I < 2018" should be "I <= 2018". It would give a different answer, but it might be more in line with AinP's statement "How many positive whole numbers are accepted and less than or equal to 2018?"

    Wednesday, November 7, 2018 2:01 PM
  • Since when do we complete homework??
    Wednesday, November 7, 2018 2:53 PM
  • Since when do we complete homework??

    The deadline for the homework is past, and you haven't presented your code.

    BTW, are you suggesting to enumerate all values from 0 up to 2018?

    This is very inneficient, as I demonstrate rite now:

    1) The number in question has exactly 4 digits (i.e., the length is 4).
    2) This means that any number part of the solution has length 4, and each digit can be, only, 1 of the 4 digits that compose the original number: either 2, or 0, or 1 or 8.
    3) Therefore, the total number of combinations is: 4 * 4 * 4 * 4 = 256

    First Corollary: iterating over all values from 0 up to 2018 is an intellectual fragile solution, because the above shows that 256 iterations (at most) is sufficient (because 0 is 1 of the digits).
    Percentually, we can say that iterating over all values from 0 up to 2018 is 788.28 % worse.

    4) Additionally, considering the requirement that any number part of the solution do not be greater than the original, we can subtract from the total 256 iterations, those iterations where the most significant digit is greater than 2 (in this case).
    5) For the number in question, it is unnecessary to iterate when the most significant digit is 8, decreasing the total number of iterations to 256 * 3 / 4 = 192.

    Second Corollary: the previous optimization can be further optimized, avoiding iterations for the most significant digit greater than the corresponding digit in the original number.

    Conclusion: the total number of combinations is upper limited to 192.

    As another example, just suppose the number in question would be 7089 (and not 2018): your method would require 7,089 iterations, while mine would require the same 192 iterations!

    P.S.: if the number in question has no 0 digit, the method above requires a bit of extra code.

    Thursday, November 8, 2018 2:43 AM
  • using System;
    namespace Example
    {
        public class Program
        {
            public static void Main(string[] args)
            {
                string number=2018.ToString(); // any 4 digit number with one 0 digit, at least
                for(int total=0,len=number.Length,i=0;i<len;++i)
                {
                    if(number[i]>number[0])continue;
                    bool equal=number[i]==number[0];
                    for(int j=0;j<len;++j)for(int k=0;k<len;++k)for(int m=0;m<len;++m)
                    {
                        string s=""+number[i]+number[j]+number[k]+number[m];
                        if(equal&&s.CompareTo(number)==1)continue;
                        Console.WriteLine("{0:D3} : {1}",++total,s);
                    }
                }
                
                Console.WriteLine("\nHello, world!");
            }
        }
    }

    A total of 136 numbers are part of the solution.



    • Edited by ritehere44 Thursday, November 8, 2018 2:52 AM continue
    Thursday, November 8, 2018 2:46 AM
  • Your math is as good as your code:

    It's place value system of a restircted alphatbet {0, 1, 2, 8}. As 0 is part if the alphabet, there are exactly 4^4 numbers possible. As a developer you have immeditaly seen that this is equal to 2^8 or 256.
    How many of them are lesser or equal to 2018?

    I. 2*4*4*4 numbers are lesser than 2000. Cause the first digit can be only {0,1}.

    II. The numbers greater or equal 2000 and lesser or equal 2018 are - as the first two digitis are fix and the third digit can only be {0,1} from 1*1*2*4.

    I.+II. => 2*4*4*4 + 1*1*2*4 = 128 + 8 = 136 numbers are lesser or equal then 2018.


    Thursday, November 8, 2018 3:28 PM
  • Nice try..

    namespace ConsoleCS
    {
        using System;
        using System.Linq;
    
        public class Program
        {
            public static void Main(string[] args)
            {
                Ritehere(1000);
                NumberTest(1000);
    
                Console.WriteLine("\nDone.");
                Console.ReadLine();
            }
    
            private static void Ritehere(int numberMustContainZero)
            {
                string number = numberMustContainZero.ToString(); // any 4 digit number with one 0 digit, at least
                for (int total = 0, len = number.Length, i = 0; i < len; ++i)
                {
                    if (number[i] > number[0])
                    {
                        continue;
                    }
    
                    bool equal = number[i] == number[0];
                    for (int j = 0; j < len; ++j)
                    {
                        for (int k = 0; k < len; ++k)
                        {
                            for (int m = 0; m < len; ++m)
                            {
                                string s = "" + number[i] + number[j] + number[k] + number[m];
                                if (equal && s.CompareTo(number) == 1)
                                {
                                    continue;
                                }
    
                                Console.WriteLine("{0:D3} : {1}", ++total, s);
                            }
                        }
                    }
                }
            }
    
            private static void NumberTest(int numberMustContainZero)
            {
                char[] alphabet = numberMustContainZero.ToString().ToCharArray();
                Array.Sort(alphabet);
                char[] distinctAlphabet = alphabet.Distinct().ToArray();
                int numberOfDigits = alphabet.Length;
                int upperBoundary = (int)Math.Pow(alphabet.Length, numberOfDigits);
                for (int count = 0; count < upperBoundary; count++)
                {
                    int generatedNumber = IntToBase(count, distinctAlphabet);
                    if (generatedNumber > numberMustContainZero)
                    {
                        break;
                    }
    
                    Console.WriteLine($"{count + 1}: {generatedNumber}");
                }
            }
    
            private static int IntToBase(int value, char[] baseDigits)
            {
                int bufferSize = 32;
                char[] buffer = new char[bufferSize];
                int targetBase = baseDigits.Length;
                do
                {
                    buffer[--bufferSize] = baseDigits[value % targetBase];
                    value = value / targetBase;
                }
                while (value > 0);
    
                char[] result = new char[32 - bufferSize];
                Array.Copy(buffer, bufferSize, result, 0, 32 - bufferSize);
                return int.Parse(new string(result));
            }
        }
    }


    Thursday, November 8, 2018 5:59 PM
  • @Stefan

    As no solution is really a solution without the elegance of LINQ, here's my version of a solution implemented in LINQ:

    var qry=
        from num in new[]{"2018"}
        from w in num where w<=num[0] from x in num from y in num from z in num
        let n=""+w+x+y+z where n.CompareTo(num)<1
        select n
        ;
    

    Isn't it beautiful? And simple? And small? And elegant?

    It can be iterated with this complement:

    int total=0;
    foreach(string item in qry)
        Console.WriteLine("{0:D3} : {1}",++total,item);
    

    Friday, November 9, 2018 10:12 PM
  • P.S.: I'm not surprised that

    and

    have not posted any solution, although I'm pretty sure their code would compile!

                ... but would not do what they'd have planned it to do...  :(

    Friday, November 9, 2018 10:18 PM
  • Nice.

    Any idea how to allow numbers like 1000 to be tested? That's why I used LINQ (just being lazy) to generate a distinct set {0,1} of digits.

    Friday, November 9, 2018 10:31 PM
  •         private static void BubbleSortedCharacterArrayCombinatorMethodWithoutLinq(int numberMustContainZero)
            {
                var unique = new List<char>();
                var chars = numberMustContainZero.ToString().ToCharArray();
                foreach (var c in chars)
                    if (!unique.Contains(c))
                        unique.Add(c);
                chars = unique.ToArray();
                var done = false;
                while(!done) 
                {
                    done = true;
                    for (var i = 0; i < chars.Length - 1; i++)
                        if (chars[i] > chars[i + 1])
                        {
                            char c = chars[i];
                            chars[i] = chars[i + 1];
                            chars[i + 1] = c;
                            done = false;
                        }
                }
                var count = 1;
                foreach (var a in chars)
                    foreach (var b in chars)
                        foreach (var c in chars)
                            foreach (var d in chars)
                            {
                                var str = "" + a + b + c + d;
                                if (Int32.Parse(str) > numberMustContainZero)
                                    return;
                                Console.WriteLine($"{count++}: {str}");
                            }
            }


    math assignment from school should look like math assignment from school...
    • Edited by DerChris88 Saturday, November 10, 2018 12:05 AM
    Friday, November 9, 2018 11:32 PM
  • math assignment from school should look like math assignment from school...

    ..what I mean is give the teacher some work to do by reviewing it:

            private static void BloatedBubbleSortedCharacterArrayCombinatorMethodWithoutLinq(int numberMustNOTContainZero)
            {
                var unique = new List<char>();
                var chars = numberMustNOTContainZero.ToString().ToCharArray();
                var length = chars.Length;
                var containsNull = false;
                foreach (var c in chars)
                    if (!unique.Contains(c))
                    {
                        unique.Add(c);
                        if (c == '0')
                            containsNull = true;
                    }
                chars = unique.ToArray();
                var done = false;
                while(!done) 
                {
                    done = true;
                    for (var i = 0; i < chars.Length - 1; i++)
                        if (chars[i] > chars[i + 1])
                        {
                            char c = chars[i];
                            chars[i] = chars[i + 1];
                            chars[i + 1] = c;
                            done = false;
                        }
                }
                var count = 1;
                char[] result = new char[length];
                int[] slots = new int[length];
                var tst = 0;
                for (int i = 0; i < length; i++)
                    slots[i] = containsNull ? 0 : -1;
                if (containsNull)
                {
                    slots[0] = -1;
                    tst = (int)Math.Pow(length, chars.Length) - 1;
                }
                else
                    for (int i = 1; i <= chars.Length; i++)
                        tst += (int)Math.Pow(length, i);
                for (int j = 0; j < tst; j++)
                    for (int k = 0; k <= length; k++)
                    {
                        if (k == 0)
                            slots[0]++;
                        else if (k < length)
                        {
                            if (slots[k - 1] >= chars.Length)
                            {
                                slots[k - 1] = 0;
                                slots[k]++;
                            }
                        }
                        else
                        {
                            for (int l = 0; l < length; l++)
                                if (slots[l] == -1)
                                    result[l] = '\0';
                                else
                                    result[l] = chars[slots[l]];
                            for (int l = 0; l< result.Length/2;l++)
                            {
                                var i = result[l];
                                result[l] = result[result.Length - 1 - l];
                                result[result.Length - 1 - l] = i;
                            }
                            int ii = 0;
                            while (result[ii] == '0' && ii < result.Length - 1) result[ii++] = '\0';
                            var str = new String(result).Replace("\0", "");
                            if (str == "")
                                str = "0";
                            if (Int32.Parse(str) > numberMustNOTContainZero)
                                return;
                            Console.WriteLine($"{count++}: {str}");
                        }
                    }
            }


    • Edited by DerChris88 Saturday, November 10, 2018 11:50 PM
    Saturday, November 10, 2018 11:41 PM
  • Nice.

    Any idea how to allow numbers like 1000 to be tested? That's why I used LINQ (just being lazy) to generate a distinct set {0,1} of digits.

    Numbers like 1000 are correctly processed, out-of-the-box; i.e., every number (as string type) outputted by the computational routine is part of the solution, and every number that must be part of the solution is outputted by the computational routine.

    Numbers duplicity can be eliminated as usual, through grouping. In the LINQ version, it means adding just it, group:

    var qry=
        from num in new[]{"1000"}
        from w in num where w<=num[0] from x in num from y in num from z in num
        let n=""+w+x+y+z where n.CompareTo(num)<1
        group n by n into g
        select g.Key
        ;
    

    Sunday, November 11, 2018 9:30 PM