Page 1 of 3 123 LastLast
Results 1 to 10 of 56

Thread: Beginner Programming Challenge 13

Hybrid View

  1. #1
    Join Date
    Jan 2010
    Location
    Not Texas
    Beans
    340
    Distro
    Ubuntu 14.04 Trusty Tahr

    Lightbulb Beginner Programming Challenge 13

    Beginner Programming Challenge #13

    Welcome to the 13th Beginner Programming Challenge!

    Hi fora, as the winner of the last beginner programming challenge, I am pleased to present the next challenge.

    For the next challenge, let's make a simple banking program that will take the following as input:

    transaction_code account_number amount
    The transaction codes will be as follows:
    wd - withdrawal [money taken out of the account]
    dep - deposit [money put into the account]
    cred - not what you think it is: [money taken out of the account] YES: this is a withdrawal
    deb - not what you think it is: [money put into the account] YES: this is a deposit
    fee - this is money taken out of the account, but not given to the accountholder. Although basically a withdrawal, this is the only code that allows a withdrawal if it makes the balance less than zero OR if the balance is already less than or equal to zero.

    OK, the program will accept as input in the above-named format and make a record of account numbers and the respective balances. The account can NEVER go negative [from the account-holder's perspective] EXCEPT in the case of a fee. In the event of an "overdraft", the withdrawal/credit will NOT be processed, but a fee will be assessed.

    Here's the challenging part: NO existing database or existing hashing sequence can be used. Hint: I would recommend using a hashing technique, but as long as an existing database/MySQL method isn't used, I will allow any implementation.

    To simplify what I mean here: the programmer should make everything here from scratch except the container for the data and/or the method of resizing the array. Or in other words. Some languages have an "insert" or "append" entry for arrays. C has remalloc. These are both acceptable or *anything* comparable. If a sort or search method is used, you must make this from scratch. If there is a list.search... you can't use it.

    EXTRA CREDIT REQUIREMENTS ONLY
    : If you want extra credit, make your table with a max number of entries so that your overall array can not be a) resizeable b) greater than xx% greater than the maximum number of entries. At the point that you start using malloc and resize, you would have to sort or redo the whole hash table, which is very inefficient. So, to simplify the task, we'll just set a maximum number of entries at 200. That would make the array's maximum size of 200+200*.xx. Want more credit: find out what the minimal percentage is that still allows an efficient hash search/recall routine.

    Please note: regardless of implementation, it will need to accommodate 200 account numbers.

    I will submit a file that will contain sample entries. The bank program won't "open" the file, but the file will be redirected as the std input. This file may contain any number of entries to facilitate making a decisive choice on speed. To clarify, the speed factor is just to encourage people to be wary of the method they choose in storage/retrieval of the account # & balance.

    Here is how I will be judging the entries:
    1) Readability and appropriate commenting. Following standard code formatting will make your code more readable. Although I have a tendency to comment quite a bit, if you use strategic commenting, you would be surprised how little commenting can actually be useful
    2) Elegance of design. While not as obvious, consider how a feature is being implemented to see if there is a better way.
    3) Overall program speed. To reward those who do this in a way that maximizes speed. Specifically, use whatever implementation you want, but bear in mind that some methods will mean speed sacrifices.
    4) Robustness of design. If the program handles all the above-named things without crashing and is able to handle all exceptions this will look very good.
    5) Extra credit.

    Extra credit section: I will try to make two files, one that has 100% correct entries [as in no invalid transaction codes] and one that has many transaction codes. The format for all the data will be correct and inviolable [you don't have to worry about getting text for the account number or dollar amount of transaction]. The account number will be a number with no leading zeros. It will also be an integer. Assume whole dollar amounts.

    Another extra credit will be to see how small a percentage over the max account numbers you can get while still being able to fulfill the maximum account numbers. Or in other words, it should be possible to fit 200 accounts in a 240 entry table.

    This challenge may seem daunting, but once you figure out your hashing routine, the rest of the challenge will be much easier.

    Good luck

    and p.s. until I get a file uploaded, you can test your program with normal input or make up your own file.
    The file will be 3 items wide, separated with a space, the lines will be terminated normally.
    An example input file would be

    dep 11111 25
    wd 11111 22599
    wd 11111 -2525
    Last edited by texaswriter; June 6th, 2010 at 03:41 AM. Reason: clarified

  2. #2
    Join Date
    Jun 2007
    Location
    Porirua, New Zealand
    Beans
    Hidden!
    Distro
    Ubuntu

    Re: Beginner Programming Challenge 13

    Quote Originally Posted by texaswriter View Post
    transaction_code account_number amount
    The transaction codes will be as follows:
    wd - withdrawal [money taken out of the account]
    dep - deposit [money put into the account]
    cred - not what you think it is: [money taken out of the account]
    deb - not what you think it is: [money put into the account]

    fee - this is money taken out of the account, but not given to the accountholder.
    Nice touch! I see what you did there.....
    Forum DOs and DON'Ts
    Never assume that information you find using a search engine is up-to-date.
    Please use CODE tags.

  3. #3
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Beans
    24
    Distro
    Kubuntu 9.10 Karmic Koala

    Re: Beginner Programming Challenge 13

    Here's the challenging part: NO existing database or existing hashing sequence can be used. I would recommend using a hashing technique, but as long as an existing database/method isn't used, I will allow any implementation. To simplify what I mean here: the programmer should make everything here from scratch.
    I don't quite understand this. So in Python, lists, tuples and dictionaries cannot be used? Or can they?

  4. #4
    Join Date
    May 2008
    Beans
    Hidden!

    Re: Beginner Programming Challenge 13

    Quote Originally Posted by bunburya View Post
    I don't quite understand this. So in Python, lists, tuples and dictionaries cannot be used? Or can they?
    That would be a ridiculous restriction; more likely it bars the use of things like SQL- e.g. "real" databases.

  5. #5
    Join Date
    Jan 2010
    Location
    Not Texas
    Beans
    340
    Distro
    Ubuntu 14.04 Trusty Tahr

    Lightbulb Re: Beginner Programming Challenge 13

    bunburya> thanks!!

    lisati> Those have built-in capabilities that break that rule. That said, a list by itself or something similar WOULD be fine as long as you never resize it or use built-in functions/libraries to fulfill the challenges laid out.

    snova> that is the correct interpretation.
    Last edited by texaswriter; June 2nd, 2010 at 09:57 PM.

  6. #6
    Join Date
    Dec 2007
    Location
    Behind you!!
    Beans
    977
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginner Programming Challenge 13

    Quote Originally Posted by texaswriter View Post
    bunburya> thanks!!

    lisati> Those have built-in capabilities that break that rule. That said, a list by itself or something similar WOULD be fine as long as you never resize it or use built-in functions/libraries to fulfill the challenges laid out.

    snova> that is the correct interpretation.
    A list in Python is always resizeable. And does the 'from scratch' bit mean I cant use pickle to write a list to file, which would then mean I have to store it in plain textt and write a parser function?

    Bodsda
    computer-howto
    Linux is not windows
    Fluxbox & Flux menu how to
    Programming is an art. Learn it, Live it, Love it!


  7. #7
    Join Date
    Aug 2007
    Location
    UK
    Beans
    427
    Distro
    Ubuntu UNR

    Re: Beginner Programming Challenge 13

    Better to bar certain languages rather than train people to program "badly" in them IMHO.

    Also: http://dictionary.reference.com/brow...er%27s+Disease
    C Programmer's Disease definition:
    The tendency of the undisciplined C programmer to set arbitrary but supposedly generous static limits on table sizes (defined, if you're lucky, by constants in header files) rather than taking the trouble to do proper dynamic storage allocation. If an application user later needs to put 68 elements into a table of size 50, the afflicted programmer reasons that he or she can easily reset the table size to 68 (or even as much as 70, to allow for future expansion) and recompile. This gives the programmer the comfortable feeling of having made the effort to satisfy the user's (unreasonable) demands, and often affords the user multiple opportunities to explore the marvellous consequences of fandango on core. In severe cases of the disease, the programmer cannot comprehend why each fix of this kind seems only to further disgruntle the user.
    @Bodsda: The collections.deque object can be declared fixed size.
    Last edited by StephenF; June 5th, 2010 at 09:55 AM.

  8. #8
    Join Date
    Jun 2007
    Location
    Porirua, New Zealand
    Beans
    Hidden!
    Distro
    Ubuntu

    Re: Beginner Programming Challenge 13

    Quote Originally Posted by texaswriter View Post
    lisati> Those have built-in capabilities that break that rule. That said, a list by itself or something similar WOULD be fine as long as you never resize it or use built-in functions/libraries to fulfill the challenges laid out.
    Huh? I wasn't think of lists, but of debit and credit.

    In a real-world bookkeeping system......
    Last edited by lisati; June 7th, 2010 at 08:12 AM. Reason: Added explanation; said too much
    Forum DOs and DON'Ts
    Never assume that information you find using a search engine is up-to-date.
    Please use CODE tags.

  9. #9
    Join Date
    Jan 2010
    Location
    Not Texas
    Beans
    340
    Distro
    Ubuntu 14.04 Trusty Tahr

    Lightbulb Re: Beginner Programming Challenge 13

    Quote Originally Posted by lisati View Post
    Huh? I wasn't think of lists, but of debit and credit.

    In a real-world bookkeeping system......
    Yeah, strike the part about not having a resizeable array. I think I edited that out, if not you can use a resizeable array. I will only create 200 account numbers in my test and will only expect 200 to be created. Nobody has to implement a static limit, however. Please read the rest of this post to understand why. Otherwise, your code is fine.


    Notarika>
    Quote Originally Posted by Notarika View Post
    To clarify, according to the contest rules, does using the stl iterator violate the rules? E.g.
    OK, from what I see, is not 'iter' similar to the list with comparable built-in functions accompanying it? If so, it is acceptable given the same restrictions set for the other one. Simple built-in functions are acceptable such as insert, append...

    So yes, that is acceptable.


    For everybody else too>
    Anyways, for others as well, after anybody uploads code, within 24 hours I will test your code. Then I will PM you on how the program handled everything, general comments, as well as the time it took to handle 2100 random. The real final test will include something like 10,000 or 20,000 randomly generated transactions.

    How verbose the program is varies on the programmers tastes as long as, at the very least, the end balance of the accounts is apparent. Even just printing the balance at the end of each transaction would work perfectly. One person just printed the balances at the very end. Either of these implementations is fine.

    Finally, just a quick bit about judging. Although most of the categories will be more or less pass/fail, which will be a cursory glance for me, one category will be looked at much closer. I have simply divided the points among each category [25% each] and then the extra credit [20% extra]. The hash key will be challenging, though rewarding to learn and for judging consideration. Edit: in light of recent changes to make this challenge more beginner friendly, how much someone learns/grows with their program will be considered. It's hard to really elaborate on this, but needless to say it's of benefit to any programmers poking their head into the world of programming.

    To summarize the above again, most people *should* get 75% of the points. If you use a hash key to store/retrieve account numbers and/or balances you will be simply awarded the 20% [supposing it is genuinely used]. Otherwise, the contest will come down to time.

    The only one worth mentioning in detail is the time. Here is exactly how I will judge who gets what for their time. First off, I will make a file with 10,000 or 20,000 account numbers. I will have transactions for non-existing account numbers. If an account number doesn't exist AND the transaction is not a deposit [or something that does the same thing], the account number should not be created. I will put alot of non-existent account numbers in there and I will put a penalty in this category if account numbers are just blindly created. I'm really testing how fast your subroutine searches for account numbers and the only way to really test it is to see how long it takes to go through all your account numbers [if applicable].

    Anyways, so let's say we have the following times for processing the file:

    Person 1: 5 seconds
    Person 2: 4 seconds
    Person 3: 2 seconds
    Person 4: .5 seconds
    Person 5: .6 seconds

    Person 4 has the lowest time and will be awarded 100% of points for this category. Here is how the rest's points will be calculated.

    Person 1: 1/(5/.5) = 10%
    Person 2: 1/(4/.5) = 12.5%
    Person 3: 1/(2/.5) = 25%
    Person 4: 1/(.5/.5)= 100%
    Person 5: 1/(.6/.5)= 83.3%

    Please note: I will post everybody's times [possibly anonymously, as in just a list of times] one week before the competition ends to give people a chance to possibly change. Since I would have PM'ed you your time(s), you can easily know what score you will get here.

    Like I said, this will be the only category that will be assessed technically, the rest are essentially pass fail. I want the challenge to be a learning experience, and if you wrote good, readable, straight-forward code, I want you to know this. I'm not trying to nit-pick anyone. The speed is important however.

    That said, kudos to those who have submitted code so far and I look forward to seeing more novel implementations by others.

    Keep up the great work!!
    Last edited by texaswriter; June 8th, 2010 at 06:27 AM.

  10. #10
    Join Date
    Jun 2006
    Beans
    2,930

    Re: Beginner Programming Challenge 13

    Quote Originally Posted by texaswriter View Post
    At the point that you start using malloc and resize, you would have to sort or redo the whole hash table, which is very inefficient.
    Wouldn't using a linked-list address this?
    Support 7z in default installs!!!: Click Here

    How to use code blocks to post command output: Click Here
    Official Ubuntu Documentation

Page 1 of 3 123 LastLast

Tags for this Thread

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
  •