## The New Order Oracle Coding Challenge 2

2 08 2011

August 2, 2011

In the previous article in this series we tried to develop different methods for identifying special numbers between 1 and 1,000,000, such that the number formed by reversing the order of the digits will evenly divide into the original number.  I initially predicted that there would be at least three unique solutions provided before the undocumented REVERSE function was mentioned.  A fellow Oak Table member quickly provided a solution using the REVERSE function, which happens to be the fastest of the various approaches.  Another reader noticed a pattern that helps find those special numbers – if that pattern identifies all of the special numbers, it is easily the most efficient approach to finding these special numbers.

Today’s blog article also is on the topic of finding special numbers, determined as special after changing the order of the number’s digits.  I used my fancy, on-point introduction for this article in the earlier article (letters on the dice, trying to form words from those letters), so I thought that I would jump the little pony over the edge of the cliff in search of another introduction (there are probably five readers with an odd image stuck in their head at this moment).   😉

Have you ever noticed the disparity between the Environment Protection Agency’s (EPA or the equivalent in other countries) estimates for fuel efficiency and the actual fuel efficiency calculated with the hand held calculator?  Take for instance a car that I own – that car has never achieved the EPA’s estimated fuel efficiency rating.  A 412 horsepower (at the flywheel as claimed by the manufacturer, other tests have concluded that it might be higher) V8 achieving 25 miles per U.S. gallon (MPG) of fuel?

Time for the Oracle Database test case.  On a frigid 32 degree day (in Celsius, that is a hot 90 degrees Fahrenheit), I lowered the windows, topped off the fuel tank with premium grade fuel, reset the car’s fuel efficiency gauge (the MPG gauge… oddly, this gauge always reads 6% to 8% lower than the actual fuel efficiency), and then set out on a roughly 117 mile (188 KM) drive down the highway with the radar detector on the dash board.  While I have heard that the car’s speed limit is set at the factory to roughly 160 miles per hour (258 KM/H), the posted speed limit was typically 55 MPH (miles per hour) except in the roughly half-dozen or so cities along the way.  The car never did hit the EPA’s estimated fuel efficiency rating.  Somebody was playing with the numbers a bit, I think. 🙂

Along the route selected for the 117 mile test loop, I captured cell phone pictures showing the car’s fuel efficiency gauge (MPG gauge).  Below are the cell phone pictures captured at 15 miles into the drive, roughly half way through the drive, and near the end of the 117 mile drive.

So, how does Oracle Database play a part in the introduction to this blog article?  Let’s take a guess at the car’s actual fuel efficiency using a SQL statement:

```SELECT
29.5 CAR,
ROUND(29.5 * 1.06, 2) LOW_ACTUAL,
ROUND(29.5 * 1.08, 2) HIGH_ACTUAL
FROM
DUAL;

CAR LOW_ACTUAL HIGH_ACTUAL
---------- ---------- -----------
29.5      31.27       31.86```

So much for EPA estimates – between 25.08% and 27.44% lower than the actual fuel efficiency.  Does this test case then suggest that if we do not use all of the features that are available in a tool, that we are then more efficient than expected?  I think that I need another test case to decide.  😉

Side note: For the tank of fuel when the car rolled over the 1,000 mile mark, the car achieved 28.75 miles per gallon while touring some of the sites around Michigan, specifically the hills and curves along the north-west shoreline of the lower peninsula (several of those hills were steep – for one hill in particular the car downshifted three gears to maintain speed going down the hill).  The car’s overall fuel efficiency since it left the factory is 25.58 MPG (excluding the 117 mile test case), so I guess that one could argue that if you TRUNC the fuel efficiency number, at the root the EPA is right.  Make like a tree and leave (that was a movie quote from “Back to the Future”).

After returning from the test case I set out on my other 412 HP vehicle… cough, that would be a 4 cylinder 12 horsepower 1946 Farmall A tractor.  Time to mow the lawn in second gear.  Cutting a 6 foot (1.83 meter) wide path through grass that is up to 12 inches (30.48 cm) high, and capable of mowing down 2 inch diameter trees as necessary.  Oh, the power of the horse…

OK, now that we have drifted far from the topic of this article and have had a chance to play with numbers in the long introduction, on to the challenge.  Consider the four digit integer numbers between 1,000 and 9,999.  There are 4! (1 * 2 * 3 * 4 = 24) possible combinations of the four digits of each of these numbers.  For example, consider the number 8712 – the 24 possible combinations are:

```1278
1287
1728
1782
1827
1872
2178
2187
2718
2781
2817
2871
7128
7182
7218
7281
7812
7821
8127
8172
8217
8271
8712 8721```

The objective is to find all combinations of the four digit numbers between 1,000 and 9,999 that evenly divide into the original number.  For the above example with the original number 8712, the combination 2178 evenly divides into 8712.  Thus, the output would include:

```ORIGINAL COMBINATION
-------- -----------
8712        2178```

The restrictions:

• The four digit original numbers between 1,000 and 9,999 should not be included in the output if the last digit of those numbers is 0 – the combination number may end with 0 if the original number included a 0 digit.  Thus, do not include the original numbers 1000, 1010, 1020, 1030, 1040, etc.
• The original value cannot be equal to the combination value (in the above example, it is not valid to output the combination value 8712).
• Each original number and combination pair should be output at most one time.
• You may not reuse a digit position twice; all digit positions must be used once.  For example, the number 7141 includes the digit 1 twice, therefore, all generated combinations of that number must include two number 1 digits.

This challenge is a bit more difficult than was the challenge in part 1 of this series.  The greatest difficulty likely involves creating the 23 valid digit combinations (there are 24, but one of those combinations will always be invalid) of the four digit numbers.

The problem is solvable – will your solution be the same as mine?  I will give the readers a couple of days to ponder the thoughts of why a horse entered a race between a car and a tractor before sharing my approach to solving the problem.

### 7 responses

2 08 2011

Here is my attempt … as mentioned in the code, Anagram credit goes to Laurent. Due to use of pl/sql, this is not a pure-sql solution but at-least an attempt.

```-- anagram code taken from Laurent Schneider's Anagram solution posted at
-- shamelessly reused with full credit to Laurent for that code. Hope he won't mind the reuse ... :)
--
-- we treat numbers as char to generate anagrams (as possible combinations)
-- raj (rjamya@gmail.com)
-- please suggest anything i missed or improvements
--
create or replace type table_of_varchar2 as table of varchar2(255);
/
create or replace package anagram is
procedure p(x varchar2, y varchar2 default null);
function f(x varchar2) return table_of_varchar2;
end;
/
create or replace package body anagram is
t table_of_varchar2;
procedure p(x varchar2, y varchar2 default null) is
begin
if (length(x) = 1) then
t.extend(1);
t(t.last):=y||x;
else
for i in 1..length(x) loop
p(substr(x,1,i-1)||substr(x,i+1),y||substr(x,i,1));
end loop;
end if;
end p;

function f(x varchar2) return table_of_varchar2 is
begin
t := new table_of_varchar2();
p(x);
return t;
end f;

end;
/
set timing on
declare
procedure p (p_msg in varchar2) is
begin
-- dbms_output.put_line(to_char(systimestamp,'hh24:mi:ss.ff6') || ': ' || p_msg);
dbms_output.put_line(p_msg);
end;
--
begin
p('Original  Combination');
p('--------  -----------');
for f in (select r r0 from (select rownum r from dual connect by level = 1000 and mod(r,10)  0)
loop
for a in (select distinct column_value as c0 from table(anagram.f(f.r0)))
loop
if    f.r0  a.c0
and f.r0 > a.c0
and mod(f.r0,a.c0) = 0 then
-- p(f.r0 || ' : ' || a.c0 || ' : ' || (f.r0/a.c0));
end if;
end loop ;
end loop;
end;
/
commit
/
Output is ...

Original  Combination
--------  -----------
1001         0011
1005         0015
1008         0018
1053         0351
2002         0022
2016         0126
2025         0225
2079         0297
2106         0162
3003         0033
3024         0432
3042         0234
3045         0435
3105         0135
3105         1035
3402         0243
4004         0044
4005         0045
5005         0055
5049         0459
6006         0066
6031         0163
6045         0465
6048         0864
6072         0276
6075         0675
6084         0468
6105         0165
6804         0486
7007         0077
7011         0171
7128         1782
7425         2475
8008         0088
8019         0891
8092         0289
8316         1386
8712         2178
9009         0099
9016         0196
9021         0291
9108         0198
9207         0279
9207         0297
9405         0495
9504         0594
9513         1359
9801         0891
9801         1089
```
2 08 2011

I think i am missing at-last one more combinations (9009 and 0099), will check my code (it is w-i-p).

2 08 2011

sorry about incovenience. here are the original 2 replies (unaltered):
1:

```
select * from (
select nr original,
to_number(substr(ch,d1,1)||substr(ch,d2,1)||substr(ch,d3,1)||substr(ch,d4,1)) combination
from
(select d1,d2,d3,d4 from
(select level d1 from dual connect by level<=4),
(select level d2 from dual connect by level<=4),
(select level d3 from dual connect by level<=4),
(select level d4 from dual connect by level<=4)
where d1!=d2 and d1!=d3 and d1!=d4 and d2!=d3 and d2!=d4 and d3!=d4 and (d1,d2,d3,d4) not in(select 1,2,3,4 from dual)
) comb,
(select * from (select level nr, to_char(level) ch from dual connect by level<=9999) where nr>1000 and mod(nr,10)!=0) numbers
where mod(nr, to_number(substr(ch,d1,1)||substr(ch,d2,1)||substr(ch,d3,1)||substr(ch,d4,1)))=0 and substr(ch,d1,1)!='0'
)
where original!=combination
```

2:

```select * from (
select nr original,
to_number(substr(ch,d1,1)||substr(ch,d2,1)||substr(ch,d3,1)||substr(ch,d4,1)) combination
from
(select substr(ch,2,1) d1,substr(ch,4,1) d2,substr(ch,6,1) d3,substr(ch,8,1) d4 from
(select SYS_CONNECT_BY_PATH(5-l,' ') ch from (select level l from dual connect by level<=4)
connect by nocycle prior l<5)
where length(ch)=8 and ch!=' 1 2 3 4'
) digits,
(select * from (select level nr, to_char(level) ch from dual connect by level<=9999) where nr>1000 and mod(nr,10)!=0) numbers
where substr(ch,d1,1)!='0'
)
where original!=combination and mod(original, combination)=0
```

p.s. pls delete the older ones

3 08 2011

There have been a couple of possible solutions posted so far, and there has been no more suggestions posted in the last 36 hours, so I thought that I would share the solution that I developed.

First, we need to find a way to build all 24 combinations of the 4 digits in the 4 digit numbers. For instance, we might arrange the 4 digits into the 24 combinations using a SQL statement like the following (the numbers represent the original positions of the digits):

```WITH N AS
(SELECT
ROWNUM RN
FROM
DUAL
CONNECT BY
LEVEL<=4)
SELECT
N1.RN P1,
N2.RN P2,
N3.RN P3,
N4.RN P4
FROM
N N1,
N N2,
N N3,
N N4
WHERE
N1.RN<>N2.RN
AND N1.RN<>N3.RN
AND N1.RN<>N4.RN
AND N2.RN<>N3.RN
AND N2.RN<>N4.RN
AND N3.RN<>N4.RN
ORDER BY
P1,
P2,
P3,
P4;

P1  P2  P3  P4
--- --- --- ---
1   2   3   4
1   2   4   3
1   3   2   4
1   3   4   2
1   4   2   3
1   4   3   2
2   1   3   4
2   1   4   3
2   3   1   4
2   3   4   1
2   4   1   3
2   4   3   1
3   1   2   4
3   1   4   2
3   2   1   4
3   2   4   1
3   4   1   2
3   4   2   1
4   1   2   3
4   1   3   2
4   2   1   3
4   2   3   1
4   3   1   2
4   3   2   1

24 rows selected.
```

Now for the easy part, use the above matrix to simply pull out the digits in the specified order from the list of numbers between 1000 and 9999:

```SELECT DISTINCT
*
FROM
(SELECT
N.RN,
TO_NUMBER(SUBSTR(N.RNC,P.P1,1)||SUBSTR(N.RNC,P.P2,1)||SUBSTR(N.RNC,P.P3,1)||SUBSTR(N.RNC,P.P4,1)) RND
FROM
(SELECT
ROWNUM+1000 RN,
TO_CHAR(ROWNUM+1000) RNC
FROM
DUAL
CONNECT BY
LEVEL<=8999) N,
(WITH N AS
(SELECT
ROWNUM RN
FROM
DUAL
CONNECT BY
LEVEL<=4)
SELECT
N1.RN P1,
N2.RN P2,
N3.RN P3,
N4.RN P4
FROM
N N1,
N N2,
N N3,
N N4
WHERE
N1.RN<>N2.RN
AND N1.RN<>N3.RN
AND N1.RN<>N4.RN
AND N2.RN<>N3.RN
AND N2.RN<>N4.RN
AND N3.RN<>N4.RN) P
WHERE
RN/10<>TRUNC(RN/10))
WHERE
RN<>RND
AND RN/RND=TRUNC(RN/RND)
ORDER BY
RN,
RND;

RN   RND
----- -----
1001    11
1005    15
1008    18
1053   351
2002    22
2016   126
2025   225
2079   297
2106   162
3003    33
3024   432
3042   234
3045   435
3105   135
3105  1035
3402   243
4004    44
4005    45
5005    55
5049   459
6006    66
6031   163
6045   465
6048   864
6072   276
6075   675
6084   468
6105   165
6804   486
7007    77
7011   171
7128  1782
7425  2475
8008    88
8019   891
8092   289
8316  1386
8712  2178
9009    99
9016   196
9021   291
9108   198
9207   279
9207   297
9405   495
9504   594
9513  1359
9801   891
9801  1089

49 rows selected.
```

Any other solutions?

4 08 2011

what about a very short one? (disregard the timing 🙂 ) :

```with nr as
(select level+1000 n1,level n2  from dual connect by level<9000)
select a.n1 original,b.n2 combination
from nr a, nr b
where   mod(a.n1,b.n2)=0 and a.n1>b.n2 and mod(a.n1,10)>0 and
cast(multiset(select substr(a.n1,level,1) from dual connect by level<5) as KU\$_OBJNUMSET)=
cast(multiset(select substr(lpad(b.n2,4,0),level,1) from dual connect by level<5) as KU\$_OBJNUMSET)
```
4 08 2011

I didn’t succeed right now to have a pure SQL solution. I have however created a pipelined function giving me the four digit combinations as follows

```
mhouri.world >select * from table(f_get_number(8712));

COLUMN_VALUE
------------
8712
8721
8172
8127
8271
8217
7812
7821
7182
7128
7281
7218
1872
1827
1782
1728
1287
1278
2871
2817
2781
2718
2187
2178

24 rows selected.

mhouri.world >select * from table(f_get_number(7141));

COLUMN_VALUE
------------
7141
7114
7411
7411
7114
7141
1741
1714
1471
1417
1174
1147
4711
4711
4171
4117
4171
4117
1714
1741
1174
1147
1471
1417

24 rows selected.
```

and have started figuring out how to use this function with the original numbers selected as follows

```
mhouri.world > SELECT original
2    FROM
3      ( select rownum original
4       from dual connect by level <= 9999
5       )
6    WHERE original           >= 1000
7    AND SUBSTR(original,4,1) != 0
8  ;

ORIGINAL
----------
1001
1002
1003
1004
1005
1006
1007
1008
1009
1011
1012
1013
1014
1015
1016
1017
1018
1019
1021
1022
1023
1024
....
```

4 08 2011

Mohamed,

Good idea to try a pipelined function. I have not worked with those very much.

As an experiment, I quickly put together an Excel macro/Visual Basic 6 program that accepts a number as input and outputs to the debug window all combinations of the digits in that number:

```Private Function Combinations(lngNumber As Long) As Long
Dim i As Integer
Dim intFlag As Integer
Dim intDigits As Integer
Dim intDigit(20) As Integer
Dim intDigitIndex(20) As Integer

intDigits = Len(CStr(lngNumber))
For i = 1 To intDigits
intDigitIndex(i) = i
Next i

intFlag = 0
For i = 1 To intAdjustmentPosition - 1
'Found a duplicate index position in the other values to the left
intFlag = 1
End If
Next i
If intFlag = 1 Then
'Try the next index position in this element
Else
'Output
For i = 1 To intDigits
Debug.Print intDigitIndex(i);
Next i
Debug.Print ""
Else
'No duplicate so prepare to check the next position
End If
End If

'Roll back one index position as many times as necessary
Loop
Loop
End Function
```

Now let’s convert that VB 6 code into a function that will eventually return pipelined rows (is SYS.AQ\$_MIDARRAY the correct type, I borrowed it from another example posted by someone to this blog – it appears that we *could* use this to return VARCHAR strings:

```CREATE OR REPLACE FUNCTION COMBINATIONS(SNUMBER IN NUMBER) RETURN SYS.AQ\$_MIDARRAY PIPELINED
AS
TYPE MY_ARRAY IS TABLE OF NUMBER INDEX BY PLS_INTEGER;
intDigit MY_ARRAY;
intDigitIndex MY_ARRAY;
intDigits NUMBER;
intFlag NUMBER;
strOutput VARCHAR2(100);
BEGIN
intDigits := LENGTH(TO_CHAR(SNUMBER));
FOR I IN 1 .. intDigits LOOP
intDigitIndex(I) := I;
END LOOP;

intFlag := 0;
FOR I IN 1 .. intAdjustmentPosition - 1 LOOP
-- Found a duplicate index position in the other values to the left
intFlag := 1;
END IF;
END LOOP;
IF intFlag = 1 Then
-- Try the next index position in this element
ELSE
-- Output
strOutput := '';
FOR i IN 1 .. intDigits LOOP
strOutput := strOutput || SUBSTR(TO_CHAR(SNUMBER),intDigitIndex(i),1);
END LOOP;

DBMS_OUTPUT.PUT_LINE(strOutput);
ELSE
-- No duplicate so prepare to check the next position
END IF;
END IF;

-- Roll back one index position as many times as necessary
END LOOP;
END LOOP;
END;
/
```
```SET SERVEROUTPUT ON

SELECT * FROM TABLE(COMBINATIONS(1234));

no rows selected

1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
```

As can be seen by the above output, if we input the 4 digit number 1234, the function outputs all combinations of the digits 1234. It will work with numbers with 1, 2, 3, 4, 5, 6, 7, 8, 9, and etc. digits. Let’s fix the function so that it returns pipelined rows:

```CREATE OR REPLACE FUNCTION COMBINATIONS(SNUMBER IN NUMBER) RETURN SYS.AQ\$_MIDARRAY PIPELINED
AS
TYPE MY_ARRAY IS TABLE OF NUMBER INDEX BY PLS_INTEGER;
intDigit MY_ARRAY;
intDigitIndex MY_ARRAY;
intDigits NUMBER;
intFlag NUMBER;
strOutput VARCHAR2(100);
BEGIN
intDigits := LENGTH(TO_CHAR(SNUMBER));
FOR I IN 1 .. intDigits LOOP
intDigitIndex(I) := I;
END LOOP;

intFlag := 0;
FOR I IN 1 .. intAdjustmentPosition - 1 LOOP
-- Found a duplicate index position in the other values to the left
intFlag := 1;
END IF;
END LOOP;
IF intFlag = 1 Then
-- Try the next index position in this element
ELSE
-- Output
strOutput := '';
FOR i IN 1 .. intDigits LOOP
strOutput := strOutput || SUBSTR(TO_CHAR(SNUMBER),intDigitIndex(i),1);
END LOOP;

PIPE ROW (strOutput);
ELSE
-- No duplicate so prepare to check the next position
END IF;
END IF;

-- Roll back one index position as many times as necessary
END LOOP;
END LOOP;
END;
/
```
```SELECT * FROM TABLE(COMBINATIONS(1234));

COLUMN_VALUE
-----------------
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321

24 rows selected.
```

Now the interesting thing is that if we input 1234, we are able to use the first, second, third, and fourth characters in the returned values to determine how to reorganize the digits in the original numbers that are supplied by the CONNECT BY syntax:

```SELECT DISTINCT
N,
D
FROM
(SELECT
N.N,
TO_NUMBER(SUBSTR(TO_CHAR(N.N), SUBSTR(P.COLUMN_VALUE,1,1),1) ||
SUBSTR(TO_CHAR(N.N), SUBSTR(P.COLUMN_VALUE,2,1),1) ||
SUBSTR(TO_CHAR(N.N), SUBSTR(P.COLUMN_VALUE,3,1),1) ||
SUBSTR(TO_CHAR(N.N), SUBSTR(P.COLUMN_VALUE,4,1),1)) D
FROM
(SELECT
*
FROM
TABLE(COMBINATIONS(1234))) P,
(SELECT
ROWNUM+1000 N
FROM
DUAL
CONNECT BY
LEVEL<=8999) N
WHERE
N/10 <> TRUNC(N/10))
WHERE
N>D
AND N/D = TRUNC(N/D)
ORDER BY
N;
```

I am not sure if the above helps – maybe someone can figure out how to directly feed the numbers from the N inline view into the COMBINATIONS function.