This discussion is archived
1 2 Previous Next 29 Replies Latest reply: Jan 24, 2013 11:33 AM by AdamMartin Go to original post RSS
  • 15. Re: Need the best way to solve this problem
    jihuyao Journeyer
    Currently Being Moderated
    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 Pro
    Currently Being Moderated
    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 Guru Moderator
    Currently Being Moderated
    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 Pro
    Currently Being Moderated
    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 Pro
    Currently Being Moderated
    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 Pro
    Currently Being Moderated
    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 Expert
    Currently Being Moderated
    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 Expert
    Currently Being Moderated
    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 Pro
    Currently Being Moderated
    Manik wrote:
    Just one word.... WOW!
    Thanks! It was a lot of fun.
  • 24. Re: Need the best way to solve this problem
    padders Pro
    Currently Being Moderated
    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 Pro
    Currently Being Moderated
    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 Pro
    Currently Being Moderated
    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 Pro
    Currently Being Moderated
    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 Guru Moderator
    Currently Being Moderated
    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 Pro
    Currently Being Moderated
    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

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points