Home » Other » General » Puzzle n°03 - Sharing articles ***
| Puzzle n°03 - Sharing articles *** [message #290791] |
Mon, 31 December 2007 15:35  |
 |
Michel Cadot
Messages: 68716
Registered: March 2007
Location: Saint-Maur, France, https...
|
Senior Member
Account Moderator |
|
|
Assuming we have a table of N batches, each one containing some articles.
Now we want to get X articles and we want that they are evenly taken from the batches.
That's easy if each batch contains at least X/N articles but what happens if this not the case?
This is the purpose of this puzzle to create a SQL statement to answer this question.
In case of X/N (of whatever number of articles) is not an integer, we round up the first batches (in the order of their id) and round down the last ones.
Here a test case:
DROP TABLE batches PURGE;
CREATE TABLE batches (batch_id INTEGER PRIMARY KEY, avail_qty INTEGER NOT NULL);
INSERT INTO batches VALUES (9, 2);
INSERT INTO batches VALUES (1, 3);
INSERT INTO batches VALUES (12, 4);
INSERT INTO batches VALUES (4, 5);
INSERT INTO batches VALUES (2, 8);
INSERT INTO batches VALUES (3, 13);
INSERT INTO batches VALUES (8, 7);
COMMIT;
Now we want 30 articles.
Result should be:
BATCH_ID AVAIL_QTY GIVEN_ART
---------- ---------- ----------
1 3 3
2 8 6
3 13 5
4 5 5
8 7 5
9 2 2
12 4 4
----------
Total 30
Enjoy!
Regards
Michel
[Updated on: Tue, 01 January 2008 01:08] Report message to a moderator |
|
|
|
| Re: Puzzle n°03 - Sharing articles *** [message #292274 is a reply to message #290791] |
Tue, 08 January 2008 06:32  |
 |
rajavu1
Messages: 1574
Registered: May 2005
Location: Bangalore , India
|
Senior Member |
|
|
One Solution could be like this.
SELECT BATCH_ID, AVAIL_QTY,XX + D
FROM (SELECT BATCH_ID,
AVAIL_QTY,
XX,
DECODE (SIGN (LEAST (BAL, NVL (LAG (ZZ) OVER (ORDER BY AVAIL_QTY), Y))),
-1, 0,
LEAST (BAL, NVL (LAG (ZZ) OVER (ORDER BY AVAIL_QTY), Y))
) D
FROM (SELECT BATCH_ID,
AVAIL_QTY,
XX,
Y,
BAL,
Y - SUM (BAL) OVER (ORDER BY BAL) ZZ
FROM (WITH DATASET AS
(SELECT COUNT (*) CNT,
&NUM N
FROM BATCHES)
SELECT BATCH_ID,
AVAIL_QTY,
LEAST (AVAIL_QTY, ROUND ((N / CNT))) XX,
N - SUM (LEAST (AVAIL_QTY, ROUND ((N / CNT)))) OVER (ORDER BY NULL) Y,
AVAIL_QTY - LEAST (AVAIL_QTY, ROUND ((N / CNT))) BAL
FROM BATCHES, DATASET)))
SQL> /
Enter value for num: 30
old 17: &NUM N
new 17: 30 N
BATCH_ID AVAIL_QTY XX+D
---------- ---------- ----------
9 2 2
1 3 3
12 4 4
4 5 5
8 7 7
2 8 5
3 13 4
7 rows selected.
SQL> /
Enter value for num: 10
old 17: &NUM N
new 17: 10 N
BATCH_ID AVAIL_QTY XX+D
---------- ---------- ----------
9 2 2
1 3 3
12 4 1
4 5 1
8 7 1
2 8 1
3 13 1
There could be some other fine solution 
Rajuvan.
[Updated on: Sun, 27 January 2008 00:42] by Moderator Report message to a moderator |
|
|
|
| Re: Puzzle n°03 - Sharing articles *** [message #292279 is a reply to message #290791] |
Tue, 08 January 2008 07:01 |
|
rajavu1
Messages: 1574
Registered: May 2005
Location: Bangalore , India
|
Senior Member |
|
|
Slight Modificaton to the code
SELECT BATCH_ID, AVAIL_QTY,XX + D
FROM (SELECT BATCH_ID,
AVAIL_QTY,
XX,
DECODE (SIGN (LEAST (BAL, NVL (LAG (ZZ) OVER (ORDER BY AVAIL_QTY), Y))),
-1, 0,
LEAST (BAL, NVL (LAG (ZZ) OVER (ORDER BY AVAIL_QTY), Y))
) D
FROM (SELECT BATCH_ID,
AVAIL_QTY,
XX,
Y,
BAL,
Y - SUM (BAL) OVER (ORDER BY BAL) ZZ
FROM (WITH DATASET AS
(SELECT COUNT (*) CNT,
&NUM N
FROM BATCHES)
SELECT BATCH_ID,
AVAIL_QTY,
LEAST (AVAIL_QTY, TRUNC ((N / CNT))) XX,
N - SUM (LEAST (AVAIL_QTY, TRUNC ((N / CNT)))) OVER (ORDER BY NULL) Y,
AVAIL_QTY - LEAST (AVAIL_QTY, TRUNC((N / CNT))) BAL
FROM BATCHES, DATASET)))
SQL> -- Previous query
SQL> /
Enter value for num: 13
old 17: &NUM N
new 17: 13 N
BATCH_ID AVAIL_QTY XX+D
---------- ---------- ----------
9 2 2
1 3 2
12 4 2
4 5 2
8 7 2
2 8 2
3 13 2
7 rows selected.
SQL> -- New query
SQL> /
Enter value for num: 13
old 17: &NUM N
new 17: 13 N
BATCH_ID AVAIL_QTY XX+D
---------- ---------- ----------
9 2 2
1 3 3
12 4 4
4 5 1
8 7 1
2 8 1
3 13 1
Rajuvan
[Updated on: Sun, 27 January 2008 00:42] by Moderator Report message to a moderator |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Re: Puzzle n°03 - Sharing articles *** [message #292966 is a reply to message #290791] |
Thu, 10 January 2008 05:46 |
|
rajavu1
Messages: 1574
Registered: May 2005
Location: Bangalore , India
|
Senior Member |
|
|
Coming back to the solution , i have an option having some problem with it..
SQL> select batch_id , avail_qty AVAIL_ART ,xx+ROUND(Y/Z *bal) GIVEN_ART
2 from(SELECT BATCH_ID,
3 AVAIL_QTY,
4 XX,
5 Y,
6 BAL,
7 SUM (bal) OVER (order by null ) Z ,
8 Y - SUM (BAL) OVER (ORDER BY BAL) ZZ
9 FROM (WITH DATASET AS
10 (SELECT COUNT (*) CNT,
11 &NUM N
12 FROM BATCHES)
13 SELECT BATCH_ID,
14 AVAIL_QTY,
15 LEAST (AVAIL_QTY, TRUNC ((N / CNT))) XX,
16 N - SUM (LEAST (AVAIL_QTY, TRUNC ((N / CNT)))) OVER (ORDER BY NULL) Y,
17 AVAIL_QTY - LEAST (AVAIL_QTY, TRUNC((N / CNT))) BAL
18 FROM BATCHES, DATASET))
19 ORDER BY 1 ;
Enter value for num: 7
old 11: &NUM N
new 11: 7 N
BATCH_ID AVAIL_ART GIVEN_ART
---------- ---------- ----------
1 3 1
2 8 1
3 13 1
4 5 1
8 7 1
9 2 1
12 4 1
7 rows selected.
SQL> /
Enter value for num: 8
old 11: &NUM N
new 11: 8 N
BATCH_ID AVAIL_ART GIVEN_ART
---------- ---------- ----------
1 3 1
2 8 1
3 13 1
4 5 1
8 7 1
9 2 1
12 4 1
7 rows selected.
SQL> /
Enter value for num: 30
old 11: &NUM N
new 11: 30 N
BATCH_ID AVAIL_ART GIVEN_ART
---------- ---------- ----------
1 3 3
2 8 5
3 13 7
4 5 4
8 7 5
9 2 2
12 4 4
Above Example itself shows the flaw in the technique
Rajuvan.
[Updated on: Sun, 27 January 2008 00:41] by Moderator Report message to a moderator |
|
|
|
|
|
|
|
|
|
| Re: Puzzle n°03 - Sharing articles *** [message #296263 is a reply to message #290791] |
Fri, 25 January 2008 06:38 |
|
Michel Cadot
Messages: 68716
Registered: March 2007
Location: Saint-Maur, France, https...
|
Senior Member
Account Moderator |
|
|
First I will work on float numbers (we will see integer version below).
I will show the query and will detail how it works after.
Let N be the total number of articles we want:
SQL> break on report
SQL> compute sum label Total of given_art on report
SQL> def N=30
SQL> def max_iter=10
SQL> select batch_id, avail_qty, ga given_art, ra, rg, pr, ni
2 from batches
3 model
4 dimension by (batch_id)
5 measures (avail_qty, -- number of available articles in batch
6 cast(null as number) ga, -- number of given articles
7 cast(null as number) ra, -- number of remaining articles to get
8 cast(null as number) rg, -- number of batches that didn't give articles
9 cast(null as number) pr, -- previous value of rg
10 0 as ni) -- number of iterations
11 rules update sequential order
12 iterate(&max_iter) until (rg[1] = 0)
13 ( -- ra = remaining articles to get at the beginning of iteration
14 ra[ANY] = &N - nvl(sum(ga)[ANY],0),
15 -- rg = remaining batches that didn't give articles at the beginning of iter.
16 rg[ANY] = count(*)[ANY] - count(ga)[ANY],
17 -- ga = given articles
18 ga[ANY] = case
19 when ga[cv()] is not null
20 -- don't change what's already set
21 then ga[cv()]
22 when ra[cv()]/rg[cv()] >= avail_qty[cv()]
23 -- if share does not fit take only available
24 then avail_qty[cv()]
25 when pr[cv()] = rg[cv()]
26 -- no change in the previous iteration -> fill the rest
27 then ra[cv()]/rg[cv()]
28 end,
29 -- memorize previous value of rg
30 pr[ANY] = rg[cv()],
31 -- ra = remaining articles in batches at the end of iteration
32 -- (not useful for computing, just for display purpose)
33 ra[ANY] = &N - nvl(sum(ga)[ANY],0),
34 -- rg = remaining batches that didn't give articles at the end of iteration
35 -- (not useful for computing, just for display purpose)
36 rg[ANY] = count(*)[ANY] - count(ga)[ANY],
37 -- number of iterations
38 -- (not useful for computing, just for display purpose)
39 ni[ANY] = ni[cv()] + 1
40 )
41 order by 1
42 /
BATCH_ID AVAIL_QTY GIVEN_ART RA RG PR NI
---------- ---------- ---------- ---------- ---------- ---------- ----------
1 3 3 1.0000E-38 0 3 4
2 8 5.33333333 1.0000E-38 0 3 4
3 13 5.33333333 1.0000E-38 0 3 4
4 5 5 1.0000E-38 0 3 4
8 7 5.33333333 1.0000E-38 0 3 4
9 2 2 1.0000E-38 0 3 4
12 4 4 1.0000E-38 0 3 4
----------
Total 30
Let see the MODEL clause.
It works by updating or creating rows and columns from the source given in the FROM clause. Each row as its primary key defined in the DIMENSION clause at line 4. Columns include the DIMENSION ones (here batch_id) and those defined in the MEASURES clause. Each "measure" value is built from the "rules" defined afterward.
The "measures" are the follwing ones:
- avail_qty: available articles for each batch_id, its value directly comes from the source.
- ga: the number of articles given by each batch_id.
- ra: the number of articles still to get. This is independent of batch_id. It starts from N and will decrease at each iteration (see below) until it reaches (about) 0.
- rg: the number of batches that still did not give articles. This is independent of batch_id. It starts from the number of batches and will decrease at each iteration (see below) until it reaches 0.
- pr: the value of rg in the previous iteration. Then pr-rg gives the number of batches that give articles during the current iteration.
- ni: the number of iterations already executed (starts at 0).
Line 11 introduces the computation rules. "update" means only updated source row should be returned by the MODEL clause (MODEL clause can also create new rows, this is not the case here). "sequential order" means the rules must be executed in the order they are expressed (by default Oracle tries to search the best order given the relations between rules).
Line 12 indicates that the rule can be applied at most the number of times stated by "ITERATE" clause unless condition in "UNTIL" is satisfied before. Our exit condition here is that the number of batches that still don't give articles (rg) is 0: all batches are taken into account.
Now the rules:
ra[ANY] = &N - nvl(sum(ga)[ANY],0)
rg[ANY] = count(*)[ANY] - count(ga)[ANY]
This is the core rule that will determine for each batch how many articles it will give.
* If "ga" for the current batch_id (given by the function CV) is not null then this batch already gave articles, so we don't change the value
* If the current theorical number of articles to get from each remaining batch (given by the ratio between the number of articles still not gotten to the number of batches that still not gave articles), if this number is greater than the number of available articles in the batch, then this batch gives all what it has: avail_qty.
* If applying the 2 preceding rules result on no change during the previous iteration then the current batch give this theorical number of articles.
This rule memorizes the current "rg" values before recalculating it. Its purpose is to verify if an iteration leads to some changes in measures or not (see third case above)
The 2 next rules are the same as the 2 first ones.
The last one, "ni[ANY] = ni[cv()] + 1", just counts the number of iterations.
These last 3 rules are not necessary for the computation, there are just there to see how the query works (see below).
Finally, SELECT clause displays the measures (or expressions from them).
Now let see what happens at each iteration.
First before any iteration:
SQL> def max_iter=0
SQL> /
BATCH_ID AVAIL_QTY GIVEN_ART RA RG PR NI
---------- ---------- ---------- ---------- ---------- ---------- ----------
1 3 0
2 8 0
3 13 0
4 5 0
8 7 0
9 2 0
12 4 0
----------
Total
Then now let's execute the first one:
SQL> def max_iter=1
SQL> /
BATCH_ID AVAIL_QTY GIVEN_ART RA RG PR NI
---------- ---------- ---------- ---------- ---------- ---------- ----------
1 3 3 21 4 7 1
2 8 21 4 7 1
3 13 21 4 7 1
4 5 21 4 7 1
8 7 21 4 7 1
9 2 2 21 4 7 1
12 4 4 21 4 7 1
----------
Total 9
For this first iteration, the number theorical articles to get per batch is 30/7=4.3. We see that bacth 1, 9 and 12 can't give so much, so accordingly to the second branch of case, they give all what they have. In the end, they gave 9 articles, so 21 are still to get ("ra" measure). 4 ("rg" measures) batches still not gave anything and there previously were 7 ("pr" measure), so 3 (=7-4) bacthes gave articles during this iteration (batches 1, 9, 12, so three of them).
The number of iterations done is 1 ("ni" measure).
Let's go to the next iteration with the new theorical number of articles: "ra"/"rg"=21/4=5.25.
SQL> def max_iter=2
SQL> /
BATCH_ID AVAIL_QTY GIVEN_ART RA RG PR NI
---------- ---------- ---------- ---------- ---------- ---------- ----------
1 3 3 16 3 4 2
2 8 16 3 4 2
3 13 16 3 4 2
4 5 5 16 3 4 2
8 7 16 3 4 2
9 2 2 16 3 4 2
12 4 4 16 3 4 2
----------
Total 14
This time among the remaining batches, only batch_id 4 can't give the whole theorical number of articles, so it gives its 5 ones. New remaining number of articles and batches are 16 and 3.
Next iteration with theorical number 16/3=5.3
SQL> def max_iter=3
SQL> /
BATCH_ID AVAIL_QTY GIVEN_ART RA RG PR NI
---------- ---------- ---------- ---------- ---------- ---------- ----------
1 3 3 16 3 3 3
2 8 16 3 3 3
3 13 16 3 3 3
4 5 5 16 3 3 3
8 7 16 3 3 3
9 2 2 16 3 3 3
12 4 4 16 3 3 3
----------
Total 14
This time every batch can give the theorical number of articles, so nothing happened. As we will see in the next iteration, the third branch of "case" will come into action:
SQL> def max_iter=4
SQL> /
BATCH_ID AVAIL_QTY GIVEN_ART RA RG PR NI
---------- ---------- ---------- ---------- ---------- ---------- ----------
1 3 3 1.0000E-38 0 3 4
2 8 5.33333333 1.0000E-38 0 3 4
3 13 5.33333333 1.0000E-38 0 3 4
4 5 5 1.0000E-38 0 3 4
8 7 5.33333333 1.0000E-38 0 3 4
9 2 2 1.0000E-38 0 3 4
12 4 4 1.0000E-38 0 3 4
----------
Total 30
The last 3 batches (2, 3 and 8 ) gave the whole theorical number (more or less 1E-38, maximum Oracle precision).
Now, even if we allow more iterations, we stop there because the condition "rg=0" is met:
SQL> def max_iter=10
SQL> /
BATCH_ID AVAIL_QTY GIVEN_ART RA RG PR NI
---------- ---------- ---------- ---------- ---------- ---------- ----------
1 3 3 1.0000E-38 0 3 4
2 8 5.33333333 1.0000E-38 0 3 4
3 13 5.33333333 1.0000E-38 0 3 4
4 5 5 1.0000E-38 0 3 4
8 7 5.33333333 1.0000E-38 0 3 4
9 2 2 1.0000E-38 0 3 4
12 4 4 1.0000E-38 0 3 4
----------
Total 30
As you can see in the last column, the process ends at iteration 4.
Well, now for myself I should not like to have to get my Porsche the wheels and seats in one warehouse, the body in another one and the engine in a third one.
So let's work with integers.
The rule is: "in case of a number of articles is not an integer, we round up the first batches (in the order of their id) and round down the last ones".
So here we should round up batch 2 and down batches 3 and 8.
In a more formal and iterative way, we have to round up the value while what we add with this (from the truncated value) is less than the difference between the total and the truncated values.
Here the total is 5.33333333+5.33333333+5.33333333 = 16. The total of the truncated values is 5+5+5 = 15. We have to add 1 to the truncated values to get the actual total, so only the first value is rounded up.
Or, in other words, we round up until the decimal parts we add reaches the sum of decimal parts.
The total of decimal parts we have to handle is given with sum(ga-floor(ga)) over the whole set and the total of decimals part already counted till the current row (order by the batch id) is sum(ceil(ga)-floor(ga)) over the rows from the first one to the current one.
So, in SQL, putting the previous query in a WITH clause this gives:
SQL> with
2 data as (
3 select bid batch_id, avail_qty, ga, ra, rg, pr, ni
4 from batches
5 model
6 dimension by (batch_id bid)
7 measures (avail_qty, -- number of available articles in batch
8 cast(null as number) ga, -- number of given articles
9 cast(null as number) ra, -- number of remaining articles to get
10 cast(null as number) rg, -- number of batches that didn't give articles
11 cast(null as number) pr, -- previous value of rg
12 0 as ni) -- number of iterations
13 rules update sequential order
14 iterate(&max_iter) until (rg[1] = 0)
15 ( -- ra = remaining articles to get at the beginning of iteration
16 ra[ANY] = &N - nvl(sum(ga)[ANY],0),
17 -- rg = remaining batches that didn't give articles at the beginning of iter.
18 rg[ANY] = count(*)[ANY] - count(ga)[ANY],
19 -- ga = given articles
20 ga[ANY] = case
21 when ga[cv()] is not null
22 -- don't change what's already set
23 then ga[cv()]
24 when ra[cv()]/rg[cv()] >= avail_qty[cv()]
25 -- if share does not fit take only available
26 then avail_qty[cv()]
27 when pr[cv()] = rg[cv()]
28 -- no change in the previous iteration -> fill the rest
29 then ra[cv()]/rg[cv()]
30 end,
31 -- memorize previous value of rg
32 pr[ANY] = rg[cv()]
33 )
34 )
35 select batch_id, avail_qty,
36 case
37 when sum(ceil(ga)-floor(ga)) over (order by batch_id)
38 <= sum(ga-floor(ga)) over() + 1E-30
39 then ceil(ga)
40 else floor(ga)
41 end given_art
42 from data
43 order by 1
44 /
BATCH_ID AVAIL_QTY GIVEN_ART
---------- ---------- ----------
1 3 3
2 8 6
3 13 5
4 5 5
8 7 5
9 2 2
12 4 4
----------
Total 30
You may have noticed "+ 1E-30", well this is to handle the fact that Oracle does not work with an infinite precision but up to 38 digits (as we saw in the previous query) so we add a little bit to be sure that the test returns the correct result (try it without this bit and you will see some errors in the final result, depending on &N).
Let's give the result for the different values tested by Rajuvan in his posts:
SQL> def n=7
SQL> /
BATCH_ID AVAIL_QTY GIVEN_ART
---------- ---------- ----------
1 3 1
2 8 1
3 13 1
4 5 1
8 7 1
9 2 1
12 4 1
----------
Total 7
SQL> def n=8
SQL> /
BATCH_ID AVAIL_QTY GIVEN_ART
---------- ---------- ----------
1 3 2
2 8 1
3 13 1
4 5 1
8 7 1
9 2 1
12 4 1
----------
Total 8
SQL> def n=10
SQL> /
BATCH_ID AVAIL_QTY GIVEN_ART
---------- ---------- ----------
1 3 2
2 8 2
3 13 2
4 5 1
8 7 1
9 2 1
12 4 1
----------
Total 10
SQL> def n=13
SQL> /
BATCH_ID AVAIL_QTY GIVEN_ART
---------- ---------- ----------
1 3 2
2 8 2
3 13 2
4 5 2
8 7 2
9 2 2
12 4 1
----------
Total 13
Regards
Michel
[Updated on: Sun, 27 January 2008 13:46] Report message to a moderator |
|
|
|
| Re: Puzzle n°03 - Sharing articles *** [message #299853 is a reply to message #296263] |
Wed, 13 February 2008 06:53 |
zozogirl
Messages: 77
Registered: November 2005
Location: Seoul, Korea
|
Member |
|
|
Make it simple. &NUM is our variable.
(sorry for my last post)
SELECT BATCH_ID, MIN (AVAIL_QTY), COUNT (A)
FROM (SELECT A.BATCH_ID, A.AVAIL_QTY, CASE
WHEN ROW_NUMBER () OVER (ORDER BY B.LV, A.BATCH_ID) <= &NUM
THEN 1
END A
FROM BATCHES A
JOIN
(SELECT LEVEL LV
FROM DUAL
CONNECT BY LEVEL <= &NUM) B ON (A.AVAIL_QTY >= B.LV)
)
GROUP BY BATCH_ID
ORDER BY BATCH_ID
[Updated on: Mon, 08 September 2008 12:29] by Moderator Report message to a moderator |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Re: Puzzle n°03 - Sharing articles *** [message #346037 is a reply to message #290791] |
Fri, 05 September 2008 12:56 |
Brian Tkatch
Messages: 6
Registered: September 2008
Location: Oak Park, MI USA
|
Junior Member |
|
|
The puzzle had three parts to it.
1) Figuring out the sets to deal with.
2) Figuring out the math.
3) Figuring out the SQL.
1) Sets - The ingenuity is in the simplicity. 3 stars here.
2) Math - COUNT() could have used SUM(). 0 stars.
3) SQL - The SQL here was relatively easy, it just needed to implement the sets. 1.5 stars.
So, if the puzzle rates maths. It is not even a puzzle.
If the puzzle rates SQL, i agree with rajavu1 that it should be 1 or 2 stars.
If the puzzle is figuring out the sets, it is 3 stars.
Math puzzles aren't SQL puzzles, so that is irrelevant.
Figuring out the SQL, is deductive.
Figuring out sets, is inductive.
So, it really is based on your personality type. Using the MBTI, dominant Ts want deductive challenges, dominant Ns want inductive challenges.
|
|
|
|
|
|
|
|
|
|
|
|
| Re: Puzzle n°03 - Sharing articles *** [message #409215 is a reply to message #299853] |
Sat, 20 June 2009 10:09 |
|
Michel Cadot
Messages: 68716
Registered: March 2007
Location: Saint-Maur, France, https...
|
Senior Member
Account Moderator |
|
|
Back to zozogirl's solution and how it works.
First generate &NUM lines with a standard row generator (see Puzzle 0).
Then join this to BATCHES table to generate a row per article in each batch but we will only need the first &NUM articles, so we flag them:
SQL> with
2 lines as ( select level line from dual connect by level <= &num )
3 select batch_id, avail_qty, line,
4 row_number () over (order by line, batch_id) rn,
5 case
6 when row_number () over (order by line, batch_id) <= &NUM
7 then 1
8 end flag
9 from batches, lines
10 where line <= avail_qty
11 /
BATCH_ID AVAIL_QTY LINE RN FLAG
---------- ---------- ---------- ---------- ----------
1 3 1 1 1
2 8 1 2 1
3 13 1 3 1
4 5 1 4 1
8 7 1 5 1
9 2 1 6 1
12 4 1 7 1
1 3 2 8 1
2 8 2 9 1
3 13 2 10 1
4 5 2 11 1
8 7 2 12 1
9 2 2 13 1
12 4 2 14 1
1 3 3 15 1
2 8 3 16 1
3 13 3 17 1
4 5 3 18 1
8 7 3 19 1
12 4 3 20 1
2 8 4 21 1
3 13 4 22 1
4 5 4 23 1
8 7 4 24 1
12 4 4 25 1
2 8 5 26 1
3 13 5 27 1
4 5 5 28 1
8 7 5 29 1
2 8 6 30 1
3 13 6 31
8 7 6 32
2 8 7 33
3 13 7 34
8 7 7 35
2 8 8 36
3 13 8 37
3 13 9 38
3 13 10 39
3 13 11 40
3 13 12 41
3 13 13 42
42 rows selected.
Now we just have to count the row flagged in each batch (removing the useless columns):
SQL> break on report
SQL> compute sum label Total of given_art on report
SQL> with
2 lines as ( select level line from dual connect by level <= &num ),
3 flagged as (
4 select batch_id, avail_qty,
5 case
6 when row_number () over (order by line, batch_id) <= &NUM
7 then 1
8 end flag
9 from batches, lines
10 where line <= avail_qty
11 )
12 select batch_id, avail_qty, count(flag) given_art
13 from flagged
14 group by batch_id, avail_qty
15 order by batch_id
16 /
BATCH_ID AVAIL_QTY GIVEN_ART
---------- ---------- ----------
1 3 3
2 8 6
3 13 5
4 5 5
8 7 5
9 2 2
12 4 4
----------
Total 30
7 rows selected.
As the previous "line" column indicates the number of the article we get in a batch: 1 is the first article we take in the batch, 2 the second one... we could also take the number of the last flagged article per batch:
SQL> with
2 lines as ( select level line from dual connect by level <= &num ),
3 flagged as (
4 select batch_id, avail_qty, line,
5 case
6 when row_number () over (order by line, batch_id) <= &NUM
7 then 1
8 end flag
9 from batches, lines
10 where line <= avail_qty
11 )
12 select batch_id, avail_qty, max(line) given_art
13 from flagged
14 where flag = 1
15 group by batch_id, avail_qty
16 order by batch_id
17 /
BATCH_ID AVAIL_QTY GIVEN_ART
---------- ---------- ----------
1 3 3
2 8 6
3 13 5
4 5 5
8 7 5
9 2 2
12 4 4
----------
Total 30
7 rows selected.
Regards
Michel
|
|
|
|
| Puzzle no. 3 - uniform contribution to required quantity [message #687414 is a reply to message #409215] |
Mon, 06 March 2023 18:25 |
 |
mathguy
Messages: 108
Registered: January 2023
|
Senior Member |
|
|
zozogirl's solution takes the gold medal for simplicity. In pure math, where the time required to execute some process is irrelevant, this would be the best answer.
In applied math / engineering, once we have a solution (like zozogirl's), we can then ask, how efficient is it - and can we find a faster solution. Often a faster solution would have no choice but to be more complicated; so one would also need to ask, "is the tradeoff between complexity and efficiency justified".
The practical weakness in zozogirl's solution is the need to assign the "required quantity" to batches one unit at a time. If there are, say, seven batches, with very large quantities each (say in the hundreds of thousands), and the required quantity was something like 1 million, the solution may take some time to complete. We might want to look for a solution that would complete in O(m) time rather than O(n), where m is the number of batches (like 7) and n is the required quantity (like 1 million). Even O(m log m) or O(m^2) might be much better than O(n).
Below I will show a solution that may work faster in a situation like that. For testing, I multiplied the available quantity in each batch by 10,000 (so the quantities are 30,000, 80,000 etc. instead of 3, 8 etc.) and I request a total quantity of 300,000 instead of 30. The number of batches is still 7. With this setup, zozogirl's solution completes in 1.25 seconds on my machine (using Linux 7.9 and Oracle 12.2.0.1 on a cheap, six-year-old desktop computer). The solution I show below completes in 0.002 seconds, about 600 times faster. The discrepancy will increase if the quantities (both "available" and "required") continue to grow, but the number of batches remains small.
First, here is the algorithm. Order the batches by quantity, and then by batch id (so that we have a deterministic, total ordering). If the first batch has less quantity than "the average" (total quantity needed, divided by number of batches), then the entire quantity from the first batch will be needed. Make note of that; then reduce the "required quantity" by the available quantity in the first batch, reduce the batch count by one, and repeat. Continue until the first batch with quantity greater than the current average. Note that the "current" average is not the original one; it is the "current" remaining required quantity, divided by the current remaining count. The "current" remaining quantity was the original one, reduced by available counts; the "current" average may increase at each step. So, this process is iterative, it is not static. Luckily, analytic functions can handle this problem - we don't need recursive subquery factoring or other such tools.
Then we are potentially left with several batches with quantity greater than the then-current average. At that point each batch will get either the TRUNC of that average or the CEIL of the average, depending only on batch id, according to the specification. This is much easier to handle - compare a rank (such as given by ROW_NUMBER) to the modulus of remaining quantity by remaining count.
The coding of the solution is trivial, as it follows the algorithm step by step, exactly as described above. Note that the "remaining quantity" at each step in the first pass is the original required quantity, reduced by the lagged sum of available quantities. We can avoid the nesting of analytic functions (which would require a subquery-superquery arrangement) by taking the standard analytic sum and then subtracting the row's own quantity - see below.
So - here is the solution:
with
first_pass (batch_id, avail_qty, given_qty) as (
select batch_id, avail_qty,
case when avail_qty <=
(:req_qty - sum(avail_qty) over (order by avail_qty, batch_id) + avail_qty)
/ (count(*) over () - count(*) over (order by avail_qty, batch_id) + 1) then avail_qty end
from batches
)
select batch_id, avail_qty, given_qty
from first_pass
where given_qty is not null
UNION ALL
select batch_id, avail_qty,
trunc(rem_qty / rem_count) + case when row_number() over (order by batch_id) <= mod(rem_qty, rem_count) then 1 else 0 end
from first_pass cross join
(select :req_qty - nvl(sum(given_qty), 0) as rem_qty, count(*) - count(given_qty) as rem_count from first_pass)
where given_qty is null
ORDER BY batch_id; |
|
|
|
Goto Forum:
Current Time: Fri Nov 22 10:46:17 CST 2024
|
] 
Blog
Search
Help
Members
Register
Login
Home
(Just kidding )