Qbasicnews.com

Full Version: Real life problems :)
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Pages: 1 2 3
>O_O< Ditto....
.
.
.
.
Mine's still better! It's short =P
I regret to let you know that I have no way to make do the testing(!), tangling(?) and fine-tuning(!?!) works of my promised solution optimizer for next few days.

I'm an intern at an outsourcing Turkish game company, and my internship is coming to an end. I've got to deliver my last project on simplifying a "Docking Tool Bar Foundation" in C++.

Hey, just prioritizing tasks here!.. Cry
Quote:Mine's still better! It's short =P

WT, yours only solved one of the three problems though. So you would expect Toohtooh's and my code to be a lot longer.
Quote:WT, yours only solved one of the three problems though. So you would expect Toohtooh's and my code to be a lot longer.

uh eh hmmmm I KNOW YOU WHERE LIVE! *tracerts IP*
.
.
fine but it's still better on some other degree. -_-
Hello! Time for reviews:

ToohTooh: Your sollution has some of the problems that the original DarkPrevail's and Whitetigers': It's a greedy approach. The greedy approach doesn't guarantee that the best sollution is gonna be returned; it doesn't even guarantee that you're gonna get a sollution (you won't ever get a sollution for (100, 75, 52) with amount = 150, when there's one. The greedy approach just tries once, tries to get the best fit at once, and when it finds a sollution it stops trying.

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 Smile, i.e. DO WHILE temp >= v(i) AND coinno < lowest Wink

Right now, DarkPrevail is the winner, unless ToohTooh posts the new version or someone else post something better.

PS. Moneo, weren't you gonna enter this one?
Quote: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 Smile, 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: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. =)
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.
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]
Hello again.
  • WARNING
  • 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
  • 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()
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? Smile
Pages: 1 2 3