Home » Other » General » Puzzle n°03 - Sharing articles ***
Puzzle n°03 - Sharing articles *** [message #290791] Mon, 31 December 2007 15:35 Go to next message
Michel Cadot
Messages: 68704
Registered: March 2007
Location: Nanterre, France, http://...
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 Go to previous messageGo to next message
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 Smile

Thumbs Up
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 Go to previous messageGo to next message
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

Thumbs Up
Rajuvan

[Updated on: Sun, 27 January 2008 00:42] by Moderator

Report message to a moderator

Re: Puzzle n°03 - Sharing articles *** [message #292283 is a reply to message #292274] Tue, 08 January 2008 07:12 Go to previous messageGo to next message
Michel Cadot
Messages: 68704
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
In case you want 30 articles and have 7 batches, the average is between 4 and 5.
Your query takes 7 to batch_id 8, it should be at most 1 over the next one which is 5 (batch id 4 and 2), so this is not correct (not evenly distributed, at most as posible): batch 2 should give 6 and batch 8 also 6 (batch 4 can't give more than 5).
But as batch 3 can give 5 there is no reason that it gives 4 when others gives 6. So it has to gives 5 and batch 2 or batch 8 one less and accordingly to the rule "we first take to the first batches", this is batch 2...

Please order your result by batch_id, it would be easier to compare.

Regards
Michel

Re: Puzzle n°03 - Sharing articles *** [message #292284 is a reply to message #292279] Tue, 08 January 2008 07:13 Go to previous messageGo to next message
Michel Cadot
Messages: 68704
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
I didn't checked the "slight" modification.
It would be nice you comment your queries.

Regards
Michel
Re: Puzzle n°03 - Sharing articles *** [message #292312 is a reply to message #290791] Tue, 08 January 2008 09:14 Go to previous messageGo to next message
varu123
Messages: 754
Registered: October 2007
Senior Member
I must say rajuvan is an expert in SQL/PLSQL.
How much experience do you have?
Re: Puzzle n°03 - Sharing articles *** [message #292470 is a reply to message #290791] Wed, 09 January 2008 00:42 Go to previous messageGo to next message
rajavu1
Messages: 1574
Registered: May 2005
Location: Bangalore , India
Senior Member

Ok . Then balance after adjusting the Average should be distributed as per the wieghtage , i guess . I will try to do that . But very busy with some official work .

Thumbs Up
Rajuvan

[Updated on: Wed, 09 January 2008 00:43]

Report message to a moderator

Re: Puzzle n°03 - Sharing articles *** [message #292476 is a reply to message #290791] Wed, 09 January 2008 00:51 Go to previous messageGo to next message
rajavu1
Messages: 1574
Registered: May 2005
Location: Bangalore , India
Senior Member

@ Varu :

Thanx for your compliment Smile , though I don't believe that I am an 'EXPERT' . I am still a student . I am still learning and have to learn a lot . Cool

Hmhm.. Why do you want to know about my experience ? Do you want to hire me / recommend my name somewhere ? Laughing (Just kidding )


Thumbs Up
Rajuvan
Re: Puzzle n°03 - Sharing articles *** [message #292505 is a reply to message #290791] Wed, 09 January 2008 01:46 Go to previous messageGo to next message
varu123
Messages: 754
Registered: October 2007
Senior Member
Just wanted to know how much experience does it take to become proficient.
Re: Puzzle n°03 - Sharing articles *** [message #292513 is a reply to message #290791] Wed, 09 January 2008 01:59 Go to previous messageGo to next message
rajavu1
Messages: 1574
Registered: May 2005
Location: Bangalore , India
Senior Member

varu :

There is not such hard and fast rule for that Smile . It simply depends on your 'Quest for learning' , 'Mindset for Hardwork ' and 'Building your own Logics' (It is purely my definition Smile ). Generally with One/Two year's experience, One can become an 'Expert' . It doesn't mean that Every body having 2+ year experience is 'Expert' .

For your point of intererst : I am 4 year experienced Cool

Let me stick to my point 'There is no real Expert . Everybody is Learning '

Thumbs Up
Rajuvan

[Updated on: Wed, 09 January 2008 02:00]

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 Go to previous messageGo to next message
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

Thumbs Up
Rajuvan.

[Updated on: Sun, 27 January 2008 00:41] by Moderator

Report message to a moderator

Re: Puzzle n°03 - Sharing articles *** [message #292971 is a reply to message #292966] Thu, 10 January 2008 06:10 Go to previous messageGo to next message
Michel Cadot
Messages: 68704
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
Quote:

Above Example itself shows the flaw in the technique

What do you mean?

Regards
Michel
Re: Puzzle n°03 - Sharing articles *** [message #292974 is a reply to message #290791] Thu, 10 January 2008 06:16 Go to previous messageGo to next message
rajavu1
Messages: 1574
Registered: May 2005
Location: Bangalore , India
Senior Member

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

Input is 8 , But Sum of GIVEN_ART is 7 !!!

Thumbs Up
Rajuvan.

[Updated on: Sun, 27 January 2008 00:41] by Moderator

Report message to a moderator

Re: Puzzle n°03 - Sharing articles *** [message #292979 is a reply to message #292974] Thu, 10 January 2008 06:27 Go to previous messageGo to next message
Michel Cadot
Messages: 68704
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
In this case, batch_id 1 should give 2.

Regards
Michel
Re: Puzzle n°03 - Sharing articles *** [message #296263 is a reply to message #290791] Fri, 25 January 2008 06:38 Go to previous messageGo to next message
Michel Cadot
Messages: 68704
Registered: March 2007
Location: Nanterre, France, http://...
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)
It puts in ANY batch "ra" measure the sum of all current values in "ga" measure. "ga" is the number of given articles in the previous iterations, so "ra" measure for every batch will contain the number of articles that still have to be gotten.
rg[ANY] = count(*)[ANY] - count(ga)[ANY]
It puts in ANY "rg" measure the difference between the count of batches and the count of batches where "ga" is not null. So "rg" measure (for each batch) contains the number of batches that currently did not give articles.
ga[ANY] = case ...
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.
pr[ANY] = rg[cv()]
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 Go to previous messageGo to next message
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 #299854 is a reply to message #290791] Wed, 13 February 2008 06:56 Go to previous messageGo to next message
rajavu1
Messages: 1574
Registered: May 2005
Location: Bangalore , India
Senior Member

Its simply Excellent solution ... .

Warm welcome to Orafaq again.!!!! /forum/fa/1581/0//forum/fa/1581/0//forum/fa/1581/0/

Michel , Now it is time to downgrade the Star level of this Puzzle Smile

Thumbs Up
Rajuvan

[Updated on: Wed, 13 February 2008 07:03]

Report message to a moderator

Re: Puzzle n°03 - Sharing articles *** [message #299867 is a reply to message #299854] Wed, 13 February 2008 07:35 Go to previous messageGo to next message
Michel Cadot
Messages: 68704
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
Quote:
Michel , Now it is time to downgrade the Star level of this Puzzle

I don't see why.

Well done, zozogirl!

Regards
Michel
Re: Puzzle n°03 - Sharing articles *** [message #299992 is a reply to message #290791] Wed, 13 February 2008 23:31 Go to previous messageGo to next message
rajavu1
Messages: 1574
Registered: May 2005
Location: Bangalore , India
Senior Member

Reason , You said it already here

Quote:
This is a rating for SQL (or PL/SQL) difficulty not rating for arithmetical one.


If the rating is based on SQL difficulty , This star level should be reduced defenitely .

Zozogirl's SQL looks simple both by arithmatic And by SQL. So I will give rating of star One or Maximum Two . But never three. Smile

Thumbs Up
Rajuvan
Re: Puzzle n°03 - Sharing articles *** [message #300031 is a reply to message #299992] Thu, 14 February 2008 01:10 Go to previous messageGo to next message
Michel Cadot
Messages: 68704
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
The final expression looks simple but the way to find is not.
There is also a temporal point in the definition.

Regards
Michel
Re: Puzzle n°03 - Sharing articles *** [message #300037 is a reply to message #290791] Thu, 14 February 2008 01:16 Go to previous messageGo to next message
rajavu1
Messages: 1574
Registered: May 2005
Location: Bangalore , India
Senior Member

Hmhm..

That is a diplomatic answer Micheal ,

ie, Complexity of SQL depends on the definition of complexity .
But that compleity cahnges from member to member .

Clever .

Thumbs Up
Rajuvan.
Re: Puzzle n°03 - Sharing articles *** [message #300042 is a reply to message #300037] Thu, 14 February 2008 01:35 Go to previous messageGo to next message
Michel Cadot
Messages: 68704
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
First time someone says I'm diplomatic. Smug

I try to see the problem and solution in a non-expert eyes and, in this case, I think the idea to "fill" each batch line one by one until conditions are reached really neat.

Regards
Michel
Re: Puzzle n°03 - Sharing articles *** [message #300047 is a reply to message #290791] Thu, 14 February 2008 01:51 Go to previous messageGo to next message
rajavu1
Messages: 1574
Registered: May 2005
Location: Bangalore , India
Senior Member

Yes ,

I also try to do in the same way as you tried .

Quote:
But that compleity cahnges from member to member .


Means , Micheal Posted it with 3 stars ( even I would do the same ) .
If zozogirl was the OP , she could have been rating it with One or Max two stars.

Well , That is the difference between "Non-expert" and "Expert" point of view. Cool

Thumbs Up
Rajuvan

Re: Puzzle n°03 - Sharing articles *** [message #346037 is a reply to message #290791] Fri, 05 September 2008 12:56 Go to previous messageGo to next message
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 #346041 is a reply to message #346037] Fri, 05 September 2008 13:03 Go to previous messageGo to next message
Michel Cadot
Messages: 68704
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
What is the purpose of your post? Trolling?

Regards
Michel
Re: Puzzle n°03 - Sharing articles *** [message #346421 is a reply to message #346041] Mon, 08 September 2008 09:09 Go to previous messageGo to next message
Brian Tkatch
Messages: 6
Registered: September 2008
Location: Oak Park, MI USA
Junior Member

Trolling? What about my post made you think that?

I was reading the puzzle and the reply and had some thoughts. Isn't that what the forum is for?
Re: Puzzle n°03 - Sharing articles *** [message #346439 is a reply to message #346421] Mon, 08 September 2008 10:20 Go to previous messageGo to next message
Michel Cadot
Messages: 68704
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
The purpose of the topic is to provide SQL solution for the problem in order to learn more on SQL and Oracle SQL features not to solve mathematical problem and even less discuss about stars.
The "stars" rating has been defined in http://www.orafaq.com/forum/t/94909/102589/
You can discuss about them (and possibly make them change) in "Suggestions & Feedback" forum not in the puzzles themselves.

By the way, you last sentence is completly ununderstandable for people that does not live in english world.

Regards
Michel
Re: Puzzle n°03 - Sharing articles *** [message #346466 is a reply to message #346439] Mon, 08 September 2008 11:38 Go to previous messageGo to next message
Brian Tkatch
Messages: 6
Registered: September 2008
Location: Oak Park, MI USA
Junior Member

"The purpose of the topic is to provide SQL solution for the problem in order to learn more on SQL and Oracle SQL features not to solve mathematical problem and even less discuss about stars."

The difference between sets used by SQL and the SQL language itself was brought to light with zozo's reply and the responses to it. I would think that makes it on-topic. The mention of the stars is only secondary, as it brings the point to more practical terms.

"By the way, you last sentence is completly ununderstandable for people that does not live in english world."

Although written in English, the sentence references the MBTI, which is not specifically English.

Regardless, i'll try to keep my comments to a minimum here. I am just interested in the puzzles.
Re: Puzzle n°03 - Sharing articles *** [message #409215 is a reply to message #299853] Sat, 20 June 2009 10:09 Go to previous messageGo to next message
Michel Cadot
Messages: 68704
Registered: March 2007
Location: Nanterre, France, http://...
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 Go to previous message
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;
The required quantity is given as a bind variable, :req_qty.
Previous Topic: Oracle licensing
Next Topic: Puzzle n°09 - Finding a query for sine function distribution **
Goto Forum:
  


Current Time: Tue Nov 05 19:23:15 CST 2024