Sunday, January 27, 2008

Puzzle

On the russian SQL forum there was a question for friday brain warm-up. The main idea is that the OP knows the answer beforehands, but he wants forum members to put some efforts on it to come up with easier solution.
So here is the problem. I've taken the description from that site.
You have a list of numbers:
1
11
21
1211
111221
312211
13112221
1113213211
...

You need to understand the logic of building such a sequence and then post a SQL solution for that.

Ok. If you want to try your skills - now it is the best time to stop and proceed by yourown. For solution look forward.

Solution: It's actually quite simple :) After starting the sequence with 1, each term in the sequence consists of groups of two numbers based on the previous term - the first being the quantity and the second specifying which digit.

Example: the first term is 1, which has "one 1" in it, therefore 11.
11 has "two 1's" in it, therefore 21.
21 has "one 2 and one 1" in it and therefore 1211.

Now let's proceed with the second part - SQL solution.
Although a query with similar idea was posted before I did, mine was:
SQL> select s from (select * from dual
2 model
3 dimension by (0 d)
4 measures(cast('1' as varchar2(1000)) s, cast(null as varchar2(1000)) s_new, 10 n, 1 flag)
5 rules iterate (10000000) until(flag[iteration_number+1]=n[0])
6 (s_new[iteration_number+1]=decode(flag[CV()-1],0,s_new[CV()-1],null)||
7 length(regexp_substr(s[CV()-1],'^(.)\1*'))||substr(s[CV()-1],1,1),
8 s[iteration_number+1]= regexp_replace(s[CV()-1],'^(.)\1*'),
9 flag[iteration_number+1]=nvl2(s[CV()],0,max(flag)[d 10 s[iteration_number+1]=nvl(s[CV()], s_new[CV()])
11 ))
12 where flag>0
13 /

S
--------------------------------------------------------------------------------
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211

10 rows selected

SQL>

2 comments:

prodlife said...

1. Do you know this site? http://projecteuler.net/index.php?section=problems
I think you'll enjoy it.

2. The correct way to blog about a puzzle is by posting only the problem, ask readers to reply with solutions, and post your solution few days later. More fun that way :-)

Volder said...

thanks, Chen, for a nice link ;)
Have not seen this site before.

I don't think my blog is so readable to post puzzle here and wait for replies. Better to put it in the forum.

I placed it here if someone will learn model clause to have an example to elaborate.