July 31, 2011
(Forward to the Next Post in the Series)
Years ago I played a couple of different games with letters, rather than numbers, on dice – attempting to form words from the letters displayed on top of the dice. I was not very good with those games, and I recall attempting to create a computer program to help me with the challenge. The screaming fast 1 MHz CPU and 64KB of memory proved to be no match for the words listed in the paper-bound dictionary sitting on the shelf. Computers are significantly faster now, with wide-spread access to Internet based word lists, so it probably would not be much of a challenge today to build a solution for one of those dice letter games.
Finding different combinations with number digits is a bit easier than working with letters – we are able to use math rules to determine if the specified conditions are met rather than a dictionary. We will start with an easy problem that I found on the web, but I will keep the source of that problem a secret for now. Consider the number 989,901. If we write the digits in that number from right to left, we obtain the new number 109,989. What is special about that new number? The number is evenly divisible by 3 and 9, but more interesting is that the new number divides evenly into the original number (989,901).
With the help of Oracle Database, find all of the numbers from 1 to 1,000,000 where the digits in the number when listed from left to right are evenly divisible by those same digits listed from right to left. The numbers that end with 0 are a special case, reversing the order of the digits in those numbers will result in the 0 digit effectively disappearing – as such, exclude any number that ends with 0 from being tested.
There are several methods to swap the order of the digits in the number. Would you use a different method to test all of the numbers between 1 and 10,000, or to test all of the numbers up to 10,000,000?
Might it work to store the numbers in a reverse key index, and then dump the resulting index values – is that the fourth method to switch the order of the digits? 😉
The undocumented REVERSE function:
http://awads.net/wp/2006/08/30/cool-undocumented-sql-function-reverse/
That is a great way to start the possible solutions for this particular problem.
Sorry, couldn’t help myself. I actually think numbers with trailing zero’s are more interesting than numbers that write the same way backwards and forwards (e.g., 414, 5225, etc…)
Dominic,
I was 99% certain that a solution with the REVERSE function would not appear before the third or fourth unique solution. The solution that I put together before finalizing this blog article is this one:
The above solution is similar to your solution, except for the way that I checked to see if the last digit is a zero.
Without the last digit check it appears that 1,548 numbers match the criteria when testing the numbers up to 1,000,000, but with the check there are 6 numbers. How about when checking the numbers up to 10,000,000 – zero rows returned: 😉
Did you check the divisor in each case ? Only 4 or 9.
Assuming we have a pattern here, it should go on forever I assume ?
Gary,
That is an interesting observation – I did not see the pattern until you pointed it out.
Going back to the inefficient ways to do this, how about the following (requires 11gR2):
This makes a custom reverse function by generating a row for each digit in a number. Work backwards through the digits in the number (using negative numbers in the substr). Then combine back together using listagg.
You could use a positive number in the substr and order descending in the listagg grouping clause as well.
I also hit the “not enough memory” error when trying this with 10,000,000 rows.
Chris,
Good idea to use the LISTAGG function – the concept behind what you did will be necessary for part 2 of the blog article series.
I have 3 other solutions to this particular problem waiting to be publish, in the hope that someone else will come up with a similar (and likely better) solution – there will certainly be variances between my approach and the one proposed by readers of this blog. For example, the following is the example that I put together using the LISTAGG function:
Building a solution to handle up to a 10 digit number. The idea in this case is to convert the number to a string (VARCHAR), join the number to a view that counts from 1 up to the number of characters in the string version of the number, and use the SUBSTR function to pull out the digits from the right to the left:
Next, we use the LISTAGG function that was introduced in 11.2.0.1 to recombine the reverse ordered digits back into a single row:
The final step performs the specified checks:
I forgot to mention that it is possible to work around the “not enough memory” error when using CONNECT BY through the use of an intentional Cartesian join. As demonstrated below, checking all numbers up to 10,000,000:
If you did not know about the undocumented REVERSE function and were running a version of Oracle Database prior to 11.2.0.1, how might you solve this sort of problem?
If you you know that the largest number will have 10 digits, you could do something like the following:
The above approach is probably a bit slow.
Instead, you might build a reverse number function:
Any other solutions?
Another method – use mathematics to reverse the digits in the numbers – the DECODE and SIGN conbination make certain that we do not accidentally pad additional zeros at the end of the reversed number:
Then slide the above into an inline view to perform the tests:
Another example that probably will not work with all NLS settings. DUMP the value of the string version of the number, examine the dump value after the colon (:), and use REGEXP_SUBSTR to pick out the “words” (numbers) from the comma separated list that remains. The final step converts the numbers back into ASCII characters with the CHR function:
Next, we slide the above into an inline view and apply the conditions:
Note the number of times the SUBSTR(D,INSTR(D,’:’)+2) value is calculated – for better performance, that value should have been calculated in the inline view where DUMP(TO_CHAR(ROWNUM)) is performed.
Here is another example that uses recursion to reverse the order of the digits. On Oracle Database 11.2.0.2, this returns an error if there are more than 3 digits in the number:
The same error is returned if we precreate a table:
Trying a 4 digit number:
Recursion in this case is apparently possible on SQL Server, as found in this SQL Server forum thread:
http://www.sqlservercentral.com/Forums/Topic697178-23-1.aspx
Is there a work-around that allows a recursion approach to work on Oracle Database?
Mohamed,
Very nice solution. What you put together shares some similarities with the solution provided by Dominic Delmolino, and one of the solutions that I posted.
Any thoughts on part 2 of the series?:
https://hoopercharles.wordpress.com/2011/08/02/the-new-order-oracle-coding-challenge-2/