1 2 Previous Next 13 Replies Latest reply on Jul 7, 2020 2:37 AM by Quanwen Zhao

# How to obtain answer of this topic using PL/SQL snippet?

Hello, my ODC friends and guys .

A couple of days ago I listened a session about how to optimizing oracle procedure. At the end of this session the speaker left us an exercise of PL/SQL. Unfortunately I was stucking the topic yesterday more than one hour. So coming here to get help.

The topic is as folllows:

A conference venue can provide some tables and chairs for the venue layout. The following is the daily

rental unit price information (RMB/day/per amount):

Three-legged round table: 7

Four-legged square table: 15

Three-legged chair: 12

Four-legged chair: 8

A boss expects to use the price of 1888 RMB/day to arrange the venue. He needs at least two number of tables or chairs.

The total number of tables and chairs is expected to be 188, and the total number of legs of the tables and chairs is

between 588 and 699 (including 588 and 699). Of course, the money should also be spent.

Please use a piece small of PL/SQL code to help the boss design all possible solutions. The desired output is as follows:

TT_NUM    FT_NUM     TC_NUM     FC_NUM     TOTAL_LEGS

The variables are named as follows:

Three-legged round table is TT, four-legged square table is FT, three-legged chair is TC, four-legged chair is FC.

Thank you beforehand.

Best Regards

Quanwen Zhao

• ###### 1. Re: How to obtain answer of this topic using PL/SQL snippet?

My solution has never taken any effect .

```DECLARE
tt_pp CONSTANT INTEGER := 7;     -- three-legged rounc table (per price)
ft_pp CONSTANT INTEGER := 15;    -- four-legged square table (per price)
tc_pp CONSTANT INTEGER := 12;    -- three-legged chair (per price)
fc_pp CONSTANT INTEGER := 8;     -- four-legged chair (per price)

tt_num INTEGER;                  -- the number of three-legged rounc table
ft_num INTEGER;                  -- the number of four-legged square table
tc_num INTEGER;                  -- the number of three-legged chair
fc_num INTEGER;                  -- the number of four-legged chair

tt_tp INTEGER := tt_pp * tt_num; -- three-legged rounc table (total price)
ft_tp INTEGER := ft_pp * ft_num; -- four-legged square table (total price)
tc_tp INTEGER := tc_pp * tc_num; -- three-legged chair (total price)
fc_tp INTEGER := fc_pp * fc_num; -- four-legged chair (total price)

tt_legs INTEGER := 3 * tt_num;   -- the legs number of three-legged rounc table
ft_legs INTEGER := 4 * ft_num;   -- the legs number of four-legged square table
tc_legs INTEGER := 3 * tc_num;   -- the legs number of three-legged chair
fc_legs INTEGER := 4 * fc_num;   -- the legs number of four-legged chair

total_legs INTEGER := tt_legs + ft_legs + tc_legs +fc_legs;
BEGIN
IF total_legs BETWEEN 588 AND 699 THEN
fc_num := 188-tt_num-ft_num-tc_num;
fc_num := (1888-7*tt_num-15*ft_num-12*tc_num)/8;
END IF;
DBMS_OUTPUT.PUT_LINE('TT_NUM: ' || tt_num);
DBMS_OUTPUT.PUT_LINE('FT_NUM: ' || ft_num);
DBMS_OUTPUT.PUT_LINE('TC_NUM: ' || tc_num);
DBMS_OUTPUT.PUT_LINE('FC_NUM: ' || fc_num);
DBMS_OUTPUT.PUT_LINE('TOTAL_LEGS: ' || total_legs);
END;
/
```
• ###### 2. Re: How to obtain answer of this topic using PL/SQL snippet?

Hi,

Could you clarify what the following means :

He needs at least two number of tables or chairs.

and,

Of course, the money should also be spent.

does it mean totally spent?

• ###### 3. Re: How to obtain answer of this topic using PL/SQL snippet?

Hello odie_63 ,

He needs at least two number of tables or chairs.

Means that, at least two number of "three-legged round table", "four-legged square table", "three-legged chair", and "four-legged chair".

Of course, the money should also be spent.

Yes, the money totally spent should be 1888 RMB.

• ###### 4. Re: How to obtain answer of this topic using PL/SQL snippet?

Quanwen Zhao wrote:

He needs at least two number of tables or chairs.

Means that, at least two number of "three-legged round table", "four-legged square table", "three-legged chair", and "four-legged chair".

Still not clear. Does that mean that there must be at least two of each of the four furniture types?

Can there be all chairs and no tables? All tables and no chairs? That doesn't make sense.

Regards,

Stew

• ###### 5. Re: How to obtain answer of this topic using PL/SQL snippet?

Hello Stew ,

From the author's perspective, it seems like that means. but from the aspect of mathematic (some combination) also should be what you mentioned. On the other hand, from the business requirement the boss expects to put at least two number of tables and chairs (all including four categories).

Yes, when finishing reading that topic, I've also been your thoughts. You can first try to answer it based on the requirement of the topic. I guess some conditions (such as, 188, 1888, between 588 and 699) should be satisfied with having a restriction that the number of tables and chairs.

Best Regards

Quanwen Zhao

• ###### 6. Re: How to obtain answer of this topic using PL/SQL snippet?

Hello Quanwen Zhao,

for the fun I tried with a SQL statement.

First approach: brutal force: compute all the possibilities for tt_num ... fc_num and checks if the various conditions are met.

The only limit for each xx_num is that total price cannot be exceeded, total number of items cannot be exceeded, total number of legs cannot be exceeded.

((and as we need at least 2 different types of items we can substract 1 -well, more or less... see replies #9 and #10))

For example: for tt: the number must be <= 1888 / 7 - 1, <= 188 - 1, <= 699 / 3 - 1

i.e. <= LEAST( 268, 187, 232 ), i.e. <= 187

for ft: <= LEAST( 1888 / 15 - 1, 188 - 1, 699 / 4 - 1 ) i.e. <= LEAST( 124, 187, 173 ), i.e. <= 124

and so on.

Still: this makes quite a lot of possibilities to check (close to 700 million)

Anyway I ran the statement, it took 15 minutes and gave me 396 solutions.

Then I thought: once three of the numbers are fixed, we can just compute what should be the fourth one and check if this is part of the possibilities.

So my second way: combine all possibilities for ft_num, tc_num, fc_num, compute the corresponding tt_num (as 188 - other items) and check if the conditions are met.

The conditions are a bit more complex to write, but the reward is there: same result but in 5 seconds...

First one:

WITH constants AS

( SELECT 7 tt, 15 ft, 12 tc, 8 fc, 1888 tot, 188 num, 588 mini, 699 maxi FROM dual )

, tt AS

( SELECT LEVEL - 1 tt_num

FROM constants

CONNECT BY LEVEL <= LEAST( tot / tt, num, 1 + maxi / 3 )

)

, ft AS

( SELECT LEVEL - 1 ft_num

FROM constants

CONNECT BY LEVEL <= LEAST( tot / ft, num, 1 + maxi / 4 )

)

, tc AS

( SELECT LEVEL - 1 tc_num

FROM constants

CONNECT BY LEVEL <= LEAST( tot / tc, num, 1 + maxi / 3 )

)

, fc AS

( SELECT LEVEL - 1 fc_num

FROM constants

CONNECT BY LEVEL <= LEAST( tot / fc, num, 1 + maxi / 4 )

)

SELECT tt_num, ft_num, tc_num, fc_num

FROM constants

, tt, ft, tc, fc

WHERE tt_num * tt + ft_num * ft + tc_num * tc + fc_num * fc = tot

AND tt_num + ft_num + tc_num + fc_num = num

AND ( tt_num + ft_num ) * 3 + ( ft_num + fc_num * 4 ) BETWEEN mini AND maxi

AND ( tt_num + ft_num ) * 3 + ( ft_num + fc_num ) * 4 BETWEEN mini AND maxi

AND SIGN( tt_num ) + SIGN( ft_num ) + SIGN( tc_num ) + SIGN ( fc_num ) >= 2

;

TT_NUM    FT_NUM    TC_NUM    FC_NUM

---------- ---------- ---------- ----------

0        32        40        116

0        36        33        119

0        40        26        122

0        44        19        125

1        35        35        117

1        39        28        120

1        43        21        123

1        47        14        126

2        34        37        115

...

115        69          4          0

396 rows selected.

Elapsed: 00:15:00.01

Second one:

WITH constants AS

( SELECT 7 tt, 15 ft, 12 tc, 8 fc, 1888 tot, 188 num, 588 mini, 699 maxi FROM dual )

, ft AS

( SELECT LEVEL - 1 ft_num

FROM constants

CONNECT BY LEVEL <= LEAST( tot / ft, num, 1 + maxi / 4)

)

, tc AS

( SELECT LEVEL - 1 tc_num

FROM constants

CONNECT BY LEVEL <= LEAST( tot / tc, num, 1 + maxi / 3 )

)

, fc AS

( SELECT LEVEL - 1 fc_num

FROM constants

CONNECT BY LEVEL <= LEAST( tot / fc, num, 1 + maxi / 4 )

)

SELECT num - ( ft_num + tc_num + fc_num ) tt_num

, ft_num, tc_num, fc_num

FROM constants

, ft, tc, fc

WHERE  num - ( ft_num + tc_num + fc_num ) >= 0

AND ( num - ( ft_num + tc_num + fc_num ) ) * tt + ft_num * ft + tc_num * tc + fc_num * fc = tot

AND ( num - tc_num ) * 3 + ft_num + fc_num BETWEEN mini AND maxi

AND num * 3 + ft_num + fc_num BETWEEN mini AND maxi

AND SIGN( num - ( ft_num + tc_num + fc_num ) )

+ SIGN( ft_num ) + SIGN( tc_num ) + SIGN ( fc_num ) >= 2

;

...

396 rows selected.

1223 rows selected.

Elapsed: 00:00:05.02

(I know that original question is about PL/SQL, but then: I write a block with the SQL statement and that's it ;-)

BEGIN FOR r IN ( SELECT ... ) LOOP DBMS_OUTPUT.PUT_LINE( TO_CHAR( r.tt_num ) ... ); END LOOP; END;

Best regards,

Bruno Vroman.

Edited: correcting mistakes in formulas, thanks to Quanwen Zaho (see replies #7 and #8)

Edited: correcting more mistakes in formulas "1 +", (see replies #9 and #10)

• ###### 7. Re: How to obtain answer of this topic using PL/SQL snippet?

Hi Bruno ,

By the way, your expression in the first approach and the second might be incorrect.

Frist approach:

AND ( tt_num + ft_num ) * 3 + ( ft_num + fc_num * 4 ) BETWEEN mini AND maxi

is

AND ( tt_num + ft_num ) * 3 + ( ft_num + fc_num ) * 4 BETWEEN mini AND maxi

Second approach:

AND ( num - tc_num ) * 3 + ft_num + fc_num BETWEEN mini AND maxi

is

AND ( num - ft_num - tc_num - fc_num ) * 3 + ft_num * 4 + tc_num * 3 + fc_num * 4 BETWEEN mini AND maxi

finally, it is as follows:

AND num * 3 + ft_num + fc_num BETWEEN mini AND maxi

Thank you very much!

Best Regards

Quanwen Zhao

• ###### 8. Re: How to obtain answer of this topic using PL/SQL snippet?

Oops!

Thank you for the correction.

1st one: indeed, "*4" was wrongly placed, shame on me! (and thanks for your good eyes)

2nd one: you're correct also... (I had started with the wrong "option1" :-(

three_legs     * 3 +     four_legs       * 4 BETWEEN mini AND maxi

<=>  ( tt_num + tc_num ) * 3 + ( ft_num + fc_num ) * 4 BETWEEN mini AND maxi

as tt_num is "num - the others":

<=>  ( num - ( tc_num + ft_num + fc_num ) + tc_num ) * 3 +  ( ft_num + fc_num  ) * 4 BETWEEN mini AND maxi

<=>  ( num - tc_num - ft_num - fc_num + tc_num ) * 3 + ( ft_num + fc_num ) * 4 BETWEEN mini AND maxi

<=>  ( num - ft_num - fc_num ) * 3 + ( ft_num + fc_num ) * 4 BETWEEN mini AND maxi

<=>  3 * num - 3 * ft_num - 3 * fc_num +  4 * ft_num + 4 * fc_num BETWEEN mini AND maxi

<=>  3 * num + ft_num + fc_num BETWEEN mini AND maxi

Remark: now I have 1223 rows selected. (05.49 sec).

Best regards,

Bruno.

• ###### 9. Re: How to obtain answer of this topic using PL/SQL snippet?

Hi Bruno ,

For example: for tt: the number must be <= 1888 / 7 - 1, <= 188 - 1, <= 699 / 3 - 1

i.e. <= LEAST( 268, 187, 232 ), i.e. <= 187

I understand other SQL statements except the preceding quoted. Maybe on which is I don't have an idea in my mind.

Why substract 1? and you just consider (assume) the situation about only one number of three-legged round table, which is able to produce a condition to limit the number of tt?

Best Regards

Quanwen Zhao

• ###### 10. Re: How to obtain answer of this topic using PL/SQL snippet?

Hi,

the statement is "nearly correct" in fact.

The key point is the condition that we need at least TWO kind of items, so we can't consume all the resources with one kind. This has impact on the number of itesm of anby type for the three points of view: total_price / price_of_1_item, total_number_of_items,  total_number_of_legs

a) total_price / price of 1 item

-- Simple case: the total amount can be divided by the price of an item (like for fc that costs 8: 1888 is full price, one fc costs 8 -> we migt think that we can buy 1888 / 8 = 236 of them, but then we are nothing left to buy anything else => we can buy a max of 1888 / 8 - 1 of such items.

-- "not so simple case": for 3 of the 4 item types, total_price divided by price_of_1_item is not an integer... So for example: 4-leg table costs 15, so 1888 / 15 = 125.86667 so as we buy "integer" items, we can buy a maximum of 125 such items and the remaining is 13, enough to buy one of the other items... Fortunately I know that the solution "125 ft + 1 of the others" will not be possible (total will not be 1888)

For the other items things are OK as the remaining amount is not enough to buy another item:

The four cases are:

1888 / 7 = 269.714... -> 269 * 7 + remaining amount of 5, not enough to buy another type of item -> we can't buy more than 268.

1888 / 8 = 236, no remaining -> we can't byu more than 235

1888 / 12 = 157.333.. -> 157 * 12 + remaining amount of 4, not enough to buy another type of item -> we can't buy more than 156

1888 / 15 = 125.8666... -> 125 * 15 + remaining amount of 13, enough to buy 1 item of any other type, but total amount cannot match total_priice -> we can't buy more than 124

To be "more exact" it is not "minus one" that we should use but divide the ( total amount minus price of the cheapest other item ) by the price of an item...

b) total_number_of_items

easier and without discussion: we need a total of 188 items, so for any item type we cannot buy more than 188 - 1 items (if we buy 188, we can't buy a second type)

c) total_number_of_legs: (ouch!)

same as "b)": one type cannot consume the maximum number of legs.

-- Simple case: 3-leg items: as total of legs is 699 maxi, if we buy 699 / 3 = 233 items of a single 3-leg type, it is not possible to buy another type of item.

-- "not so simple case": 4-leg items: as 699 / 4 = 174.75, we can buy a max of 174 items and this leaves 3 legs, enough to buy 1 item with 3-legs...

Hmmm, I have to confess that I am confused here! Very fortunately I can show that this option (174 "4-leg" + 1 "3-leg") is not possible, but this is "by luck".

Anyway, lets prove it: total price 1888, 3-leg items cost: 7 or 15, so remaining amount for 174 "4-leg" = 1881 or 1876. For this amount we have to buy 174 "4-leg", lets say X ft and (174-X) fc. (X must be an integer)

Either: X * 15 + ( 174 - X ) * 8 ?=? 1881  Or  X * 15 + ( 174 - X ) * 8 ?=? 1876

<=>   X * 7 + 174 * 8 ?=? 1881           Or  X * 7 + 174 * 8 ?=? 1876

<=>   X ?=? ( 1881  -  174 * 8 ) / 7     Or  X ?=? ( 1876 - 174 * 8 ) / 7

<=>   X ?=? 489 / 7 =  68.857...         Or  X ?=? 484 / 7 = 69.14...

So this is not possible (as X is an integer)

But yes, this is pure luck... exact condition should have been "it remains at least 3 legs" and in a more general problem (we might add new constants for "number_of_legs") the condition should be "it remains at least enough legs to buy 1 item with the least number of legs that is not of the same type.

So one more time: hmmm, a mistake (but this one is a "real mistake", the previous ones were just a typo and the consequence of a typo...

Well, lets revise slightly the statement (but the result will remain the same in our case):

CONNECT BY LEVEL <= LEAST( tot / .., num, 1 + maxi / 3or4 )

Good that you question eveything!

Best regards,

Bruno.

• ###### 11. Re: How to obtain answer of this topic using PL/SQL snippet?

The problem can be summarized by this system of Diophantine equations :

7·x1 + 15·x2 + 12·x3 + 8·x4 = b1

x1 +    x2 +    x3 +   x4 = b2

3·x1 +  4·x2 +  3·x3 + 4·x4 = b3

where x1 = TT_NUM, x2 = FT_NUM, x3 = TC_NUM and x4 = FC_NUM

and b1 = 1888, b2 = 188 and b3 an integer in the range [588, 699]

In matrix notation :

A·X = B

┌  ┐

┌             ┐ │x1│   ┌  ┐

│  7 15 12  8 │ │x2│   │b1│

│  1  1  1  1 │·│x3│ = │b2│

│  3  4  3  4 │ │x4│   │b3│

└             ┘ └  ┘   └  ┘

Applying the theorem in this paper, row-reducing the concatenated matrix [Aᵗ|I] =

┌                        ┐

│  7  1  3 │  1  0  0  0 │

│ 15  1  4 │  0  1  0  0 │

│ 12  1  3 │  0  0  1  0 │

│  8  1  4 │  0  0  0  1 │

└                        ┘

┌                          ┐

│ 1  0  0 │ -3   2   2  -7 │

│ 0  1  0 │ -2  -2   2  -5 │

│ 0  0  1 │  3   2  -3   7 │

│ 0  0  0 │  2  -1  -1   5 │

└                          ┘

Given K =

┌  ┐

│k1│

│k2│

│k3│

│k4│

└  ┘

a vector solution of RᵗK = B

we immediately have (since R is diagonal) :

k1 = b1

k2 = b2

k3 = b3

k4 = n (an arbitrary integer)

so a solution X = TᵗK is :

(1)  x1 = -3·b1 + 2·b2 + 2·b3 - 7·n

(2)  x2 = -2·b1 - 2·b2 + 2·b3 - 5·n

(3)  x3 =  3·b1 + 2·b2 - 3·b3 + 7·n

(4)  x4 =  2·b1 -   b2 -   b3 + 5·n

Possible values of integer n can be derived using, for example eq. (4), applying the constraint 0 <= x4 <= b2.

Putting it all together in a SQL query :

with consts (b1, b2, b3) as (

select 1888, 188, 588 + level - 1

from dual

connect by level <= 699 - 588 + 1

)

select x1 as TT_NUM

, x2 as FT_NUM

, x3 as TC_NUM

, x4 as FC_NUM

, 3*x1 + 4*x2 + 3*x3 + 4*x4 as TOTAL_LEGS

from (

select -3*b1 + 2*b2 + 2*b3 - 7*k as x1

, -2*b1 - 2*b2 + 2*b3 - 5*k as x2

, 3*b1  + 2*b2 - 3*b3 + 7*k as x3

, 2*b1  - b2   - b3   + 5*k as x4

from consts

, lateral (

select (level - 1 - (2*b1 - b2 - b3))/5 as k

from dual

where mod(level - 1 - (2*b1 - b2 - b3), 5) = 0

connect by level <= b2 + 1

)

)

-- post-computation filter to have at least two occurrences of each type

where x1 > 1

and x2 > 1

and x3 > 1

and x4 > 1

;

TT_NUM     FT_NUM     TC_NUM     FC_NUM TOTAL_LEGS

---------- ---------- ---------- ---------- ----------

81         19         83          5        588

74         14         90         10        588

67          9         97         15        588

60          4        104         20        588

83         21         80          4        589

76         16         87          9        589

...

30         46         23         89        699

23         41         30         94        699

16         36         37         99        699

9         31         44        104        699

2         26         51        109        699

1147 rows selected.

• ###### 12. Re: How to obtain answer of this topic using PL/SQL snippet?

Hello odie_63 ,

A big thanks for your great approach (mathematic and theory), I'll read it.

Best Regards

Quanwen Zhao

• ###### 13. Re: How to obtain answer of this topic using PL/SQL snippet?

odie_63,

I have to say how much I admire this answer and thank you for it. I gave up math (and physics) to do other things, which I don't regret, but you remind me forcefully that I did miss out on some useful stuff !

Best regards,

Stew

• ###### 14. Re: How to obtain answer of this topic using PL/SQL snippet?

As I was traveling (and, unfortunately, only able to read this forum on a tablet - no access to a computer to work on problems), I noticed this thread, and I was hoping someone will suggest a solution where most of the work is done in algebra, and the computer is only used at the very end to generate the actual solutions.

Happily, odie did that in Reply 11 - a superb answer. There is a simple, but very clever bit that he used (quite common in number theory, but often overlooked) - transforming a "between" condition into a "union all" of solutions, one member of the union for each value in the "between" condition. (Namely: total number of legs between 588 and 699 is expressed as total number of legs = 588 OR total number of legs = 589 OR ....   - therefore only having to deal with equations, not inequations, by allowing one equation to be parametric.) Exactly the right approach.

There is only one point that needs clarification (regarding the solution; there is one more regarding the reply itself). Namely, odie showed us the initial system of equations, one of which is parametric (b3 is not a fixed number, but "an integer between 588 and 699"). Then he wrote it in matrix form, and used row reduction. However, he didn't "show us the work" - he just said "row reducing the concatenated matrix ... leads to ...". Fine (100% correct!), but HOW?  There are other computations in matrix form, but those are trivial; this one, though, is not entirely trivial, even though it is 100% elementary.

In C, I would use one of the library functions from the GSL (GNU Scientific Library) to do row reduction. In Oracle, I don't even know if there is a linear algebra package that can do row reduction; if there is, it's probably not free (or perhaps not even cheap - it may be part of a bigger and expensive package). I wonder if Odie did this by hand (elementary but tedious, and possibly prone to errors - although he has made none), if he used a pl/sql package for linear algebra, or if he used some other tool outside of Oracle SQL and PL/SQL.

The other bit (not to do with the solution, but with the posted Reply): I am super-envious of the neat formatting. I suspect that it's not done 100% manually; wondering what may have been used, since I doubt it uses features of this web site.

OK - with all that said, in my next post I will show how I approached the problem. (Unable to check anything though - no computer at hand - or to post.) Now that I am back home, I did the last bit on the computer; I compared my results to odie's, and they are the same. You may view the next post as a "poor man's version" of odie's solution. One significant difference (other than "showing my work") is that I keep inequalities as inequalities, instead of transforming them into parametric equations.