Page 6 of 6 FirstFirst ... 456
Results 51 to 56 of 56

Thread: Beginner Programming Challenge 13

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

    Re: Beginner Programming Challenge 13

    Quote Originally Posted by dv3500ea View Post
    To clarify:
    If an account has a balance of 100 and something more is (attempted) withdrawn, should the new balance be 60?
    If an account has a balance of 20 and something more is (attempted) withdrawn should the new balance be -20?
    That's what sometimes happens in the real world, so why not?
    Forum DOs and DON'Ts
    Never assume that information you find using a search engine is up-to-date.
    Please use CODE tags.

  2. #52
    Join Date
    Sep 2009
    Location
    UK
    Beans
    535
    Distro
    Ubuntu 10.10 Maverick Meerkat

    Re: Beginner Programming Challenge 13

    Here is my final program:

    Code:
    #!/usr/bin/env perl
    #
    #       challenge13.pl
    #       
    #       Copyright 2010
    #       
    #       This program is free software; you can redistribute it and/or modify
    #       it under the terms of the GNU General Public License as published by
    #       the Free Software Foundation; either version 2 of the License, or
    #       (at your option) any later version.
    #       
    #       This program is distributed in the hope that it will be useful,
    #       but WITHOUT ANY WARRANTY; without even the implied warranty of
    #       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    #       GNU General Public License for more details.
    #       
    #       You should have received a copy of the GNU General Public License
    #       along with this program; if not, write to the Free Software
    #       Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
    #       MA 02110-1301, USA.
    
    use strict;
    use warnings;
    
    #arguments:
    #only the first of '--speed' or '--debug' is processed
    #and only the first non-zero numerical argument is processed
    #if --speed is given, the results, unsorted, will be printed at the end of the program
    # and no warnings will be given.
    #if --debug is given, the balance after each transaction is printed, warnings are given
    # and the results are printed sorted at the end.
    #by default, the program runs the same as debug but without printing the balance
    # after each transaction.
    #the first non-zero argument will determine the overdraft fee, which defaults to 0
    
    my $mode = 2;
    my $overdraft_fee = 0;#amount charged on overdraft
    foreach (@ARGV) {
    	if ($_ eq '--debug' && $mode == 2) {
    		$mode = 1;
    	} elsif ($_ eq '--speed' && $mode == 2) {
    		$mode = 0;
    	} elsif ($overdraft_fee == 0) {
    		$overdraft_fee = $_+0;
    	}
    }
    
    sub mywarn {#warn unless --speed flag given
    	if ($mode) {
    		warn $_[0];
    	}
    }
    
    my %accounts = ();#hash for storing/retrieving accounts
    
    sub dep { #function to deposit money into account
    		my ($account, $amount) = @_;#arguments - account_number, amount
    		if (exists $accounts{$account}) {#if account exists
    				$accounts{$account} += $amount; #add deposit amount to account balance
    		} else {#if account doesn't exist
    				$accounts{$account} = $amount; #create account with balance amount
    		}
    		return $accounts{$account}; #return new balance
    }
    
    sub fee { #function to charge a fee to the account
    		my ($account, $amount) = @_;#arguments - account_number, amount
    		if (exists $accounts{$account}) {#if account exists
    				$accounts{$account} -= $amount; #take fee amount from account balance
    		} else {#if account doesn't exist
    				mywarn "What do you mean '$account', there is no such account!\n";
    		}
    		return $accounts{$account}; #return new balance
    }
    
    sub wd { #function to withdraw from account
    		my ($account, $amount) = @_;#arguments - account_number, amount
    		if (exists $accounts{$account}) {#if account exists
    				if ($accounts{$account} >= $amount) {#only succeed if enough balance
    					$accounts{$account} -= $amount; #take fee amount from account balance
    				} else {
    					mywarn "You can't withdraw $amount if you only have $accounts{$account}, charging overdraft fee of $overdraft_fee!\n";
    					fee($account, $overdraft_fee);#charge the overdraft fee
    				}
    		} else {#if account doesn't exist
    				mywarn "What do you mean '$account', there is no such account!\n";
    		}
    		return $accounts{$account}; #return new balance	
    }
    
    sub parse {
    		my $str = shift;
    		my ($trans, $account, $amount) = split(' ', $str);
    		#parse transaction_type account_num amount
    		$amount += 0; #turn amount into a number
    		$account += 0; 
    		#ensure account is a number. This ensures numerical sorting of accounts as a opposed to alphabetical
    		if ($trans eq 'wd' || $trans eq 'cred') {#withdraw commands
    				return wd($account, $amount);
    		} elsif ($trans eq 'fee') {#fee command
    				return fee($account, $amount);
    		} elsif ($trans eq 'dep' || $trans eq 'deb') {#deposit commands
    				return dep($account, $amount);
    		} else {#mywarning on incorrect commands
    				mywarn "'$trans' is not a transaction I understand! I do understand:\n
    	dep or deb = where money is put in
    	wd or cred = where money is taken out (as long as you have enough)
    	fee = where money is taken out (even if you don't have enough)\n";
    		} 
    		return '0';
    }
    
    if ($mode == 1) {#debug
    	while (<STDIN>) {#loop over input
    		print "BALANCE: " . parse($_) . "\n";#apply transactions and print new balance
    	} 
    } else {
    	while (<STDIN>) {#loop over input
    		parse($_);
    	} 
    }
    
    print "-" x 33 . "\n";
    
    if ($mode) {
    		foreach (sort {$a <=> $b} keys(%accounts)) {
    			print "Account: $_   Balance: $accounts{$_}\n";
    		}
    } else {#speed
    		foreach (keys(%accounts)) {
    			print "Account: $_   Balance: $accounts{$_}\n";
    		}
    }
    It can be optimised for greater speed by passing an argument of '--speed'.
    To see the balance after each transaction, pass '--debug' instead.
    The amount charged on overdraft will be the first non-zero numerical argument. The default overdraft charge is 0, so you'll probably want to run the program with 40 as its 1st argument.
    DMedia - Distributed Media Library
    LaVida - A simulation game for Linux
    AskUbuntu

  3. #53
    Join Date
    Apr 2008
    Beans
    101

    Re: Beginner Programming Challenge 13

    Quote Originally Posted by texaswriter View Post
    Hrrm, hash keys are probably the most robust method of searching/storing entries that exists. Their worst performance is usually better than the average performance of alternatives.
    I'm not an expert on hash tables, which is why I'd be wary of implementing my own. A naive implementation will degenerate into a list for pathological data (all values hash to the same bucket); you can get this down to O(log n) at the cost of added complexity. So worst case is comparable to a tree structure.

    Coming up with a good hash function is as easy as finding a good hash key. Finding a good hash key is a matter of finding prime numbers. The nice thing about hash keys is IT WILL HANDLE any distribution of data, EVEN SORTED. I do believe random data is preferable, HOWEVER, by using prime numbers as the key, you can even handle regular data as well. Data can be sequential [pre-sorted] as well and this doesn't even slow the hash function down.
    Again, I'm not an expert, but the Wikipedia page on "hash function" says that "the design of good hash functions is still a topic of active research", which isn't what I'd describe as "easy". Given the right hash function, you can get constant or near-constant insert and retrieval time, but without knowing how the keys are distributed I'd be hesitant to suggest one.

    In C++, you can do std::hash as well I believe.
    It's a common extension, but not yet part of the standard.

    As far as your other concern about scaling, if you base the prime key off of the size of the array [by some formula], than you can arbitrarily rehash every entry in the original hash table blindly into the new one and free() the original table. It's that simple.
    Of course you can, but then you've lost your linear insert time.

    Now, I'm not dissing hash tables in general, and of course it's your challenge and you can specify it as you see fit. I'd still be inclined to go for an ordinary map (tree structure) in the first instance, and swap for a hash table only if I needed the extra speed and if I was confident I wouldn't hit any pathological cases and I could handle any resizing penalty.

  4. #54
    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 jim_24601 View Post
    I'm not an expert on hash tables, which is why I'd be wary of implementing my own. A naive implementation will degenerate into a list for pathological data (all values hash to the same bucket); you can get this down to O(log n) at the cost of added complexity. So worst case is comparable to a tree structure.



    Again, I'm not an expert, but the Wikipedia page on "hash function" says that "the design of good hash functions is still a topic of active research", which isn't what I'd describe as "easy". Given the right hash function, you can get constant or near-constant insert and retrieval time, but without knowing how the keys are distributed I'd be hesitant to suggest one.



    It's a common extension, but not yet part of the standard.



    Of course you can, but then you've lost your linear insert time.

    Now, I'm not dissing hash tables in general, and of course it's your challenge and you can specify it as you see fit. I'd still be inclined to go for an ordinary map (tree structure) in the first instance, and swap for a hash table only if I needed the extra speed and if I was confident I wouldn't hit any pathological cases and I could handle any resizing penalty.
    Great!! if you want to discuss it any further, take it to private email with me. Otherwise, I won't discuss it any further here.

    Here is the official one week notice. If somebody wants some more time to submit, don't feel shy asking for postponement. I will definitely postpone the end of the competition to accommodate more entries.

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

    Lightbulb Re: Beginner Programming Challenge 13

    Congratulations to all who participated!! Some interesting choices of languages and implementations were used. Very excited to have as many submissions. Although not a very hard challenge, I can appreciate that it appears daunting and therefore did not elicit as many programmers as it could. Even still, there were several that did submit programs and I applaud you all for your efforts.

    Hopefully, even if you didn't submit a program, the challenge got you to thinking about what it might have taken.

    Update: I looked over the programs and felt that two programmers in particular were newer programmers looking to flex their programming muscles. Congratulations to dv3500ea for your well-written program, motivation to try other methods of solving the problem, and otherwise stepping up to the challenge. Once again, congratulations to anybody who participated in this challenge as it proves you can take a step forward in this very challenging medium of programming.

    dv3500ea> I look forward to seeing your beginner programming challenge. Great job!!!


    Last edited by texaswriter; June 25th, 2010 at 07:44 AM.

  6. #56
    Join Date
    Sep 2009
    Location
    UK
    Beans
    535
    Distro
    Ubuntu 10.10 Maverick Meerkat

    Re: Beginner Programming Challenge 13

    Thanks!

    It was a fun challenge and made me think about how to optimise my program for speed, which I don't normally do.

    I will post challenge 14 ASAP.
    DMedia - Distributed Media Library
    LaVida - A simulation game for Linux
    AskUbuntu

Page 6 of 6 FirstFirst ... 456

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
  •