1 2 Previous Next 29 Replies Latest reply: Jan 24, 2013 1:33 PM by AdamMartin Go to original post RSS
      • 15. Re: Need the best way to solve this problem
        jihuyao
        It is like picking up available digits from the string and drop into numbered boxes......

        Here are two given conditions (correct me if wrong),

        1. a collection of digits in the string from 0 to 9, which can be built into a look up table as count(0), ..., count(9)

        2. pick up any available digit(s) from the look up and drop into the current number box, if possible, but ONLY if all left digits can be put into a valid number larger than current number.

        Now time for break before starting loop... :)
        • 16. Re: Need the best way to solve this problem
          AdamMartin
          Nicely done!

          There might still be an issue with some inputs, for example:

          76721==>1,2,6,7 | 7

          Shouldn't it return this instead?

          76721==>1,2,6,77


          Also, currently it returns: 11==>1,10 when it should be 11==>11
          • 17. Re: Need the best way to solve this problem
            BluShadow
            Adam Martin wrote:
            Nicely done!

            There might still be an issue with some inputs, for example:

            76721==>1,2,6,7 | 7

            Shouldn't it return this instead?

            76721==>1,2,6,77


            Also, currently it returns: 11==>1,10 when it should be 11==>11
            Yes, the 'requirement' is flawed, because it would have to traverse all recursive tree options until it finds all possibilities that use up all the digits, and then out of the potentially multiple solution paths, it would have to pick the 'best' of those, based on some criteria (which would need specifying).

            I'm a bit late coming to this thread myself (was off-forum for a few days).
            Anyway, allowing for the aforementioned issue, I've had a go myself using recursive subquery factoring in 11gR2...
            SQL> ed
            Wrote file afiedt.buf
            
              1  with t as (select '1124567801030904' as str from dual)
              2  --
              3      ,r(last, val, instr, outstr) as
              4            (/* Anchor Query */
              5             select 0 as last
              6                   ,0 as val
              7                   ,str as instr
              8                   ,cast('' as varchar2(100)) as outstr
              9             from t
             10             union all
             11             /* Recursive Query */
             12             select case when instr = to_char(val+1,'fm99')
             13                           or val > to_number(regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1))
             14                         then 1
             15                    else 0
             16                    end as last
             17                   ,val+1 as val
             18                   ,regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1) as instr
             19                   ,trim(',' from outstr||case when instr(instr,to_char(val+1,'fm9999999'))>0
             20                                               then ','||to_char(val+1,'fm9999999')
             21                                          else null
             22                                          end) as outstr
             23             from   r
             24             where  regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1) is not null
             25             and    val <= to_number(instr)
             26            )
             27  select t.str as orig_string
             28        ,r.outstr as result_string
             29        ,r.instr as remainder_string
             30        ,r.val as iterations
             31  from t, r
             32* where last = 1
            SQL> /
            
            ORIG_STRING                    RESULT_STRING                  REMAINDER_STRING     ITERATIONS
            ------------------------------ ------------------------------ -------------------- ----------
            1124567801030904               1,2,3,4,5,6,7,8,9,10,100       04                          100
            The "remainder" string is what's left because after picking out the occurences of values from the string in a 'left to right' order of ascending values, we're left with "04" which can't possibly be found in any further iterations.

            As already mentioned above, a 'better' result can be got if the digits are ordered from high to low first....
            SQL> ed
            Wrote file afiedt.buf
            
              1  with t_orig as (select '1124567801030904' as str from dual)
              2      ,t as (select listagg(digit) within group (order by rn) as str
              3             from (
              4                   select digit, row_number() over (order by digit desc) as rn
              5                    from (
              6                          select substr(str,level,1) as digit
              7                          from   t_orig
              8                          connect by level <= length(str)
              9                         )
             10                  )
             11             )
             12  --
             13      ,r(last, val, instr, outstr) as
             14            (/* Anchor Query */
             15             select 0 as last
             16                   ,0 as val
             17                   ,str as instr
             18                   ,cast('' as varchar2(100)) as outstr
             19             from t
             20             union all
             21             /* Recursive Query */
             22             select case when instr = to_char(val+1,'fm99')
             23                           or val > to_number(regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1))
             24                         then 1
             25                    else 0
             26                    end as last
             27                   ,val+1 as val
             28                   ,regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1) as instr
             29                   ,trim(',' from outstr||case when instr(instr,to_char(val+1,'fm9999999'))>0
             30                                               then ','||to_char(val+1,'fm9999999')
             31                                          else null
             32                                          end) as outstr
             33             from   r
             34             where  regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1) is not null
             35             and    val <= to_number(instr)
             36            )
             37  select t.str as orig_string
             38        ,r.outstr as result_string
             39        ,r.instr as remainder_string
             40        ,r.val as iterations
             41  from t_orig t, r
             42* where last = 1
            SQL> /
            
            ORIG_STRING                    RESULT_STRING                  REMAINDER_STRING     ITERATIONS
            ------------------------------ ------------------------------ -------------------- ----------
            1124567801030904               1,2,3,4,5,6,7,8,9,10,41        000                          41
            In this case we still end up with a remainder string of "000", but now it's only taking 41 iterations to use up most of the digits.
            However, the problem with this is that, by moving the digits into an order, we can prevent certain values from appearing e.g. in the following input string...
            SQL> ed
            Wrote file afiedt.buf
            
              1  with t_orig as (select '11234567801030904' as str from dual)
              2      ,t as (select listagg(digit) within group (order by rn) as str
              3             from (
              4                   select digit, row_number() over (order by digit desc) as rn
              5                    from (
              6                          select substr(str,level,1) as digit
              7                          from   t_orig
              8                          connect by level <= length(str)
              9                         )
             10                  )
             11             )
             12  --
             13      ,r(last, val, instr, outstr) as
             14            (/* Anchor Query */
             15             select 0 as last
             16                   ,0 as val
             17                   ,str as instr
             18                   ,cast('' as varchar2(100)) as outstr
             19             from t
             20             union all
             21             /* Recursive Query */
             22             select case when instr = to_char(val+1,'fm99')
             23                           or val > to_number(regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1))
             24                         then 1
             25                    else 0
             26                    end as last
             27                   ,val+1 as val
             28                   ,regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1) as instr
             29                   ,trim(',' from outstr||case when instr(instr,to_char(val+1,'fm9999999'))>0
             30                                               then ','||to_char(val+1,'fm9999999')
             31                                          else null
             32                                          end) as outstr
             33             from   r
             34             where  regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1) is not null
             35             and    val <= to_number(instr)
             36            )
             37  select t.str as orig_string
             38        ,r.outstr as result_string
             39        ,r.instr as remainder_string
             40        ,r.val as iterations
             41  from t_orig t, r
             42* where last = 1
            SQL> /
            
            ORIG_STRING                    RESULT_STRING                  REMAINDER_STRING     ITERATIONS
            ------------------------------ ------------------------------ -------------------- ----------
            11234567801030904              1,2,3,4,5,6,7,8,9,10,31,40     00                           40
            (I've added the first 3 to the string)
            ... the original string had a "30" in it, but this wasn't picked up because the 0's have been moved.

            No solution is really ideal, as nothing can cater for all possibilities, without a true recursive solution that examines all possibilities.
            • 18. Re: Need the best way to solve this problem
              AdamMartin
              It does not need to try "all possibilities" as you suggest. It simply needs to fill in the smallest integers in order and check to see if there is a remainder at the end (a remainder from which a greater integer cannot be formed). If there is a remainder, then the prior integer is invalid, and it must go upwards from there.

              For your input of '11234567801030904' the correct solution is 1,2,3,4,5,6,7,8,9,10,13,4000

              Although the integer 40 would have been next in line after 13, the number 40 must be ruled invalid because it would leave remaining digits that cannot form a greater integer.
              • 19. Re: Need the best way to solve this problem
                AdamMartin
                My version is posted below. It seems to work for all inputs tested.
                declare
                  v_input varchar2(50) := '11234567801030904'; -- <-----INPUT HERE
                  v_sorted_input varchar2(50);
                  v_output varchar2(100);
                  v_digit_check varchar2(50);
                  v_comma varchar2(1);
                  --character sort function
                  function sort_chars(p_chars varchar2) return varchar2 is
                    v_chars varchar2(50) := p_chars;
                    v_retval varchar2(50);
                    v_keep_searching boolean := true;
                    v_cnt number := 0;
                  begin
                    for i in reverse 0..9 loop
                      v_keep_searching := true;
                      while v_keep_searching loop
                        if instr(v_chars,to_char(i)) > 0 then
                          v_retval := v_retval || to_char(i);
                          v_chars := regexp_replace(v_chars,to_char(i),'',1,1);
                        else 
                          v_keep_searching := false;
                        end if;
                      end loop;
                    end loop;
                    return v_retval;
                  end;
                  --digit checking function
                  function all_digits_exist(p_int varchar2, p_input_string varchar2) return varchar2 is
                    v_instr number;
                    v_input_string varchar2(50) := p_input_string;
                  begin
                    for a in 1..length(p_int) loop 
                      v_instr := instr(v_input_string, substr(p_int,a,1));
                      if v_instr > 0 then
                        v_input_string := regexp_replace(v_input_string,substr(p_int,a,1),'',1,1);
                      else
                        return 'NOT FOUND';
                      end if; 
                    end loop;
                    return v_input_string;     
                  end;
                begin
                  dbms_output.put_line('Input= ' || v_input);
                  if nvl(to_number(v_input),0) < 1 then
                    dbms_output.put_line('Input must be greater than or equal to 1.');
                    return;
                  end if;
                  --sort digits in descending order
                  v_sorted_input := sort_chars(v_input); 
                  --loop through integers (with upper limits)
                  for i in 1..least(to_number(v_sorted_input),1000000) loop
                    --check if i works as next smallest integer
                    v_digit_check := all_digits_exist(i,v_sorted_input);
                    if v_digit_check = 'NOT FOUND' then 
                      continue; --go to the next integer
                    else 
                      --integer found, but must check for remainders
                      if nvl(length(v_digit_check),0) > 0 then
                        if to_number(v_digit_check) > to_number(i) then --a greater integer can be found
                          v_output := v_output || v_comma || to_char(i);
                          v_comma := ',';
                          for j in 1..length(to_char(i)) loop
                            v_sorted_input := regexp_replace(v_sorted_input,substr(to_char(i),j,1),'',1,1);
                          end loop;
                        else 
                          continue; --no greater integer found so continue with next highest
                        end if;
                      else 
                        v_output := v_output || v_comma || to_char(i);
                        exit; --done when no more digits exist
                      end if;
                    end if;
                  end loop;
                  dbms_output.put_line('Output= '||v_output);
                end;
                /
                
                
                Result:
                -------------------
                Input= 11234567801030904
                Output= 1,2,3,4,5,6,7,8,9,10,13,4000
                And it works for the inputs that Steve's code does not handle:
                Input= 11
                Output= 11
                
                Input= 76721
                Output= 1,2,6,77
                • 20. Re: Need the best way to solve this problem
                  AdamMartin
                  Updated to handle larger input strings (and inputs with lots of zeroes):
                  declare
                    v_input varchar2(150) := '456564231164684864864651153350000064006006456486894897897894560006456066468908000898977890660601061568044064066510308648084898900000064545456333217770';
                    v_sorted_input varchar2(150);
                    v_output varchar2(1100);
                    v_digit_check varchar2(150);
                    v_comma varchar2(1);
                    --character sort function
                    function sort_chars(p_chars varchar2) return varchar2 is
                      v_chars varchar2(150) := p_chars;
                      v_retval varchar2(150);
                      v_keep_searching boolean := true;
                      v_cnt number := 0;
                    begin
                      for i in reverse 0..9 loop
                        v_keep_searching := true;
                        while v_keep_searching loop
                          if instr(v_chars,to_char(i)) > 0 then
                            v_retval := v_retval || to_char(i);
                            v_chars := regexp_replace(v_chars,to_char(i),'',1,1);
                          else 
                            v_keep_searching := false;
                          end if;
                        end loop;
                      end loop;
                      dbms_output.put_line('Sorted='||v_retval);
                      return v_retval;
                    end;
                    --digit checking function
                    function all_digits_exist(p_int varchar2, p_input_string varchar2) return varchar2 is
                      v_instr number;
                      v_input_string varchar2(150) := p_input_string;
                    begin
                      for a in 1..length(p_int) loop 
                        v_instr := instr(v_input_string, substr(p_int,a,1));
                        if v_instr > 0 then
                          v_input_string := regexp_replace(v_input_string,substr(p_int,a,1),'',1,1);
                        else
                          return 'NOT FOUND';
                        end if; 
                      end loop;
                      return v_input_string;     
                    end;
                  begin
                    dbms_output.put_line('Input= ' || v_input);
                    if nvl(to_number(v_input),0) < 1 then
                      dbms_output.put_line('Input must be greater than or equal to 1.');
                      return;
                    end if;
                    --sort digits in descending order
                    v_sorted_input := sort_chars(v_input); 
                    --loop through integers (with upper limits)
                    for i in 1..least(to_number(v_sorted_input),100000) loop
                      --check if i works as next smallest integer
                      v_digit_check := all_digits_exist(i,v_sorted_input);
                      if v_digit_check = 'NOT FOUND' then 
                        continue; --go to the next integer
                      else 
                        --integer found, but must check for remainders
                        if nvl(length(v_digit_check),0) > 0 then
                          if to_number(v_digit_check) > to_number(i) then --a greater integer can be found
                            v_output := v_output || v_comma || to_char(i);
                            v_comma := ',';
                            for j in 1..length(to_char(i)) loop
                              v_sorted_input := regexp_replace(v_sorted_input,substr(to_char(i),j,1),'',1,1);
                            end loop;
                          else 
                            continue; --no greater integer found so continue with next highest
                          end if;
                        else 
                          v_output := v_output || v_comma || to_char(i);
                          for j in 1..length(to_char(i)) loop
                              v_sorted_input := regexp_replace(v_sorted_input,substr(to_char(i),j,1),'',1,1);
                          end loop;
                          exit; --done when no more digits exist
                        end if;
                      end if;
                    end loop;
                    if v_sorted_input is not null then 
                      v_output := v_output || v_comma || v_sorted_input; --to handle inputs with lots of zeroes
                    end if;
                    dbms_output.put_line('Output='||v_output);
                  end;
                  /
                  
                  
                  Result:
                  -------------------------
                  Input= 456564231164684864864651153350000064006006456486894897897894560006456066468908000898977890660601061568044064066510308648084898900000064545456333217770
                  Sorted=999999999988888888888888888887777777666666666666666666666666666665555555555555444444444444444444444333333322111111110000000000000000000000000000000000
                  Output=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,30,33,34,35,40,44,45,46,47,48,49,50,54,55,56,57,58,59,60,64,65,66,67,68,69,70,74,76,80,84,86,88,89,90,94,96,98,400,404,406,408,600,606,608,609,660,666,668,680,688,800,8000000000000  
                  • 21. Re: Need the best way to solve this problem
                    Manik
                    Just one word.... WOW!
                    BluShadow, open up an oracle teaching institute, and I will be your first disciple :)

                    I know the requirement is fuzzy, incomplete, may be impossible, just because its an insane thought of mine put into forum ;) but still you guys put forward some solutions which is just awesome..
                    Thanks to all the participants... Really appreciated!!!!

                    Cheers,
                    Manik.
                    • 22. Re: Need the best way to solve this problem
                      Nicosa-Oracle
                      This "fuzzy" problem solved, somehow, reminds me of [url http://littlebobeep.com/wp-content/uploads/2010/05/Calvinball1.gif]CalvinBall
                      "The score is still Q to 12!"
                      :-)


                      [url http://calvinandhobbes.wikia.com/wiki/Calvinball](an attempt to describe calvinball)
                      • 23. Re: Need the best way to solve this problem
                        AdamMartin
                        Manik wrote:
                        Just one word.... WOW!
                        Thanks! It was a lot of fun.
                        • 24. Re: Need the best way to solve this problem
                          padders
                          Tried something similar but got stuck on repeating numbers. I'm afraid yours seems to suffer similarly, e.g.

                          Input= 22222222222222222222
                          Sorted=22222222222222222222
                          Output=2,22,222,2222,2222222222
                          • 25. Re: Need the best way to solve this problem
                            AdamMartin
                            padders wrote:
                            Tried something similar but got stuck on repeating numbers. I'm afraid yours seems to suffer similarly, e.g.

                            Input= 22222222222222222222
                            Sorted=22222222222222222222
                            Output=2,22,222,2222,2222222222
                            That is the correct output. Where is the problem?

                            If you are suggesting that it is missing the integer 22222, then that would leave a remainder of exactly 22222, and remainders are not allowed. Therefore, 22222 is not a valid integer and it must be skipped. Likewise, 6 twos must be skipped, and 7 twos, and so on. The correct solution is shown in your post, which uses all the digits provided, leaving no remainder, and showing the lowest possible integers.

                            Also, note that the following line has a looping limit which can be raised (but performance would suffer if looping into the hundreds of millions):

                            for i in 1..least(to_number(v_sorted_input),100000) loop <----------------- limit of 100000 but it can be set higher

                            But if you want to see 22222, then add one more '2' to the input:

                            Input= 222222222222222222222
                            Sorted=222222222222222222222
                            Output=2,22,222,2222,22222,222222
                            • 26. Re: Need the best way to solve this problem
                              padders
                              Sorry posted wrong example, but issue is there - and you are right it is caused by looping limit.

                              Another example.

                              Input= 2222222222222222222222222222222222
                              Sorted=2222222222222222222222222222222222
                              Output=2,22,222,2222,22222,2222222222222222222

                              Should be?=2,22,222,2222,22222,222222,2222222222222

                              I'm wondering if generating number sequence based on only the numbers in the input would solve this. Not sure whether this is a likely input - I suppose you could just raise an error if the search expires.
                              • 27. Re: Need the best way to solve this problem
                                AdamMartin
                                Yes, that's a victim of the looping limit. You're right that it is an unlikely input. For inputs like these it seems like there is a more intelligent way of solving it than looping through all integers. I am thinking that it would be much more efficient to rearrange the digits into the possible integers that can be formed from the input. But the looping works very well for most other scenarios. My 150 digit input (above) completed in less than a second. But I am tempted now to see if I can do it again without the upward-counting integer loop. Seems like a great idea.
                                • 28. Re: Need the best way to solve this problem
                                  BluShadow
                                  Just for fun.... (cos I felt like it and had a few minutes spare)

                                  Here's a version that uses a recursive function to achieve the result...
                                  SQL> create or replace function sequence_values(p_instr in varchar2, v_limit in number := 100000) return varchar2 is
                                    2    v_mask  varchar2(50) := 'fm9999999999';
                                    3    function check_digits(p_instr in varchar2, p_val in number) return varchar2 is
                                    4      /* Checks if the digits of the current value are available in the remaining string */
                                    5      v_val varchar2(20) := to_char(p_val,v_mask);
                                    6      v_str varchar2(200) := p_instr;
                                    7    begin
                                    8      for i in 1..length(v_val)
                                    9      loop
                                   10        if instr(v_str,substr(v_val,i,1)) > 0 then
                                   11          v_str := regexp_replace(v_str,substr(v_val,i,1),'',1,1);
                                   12        else
                                   13          v_str := p_instr;
                                   14          exit;
                                   15        end if;
                                   16      end loop;
                                   17      return v_str;
                                   18    end;
                                   19    function max_val(p_instr in varchar2) return number is
                                   20      /* Determines the maximum possible value left in the remaining string */
                                   21      v_sorted varchar2(200) := '';
                                   22    begin
                                   23      for i in reverse 0..9
                                   24      loop
                                   25        v_sorted := v_sorted||regexp_replace(p_instr,'[^'||to_char(i)||']');
                                   26      end loop;
                                   27      return to_number(v_sorted);
                                   28    end;
                                   29    function is_valid(p_instr in varchar2, p_val in number) return varchar2 is
                                   30      /* Recurses the string to build up the result */
                                   31      v_chk varchar2(200);
                                   32    begin
                                   33      if p_val > v_limit then
                                   34        /* Allow a limit to prevent stupidity */
                                   35        return ' - Recursive Depth Limit Reached.';
                                   36      end if;
                                   37      /* Extract the current value from the string if possible */
                                   38      v_chk := check_digits(p_instr, p_val);
                                   39      if v_chk is null then
                                   40        /* No remaining string, so we have reached a solution */
                                   41        /* Pass back the current value */
                                   42        return to_char(p_val,v_mask);
                                   43      elsif v_chk = p_instr or max_val(v_chk) <= p_val then
                                   44        /* The current value wasn't found in the remaining string     */
                                   45        /* Or the remaining string after finding it will be too small */
                                   46        /* So just search on for the next possible matching value     */
                                   47        return is_valid(p_instr, p_val+1);
                                   48      else
                                   49        /* We found a value but we have more to do                    */
                                   50        /* Pass back the current value and the result of recursing    */
                                   51        /* the remainder of the string                                */
                                   52        return to_char(p_val,v_mask)||','||is_valid(v_chk, p_val+1);
                                   53      end if;
                                   54    end;
                                   55  begin
                                   56    return is_valid(p_instr, 1);
                                   57  end;
                                   58  /
                                  
                                  Function created.
                                  
                                  SQL>
                                  SQL> select sequence_values('1124567801030904') from dual;
                                  
                                  SEQUENCE_VALUES('1124567801030904')
                                  ------------------------------------------------------------------------------------------------------------------------
                                  1,2,3,4,5,6,7,8,9,10,40,100
                                  
                                  SQL>
                                  SQL> select sequence_values('11234567801030904') from dual;
                                  
                                  SEQUENCE_VALUES('11234567801030904')
                                  ------------------------------------------------------------------------------------------------------------------------
                                  1,2,3,4,5,6,7,8,9,10,13,4000
                                  
                                  SQL>
                                  SQL> select sequence_values('11275324765324234567801030904') from dual;
                                  
                                  SEQUENCE_VALUES('11275324765324234567801030904')
                                  ------------------------------------------------------------------------------------------------------------------------
                                  1,2,3,4,5,6,7,8,9,10,12,20,23,30,34,40,45,56,77
                                  
                                  SQL>
                                  SQL> select sequence_values('222222222222222222222',1000000) from dual;
                                  
                                  SEQUENCE_VALUES('222222222222222222222',1000000)
                                  ------------------------------------------------------------------------------------------------------------------------
                                  2,22,222,2222,22222,222222
                                  I've put a recursive depth limit on there (which can be overridden as required) to help prevent accidental hang-ups from really bad inputs.
                                  Hopefully I've included enough comments to make it easy to follow.

                                  Enjoy. :)
                                  • 29. Re: Need the best way to solve this problem
                                    AdamMartin
                                    BluShadow wrote:
                                    Just for fun.... (cos I felt like it and had a few minutes spare)

                                    Here's a version that uses a recursive function to achieve the result...

                                    Enjoy. :)
                                    Very nice!
                                    1 2 Previous Next