Conversion of a plain English problem into T-SQL

  • rob mcnicol

    SSC Eights!

    Points: 834

    Comments posted to this topic are about the item Conversion of a plain English problem into T-SQL

  • matt.bowler

    SSCrazy

    Points: 2660

    Thanks for that - some interesting points. I suspect that this is the modus operandii for a lot of people. It is when the problem space gets too large and complex that we need some of the more formalised structures to help manage the project.

  • dennis.hafstrom

    SSC Enthusiast

    Points: 105

    I do realize this was not the purpose of the article but it made me think of it so here's a recursive version. It'll stop after 100 recursions unless the maxrecursion option is changed of course.

    DECLARE @Start BIGINT;

    SET @Start = 10;

    WITH cte AS (

    SELECT @Start [Value]

    UNION ALL

    SELECT CASE [Value] % 2 WHEN 0 THEN [Value] / 2 ELSE ([Value] * 3) + 1 END

    FROM [cte]

    WHERE CASE [Value] % 2 WHEN 0 THEN [Value] / 2 ELSE ([Value] * 3) + 1 END != 1

    )

    SELECT *

    FROM [cte];

  • rob mcnicol

    SSC Eights!

    Points: 834

    matt.bowler (10/3/2011)


    It is when the problem space gets too large and complex that we need some of the more formalised structures to help manage the project.

    Yep, agreed. This approach is probably best used by one person working on one thing at a time. I would imagine that using this approach on a large project would result in a fair old mess.

    That said, I do recall times when I have used this approach to prototype some of the individual components before starting a larger project to help confirm that the project was viable. Also I found that the prototypes were a handy reference point for isolating and troubleshooting problems in the larger project once the build started.

    Thanks for the comment, much appreciated.

  • rob mcnicol

    SSC Eights!

    Points: 834

    dennis.hafstrom (10/3/2011)


    I do realize this was not the purpose of the article but it made me think of it so here's a recursive version.

    nice 🙂

  • ABHILASH DHONGDI

    SSC Veteran

    Points: 248

    might find this interesting...

    IF OBJECT_ID('dbo.fn_TestCollatzConjecture') > 0

    DROP FUNCTION dbo.fn_TestCollatzConjecture

    GO

    CREATE FUNCTION dbo.fn_TestCollatzConjecture ( @StartNumber BIGINT )

    RETURNS VARCHAR(200)

    AS

    BEGIN

    DECLARE @min-2 BIGINT

    DECLARE @Levels INT

    DECLARE @max-2 BIGINT

    DECLARE @Ret VARCHAR(200) ;

    WITH ApplyCollatzTransform

    AS ( SELECT @StartNumber AS NewNumber ,

    0 AS Level

    UNION ALL

    SELECT CASE WHEN NewNumber % 2 = 0

    THEN NewNumber / 2

    ELSE ( NewNumber * 3 ) + 1

    END ,

    Level + 1

    FROM ApplyCollatzTransform ACT

    WHERE NewNumber > 1

    )

    SELECT @min-2 = MIN(NewNumber) ,

    @Levels = MAX(Level) ,

    @max-2 = MAX(NewNumber)

    FROM ApplyCollatzTransform

    OPTION ( MAXRECURSION 0 )

    IF @min-2 = 1

    SET @Ret = 'Reached 1 after ' + CONVERT(VARCHAR(20), @Levels)

    + ' Level(s). Hit Max of ' + CONVERT(VARCHAR(20), @max-2)

    + ' before getting there...'

    ELSE

    SET @Ret = 'Did not hit 1 after ' + CONVERT(VARCHAR(20), @Levels)

    + ' Level(s)... Giving up...'

    RETURN @Ret

    END

    go

    DECLARE @StartNumber BIGINT

    SET @StartNumber = 27

    SELECT dbo.fn_TestCollatzConjecture(@StartNumber)

  • rob mcnicol

    SSC Eights!

    Points: 834

    ABHILASH DHONGDI (10/3/2011)


    might find this interesting...

    IF OBJECT_ID('dbo.fn_TestCollatzConjecture') > 0

    DROP FUNCTION dbo.fn_TestCollatzConjecture

    etc...

    most impressive abhilash, thanks. just to be curious, did you write it using the approach i suggested? or was it written line by line as we see it now?

  • SqlOnMyMind

    SSCertifiable

    Points: 5050

    With regards to your discussion of the iterative process of building the code, one step I didn't see was how to stop the infinite loop if the Collatz Conjecture does NOT reach the value of 1! In the generic sense, this would be the error-catching phase of the development of the code.

    p.s. ABHILASH DHONGDI - Clever use of MAXRECURSION 0! Nicely done!

  • toonjamie

    SSChasing Mays

    Points: 636

    My comment conveniently ignores the

    one of the things I am interested in is the count of how many repetitions of the sequence it took to reach 1

    but I enjoyed the problem/solution and wanted to comment so, hey ...

    Because the tool we're using to solve this poser is SQL, I'd like to see the solution 'learning' about numbers that it knows will eventually reach 1 and therefore cutting corners. So I'd INSERT into a ProvedNumbers table once I hit 1 or hit a number that was already in ProvedNumbers.

    e.g. I've learned that 8 goes 4, then 2, then 1. So when I tackle 10 I can stop at 10,5,16,8 and add 10 to ProvedNumbers. This will then help when I do 12 and 13 and they reach 10.

    Rob - I look forward to the product of more "particularly idle evenings" !

    Jamie.

    Isle of Man

  • rob mcnicol

    SSC Eights!

    Points: 834

    Carla Wilson-484785 (10/3/2011)


    With regards to your discussion of the iterative process of building the code, one step I didn't see was how to stop the infinite loop if the Collatz Conjecture does NOT reach the value of 1! In the generic sense, this would be the error-catching phase of the development of the code.

    yep fair point carla. i don't tend to put in error catching when building a prototype unless i am struggling with the prototype itself. when it comes time to rework/rebuild/productionise it then yes, error trapping is crucial.

    as it regards to this particular problem - do you have something in mind for stopping the infinite loop?

  • ABHILASH DHONGDI

    SSC Veteran

    Points: 248

    It was similar to your approach.

    I started with the math first, next came the decision of how I wanted the output structured - that is was it going to return the individual steps or just a Bit with some details. I chose the latter cuz it hardly matters how many steps it takes or what the steps look like. This assertion merely insists that all number will dwindle down to 1.

    By the way, I was reading about Collatz not long ago and I think a solution (an actual proof that all numbers share this property) is probably reached through math induction. The code we attempted to write is really a way to solve this brute force. We could, in theory, exhaustively run positive integers through our code and "see" that they all behave the same way but that is hardly proving it. What I think might be the way to prove it would involve something like this... 1. Let's say there is a number N for which we assume that Collatz is true, 2. Now, assume that for N + 1 Collatz isn't true, 3. find a way to prove that statement 2 is false. If we can do that, then, we would have proven it for all positive numbers.

    Of course, at the moment I only think it's a way to attempt to solve. I lack the math skills to go about it in any proper scientific way. Guess I'll leave it to the math world....

  • rob mcnicol

    SSC Eights!

    Points: 834

    I'd like to see the solution 'learning' about numbers that it knows will eventually reach 1 and therefore cutting corners

    great idea, jamie. well worth having a go.

  • Bill Talada

    SSChampion

    Points: 11956

    The math is pathetically simple and failing to see patterns is the mark of a beginning programmer. Some problems are too difficult to see patterns in until one has experience with them. This is the evolutionary process.

    If number is odd do

    n x 3 + 1

    which basically converts any odd number to an even one since "odd times itself an even number of times yields an even result" and "odd times itself an odd number of times yields an odd result"

    If number is even

    n / 2

    which eventually reduces all even numbers to 1.

    As Tesla said of Edison something like: a little hypothesis and he could have saved him 90% of his effort in finding a filament for the light bulb.

  • toonjamie

    SSChasing Mays

    Points: 636

    Bill,

    If number is even

    n / 2

    which eventually reduces all even numbers to 1.

    Not so fast - it only reduces 2n quickly to 1. Some even numbers (18, say) bounce around for quite a while which is the point of the whole problem.

    Jamie.

  • James Goodwin

    Hall of Fame

    Points: 3691

    The math is pathetically simple and failing to see patterns is the mark of a beginning programmer.

    The Collatz conjuecture is deceptively difficult, that's why it remains unsolved.

    Yes, 3n+1 converts an odd number into an even number that is larger than itself.

    If number is even

    n / 2

    which eventually reduces all even numbers to 1.

    No, it reduces powers of 2 to 1. It reduces other even numbers to some odd number. An early long sequence is for 9

    9 - 28 - 14 - 7 - 22 - 11 - 34 - 17 - 52 - 26 - 13 - 40 - 20 - 10 - 5 - 16 - 8 - 4 - 2 - 1

    The converse of the conjecture would say:

    There is some odd number x, such that the iteration returns to x (or goes to infinity).

    This means, for the original problem:

    1. You only need to check odd numbers

    2. The stopping point for a disproof is that the current number equals the starting number.

    3. Every number touched along the way is solved with the original number.

    --

    JimFive

Viewing 15 posts - 1 through 15 (of 19 total)

You must be logged in to reply to this topic. Login to reply