Computer Science Canada

Some challenges...

Author:  wtd [ Mon Oct 22, 2007 9:47 am ]
Post subject:  Some challenges...

Unless otherwise specified, any programming language may be used. Any language that is, with the exception of Turing.

1. Write a very short program to demonstrate polymorphism (in the object-oriented sense of the word). Note: you will likely want to use some form of object-oriented programming language.

2. Demonstrate statically verified structural subtyping in a language without mandatory explicit type annotations.

3. Explain how an object-oriented programming language can lack classes, and how inheritance can work in such a language. Offer some code to demonstrate.

4. Explain why "foo" in the following is available from within "bar" in the "Baz" class. Note: Ruby.

code:
def foo
    puts "foo"
end

class Baz
    def bar
        foo
    end
end


Also, explain why the "foo" in the class Baz overrides the previously defined "foo" when called from "bar" in Baz.

code:
def foo
    puts "foo"
end

class Baz
    def foo
        puts "FOO!"
    end
 
    def bar
        foo
    end
end


5. Consider the following Objective-C source file. Modify it such that the Bar class' "bar" method can be statically verified. Do not introduce a new class.

code:
#import <objc/Object.h>

@interface Foo : Object
- foo;
@end

@interface Bar : Object
- (void) bar;
@end

@implementation Foo
- foo
{
    // This code is unimportant, do NOT add code here.
}
@end

@implementation Bar
- (void) bar
{
    [[[[Foo alloc] init] foo] baz];
}
@end


6. Translate the following to C++ from Java.

code:
interface Foo {
    void bar();
}


7. Write a tail-recursive factorial function which takes a single integer argument.

8. Going back to Objective-C, make the following work without modifying the Foo class, and without introducing a new class. The implementation of Foo (Foo.m) is considered unimportant and has no bearing on your work.

code:
// Foo.h

#import <objc/Object.h>

@interface Foo : Object
- (void) foo;
@end

// main.m

#import "Foo.h"

int main()
{
    Foo *f = [[Foo alloc] init];

    [f foo];
    [f bar];

    return 0;
}


9. Write a simple program to demonstrate a closure.

10. Create a circular array type which can be shifted left or right such that the element on the far left will appear on the far right when the array is shifted left, and vice versa. It should be non-expandable, but the size of the array should be specified when the data structure is instantiated. The data structure must be efficiently implemented using an array. It may NOT be implemented using any sort of linked list data structure.

Author:  PaulButler [ Mon Oct 22, 2007 5:40 pm ]
Post subject:  RE:Some challenges...

Good list, I will try some of these (#7 in particular has me thinking...). One question, are you ok with us posting here when we have a solution?

Author:  rdrake [ Mon Oct 22, 2007 6:05 pm ]
Post subject:  Re: Some challenges...

Spoiler:
I think it's ok if you use the [spoiler ][ /spoiler] tags.

Author:  wtd [ Tue Oct 23, 2007 12:43 am ]
Post subject:  RE:Some challenges...

Note: successfully answering all questions will earn a great deal of respect from me. Smile

Author:  Zampano [ Tue Oct 23, 2007 7:35 am ]
Post subject:  Re: Some challenges...

And I'm there's nothing more than any of us crave than the respect of a random guy on a forum somewhere miles away (unless otherwise noted). Very Happy

Author:  wtd [ Tue Oct 23, 2007 10:07 am ]
Post subject:  RE:Some challenges...

I'm just a "random guy" on "some internet forum"?

For me, compsci.ca is more than just that. It stands for something: students coming together and taking charge of their own education, and by extension their lives.

Or maybe it's just some random internet forum, and I was bored.

Whichever. Smile

Author:  richcash [ Tue Oct 23, 2007 3:44 pm ]
Post subject:  Re: Some challenges...

3. Are you talking about a language like Javascript?
Spoiler:
Javascript is an object-oriented programming language with no classes. It has functions (which can have inner functions) that can be used as structures for objects (instances of the function).

Quote:
function Foo() {
    
var bar = function() {
    
    
return "BAR"
    
}
    
this.baz = function() {
    
    
return bar() + " car"
    
}
}
obj = new Foo()
document.write(obj.baz())

All instances of Foo() will have a public method baz(). The private method bar() can not be accessed by objects of Foo().

Quote:
function FooBar() {
    
this.inheritFoo = Foo
    
this.inheritFoo()
}
obj = new FooBar()
document.write(obj.baz())

That is inheritance. Notice you can't really say that FooBar() is inheriting everything from Foo(). If you just call Foo() inside of FooBar(), you will not get inheritance. You have to do it as above. Each object of FooBar() is inheriting everything from Foo(). Alternative syntax is :
Quote:
function FooBar() {
}
FooBar.prototype = new Foo()
obj = new FooBar()
document.write(obj.baz())

Author:  wtd [ Tue Oct 23, 2007 3:49 pm ]
Post subject:  RE:Some challenges...

You're pretty close, but explain it in English so I can see that you really understand it. Especially the inheritance bit.

Author:  richcash [ Tue Oct 23, 2007 4:51 pm ]
Post subject:  Re: Some challenges...

Well, let's say FooBar is inheriting from Foo (as in above).

I believe it is just a property of objects. Calling a function in a function will just give the result, but calling a function belonging to an object in that object (using the 'this' keyword) will give this object everything in that function (then return the result). So, we have to make a function for each object equal to Foo and then calling this function in each object will give each object everything in the function (all functions and variables). Is this right?

The prototype is easier to explain. It basically says make every object of FooBar an instance of Foo(). 'FooBar.prototype' refers to every instance of FooBar.

Author:  wtd [ Tue Oct 23, 2007 5:07 pm ]
Post subject:  RE:Some challenges...

You're making it sound far more complicated than it is.

Author:  richcash [ Tue Oct 23, 2007 5:37 pm ]
Post subject:  Re: Some challenges...

Whever an object's function is called, the object receives all the functions and variables of that function.
Javascript:
function Foo() {
        this.bar = function() {
                this.qux = function() {
                        return "qux"
                }
        }
}
obj = new Foo()
document.write(obj.qux())


So to inherit all of a structure function's stuff [Foo] into all the objects of another structure function [FooBar] (as I did in my last-last post), we need to give each object of FooBar (using 'this') a function equal to Foo so it can be called and use the above property.

Author:  wtd [ Tue Oct 23, 2007 9:57 pm ]
Post subject:  RE:Some challenges...

This still does not get at the heart of the matter of how inheritance works in such a model.

Javascript is not the easiest language to think about this in.

Author:  richcash [ Fri Oct 26, 2007 9:43 am ]
Post subject:  Re: Some challenges...

Well, I might as well put my newly found knowledge of O'Caml polymorphic classes into use. So ...
10.
code:
class ['a] circ_array length (init_val : 'a) =
   object
      val array = Array.create length init_val
      method set i x = array.(i) <- x
      method assign new_arr = Array.iteri (fun i x -> array.(i) <- x) new_arr
      method at i = array.(i)
      method values = array
      method shift_l = Array.iteri (fun i x ->
         if i == 0 then array.(length - 1) <- x else array.(i - 1) <- x) (Array.copy array)
      method shift_r = Array.iteri (fun i x ->
         if i == length - 1 then array.(0) <- x else array.(i + 1) <- x) (Array.copy array)
   end


Ocaml:
let arr = new circ_array 4 "";;
arr#assign [|"a"; "b"; "c"; "d"|];;
arr#shift_r;;
Array.iter (fun x -> print_endline x) (arr#values);;

Author:  wtd [ Fri Oct 26, 2007 11:05 am ]
Post subject:  RE:Some challenges...

Way too much copying and moving of stuff going on. There's a more efficient way to handle this. Smile

Author:  richcash [ Fri Oct 26, 2007 12:55 pm ]
Post subject:  Re: Some challenges...

Yeah, you're right. I threw that together too quickly. Here is a more efficient way.

code:
class ['a] circ_array init_length (init_val : 'a) =
        object(this)
                val last = init_length - 1
                val array = Array.create init_length init_val
                val mutable start = 0
                method assign new_arr = Array.iteri (fun i x -> array.(i) <- x) new_arr
                method at i = let index = start + i in
                                if index > last then array.(index - init_length) else array.(index)
                method values = let rec values_ i l =
                                if i == init_length then l else values_ (i+1) ((this#at (last - i))::l) in
                                        Array.of_list (values_ 0 [])
                method shift_l = if start == last then start <- 0 else start <- start + 1
                method shift_r = if start == 0 then start <- last else start <- start - 1
        end

Author:  wtd [ Fri Oct 26, 2007 1:30 pm ]
Post subject:  RE:Some challenges...

Congratulations on figuring it out. Deceptively simple, wasn't it? Smile

Author:  richcash [ Fri Oct 26, 2007 3:54 pm ]
Post subject:  Re: Some challenges...

Indeed, nice question.

Oh yeah, I'm no longer working on #3, so if someone else wants to explain it, feel free to. Smile

Author:  McKenzie [ Fri Oct 26, 2007 8:45 pm ]
Post subject:  Re: Some challenges...

wtd @ Mon Oct 22, 2007 9:47 am wrote:
Unless otherwise specified, any programming language may be used. Any language that is, with the exception of Turing.

Why ??? Why put out a challenge then say no Turing? If some kid knows how to do this in Turing why discourage him/her?

Author:  wtd [ Fri Oct 26, 2007 10:33 pm ]
Post subject:  RE:Some challenges...

Turing's deficiencies are well known, and do not need to be reiterated. I do not think anyone here would be shocked if I said I hope that students will take the initiative to learn some other programming language to expand their horizons.

That said, if someone wants to submit a Turing solution to one of these problems, the worst that can happen is that some random guy on a web forum will be upset. Or I might be mightily impressed. Nothing is written in stone.

Author:  PaulButler [ Sat Oct 27, 2007 4:29 pm ]
Post subject:  RE:Some challenges...

I did #7, but using a global variable seems like cheating.. is there a nicer way to do this?

Spoiler:


scheme:

(define fact-count 1)

(define (factorial x)
  (if (= x 1)
      (let ((ans fact-count))
        (set! fact-count 1)
        ans)
      (begin
        (set! fact-count (* fact-count x))
        (factorial (- x 1)))))


Author:  wtd [ Sat Oct 27, 2007 7:35 pm ]
Post subject:  RE:Some challenges...

There is a nicer way, and you should not need to mutate any variables.

Author:  rdrake [ Sat Oct 27, 2007 8:02 pm ]
Post subject:  RE:Some challenges...

I think I cheated more on #7:
code:
        fact 0 = 1
        fact n = foldl (*) n [1..(n - 1)]

Author:  rdrake [ Sat Oct 27, 2007 10:54 pm ]
Post subject:  RE:Some challenges...

Ok, finally got around to creating a legitimate entry:
code:
fact' 0 acc = 1
fact' 1 acc = acc
fact' n acc = fact' (n-1) (n * acc)

Author:  wtd [ Sat Oct 27, 2007 11:19 pm ]
Post subject:  RE:Some challenges...

Thanks for playing our game. Can someone show rdrake his consolation prize? The challenge specifies that the function may take only one argument.

Author:  rdrake [ Sat Oct 27, 2007 11:28 pm ]
Post subject:  Re: RE:Some challenges...

wtd @ Sat Oct 27, 2007 11:19 pm wrote:
Thanks for playing our game. Can someone show rdrake his consolation prize? The challenge specifies that the function may take only one argument.
Whoops!

code:
        fact n = fact' n 1
                where
                        fact' 0 acc = 1
                        fact' 1 acc = acc
                        fact' n acc = fact' (n-1) (n * acc)

Author:  wtd [ Sat Oct 27, 2007 11:35 pm ]
Post subject:  RE:Some challenges...

Excellent.I leave it to future challengers to figure out other ways of accomplishing this.

Author:  Nick [ Sat Oct 27, 2007 11:59 pm ]
Post subject:  RE:Some challenges...

ok im working on number 10 in turing just to impress wtd Razz ill post it when it's complete

Author:  Nick [ Sun Oct 28, 2007 12:05 am ]
Post subject:  RE:Some challenges...

ok ok how is this?

Turing:
module foo
    export ~.bar, ~.right, ~.left, add, move
    const right : int := 1
    const left : int := 2
    var bar : array 1 .. 10 of int
    for i : 1 .. 10
        bar (i) := i
    end for
    proc add (whichToAdd, addTo : int)
        bar (whichToAdd) += addTo
    end add
    proc move (direction : int)
        if direction = right then
            var hold : array 1 .. 10 of int
            for i : 1 .. 10
                hold (i) := bar (i)
            end for
            for i : 1 .. 10
                if i ~= 1 then
                    bar (i) := hold (i - 1)
                else
                    bar (1) := hold (10)
                end if
            end for
        elsif direction = left then
            var hold : array 1 .. 10 of int
            for i : 1 .. 10
                hold (i) := bar (i)
            end for
            for i : 1 .. 10
                if i ~= 10 then
                    bar (i) := hold (i + 1)
                else
                    bar (10) := hold (1)
                end if
            end for
        else
            %do nothing
        end if
    end move
end foo

for i : 1 .. 10
    put bar (i)
end for
foo.move (left)
put ""
for i : 1 .. 10
    put bar (i)
end for


and to boot its in turing

Author:  wtd [ Sun Oct 28, 2007 9:46 am ]
Post subject:  RE:Some challenges...

It looks to me like there's an awful lot of copying of data going on, and the conditional in "move" can be tremendously simplified anyway.

Author:  Saad [ Sun Oct 28, 2007 10:28 am ]
Post subject:  Re: Some challenges...

Here is what i used to test my submission for number 10.
Language : C++
Compiler: MinGW Compiler Set.

c++:

#include <iostream>
#include "CircleArray.cpp"
using std::cout;
using std::endl;

int main(){
    CircleArray<int,10> foo;
    for (int i = 0; i < 10; i++){
        foo[i] = i;
    }
    cout << "Original : ";
    for (int i = 0; i < 10; i++){
        cout << foo[i] << " ";
    }
    cout << endl;
    foo << 1;
    cout << "After rotate left 1 : ";
    for (int i = 0; i < 10; i++){
        cout << foo[i] << " ";
    }
    cout << endl;
   
    foo >> 5;
    cout << "After rotate right 5 : ";
    for (int i = 0; i < 10; i++){
        cout << foo[i] << " ";
    }
    cout << endl;
}


And i have attached CircleArray.cpp

For number 4. I'm going to say that due to scoping, It calls the method foo which is defined for bar not the global function.

Author:  Nick [ Sun Oct 28, 2007 10:33 am ]
Post subject:  Re: RE:Some challenges...

wtd @ Sun Oct 28, 2007 9:46 am wrote:
It looks to me like there's an awful lot of copying of data going on, and the conditional in "move" can be tremendously simplified anyway.


hmm it seems that it can... ill work on that and post when its better Razz

EDIT: ok its done but its not that much better but remember this is turing lol

Turing:
module foo
    export ~.bar, move
    var bar : array 1 .. 10 of int
    for i : 1 .. 10
        bar (i) := i
    end for
    proc move (direction : int)
        var hold : array 1 .. 10 of int
        if direction = 1 or direction = 2 then
            for i : 1 .. 10
                hold (i) := bar (i)
            end for
            for i : 1 .. 10
                if direction = 1 then
                    if i ~= 1 then
                        bar (i) := hold (i - 1)
                    else
                        bar (1) := hold (10)
                    end if
                else
                    if i ~= 10 then
                        bar (i) := hold (i + 1)
                    else
                        bar (10) := hold (1)
                    end if
                end if
            end for
        end if
    end move
end foo

const right : int := 1
const left : int := 2
for i : 1 .. 10
    put bar (i)
end for
foo.move (left)
put ""
for i : 1 .. 10
    put bar (i)
end for

Author:  wtd [ Sun Oct 28, 2007 12:16 pm ]
Post subject:  Re: Some challenges...

code:
            for i : 1 .. 10
                if direction = 1 then
                    if i ~= 1 then
                        bar (i) := hold (i - 1)
                    else
                        bar (1) := hold (10)
                    end if
                else
                    if i ~= 10 then
                        bar (i) := hold (i + 1)
                    else
                        bar (10) := hold (1)
                    end if
                end if
            end for


This loop can still be refactored considerably.

Author:  Nick [ Sun Oct 28, 2007 12:43 pm ]
Post subject:  RE:Some challenges...

ok i did change the loop somewhat but not that much better

Turing:
module foo
    export ~.bar, move
    var bar : array 1 .. 10 of int
    for i : 1 .. 10
        bar (i) := i
    end for
    proc move (direction : int)
        var hold : array 0 .. 10 of int
        var plusMinus : int
        if direction = 1 or direction = 2 then
            if direction = 1 then
                plusMinus := -1
            else
                plusMinus := +1
            end if
            for i : 1 .. 10
                hold (i) := bar (i)
            end for
            for i : 1 .. 10
                if (i ~= 1 and direction = 1) then
                    bar (i) := hold (i + (1 * plusMinus))
                elsif (i ~= 10 and direction = 2) then
                    bar (i) := hold (i + (1 * plusMinus))
                else
                    if direction = 1 then
                        bar (1) := hold (10)
                    else
                        bar (10) := hold (1)
                    end if
                end if
            end for
        end if
    end move
end foo

const right : int := 1
const left : int := 2
for i : 1 .. 10
    put bar (i)
end for
foo.move (left)
put ""
for i : 1 .. 10
    put bar (i)
end for

Author:  zylum [ Sun Oct 28, 2007 2:33 pm ]
Post subject:  RE:Some challenges...

#10

code:
class circArray
    export shift, getElem, putElem, initialize
    var size, start : int
    var arr : flexible array 1 .. 0 of int

    proc initialize (s : int)
        size := s
        new arr, s
        start := 1
    end initialize

    proc shift (n : int)
        start := (start - n - 1) mod size + 1
    end shift

    fcn getElem (i : int) : int
        result arr ((start + i - 1) mod size + 1)
    end getElem

    proc putElem (i, n : int)
        arr ((start + i - 1) mod size + 1) := n
    end putElem
end circArray

Author:  Nick [ Sun Oct 28, 2007 2:36 pm ]
Post subject:  Re: Some challenges...

wtd @ Mon Oct 22, 2007 9:47 am wrote:
It should be non-expandable


nice zylum its still better than mine

Author:  Aziz [ Sun Oct 28, 2007 3:07 pm ]
Post subject:  RE:Some challenges...

#10 in Java.

Didn't read any other solutions before I did it Very Happy

Also comes with a nice tester main method, and can easily be fitted to the List interface and added to a homegrown collections framework!

code:
public class CircularArray<E>
{
    private Object[] array;
    private int head;

    public CircularArray(int size)
    {
        array = new Object[size];
        head = 0;
    }
   
    public CircularArray(E[] otherArray)
    {
        this(otherArray.length);
       
        for (int i = 0; i < array.length; i++)
        {
            array[i] = otherArray[i];
        }
    }
   
    public E get(int index)
    {
        if (index < 0 && index >= array.length)
            throw new IndexOutOfBoundsException("Index: " + index + " Size: " + array.length);
       
        return (E) array[(head + index) % array.length];
    }
   
    public void set(int index, E value)
    {
        if (index < 0 && index >= array.length)
            throw new IndexOutOfBoundsException("Index: " + index + " Size: " + array.length);
       
        array[(head + index) % array.length] = value;
    }
   
    public int size()
    {
        return array.length;
    }
   
    public void shiftLeft()
    {
        shiftLeft(1);
    }
   
    public void shiftLeft(int amount)
    {
        shiftRight(array.length - (amount % array.length));
    }
   
    public void shiftRight()
    {
        shiftRight(1);
    }
   
    public void shiftRight(int amount)
    {
        head = (head + amount) % array.length;
    }
   
    public static void main(String[] args)
    {
        final String word = "Programming";
        CircularArray<String> circle = new CircularArray<String>(word.length());
       
        for (int i = 0; i < circle.size(); i++)
            circle.set(i, word.substring(i, i+1));
       
        System.out.println("Before shift:");
        for (int i = 0; i < circle.size(); i++)
            System.out.print(circle.get(i));
        System.out.println();
       
        circle.shiftRight();
        System.out.println("shiftRight()");
        for (int i = 0; i < circle.size(); i++)
            System.out.print(circle.get(i));
        System.out.println();
       
        circle.shiftRight(3);
        System.out.println("shiftRight(3)");
        for (int i = 0; i < circle.size(); i++)
            System.out.print(circle.get(i));
        System.out.println();
       
        circle.shiftLeft();
        System.out.println("shiftLeft()");
        for (int i = 0; i < circle.size(); i++)
            System.out.print(circle.get(i));
        System.out.println();
       
        circle.shiftLeft(16);
        System.out.println("shiftLeft(16)");
        for (int i = 0; i < circle.size(); i++)
            System.out.print(circle.get(i));
        System.out.println();
    }
}

Author:  zylum [ Sun Oct 28, 2007 11:01 pm ]
Post subject:  RE:Some challenges...

its not really expandable. when you create the object you set the size of the array when you call the initialize method. i wouldnt have use a flexible array if i could define the size of the array during runtime but hey, its turing.

aziz > i dont think its necessary to check if the index is in bounds because this is a circular array.. if the bound is higher than the size of the array, you just move on to the next elements in the circle no?

Author:  Aziz [ Mon Oct 29, 2007 9:48 am ]
Post subject:  RE:Some challenges...

Yeah, I suppose that's right! I wrote those methods before most of the rest and didn't really think much about it.


: