Thread: Machine Learning Algorithm in C

  1. #1
    Registered User
    Join Date
    Feb 2019
    Posts
    3

    Machine Learning Algorithm in C

    Hey guys! I am really glad that I discovered this forum when I began programming.

    However, I was recently given a homework assignment that I have some hard time coping with. Here are the instructions:

    Several cells are arranged one after the other in a straight line. In i-th cell, a given integer ai is written (i=1,2, , N). I start from the first cell at the left end and move right; I can choose to jump into the next cell, or into the next of the next cell. Every time I entered a cell i, I have to pay | ai | dollars, when ai is negative, or to receive ai dollars, when ai is nonnegative. At most, how many dollars can I earn?

    Input: Integer values of N, a1, a2, ., aN, separated by spaces.

    Output: One integer equals to the wanted profit.

    Constraints: 0 < N < 100; -100 < ai < 100 for each ai

    Example

    Input
    7 2 -1 3 2 -1 6 -5
    Output
    10

    I tried several approaches, but the best I got after the test checks on the submission page is 5/10. I soon realized my algorithm is frankly a mess. I am posting below my latest solution and would be happy if you can help me out with some tips or guidelines.

    Code:
    #include <stdio.h>
    int main()
    {
         int n,array[100];
         int i = 0;
         int sum = 0;
    
    
         if(scanf("%d",&n)){};
         for(i=0;i<n;i++){
            if(scanf("%d",&array[i])){}
         }
    
         for(i=0;i<n;i++)
         {
             if(array[i] >= 0)
             {
                sum += array[i];
             }
             else if(array[i] < 0 && array[i+1] < 0)
             {
                 if(array[i] > array[i+1])
                 {
                    sum += array[i];
                 }
                 else if(array[i] <= array[i+1])
                 {
                     sum += array[i+1];
                     i++;
                 }
             }
         }
    
         printf("%d", sum);
    
         return 0;
    }


  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,529
    Was the example provided by your instructor? I don't see how the optimal result is 10. It looks like it should be 12: 7 + 2 + (skip -1) 3 + (skip -2) -1 + 6 + -5 = 12

    Also, is there a reason why you titled this post "Machine Learning Algorithm in C"? This isn't a machine learning algorithm.

    EDIT:
    Looking at your code, I think you may need a more sophisticated approach (dynamic programming?) to deal with runs of negative numbers. For example, consider: -1 -3 -4 -1. The optimal path through this is to skip the first -1, pick -3, then skip -4 to pick -1, thus ending up with a total of -4. If you only consider pairs, you'll pick -1, then -3, then -1, resulting in the suboptimal -5 total.
    Last edited by laserlight; 02-05-2019 at 04:29 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Feb 2019
    Posts
    3
    Quote Originally Posted by laserlight View Post
    Was the example provided by your instructor? I don't see how the optimal result is 10. It looks like it should be 12: 7 + 2 + (skip -1) 3 + (skip -2) -1 + 6 + -5 = 12

    Also, is there a reason why you titled this post "Machine Learning Algorithm in C"? This isn't a machine learning algorithm.
    Thank you for the reply, laserlight!

    1. The first integer from the input indicates the number of digits(N) in the array to follow. You are also allowed to skip the first and last numbers( skip -5). The output is indeed 10, but my instructor is definitely not making this easy for a high-school level student.

    2. It seems to me that if you dig into it, to provide the correct answer the algorithm must analyze the whole array and pick the optimal path, which is what I always thought machine learning consisted of.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,529
    Quote Originally Posted by Curious_student
    1. The first integer from the input indicates the number of digits(N) in the array to follow. You are also allowed to skip the first and last numbers( skip -5). The output is indeed 10, but my instructor is definitely not making this easy for a high-school level student.
    Ah, I see. My mistake.

    Quote Originally Posted by Curious_student
    2. It seems to me that if you dig into it, to provide the correct answer the algorithm must analyze the whole array and pick the optimal path, which is what I always thought machine learning consisted of.
    That is not "machine learning" in the sense as it is currently used in computer science. Broadly speaking, machine learning involves getting machines to analyse data so as to make decisions that are as optimal as possible to what humans want when presented with similiar data that the machine has not previously encountered. You could use a machine learning approach here, but as your instructor does not appear to have provided you with a training set, that seems unlikely especially if the instructor did not mention machine learning to you.

    As I mentioned in my edit to my previous post, you probably do need a more sophisticated approach than just comparing pairs of adjacent negative numbers, and my suggestion was to look into dynamic programming.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    593
    Machine learning refers to algorithms that learn from experience. It has nothing to do with your problem. Your problem is an optimization problem.

    It looks like it can be solved "greedily". This is where you take the best answer at each step. For your given problem the first step is either 2 or -1, so you take 2. Then you can either take -1 or 3, so you take 3 (total 5). Then between -2 and -1, -1 is best (total 4). Then between 6 and -5, 6 is best (total 10). Then between -5 and the end, the end is best. Total 10.

    I'm not sure about this, though, but I can't think of a counter-example. If it can't be solved greedily then "dynamic programming" will certainly solve it since it has both optimal substructure and repeated subproblems. Brute force will not work well on large inputs since the number of possible paths grows exponentially.
    Let him who is not come to logic be plagued with continuous and everlasting filth.
    - John of Salisbury, 1160

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,529
    john.c, that is the approach that Curious_student tried, and I already provided a counter-example in post #2: -1 -3 -4 -1
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    593
    Oh, right. I obviously didn't read very closely ... at all.

    Maybe an approach that considered the values in groups of 4 would work, although a full dynamic programming solution wouldn't be that difficult. You could work backwards figuring out the optimal solution at each point. So for your example:
    Code:
    . 1  2  3  4
     -1 -3 -4 -1
     
       val  opt
    5:  0    0    after the last position counts as 0
    4: -1   -1    if we are here, the best result is -1
    3: -4   -4    if we are here, the best result is -4 (skip 4th element)
    2: -3   -4    if we are here, the best result is -4 (skip 3rd element)
    1: -1   -5    if we are here, the best result is -5 (go to 2 or 3)
    0:  0   -4    before first position counts as 0; best result here is best result overall
    Superficially this resembles a backwards greedy selection, but it's actually choosing optimally at each point so, due to the problem's optimal substructure, it results in an optimal overall solution. This is what I thought of first but due to the superficial resemblance I jumped to the conclusion that it was actually greedy.

    You can see the repeating subproblems (and convince yourself of the optimal substructure) in this diagram for 4 elements:
    Code:
    .                ________O________
                    /                 \
               ____1____             __2__
              /         \           /     \
           __2__         3         3       4
          /     \       / \       / \      |
         3       4     4   X     4   X     X
        / \      |     |         |
       4   X     X     X         X
       |
       X
    Last edited by john.c; 02-05-2019 at 06:59 PM. Reason: changed best result -1 to -4 for element 3
    Let him who is not come to logic be plagued with continuous and everlasting filth.
    - John of Salisbury, 1160

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,036
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  9. #9
    Registered User
    Join Date
    Feb 2019
    Posts
    3
    Quote Originally Posted by john.c View Post
    Oh, right. I obviously didn't read very closely ... at all.

    Maybe an approach that considered the values in groups of 4 would work, although a full dynamic programming solution wouldn't be that difficult. You could work backwards figuring out the optimal solution at each point. So for your example:
    Code:
    . 1  2  3  4
     -1 -3 -4 -1
     
       val  opt
    5:  0    0    after the last position counts as 0
    4: -1   -1    if we are here, the best result is -1
    3: -4   -4    if we are here, the best result is -4 (skip 4th element)
    2: -3   -4    if we are here, the best result is -4 (skip 3rd element)
    1: -1   -5    if we are here, the best result is -5 (go to 2 or 3)
    0:  0   -4    before first position counts as 0; best result here is best result overall
    Superficially this resembles a backwards greedy selection, but it's actually choosing optimally at each point so, due to the problem's optimal substructure, it results in an optimal overall solution. This is what I thought of first but due to the superficial resemblance I jumped to the conclusion that it was actually greedy.

    You can see the repeating subproblems (and convince yourself of the optimal substructure) in this diagram for 4 elements:
    Code:
    .                ________O________
                    /                 \
               ____1____             __2__
              /         \           /     \
           __2__         3         3       4
          /     \       / \       / \      |
         3       4     4   X     4   X     X
        / \      |     |         |
       4   X     X     X         X
       |
       X

    Any tips how do I put that in code?

  10. #10
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    593
    If you understand what I was saying then the implementation should be obvious. But I may not have been very clear, so I'll try again.

    If the input is 6 elements with values a,b,c,d,e,f, then you read them into the array like this (with a 0 at the beginning and end):
    Code:
    0 1 2 3 4 5 6 7
    0 a b c d e f 0
    Then you figure out the optimal values from element 7 back to element 0:
    Code:
    .    optimal value
    7 0    0
    6 f    f
    5 e    e + (optimal value of elem 6 or 7, whichever's best)
    4 d    d + (opt val of elem 5 or 6, whichever's best)
    3 c    c + (opt val of elem 4 or 5, ...)
    2 b    ...
    1 a    ...
    0 0    0 + (opt val of elem 1 or 2, whichever is best)
    And the optimal value for element 0 is the final answer.

    Working it on your example input: 2 -1 3 2 -1 6 -5
    Code:
    8  0    0
    7 -5   -5
    6  6    6    ( 6 +  0)
    5 -1    5    (-1 +  6)
    4 -2    4    (-2 +  6)
    3  3    8    ( 3 +  5)
    2 -1    7    (-1 +  8)
    1  2   10    ( 2 +  8)
    0  0   10    ( 0 + 10)
    Let him who is not come to logic be plagued with continuous and everlasting filth.
    - John of Salisbury, 1160

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C machine learning
    By kazzn in forum General AI Programming
    Replies: 2
    Last Post: 03-22-2010, 10:12 AM
  2. Machine Learning with Lego Mindstorms
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 14
    Last Post: 01-30-2009, 02:34 PM
  3. Replies: 4
    Last Post: 01-18-2008, 07:05 PM
  4. machine learning code in c/c++
    By nchauhan in forum Game Programming
    Replies: 0
    Last Post: 11-14-2003, 10:26 AM
  5. IDEA: A Slot Machine (aka a fruit machine)
    By ygfperson in forum Contests Board
    Replies: 0
    Last Post: 08-12-2002, 11:13 PM

Tags for this Thread