Qbasicnews.com
May 25, 2022, 10:44:55 PM *
Welcome, Guest. Please login or register.

Login with username, password and session length
News: Back to Qbasicnews.com | QB Online Help | FAQ | Chat | All Basic Code | QB Knowledge Base
 
   Home   Help Search Login Register  
Pages: 1 [2]
  Print  
Author Topic: Real life problems :)  (Read 11170 times)
KiZ
__/--\__
*****
Posts: 2879


WWW
« Reply #15 on: September 28, 2004, 10:55:23 AM »

Quote from: "na_th_an"
DarkPrevail: Your second entry is fairly better. As I understand the code, it tries to calculate every possible combination and then minimize results. That may be feasible for small quantities, but it's terribly slow: it uses brute force. Anyhow, it gets the work done. It looks alot like the iterative version of the backtracking with prune approach (the easiest to code), whose recursive version is the one I'm gonna post when this challenge ends. You can still improve your algo: you can do some pruning Smiley, i.e. DO WHILE temp >= v(i) AND coinno < lowest Wink


You got it man, thats exactly what i was aiming for. I do agree it is not very efficient. I have to say, well done for understanding the code, as I lack the motivation to include comments (lol) and it's not the neatest code ever written. You are certainly correct when it comes to the pruning, i overlooked the fact that it could be made faster with such alterations as that, although i shall not correct it as this is a competition, and you suggested that, so it would be techincally cheating, not to mention the fact I wouldnt be able to locate any more bits to "prune" (i am not very good at code optimisation ;P)


Quote from: "na_th_an"
Right now, DarkPrevail is the winner


Yay!


P.s You should post some more challenges in the future, I enjoyed the challenge posed and your comments were very knowledgeable and had good crit. =)
Logged
Sterling Christensen
Na_th_an
*****
Posts: 1328


« Reply #16 on: September 28, 2004, 06:04:58 PM »

Also, suppose you had these coins: (11, 10, 2) and you want to total 12. Every solutions so far would start with 11 and then fail.
Logged
KiZ
__/--\__
*****
Posts: 2879


WWW
« Reply #17 on: September 29, 2004, 12:16:16 PM »

Sterling, you are correct!

I have modified my code

I only needed to change
[syntax="qbasic"]IF coinno < lowest THEN[/syntax]
to
[syntax="qbasic"]IF coinno < lowest AND temp = 0 THEN[/syntax]

Now it checks wether it actually finds the correct solution or not.

[syntax="qbasic"]DECLARE FUNCTION change% (amount%, v%(), s%())
'$STATIC
DEFINT A-Z

DIM s(5)

'Please unremark the problem you wish to run:

'This one doesnt need sorted:
'DIM v(5)
'v(0) = 1
'v(1) = 5
'v(2) = 10
'v(3) = 25
'v(4) = 50
'v(5) = 100
'amount = 347

'This one does need sorted:
'DIM v(5)
'v(0) = 10
'v(1) = 50
'v(2) = 1
'v(3) = 100
'v(4) = 25
'v(5) = 5
'amount = 347

'This one can be done more easily than 1x100 + 2x25:
'DIM v(2)
'v(0) = 25
'v(1) = 75
'v(2) = 100
'amount = 150

CLS
'INPUT "Please input the amount to convert to change"; amount
coins = change(amount, v(), s())
PRINT : PRINT "Coins required:": PRINT
FOR i = UBOUND(v, 1) TO 0 STEP -1
   IF s(i) THEN PRINT " "; s(i); v(i); "credit coins"
NEXT i
PRINT : PRINT coins; "coins in total"

FUNCTION change (amount, v(), s())

'init a little siftsort:
FOR i = 1 TO UBOUND(v, 1)
  FOR j = 0 TO UBOUND(v, 1) - i
    IF v(j) > v(j + 1) THEN SWAP v(j), v(j + 1)
  NEXT
NEXT

lowest = 999
FOR ii = UBOUND(v, 1) TO 0 STEP -1
  coinno = 0
  temp = amount
  ERASE s
  FOR i = ii TO 0 STEP -1
    DO WHILE temp >= v(i)
      temp = temp - v(i)
      coinno = coinno + 1
      s(i) = s(i) + 1
    LOOP
  NEXT
  IF coinno < lowest AND temp = 0 THEN
    lowest = coinno
    lowstart = ii
  END IF
NEXT

temp = amount
ERASE s
coinno = 0
FOR i = lowstart TO 0 STEP -1
  DO WHILE temp >= v(i)
    temp = temp - v(i)
    coinno = coinno + 1
    s(i) = s(i) + 1
  LOOP
NEXT
change = coinno
END FUNCTION[/syntax]
Logged
ToohTooh
New Member

Posts: 24



« Reply #18 on: September 30, 2004, 11:31:00 AM »

Hello again.

    WARNING[/list]
      ToohTooh cannot warrant that this code will always generate optimal solution sets, or even generate a correct solution. Although algorithm is based on a scientific approach, ToohTooh's implementation may include some incorrections.
      NOTICE[/list]
        Before working to find out how it works, make sure that you understand the data structure it uses well!..
      First off, as a die-hard QBer, I'd like to state that contributing to challenges more often as time permits is so warm (what's warm, anyway?). Thanks again, na_th_an!..

      This below is the Optimal Approach using the divide-and-conquer strategy.

      It's very fast, simple, short, effective and much like those you can find in text books (just because it's being tuned for days).

      To take advantage of repetitive works of its recursive-approach predecessor which I haven't released, it allocates some memory and begins building Amount from ground up generating results very fast.

      NOTICE: I dropped FindLimit(), and Sort(). They create too much mess, and are pretty off-topic. If you want them anyway, you may copy them from my code in a past post titled
      Code:
      '  ***
      '-- na_th_an's Coin Challenge: The Greedy Approach
      '-- Explore under QB IDE.
      '  ***
      and paste to this one.

      HISTORY: This new Change() derived from recursive-version's Change() and FindNumber(Amount) functions. Old Change() had nothing to do but to map results of FindNumber(Amount) to So(). FindNumber(Amount) would recursively find every possible So()'s for every Va(). Now, it integrated into this new Change(), leaving only the idea behind.

      Initial non-recursive version had the following
      Code:
      FOR i = 1 TO Amount
          FOR ii = 1 TO Limit
              IF i >= ii THEN
                  div = i \ ii
                  IF div >= minDiv THEN
                      minDiv = div
                      loMaker = ii
                  END IF
              END IF
          NEXT ii
          nrCoins(i) = minDiv
          amtToVa(i) = loMaker
      NEXT i
      instead of the one posted below. You can see that, the
      Code:
      div = i \ ii
      IF div >= minDiv THEN
          ...
      END IF
      structure is a heritage from my very early greedy approach version.

      Presence of this structure created some problems: It, by default, assumed a greedy approach and tried to construct every amount with minimum number of available Va() and it failed as it tended to grab greater Va()s.

      It also lacked an assumption: If no divs can be computed at a pass, we had to feed the algorithm with a default (namely, the first) Va():
      Code:
      minDiv = 1
      loMaker = 1

      Second rewrite brought the skeleton of the algorithm posted below with a difference such that a forced-first-assign like
      Code:
      IF bldThis < 0 THEN bldThis = 0
          min = nrCoins(bldThis)
          prospVaInd = 1
      END IF
      appeared instead of the sanity check
      Code:
      IF (bldThis >= 0) THEN
          ...
      END IF
      of the one below. This can be explained as follows: If an Amount is unconstructable with present Va() set (this happens at the early pass stages where FOR..NEXT produces very low i amount values), then a prospective Va() index assumption shouldn't be made as including present Va()s will just corrupt the result.

      TECHNICAL: Consider partitions of Amount whose summands are taken (repetitions allowed) from a sequence of integers
        Va() : (Va1, Va2, ...); 1 <= Va1 < Va2 < ...      [1]
      Giving such a partition [1] is equivalent to giving a solution of
        (n1 x Va1) + (n2 x Va2) + (n3 x Va3) + ... = Amount; n_i, Va_i nonnegative integers.      [2]
      Generating solutions to [2] with respect to sequence [1] is defined as
        Change(Amount; Va()) = Change(Amount; Va1, Va2, ...)      [3]
      Code I posted aims to generate a solution to the described problem with assumption such that
        n1 + n2 + ... = n_total -> min      [4]
      Algorithm for [3] create a solution set for [2] strictly adhering to [4], guaranteeing [2] with a correction such that
        (n1 x Va1) + (n2 x Va2) + (n3 x Va3) + ... = Amount + e; n_i, Va_i, nonnegative integers; e, positive integer or 0.      [5]
      where e stands for the output error (namely, the mismatched Amount).

      For a [4] yielding a
        e = 0      [6]
      in [5] requires you to strictly include Va(1) = 1 to the coin (denumerant) set (as already described in [1]). This way, you can always guarantee a solution, although not necessarily the optimal one.

      This code also demonstrates the trade-offs between in "gain-in-time, lose-in-space" rule (use memory, forget recursion).

      Feel free to test and tangle.
      Code:
      '  ***
      '-- na_th_an's Coin Challenge: The Optimal Approach
      '-- Explore under QB IDE.
      '  ***

      '-- This is an Intermediate / Advance level implementation of the challenge
      '    which demonstrates the uses of divide-and-conquer approach of
      '    Computer Science.

      '-- Rewritten several times so non-recursive.

      '-- All of its magic lies behind the memory use and taking advantage of
      '    repetitive works. Print this out and work it 'on paper,' too.

      '-- ToohTooh cannot warrant that this code will always generate optimal
      '    solution sets, or even generate a correct solution.

      '-- ToohTooh, in Istanbul City.

      DEFINT A-Z

      DECLARE FUNCTION Change (Va(), Limit, Amount, So())

      TYPE buildTAG  '>> Further info in Change()
          amtToVa AS INTEGER
          nrCoins AS INTEGER
      END TYPE

      '-- At every change, make sure you re-assign myLimit and sort values().
      myLimit = 3: DIM values(myLimit), solution(myLimit)
      values(0) = 1
      values(1) = 3
      values(2) = 5
      values(3) = 7
      myAmount = 9

      CLS
      PRINT "Worked for"; RTRIM$(STR$(myAmount));

      result = Change(values(), myLimit, myAmount, solution())
      PRINT ".": PRINT "Let's see... We have"
      FOR i = 0 TO UBOUND(solution)
          IF solution(i) <> 0 THEN PRINT solution(i); "coin(s) valued at"; values(i)
      NEXT i
      '-- myAmount of below may have a sign, so LTRIM it also.
      PRINT "to remain a total of "; LTRIM$(RTRIM$(STR$(myAmount))); "."
      IF NOT result THEN PRINT "Criteria couldn't be met with present values()."

      END '>> Main

      FUNCTION Change (Va(), Limit, Amount, So())  '>> So() assumed to have been
                                                   '    pre-initialized to zeroes.

      DIM bld(1024) AS buildTAG  '>> Will store results of repetitive calc.s

      '-- Say, Va(k) and So(k). This tells us that 'So(k) number of coins valued at
      '    Va(k) are reserved for optimal solution.'

      '-- Say (bld.nrCoins(x) = m) and (bld.amtToVa(x) = t). This tells that
      '    'm number of coins valued at Va(t) are required to construct Amount x.'

      FOR i = 1 TO Amount

          bldThis = i - Va(1)
          IF (bldThis >= 0) THEN  '>> Sanity check.
              '-- Special case for Va(1). Va(1) is considered to be the lowest coin
              min = bld(bldThis).nrCoins  ' capable of building every Amount
              prospVaInd = 1              ' (not necessarily the optimal one).
          END IF

          FOR ii = 2 TO Limit  '>> 1 was special case so start from 2.
              '-- Every other Va(ii), check for minimums.
              bldThis = i - Va(ii)
              IF (bldThis >= 0) THEN  '>> i.e.: Using Va(ii) logical (positive)?
                  IF (bld(bldThis).nrCoins < min) THEN
                      '-- A new minimum and so, a new prospective Va() index.
                      min = bld(bldThis).nrCoins
                      prospVaInd = ii
                  END IF
              END IF
          NEXT ii

          '-- If no new prospVaInds, old ones still go okay
          '    (for the fact that new i's (amounts): i(n) < i(n + 1) ).
          bld(i).amtToVa = prospVaInd
          '-- Every other i, increment nr. of coins (w/o caring constructed
          '    total will exceed Amount: This way, So() this FUNC returns
          '    always construct worst case amounts greater than input Amount.)
          bld(i).nrCoins = min + 1

      NEXT i

      Change = -1  '>> Change() default.
      WHILE (Amount > 0)
          index = bld(Amount).amtToVa
          So(index) = So(index) + 1  '>> Build So() decrementing Amount.
          Amount = Amount - Va(index)
      WEND
      IF Amount <> 0 THEN Change = 0  '>> Return err for positive(?)/negative Amount.

      END FUNCTION  '>> Change()
      Logged

      Don't interrupt me while I'm interrupting." - Winston S. Churchill
      Neo
      Na_th_an
      *****
      Posts: 2150



      « Reply #19 on: October 01, 2004, 08:45:09 AM »

      To NaThan and Moneo:

      I like this real life problem, as it was an exercise at the NIO as well. It was NIO 2004 Exercise I-2 to be exactly. It was then considered to be an 'easy' real life problem, although the exercise at the NIO was quite more difficult that this one, since here you have a set amount of coins and their values are set. In the Exercise I-2 however, a file was used to determine the coins and coin types used (to a maximum of 100 different coins and a maximum value of a coin of 32767). An example of coin input would be (Coins available: {1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}, Calculate best way to pay 7592). The problem was that there was also a time-limit of 10 (?) seconds, so you really had to make a perfect algorithm.

      Shall I post complete NIO 2004 Exercise I-2 if people are up to a challenge? Smiley
      Logged
      Moneo
      Na_th_an
      *****
      Posts: 1971


      « Reply #20 on: October 02, 2004, 12:12:48 AM »

      Neo,
      Not in my opinion. The guys seem to be getting a good workout with Nathan's version. If I find the time, I still may take a crack at it myself.
      *****
      Logged
      ToohTooh
      New Member

      Posts: 24



      « Reply #21 on: October 02, 2004, 08:12:48 AM »

      Hello, Neo.

      My recent algorithm calculates
        Change(7592; {1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31})
      in about 1 second on my experimental P350. It performs no sifting, though. If I were asked, it could have gone for one :-D. Thought you would be interested.

      When trying it out, apart from redefining
      Code:
      myLimit
      for redimensioning for the new query, don't forget to redimension
      Code:
      DIM bld(1024) AS buildTAG
      under Change() to something like 8192 also.

      And, yes: Post your challenge. If they are close to my area of interest and profession, I, myself, would be glad to participate.

      Notice (this is not the best place to post this, but...): I had no way to post an entry to your character recognization challenge. A reasonable one would involve AI, statistics, and stuff like that. This is too much luxury for BASIC, I suppose. I think you told you wrote it in BASIC. Can we take a look at it? Thanks in advance.
      Logged

      Don't interrupt me while I'm interrupting." - Winston S. Churchill
      Neo
      Na_th_an
      *****
      Posts: 2150



      « Reply #22 on: October 03, 2004, 12:46:55 PM »

      Quote from: "Moneo"
      Neo,
      Not in my opinion. The guys seem to be getting a good workout with Nathan's version. If I find the time, I still may take a crack at it myself.

      You say so... Cool (*glad I don't have to translate 10 pages of exercises...* :lol:)
      Maybe I'll take a look at it myself again, after all, it was a year ago... Smiley

      Quote from: "ToohTooh"
      Notice (this is not the best place to post this, but...): I had no way to post an entry to your character recognization challenge. A reasonable one would involve AI, statistics, and stuff like that. This is too much luxury for BASIC, I suppose. I think you told you wrote it in BASIC. Can we take a look at it? Thanks in advance.

      Hello ToohTooh,

      That 1 second to calculate the problem is great! Smiley Then you have 10 points for that test run if you were on the NIO Smiley *Looks up test run files* Ah, there's no copy on the internet Sad
      Anyway, I'm interested in how you calculated the answer so quickly, because even our C++ version took ages... Smiley

      About the character recognition, I suggest you read the topic again Smiley It isn't writing an OCR, it's just solving some exercises. The exercises are rather simple to do in QB, as in the exercise description, there's also told how you can tackle the problem. If the problem was to write an OCR, this problem would have been too much in any programming language.
      You can always take a look at my code if you're interested though. Just PM me and I'll send them to you.



      To all:
      If anyone likes a real competition, try out http://www.codecup.nl/intro.php!!! Cheesy
      Logged
      Pages: 1 [2]
        Print  
       
      Jump to:  

      Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!