Page 1 of 4 123 ... LastLast
Results 1 to 10 of 37

Thread: Beginners Programming Challenge #20

  1. #1
    Join Date
    Apr 2007
    Location
    NorCal
    Beans
    1,149
    Distro
    Ubuntu 10.04 Lucid Lynx

    Beginners Programming Challenge #20

    Beginners Programming Challenge #20
    I hope this wall of text doesn't scare you. I just want to make sure you have a few simple concepts down, and then the rest of the challenge should be fairly simple. Feel free to skip ahead if you think you've got the idea down.

    Concepts
    First-class functions are a very useful tool. When a language allows first-class functions, it lets you pass around a function just like any other piece of data. You can store a function in a variable, pass it in to some other function, evaluate it with parameters, and return some other function. You can pass it around just like you would an integer or a character. This has some interesting benefits, and lets you describe common patterns in less code.

    A common pattern is to take every element from a list, do something with it (say, add 5 to it, or square it, etc), and then make a list of the results. By sticking that "do something" into a function, we can hide the explicit iteration inside of a function we only have to write once. This is called 'mapping':
    Code:
    data = range(1, 11)
    new_list = []
    
    for i in data:
        new_list.append(i * i)
    can be transformed into
    Code:
    def square(x):
        return x * x
    
    def map(func, data):
        new_list = []
    
        for i in data:
            new_list.append( func(i) )
    
        return new_list
    
    map(square, range(1, 11))
    Now, this might look like MORE code, and that's true for this small example. But the benefit is that you only have to write 'map' once. Then, you can customize the behavior by writing a different function in place of 'square', and passing it in to 'map'.

    Mapping is just one example of a common pattern that can be solved using first class functions. Your challenge is implement a couple more.

    The Challenge
    You must implement two functions, filter and reduce.
    • Filter will take two arguments, a function 'f' and a list 'x'.
      • 'f' will be a function that returns True or False based on some input. For example, the function 'isOdd' should return True if it's given an odd number, and False otherwise.
      • Filter will return a list that contains all of the elements of 'x' such that 'f' returns True.

    Code:
    def isOdd(x):
        return x % 2 == 1
    
    filter(isOdd, range(1, 11)) # returns [1, 3, 5, 7, 9]
    • Reduce will take a function 'f', a list 'x', and an initial value 'i'.
      • 'f' will take two parameters, combine them in some way, and return the result.
      • Reduce takes all of the elements of 'x', combines them one at a time using 'f', and uses the value 'i' as the starting value when doing the first combination.

    Code:
    def add(x, y):
        return x + y
    
    reduce(add, range(1, 6), 0) # returns (((((0 + 1) + 2) + 3) + 4) + 5), which is 15
    Extra credit
    A lot of things can be defined in terms of reduce, including map and filter. Other examples include: taking the sum or product of all elements in a list, concatenating a list of lists into one flat list, reversing a list, finding the minimum/maximum of a list, and so on. Implement anything else you feel like doing in terms of the functions presented here.

    Help
    For people who have never dealt with them before, first-class functions can be a little intimidating. If you're unclear on what filter and reduce should do or how first-class functions work, feel free to ask for a different explanation or more examples. Note that many languages already have map, filter and reduce built in or as part of the standard library under various names. You should experiment with those to get a better sense of what they do and what you can do with them.

    Judging
    Entries will be judged based on how well you seem to understand the applications of first class functions, as well as the basic criteria that you code must work and be readable. One way of demonstrating understanding is to at least attempt the extra credit, even if you can't get it working. The goal here is to make you think, not churn something out for a grade.

    Have fun! Judging will commence in a few weeks, or when the entries stop coming in.
    Last edited by schauerlich; April 26th, 2011 at 10:29 PM.
    Posting code? Use the [code] or [php] tags.
    I don't care, I'm still free. You can't take the sky from me.

  2. #2
    Join Date
    Jun 2006
    Beans
    596
    Distro
    Kubuntu

    Re: Beginners Programming Challenge #20

    Great challenge!
    I like the idea of demonstrating understanding of a concept, rather than producing a result. Explaining something to someone else always aids your own understanding by making you think things through step-by-step.

    Here's my entry, in Ruby. Two very helpful sites I used to aid my understanding are here and here (both are good for further reading on functions in Ruby).

    PHP Code:
    #!/usr/bin/ruby

    # Ruby has several kinds first-class functions, but I'm only going to look at
    # two: Procs and Lambdas.
    # First, Procs:

    is_odd Proc.new{ |n| !(n%2).zero? }

    def filter(function, range)
        
    values = []
        
    range.each do |i|
            
    values << if function.call(i)
        
    end
        values
    end

    p filter
    (is_odd, (1..10))

    # Procs also have a shorthand syntax.

    add = ->(n,m){ n+}

    def reduce(function, rangeinitial)
        
    range.each do |i|
            
    initial = function.call(iinitial)
        
    end
        initial
    end

    p reduce
    (add, (1..10), 0)


    # Ruby also has Lambdas, which are similar to Procs but have different rules
    # for flow control, and behave more like methods in other languages. For
    # example, you can return from a Lambda back *to* the calling function, but
    # returning from a Proc is the same as returning *from* the calling function.

    def test
        my_lambda 
    lambda{ return "returning from Lambda" }
        
    my_proc Proc.new{ return "returning from Proc" }

        
    puts "starting test.."
        
    puts my_lambda.call     # the lambda returns to here.
        
    my_proc.call            # the Proc does *not* return to here.
        
    "returning from test.." # control does *not* get here.
    end

    puts test                   
    # the Proc returns to here! 
    Edit: This code is written in a more functional style than I'm used to; it's not very Rubyish, and is not the technique I would normally use for code re-use. However, this was the format requested in the challenge.

    Edit 2: This is the output:
    Code:
    [1, 3, 5, 7, 9]
    55
    starting test..
    returning from Lambda
    returning from Proc
    Last edited by krazyd; April 27th, 2011 at 06:47 PM.

  3. #3
    Join Date
    Sep 2006
    Location
    BC, Canada
    Beans
    347
    Distro
    Ubuntu 10.10 Maverick Meerkat

    Re: Beginners Programming Challenge #20

    For a lark, I thought I'd do this one in ANSI C. I decided to break the rules by adding additional arguments to the required functions to make the test more friendly to C:

    func_callback.h
    PHP Code:
    /* Programming Challenge 20
     * Due to the difficulty of implementing generalized arguments in C, 
     * only an integer compatible version of the functions exist. */

    #ifndef FUNC_CALLBACK_H
    #define FUNC_CALLBACK_H 1

    #define TRUE  1
    #define FALSE 0

    typedef unsigned char boolean;

    typedef boolean (*TestFunc) (int);
    typedef int (*CombineFunc) (intint);

    /* remove entries which do not match criteria specified by user supplied
     * function 'f' and return an array containing only those matches. */
    int *filter (const TestFunc fint *arr, const int szint *result_sz);

    /* reduce array 'arr' by applying user supplied function 'f' into one result,
     * starting with value 'start' */
    int reduce (const CombineFunc fint *arr, const int sz, const int start);

    #endif /* FUNC_CALLBACK_H */ 
    func_callback.c
    PHP Code:
    #include "func_callback.h"
    #include <stdlib.h>

    int *
    filter (const TestFunc fint *arr, const int szint *result_sz)
    {
        
    int i;
        
    int x 0;
        
    int *tmp malloc (sizeof (int) * sz);
        
        if (!
    tmp) return NULL;
        
        for (
    0szi++)
          if (
    (arr[i])) 
                
    tmp[x++] = arr[i++];
        
        
    tmp realloc (tmpsizeof (int) * x);
        
        *
    result_sz = !tmp x;
        
        return 
    tmp;
    }

    int 
    reduce 
    (const CombineFunc fint *arr, const int sz, const int start)
    {
        
    int i;
        
    int result start;
        
        for (
    0szi++)
            
    result (resultarr[i]);
        
        return 
    result;

    The following is the code used to test the above:

    func_cb_main.c
    PHP Code:
    #include "func_callback.h"
    #include <stdio.h>
    #include <stdlib.h>

    /* "user" defined functions for use with filter and reduce */
    static boolean 
    isOdd 
    (const int num)
    {
        return (
    num 2);
    }

    static 
    boolean 
    isEven 
    (const int num)
    {
        return !(
    num 2) && num != 0;
    }

    static 
    int
    add 
    (const int x, const int y)
    {
        return 
    y;
    }

    static 
    int
    sub 
    (const int x, const int y)
    {
        return 
    y;
    }

    int
    main 
    (void)
    {
        
    int test_arr[] = {0123456789};
        
    int *result_arr;
        
    int result 0;
        
    int i;
        
    int sz;
        
        
    result_arr filter (isEventest_arrsizeof(test_arr) / sizeof (int), &sz);
        
    printf ("Printing even numbers from array:\n");
        for (
    0szi++)
            
    printf ("%d "result_arr[i]);
        
    printf ("\n");
        
    free(result_arr);
        
        
    result_arr filter (isOddtest_arrsizeof(test_arr) / sizeof (int), &sz);
        
    printf ("Printing odd numbers from array:\n");
        for (
    0szi++)
            
    printf ("%d "result_arr[i]);
        
    printf ("\n");
        
    free(result_arr);
        
    result_arr NULL;
        
        
    result reduce (addtest_arr100);
        
    printf ("reduce (add) returned a result of %d\n"result);
        
        
    result reduce (subtest_arr1020);
        
    printf ("reduce (sub) returned a result of %d\n"result);
        
        return 
    0;

    Use whatever compile flags you want. I tested with:
    Code:
    gcc -Wall -Wextra -ansi -pedantic func_callback.c func_cb_main.c && ./a.out
    Results:
    Code:
    Printing even numbers from array:
    2 4 6 8 
    Printing odd numbers from array:
    1 3 5 7 9 
    reduce (add) returned a result of 45
    reduce (sub) returned a result of -25

  4. #4
    Join Date
    Apr 2007
    Location
    NorCal
    Beans
    1,149
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginners Programming Challenge #20

    Quote Originally Posted by JupiterV2 View Post
    For a lark, I thought I'd do this one in ANSI C. I decided to break the rules by adding additional arguments to the required functions to make the test more friendly to C:
    I was waiting for someone to try it in C. The idea for this challenge actually came from a discussion on how to make a generic version of map in C. There's no good way to do it. One method is to force the function you hand in to be of the type void foo(void *), and then make the user take care of casting the void * properly. Ugly.

    If someone made a generic reduce in C, I'd be very impressed. After all, the value it accumulates should be able to be ANY type, including an array.
    Last edited by schauerlich; April 28th, 2011 at 04:55 AM.
    Posting code? Use the [code] or [php] tags.
    I don't care, I'm still free. You can't take the sky from me.

  5. #5
    Join Date
    Feb 2009
    Beans
    518
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Beginners Programming Challenge #20

    Interesting. I think I had an assignment a year or so ago where implementing filter in terms of reduce (in Haskell) was not just extra credit but actually required. It's been a while, though, the course was in German, and I seem to remember pulling my hair out over the problem.

    EDIT: In fact, I seem to have found it so difficult that I used a loophole in the way the assignment was written to not implement filter in terms of reduce. I'll have to try again.
    Last edited by jwbrase; April 28th, 2011 at 06:07 AM.

  6. #6
    Join Date
    Feb 2011
    Location
    Cambridge, ON, CAN
    Beans
    105
    Distro
    Ubuntu 10.10 Maverick Meerkat

    Re: Beginners Programming Challenge #20

    I figured reduce lends itself nicely to a recursive approach. Here's a concise Python example:

    Code:
    def filter(function, list_):
        return [i for i in list_ if function(i)]
    
    def reduce(function, list_):
        if len(list_) > 1:
            list_ = [reduce(function, [function(list_[0], list_[1])] + list_[2:])]
        return list_[0]
    Last edited by andrew1992; April 28th, 2011 at 01:46 PM.

  7. #7
    Join Date
    Feb 2011
    Location
    Cambridge, ON, CAN
    Beans
    105
    Distro
    Ubuntu 10.10 Maverick Meerkat

    Re: Beginners Programming Challenge #20

    Quote Originally Posted by schauerlich View Post
    I was waiting for someone to try it in C. The idea for this challenge actually came from a discussion on how to make a generic version of map in C. There's no good way to do it. One method is to force the function you hand in to be of the type void foo(void *), and then make the user take care of casting the void * properly. Ugly.

    If someone made a generic reduce in C, I'd be very impressed. After all, the value it accumulates should be able to be ANY type, including an array.
    I've never touched C before, though I'm aware it has no support for function overloading as far as I know. I'm going to give this a shot though, just for kicks

  8. #8
    Join Date
    Feb 2009
    Beans
    789
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginners Programming Challenge #20

    Quote Originally Posted by andrew1992 View Post
    I figured reduce lends itself nicely to a recursive approach. Here's a concise Python example:

    Code:
    def filter(function, list_):
        return [i for i in list_ if function(i)]
    
    def reduce(function, list_):
        if len(list_) > 1:
            list_ = [reduce(function, [function(list_[0], list_[1])] + list_[2:])]
        return list_[0]
    Your reduce function does not have an initial value (see opening post). The initial value is needed to perform certain tricks with reduce. For example, when calculating the sum or the product of a list then the initial value should be 0 and 1 respectively. You can also have a different value to do something like computing the sum of a list plus a value n > 0 or multiplying all elements of a list with each other and a value n > 1.

  9. #9
    Join Date
    Feb 2011
    Location
    Cambridge, ON, CAN
    Beans
    105
    Distro
    Ubuntu 10.10 Maverick Meerkat

    Re: Beginners Programming Challenge #20

    Your example doesn't help me see why those initial values are needed. Let's say you want to take the product of all the values in a list [1, 2, 3, 4, 5]. With my algorithm, an initial value isn't necessary.

    [1, 2, 3, 4, 5]
    [2, 3, 4, 5]
    [6, 4, 5]
    [24, 5]
    120

  10. #10
    Join Date
    Feb 2009
    Beans
    789
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginners Programming Challenge #20

    Quote Originally Posted by andrew1992 View Post
    Your example doesn't help me see why those initial values are needed. Let's say you want to take the product of all the values in a list [1, 2, 3, 4, 5]. With my algorithm, an initial value isn't necessary.

    [1, 2, 3, 4, 5]
    [2, 3, 4, 5]
    [6, 4, 5]
    [24, 5]
    120
    In my examples the initial values indeed cancel out. But the initial value is nonetheless part of reduce and foldr/foldl functions in languages such as Haskell.

    The reason for the intial value is that the types can differ. Your reduce function can only handle functions that take two values of the same type. It's a function that takes two int values and returns an int.

    More abstractly we can say that it takes two values of type a and it returns a value of type a.

    But we can also think of functions that take a value of type a, a value of type b and return a value of type a. This allows us to reduce a list of values of type b by starting with a value of type a.

    The following example shows how this can be used:

    Code:
    def f(a, b):
        if b in a[1]:
            return (a[0] + [b], a[1])
        return a
        
    def contains(my_words):
        return reduce(f, my_words, ([], ["aaa", "bbb", "ccc"]))[0]
    
    print contains(["aaa", "ddd", "bbb"])
    which will print:

    Code:
    ['aaa', 'bbb']
    In other words, we have a function called contains that shows all words from my_words that are also in the predefined list of words ["aaa", "bbb", "ccc"]. Note that we can only do this because the types of a and b in function f differ.
    Last edited by simeon87; April 28th, 2011 at 02:54 PM.

Page 1 of 4 123 ... LastLast

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •