Thread: Almost Daily Contest #1

  1. #1
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897

    Almost Daily Contest #1

    To start of my tenure as contest master, I'll test the waters with some quick contests. If everyone likes them then I'll make some more on a (hopefully) almost daily basis. I say almost daily because it's not easy coming up with something good and my time is limited.

    Please PM me with suggestions and comments so that I can adjust my methods to meet the demand.

    The Almost Daily Contest will run for a set amount of time. Anyone may participate by emailing their submission to [email protected] with the subject "Almost Daily Contest Entry". Be sure to specify which difficulty level you're solving. There's no need to sign up ahead of time.

    Almost Daily Contest #1

    Beginner:

    Write a function in C or C++:

    long double digRev ( int val )

    that takes any valid integer and reverses the digits. Your function should work for every valid int from INT_MAX to INT_MIN. Example:

    digRev ( 12345 );

    This should result in 54321. You will be graded on the following categories:

    Speed: Nice and toasty.
    Elegance: Easy on the eyes.
    Portability: It needs to run wherever I test it.


    Intermediate:

    A triangle can be formed with side lengths 4, 5, and 8. It's not possible to form a triangle with side lengths of 4, 5, and 9.

    You have eight sticks, no three of which can be used to form a triangle. Write a program to calculate the shortest possible length of the longest stick where the shortest stick is length 1.

    Correctness: Does it work right?
    Speed: Is efficient?
    Elegance: Elegant solutions are most welcome

    Hints: Triangle Inequality


    Advanced:

    Write a function in C or low level C++ (no STL):

    char findFirstNonRepeat ( char *s );

    that returns the first character that is not repeated in the string. For example, in "google", the first nonrepeated character is 'l', in "better", the first nonrepeated character is 'b'.

    You may use any number and type of helper functions and data structures, but the algorithm must have a complexity of O(n) or better. Your function will be graded on:

    Speed: Pedal to the metal
    Elegance: Nifty algorithms are always good

    Contest End: Tuesday, August 5, 2003
    Last edited by Prelude; 08-02-2003 at 12:21 PM.
    My best code is written with the delete key.

  2. #2
    Registered User
    Join Date
    Jan 2003
    Posts
    648
    I have submitted my entries for all three.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >I have submitted my entries for all three.
    Recieved and graded, thank you.
    My best code is written with the delete key.

  4. #4
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    You have eight sticks, no three of which can be used to form a triangle. Write a program to calculate the shortest possible length of the longest stick.
    I don't understand...The shortest length...So you want us to generate 7 random lengths that can't make a triangle and determine what the shortest length of the eighth would be assuming its the longest?

    edit: Ok I think it makes more sense now...are we assuming no decimals?
    Last edited by JaWiB; 08-02-2003 at 12:42 PM.
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >I don't understand...The shortest length...
    Triangle Inequality: In order to be unable to make a triangle with three sticks, one has to be at least as long as the sum of the others.

    What I want is a function that takes the number of sticks (in this case 8), where the shortest of them is 1. It then proceeds to calculate the shortest possible length of the longest stick. Keep in mind the rule of triangle inequality when doing this though.

    >So you want us to generate 7 random lengths that can't make a triangle
    You don't need any lengths at all except for the shortest, which is 1. Your program should be able to calculate the correct answer given the number of sticks and the assumption that the shortest stick is 1.

    >are we assuming no decimals?
    Use whatever helps you to get the answer, but you don't need decimals.

    This task is dreadfully easy if you make the connection, but I'm thinking that maybe I should have swapped the intermediate and advanced tasks.
    My best code is written with the delete key.

  6. #6
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    I think I understand now...I think your sneaky little edit made it a bit clearer
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  7. #7
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    I would have liked a string size passed on on findFirstNonRepeat() but hey, can't have everything I guess. It would have been easier to do an O(n) anyway. But if I remember my order notation stuff correctly, walking through exactly twice is 2n which is O(n) right? ok, nevermind.
    "You are stupid! You are stupid! Oh, and don't forget, you are STUPID!" - Dexter

  8. #8
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    My entry is submitted...
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  9. #9
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    submitted one, loads a fun, so quickly done, it means a ton.
    "You are stupid! You are stupid! Oh, and don't forget, you are STUPID!" - Dexter

  10. #10
    Registered User KurtSurge's Avatar
    Join Date
    Aug 2003
    Posts
    25
    Umm... whats this mean? --> O(n)
    It's too bad that stupidity isn't painful
    --Anton Szandor LaVey

  11. #11
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    It's Big O notation, and is a measurement of the speed of the algorithm.

    edit: well, sorta. Look it up on Google.
    Away.

  12. #12
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Update

    The following people have submitted entries and been graded (in order of submission):

    Speedy5 (Beginner, Intermediate, Advanced)
    Sean345 (Advanced)
    JaWiB (Intermediate)
    FillYourBrain (Advanced)
    Hammer (Advanced)
    XSquared (Advanced)

    Keep the entries coming, every task can still be won. So far nobody has matched or exceeded my test functions. Who's going to do it? Could it be you? We'll just have to wait and see, but if you don't enter, you won't win.
    My best code is written with the delete key.

  13. #13
    Registered User
    Join Date
    Jan 2003
    Posts
    648
    Originally posted by Prelude
    Keep the entries coming, every task can still be won. So far nobody has matched or exceeded my test functions.[/B]
    Huh? All my functions work and they are pretty partly optimized too (for speed).

  14. #14
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Huh? All my functions work and they are pretty partly optimized too (for speed).
    You'll see when the winners are posted. Though I will tell you that your intermediate entry didn't solve the right problem. I'll accept an update if you want to send another attempt. This is because my description of the task was vague at best, my appologies.
    My best code is written with the delete key.

  15. #15
    Registered User
    Join Date
    Jan 2003
    Posts
    648
    Could you re-explain the intermediate problem? What I got out of it the first time was that there are 8 sticks. You have to use two of those eight for 2 sides of a triangle. The goal is to choose the correct sticks so that the third side is the smallest possible. Coming to think of it, my function does it in a kinda inefficient way...

    Ok I think I got the new problem: You have 8 sticks, which one of them is 1. The other 7 can be any numbers in the world, and they can repeat in the list -- just as long as no trio of sticks can make a triangle. What you want is a function that'll find the shortest length so that all 9 sticks still can't make triangles. Right?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Almost Daily Contest Details
    By dagdarian in forum Contests Board
    Replies: 4
    Last Post: 01-25-2005, 05:03 AM
  2. Almost Daily Contest Details
    By Prelude in forum Contests Board
    Replies: 29
    Last Post: 09-19-2004, 10:32 PM
  3. Almost Daily Contest #4
    By Prelude in forum Contests Board
    Replies: 35
    Last Post: 08-25-2003, 08:54 AM
  4. Almost Daily Contest #3
    By Prelude in forum Contests Board
    Replies: 29
    Last Post: 08-16-2003, 08:48 PM
  5. Almost Daily Contest #2
    By Prelude in forum Contests Board
    Replies: 37
    Last Post: 08-09-2003, 10:51 PM