Computer Science Canada Test your skills (2006) |
Author: | wtd [ Mon Jan 02, 2006 3:48 am ] | ||||
Post subject: | Test your skills (2006) | ||||
Io TYS.
Write a method which makes the above possible.
|
Author: | wtd [ Sun Jan 15, 2006 5:09 pm ] | ||||
Post subject: | |||||
Write a function which appends lists.
A few samples:
You may use the following functions or macros.
You may very explicitly not use the loop macro. You may not have any code outside of the list-append function. |
Author: | wtd [ Fri Feb 03, 2006 2:27 am ] | ||
Post subject: | |||
C++ gurus: a TYS just for you. Explain why this code will not compile.
|
Author: | Martin [ Tue Feb 07, 2006 3:18 am ] | ||||||
Post subject: | |||||||
C/C++ (or Java). Complete this function to determine if n is a power of 2.
|
Author: | Andy [ Tue Feb 07, 2006 9:37 am ] | ||
Post subject: | |||
does that count as cheating? lol |
Author: | Martin [ Tue Feb 07, 2006 7:23 pm ] |
Post subject: | |
There's a much better way. Think bitwise. |
Author: | Andy [ Tue Feb 07, 2006 10:27 pm ] |
Post subject: | |
haha yea, i was going to do it bitwise, but then i got lazy =P, if i have time, i'll do it at work tomorow |
Author: | bugzpodder [ Wed Feb 08, 2006 12:53 pm ] | ||
Post subject: | |||
|
Author: | bugzpodder [ Wed Feb 08, 2006 12:56 pm ] | ||
Post subject: | |||
>> is an operator in C++. need a space in between. |
Author: | wtd [ Wed Feb 08, 2006 12:58 pm ] | ||
Post subject: | |||
bugzpodder wrote:
>> is an operator in C++. need a space in between. Yes, that is the solution. But why is it a problem? |
Author: | bugzpodder [ Wed Feb 08, 2006 1:07 pm ] |
Post subject: | |
? its a problem because >> is a predefined operator in C++. But i thought I've already said that. |
Author: | wtd [ Wed Feb 08, 2006 1:08 pm ] |
Post subject: | |
But surely C++ compilers can tell the difference? |
Author: | bugzpodder [ Wed Feb 08, 2006 2:33 pm ] |
Post subject: | |
clearly not? lol |
Author: | Martin [ Wed Feb 08, 2006 6:26 pm ] | ||||
Post subject: | |||||
bugzpodder wrote:
Another one is.
|
Author: | wtd [ Wed Feb 08, 2006 6:30 pm ] | ||
Post subject: | |||
bugzpodder wrote: clearly not? lol
Could clearly never be a type. So... why does C++ get confused? |
Author: | Martin [ Wed Feb 08, 2006 7:59 pm ] |
Post subject: | |
Would this be a problem relating to operator overloading? |
Author: | bugzpodder [ Wed Feb 08, 2006 8:02 pm ] | ||||
Post subject: | |||||
bugzpodder wrote:
actually this is wrong. it should be
|
Author: | wtd [ Wed Feb 08, 2006 8:57 pm ] |
Post subject: | |
Martin wrote: Would this be a problem relating to operator overloading?
More fundamental. |
Author: | Martin [ Wed Feb 08, 2006 9:44 pm ] |
Post subject: | |
I'm at a loss. Can we have a hint? |
Author: | wtd [ Wed Feb 08, 2006 9:51 pm ] | ||
Post subject: | |||
C++ templates work with more than just types. They permit the use of values as template parameters as well.
That isn't a type, but it is a value. The compiler is stupid enough that it sees something like "foo>>" as potentially being a value that could be a template parameter. The problem exists because the parser is not aware enough of the semantics of the language it's parsing. One of the requirements of C++0x compliant compilers will be that they not exhibit this problem. |
Author: | wtd [ Fri Feb 10, 2006 5:29 pm ] | ||||||
Post subject: | |||||||
Another C++ question In Objective-Caml it's relatively easy to define a function which can compose two other functions to create a new function.
Now I can write:
And this is equivalent to:
Write a function or function object in C++ which replicates the functionality of the compose function demonstrated above. |
Author: | wtd [ Wed Feb 15, 2006 11:08 pm ] | ||||
Post subject: | |||||
Give myList.ml as follows:
Complete the following:
|
Author: | rizzix [ Thu Feb 16, 2006 7:20 pm ] | ||
Post subject: | |||
Write the following expression in point-free form:
|
Author: | wtd [ Wed Mar 01, 2006 9:53 pm ] | ||
Post subject: | |||
Explain why:
Does not cause a stack overflow when called with a value of ten million. |
Author: | rizzix [ Sat Mar 18, 2006 1:11 am ] | ||
Post subject: | |||
rizzix wrote: Write the following expression in point-free form:
500 bits to the first person who correctly answers this. Oh and you need to explain your solution. |
Author: | Martin [ Tue Mar 21, 2006 6:22 pm ] |
Post subject: | |
Rizzix - what is point free form? |
Author: | rizzix [ Wed Mar 22, 2006 1:58 am ] |
Post subject: | |
eta reduce it to the point where there is no "n" (function parameter) visible in that code. |
Author: | Martin [ Wed Mar 22, 2006 2:17 am ] |
Post subject: | |
Huh? Is there a website on this, I'm not following... |
Author: | rizzix [ Wed Mar 22, 2006 5:07 pm ] | ||||||||||||||
Post subject: | |||||||||||||||
An example:
Eta-reduced, yet it is still not point free. As you can see there is still one parameter visible: m. Another example:
As you can see after completly eta-reducing it, there are no parameters visible. This final form is an example of point-free form. |
Author: | tez_h [ Mon Apr 03, 2006 9:13 pm ] | ||||||
Post subject: | |||||||
rizzix wrote: Write the following expression in point-free form:
First, some useful functions:
Now, we can derive a point-free expression of your function:
Is that the sort of answer you were looking for? -Tez |
Author: | rizzix [ Tue Apr 04, 2006 12:56 am ] | ||||||||
Post subject: | |||||||||
Hey! Congrats and welcome to compsci! BTW: There is no need for you to redefine any of the Prelude functions (flip, composition). I was hoping you could do it without defining any of your own functions, like twice. The truth is, that is not the answer I was hoping for, but it is an answer I was expecting -- or one kind of answer anyway. You get 350 bits for that one Here's my solution that's synonymous to yours (i.e worth 350bits) Helper function:
Note that if we used your function twice, it was just a matter of:
|
Author: | tez_h [ Tue Apr 04, 2006 5:31 am ] | ||||
Post subject: | |||||
rizzix wrote: Hey! Congrats and welcome to compsci!
BTW: There is no need for you to redefine any of the Prelude functions (flip, composition). I was hoping you could do it without defining any of your own functions, like twice. Hi, and thanks. Yeah, I thought I'd just write out the definitions for ease of reference. rizzix wrote: The truth is, that is not the answer I was hoping for, but it is an answer I was expecting -- or one kind of answer anyway. You get 350 bits for that one
<snip> Eitherway, this is still not what I'm looking for, for that extra 150bits. Well, I haven't quite worked out if you're expecting some ultra-clever combination of (.), ($), and flip, say, but here's one that only uses standard prelude functions, starting from near the end of my derivation:
Not pretty, and certainly point-less . Similarly, starting from near the end of your derivation:
Is that more what you're looking for? -Tez |
Author: | rizzix [ Tue Apr 04, 2006 11:51 am ] |
Post subject: | |
No. Let me give you a hint: I'm looking for a simpler solution Another hint: (->a) |
Author: | tez_h [ Wed Apr 05, 2006 4:27 am ] |
Post subject: | (-> a) monad |
rizzix wrote: No. Let me give you a hint: I'm looking for a simpler solution
Another hint: (->a) Yes, well I did see somewhere that there is a "(-> a)" monad that lambdabot (on #haskell on freenode) uses to transform point-wise expressions into point-free form. But since I haven't really done much proper haskell programming for a good few years, and googling for ' "(-> a)" monad ' turned up very little, I'm afraid I'm going to have to admit defeat here. I'd love it if you could provide a reference or something about the (-> a) monad, or even if it has a more googlable name. Or PM me a more obvious hint! Thanks for your time and the challenge. Now I need something to get me to learn about arrows! -Tez |
Author: | rizzix [ Thu Apr 06, 2006 1:04 am ] |
Post subject: | |
Just lookup the Reader Monad. (->a) is just an instance of Control.Monad.Reader. Where (->) is the function type constructor. http://www.nomaware.com/monads/html/readermonad.html |
Author: | wtd [ Thu Apr 20, 2006 2:34 pm ] | ||
Post subject: | |||
C++ today.
I have done something wrong here. Find and explain the mistake. |
Author: | Aziz [ Wed Jul 12, 2006 7:48 pm ] |
Post subject: | |
I like these...get more going...I'd like to see some more java and possibly even turing? |
Author: | Cervantes [ Thu Jul 13, 2006 3:25 pm ] |
Post subject: | |
We had one Turing TYS (of sorts) a while back: http://www.compsci.ca/v2/viewtopic.php?t=10450 |
Author: | Slaivis [ Thu Jul 13, 2006 5:15 pm ] |
Post subject: | |
Cervantes wrote: We had one Turing TYS (of sorts) a while back: http://www.compsci.ca/v2/viewtopic.php?t=10450
That's pretty cool. Can we start it up again? I'd like to be a participant of that. |
Author: | Cervantes [ Thu Jul 13, 2006 5:47 pm ] |
Post subject: | |
That one was already solved. Feel free to dream up questions to ask. If there are no questions, there will be no TYS. |
Author: | Aziz [ Thu Jul 13, 2006 7:14 pm ] |
Post subject: | |
I was going to say only the well-experienced could come up with good questions, but you know what, I'm thinkin' it's not that hard, just not so many uber-complex ones (that I never get anyways). Maybe I'll write some... |
Author: | wtd [ Thu Jul 13, 2006 8:16 pm ] |
Post subject: | |
TYS isn't about "hard" questions. It isn't about questions that take a lot of "work" to solve. |
Author: | Aziz [ Fri Jul 14, 2006 8:41 am ] | ||
Post subject: | |||
Exactly. Here's an easy one:
This code compiles fine. 1) Change it all to proper convention. 2) Make it effecient (ie. there are several things in there that are too much work, I'm not asking for extreme effeciency, but plain sense) |
Author: | wtd [ Fri Jul 14, 2006 11:56 am ] | ||||
Post subject: | |||||
Another C++ TYS.
Make this work, such that the output is:
You may not use "sizeof" or hard-code the size of the array. In other words, it must still work if the size of the array changes. It must also work if the type of the array is changed. For instance, if foo were an array of five integers. Bonus points if the body of the print_all function is only one line long. |
Author: | Aziz [ Fri Jul 14, 2006 2:25 pm ] |
Post subject: | |
can i try doing this in java? i think i know a way... |
Author: | wtd [ Fri Jul 14, 2006 2:33 pm ] |
Post subject: | |
Arrays work somewhat differently in Java, so it really wouldn't be much of a challenge. That said, if you want to try, then go for it. |
Author: | Null [ Fri Jul 14, 2006 9:00 pm ] | ||
Post subject: | |||
Quote: Another C++ TYS.
Partial answer. Everything is there (and in 1 line), except I don't know how you'd find the length of an array. It's just a pointer to memory. On a related note, I don't find these challenges test one's skill, but rather they test their familiarity with the intricacies of a single language. |
Author: | OneOffDriveByPoster [ Fri Jul 14, 2006 9:47 pm ] | ||||||
Post subject: | |||||||
wtd wrote: Another C++ TYS.
Make this work, such that the output is:
You may not use "sizeof" or hard-code the size of the array. In other words, it must still work if the size of the array changes. It must also work if the type of the array is changed. For instance, if foo were an array of five integers. Bonus points if the body of the print_all function is only one line long. My STL is not that good, but I think this is a full solution:
|
Author: | [Gandalf] [ Fri Jul 14, 2006 10:07 pm ] | ||
Post subject: | |||
Just about. Though that for loop should really be two lines. Here's wtd's solution:
Some crazy code, I must say. |
Author: | Aziz [ Fri Jul 14, 2006 11:30 pm ] | ||||||
Post subject: | |||||||
wtd wrote: Another C++ TYS.
Make this work, such that the output is:
You may not use "sizeof" or hard-code the size of the array. In other words, it must still work if the size of the array changes. It must also work if the type of the array is changed. For instance, if foo were an array of five integers. Bonus points if the body of the print_all function is only one line long.
I don't think it's quite as difficult as in c++, though? |
Author: | Andy [ Sat Jul 15, 2006 12:08 am ] |
Post subject: | |
not even close... it wouldnt be an error in c++.. it would just output garbage. |
Author: | OneOffDriveByPoster [ Sat Jul 15, 2006 12:09 am ] | ||||||||
Post subject: | |||||||||
wtd wrote: C++ today.
I have done something wrong here. Find and explain the mistake. The obvious one is:
which should be
I am not so clear about the explanation though, so here is my try at it: argc can be 1; args can point to a zero-length array and be distinct from a pointer to any other object; using "plain" delete on args in such a case causes undefined behaviour (afaik). I suspect that
is also a cause of undefined behaviour when argc is 1. |
Author: | OneOffDriveByPoster [ Sat Jul 15, 2006 12:19 am ] | ||||
Post subject: | |||||
[Gandalf] wrote: Just about. Though that for loop should really be two lines.
Here's wtd's solution:
Some crazy code, I must say. For loop is one line now (unless if I messed the code up):
|
Author: | [Gandalf] [ Sat Jul 15, 2006 1:09 am ] |
Post subject: | |
Andy wrote: dump the contents of the array into the vector, and use iterators to access them?
That was my original guess as well, but how would you "dump the contents of the array into a vector" under these circumstances? Aziz, why do that when arrays already keep track of their size in Java? Just use o.length. |
Author: | Aziz [ Sat Jul 15, 2006 8:19 am ] |
Post subject: | |
[Gandalf] wrote: Andy wrote: dump the contents of the array into the vector, and use iterators to access them?
That was my original guess as well, but how would you "dump the contents of the array into a vector" under these circumstances? Aziz, why do that when arrays already keep track of their size in Java? Just use o.length. Trying to follow to question as much as possible... Quote: You may not use "sizeof" or hard-code the size of the array. In other words, it must still work if the size of the array changes. |
Author: | wtd [ Sat Jul 15, 2006 8:37 am ] | ||||||||||
Post subject: | |||||||||||
OneOffDriveByPoster wrote: The obvious one is:
which should be
Yes. OneOffDriveByPoster wrote: I am not so clear about the explanation though, so here is my try at it:
argc can be 1; args can point to a zero-length array and be distinct from a pointer to any other object; using "plain" delete on args in such a case causes undefined behaviour (afaik). I suspect that
is also a cause of undefined behaviour when argc is 1.
This is simply pointer arithmetic. If argc is one, then one minus one is zero, and we get the same args pointer back. The reason we use:
Is that using just delete would treat the start of the dynamic array as a pointer to a single string object. It would free the memory for that one object, but not for the remainder of the array. The correct form of delete in this case frees all of the memory used by the array. Yes, the run-time does track information about how long the array is, so that it can do this. |
Author: | OneOffDriveByPoster [ Sat Jul 15, 2006 10:58 am ] | ||||||||||
Post subject: | |||||||||||
wtd wrote: OneOffDriveByPoster wrote: I suspect that
is also a cause of undefined behaviour when argc is 1.
This is simply pointer arithmetic. If argc is one, then one minus one is zero, and we get the same args pointer back. I was not thinking straight--argc does not have to be 1 for the code to be wrong.
The result of
is undefined, afaik. To get what you want, you need
|
Author: | wtd [ Sat Jul 15, 2006 11:07 am ] | ||||||||
Post subject: | |||||||||
OneOffDriveByPoster wrote: The result of
is undefined, afaik. To get what you want, you need
It is not undefined. args is a pointer. argc is an integer, as is "argc - 1". Adding a pointer and an integer is not undefined. It is in fact the way array access works.
Is equivalent to:
|
Author: | OneOffDriveByPoster [ Sat Jul 15, 2006 11:19 am ] | ||||||||||
Post subject: | |||||||||||
wtd wrote: OneOffDriveByPoster wrote: The result of
is undefined, afaik. To get what you want, you need
It is not undefined. args is a pointer. argc is an integer, as is "argc - 1". Adding a pointer and an integer is not undefined. It is in fact the way array access works.
Is equivalent to:
Seriously:
I guess I was wrong to say that it is "undefined", as the operation is defined (I guess). |
Author: | wtd [ Sat Jul 15, 2006 11:23 am ] |
Post subject: | |
It only produces undefined behavior if you dereference it. My code never does that. |
Author: | OneOffDriveByPoster [ Sat Jul 15, 2006 11:27 am ] |
Post subject: | |
wtd wrote: It only produces undefined behavior if you dereference it. My code never does that. :)
That was fast... There is a limitation to pointer arithmetic: for any object, you can only go "one past the end" of it and still have it work the way you expect it to. Of course, dereferencing the "one past the end" produces undefined behaviour. :) |
Author: | wtd [ Sat Jul 15, 2006 11:31 am ] |
Post subject: | |
Indeed. I'm headed out in a bit, but until then I'm hanging out on the forums and in IRC. And all I need to do is go one past the end of the array, so that I have a known sentinel value. |
Author: | OneOffDriveByPoster [ Sat Jul 15, 2006 11:35 am ] | ||
Post subject: | |||
wtd wrote: And all I need to do is go one past the end of the array, so that I have a known sentinel value.
Thus
so that you don't go past "one-past". |
Author: | wtd [ Sat Jul 15, 2006 11:38 am ] |
Post subject: | |
Ok... I think you're missing something here. Pointers are just numbers. Within the range of that integer type, I can assign any value I want to a pointer. As long as I don't dereference it, there's no problem. |
Author: | OneOffDriveByPoster [ Sat Jul 15, 2006 11:40 am ] |
Post subject: | |
wtd wrote: Ok... I think you're missing something here.
Pointers are just numbers. Within the range of that integer type, I can assign any value I want to a pointer. As long as I don't dereference it, there's no problem. Everything on a computer are just numbers :) Just do a Google search on "C++ pointer-arithmetic one-past-the-end". |
Author: | Aziz [ Sat Jul 15, 2006 11:43 am ] |
Post subject: | |
This noobie knows something doesn't it feel good? |
Author: | wtd [ Sat Jul 15, 2006 12:34 pm ] |
Post subject: | |
As far I can tell, the standard specifies only that any of this becomes an issue when dereferencing is brought into question. Comparing the value of two pointers does not entail any dereferencing operation(s). If you know of a section of the standard that specifies otherwise, please enlighten me. |
Author: | [Gandalf] [ Sat Jul 15, 2006 12:37 pm ] |
Post subject: | |
Aziz wrote: Trying to follow to question as much as possible...
Quote: You may not use "sizeof" or hard-code the size of the array. In other words, it must still work if the size of the array changes. You're not using any Java equivalent of "sizeof" (which wouldn't really help you anyway) by using myArray.length, nor does it cause problems when the size of the array changes. It's still only checking for the length of the array that was passed, which does not change. |
Author: | Aziz [ Sat Jul 15, 2006 12:47 pm ] |
Post subject: | |
I guess I should learn C++ then eh |
Author: | OneOffDriveByPoster [ Sat Jul 15, 2006 12:49 pm ] |
Post subject: | |
wtd wrote: As far I can tell, the standard specifies only that any of this becomes an issue when dereferencing is brought into question. Comparing the value of two pointers does not entail any dereferencing operation(s).
If you know of a section of the standard that specifies otherwise, please enlighten me. 5.7 [expr.add] paragraph 5; hope this helps. Also: I'm sorry for not pm'ing the stuff to you instead of posting--I did not read the 2005 TYS thread until now. |
Author: | wtd [ Sat Jul 15, 2006 1:48 pm ] |
Post subject: | |
If "enum" is being used in reference to all integral types, then pointer arithmetic is smply outright undefined behavior in all forms. |
Author: | OneOffDriveByPoster [ Sat Jul 15, 2006 2:07 pm ] |
Post subject: | |
wtd wrote: If "enum" is being used in reference to all integral types, then pointer arithmetic is smply outright undefined behavior in all forms.
? are we looking at the same thing? |
Author: | wtd [ Sat Jul 15, 2006 2:15 pm ] |
Post subject: | |
Can you provide an exact quotation for what you're looking at? |
Author: | OneOffDriveByPoster [ Sat Jul 15, 2006 2:36 pm ] |
Post subject: | |
wtd wrote: Can you provide an exact quotation for what you're looking at?
Here it is: ISO C++98 5.7.5 wrote: When an expression that has integral type is added to or subtracted
from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integral expression. In other words, if the expression P points to the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N (where N has the value n) point to, respectively, the i+n-th and i-n- th elements of the array object, provided they exist. Moreover, if the expression P points to the last element of an array object, the expression (P)+1 points one past the last element of the array object, and if the expression Q points one past the last element of an array object, the expression (Q)-1 points to the last element of the array object. If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined. |
Author: | wtd [ Sat Jul 15, 2006 2:49 pm ] |
Post subject: | |
Gracias. Interesting. Of course, having the ability to go one past the end suffices for pretty much any foreseeable scenario. |
Author: | OneOffDriveByPoster [ Sat Jul 15, 2006 4:59 pm ] |
Post subject: | |
wtd wrote: Gracias.
Interesting. Of course, having the ability to go one past the end suffices for pretty much any foreseeable scenario. You're welcome. Your TYS question was interesting too. :) |
Author: | wtd [ Sat Jul 15, 2006 5:17 pm ] |
Post subject: | |
You should try some of the non-C++ questions so your frightening knowledge of ISO standards won't come into play. Though admittedly there are a fair number of C++ TYS questions. I chalk it up to the number of odd quirks in C++ syntax and semantics. |