The Steps Problem

[Linux]

I had to solve this problem in a programing content, a few years ago, and I never found the same problem on internet.

We had 4 hours to solve 2 problems like this.

Problem:

Mr. John has a house. In front of the house door there is a stair. Every time Mr. John climbs the stairs, he can ONLY climb 1 or 2 steps at time.

given the amount of step of the stairs (max 30) make a program that output how many combinations, and the detailed combinations available.

Example:

Input Total steps of the stairs: 1 
  
  Program output: 
  Combinations: 1
  combination nº 1: 1

Input Total steps of the stairs: 2
   
   Program output: 
   Combinations: 2
   combination nº 1: 1-1
   combination nº 2: 2

Input Total steps of the stairs: 3
   
   Program output: 
   Combinations: 3
   combination nº 1: 1-1-1
   combination nº 2: 1-2
   combination nº 3: 2-1

Input Total steps of the stairs: 4
   
   Program output: 
   Combinations: 5
  combination nº 1: 1-1-1-1
  combination nº 2: 2-1-1
  combination nº 3: 2-2
  combination nº 4: 1-1-2
  combination nº 5: 1-2-1

Note: the order of the combinations is not important. the program can read the number of steps from a inputbox, file, etc..

I wont post more information. I want to see how people think about this.

The first to make an example will win a free beer at my house. (trip not included)

Hint. you dont need a lot of lines to make it.

Edited May 25, 2008 by Linux

[martin]

I had to solve this problem in a programing content, a few years ago, and I never found the same problem on internet.

We had 4 hours to solve 2 problems like this.

Problem:

Mr. John has a house. In front of the house door there is a stair. Every time Mr. John climbs the stairs, he can ONLY climb 1 or 2 steps at time.

given the amount of step of the stairs (max 30) make a program that output how many combinations, and the detailed combinations available.

Example:

Input Total steps of the stairs: 1 
  
  Program output: 
  Combinations: 1
  combination nº 1: 1

Input Total steps of the stairs: 2
   
   Program output: 
   Combinations: 2
   combination nº 1: 1-1
   combination nº 2: 2

Input Total steps of the stairs: 3
   
   Program output: 
   Combinations: 3
   combination nº 1: 1-1-1
   combination nº 2: 1-2
   combination nº 3: 2-1

Input Total steps of the stairs: 4
   
   Program output: 
   Combinations: 5
  combination nº 1: 1-1-1-1
  combination nº 2: 2-1-1
  combination nº 3: 2-2
  combination nº 4: 1-1-2
  combination nº 5: 1-2-1

Note: the order of the combinations is not important. the program can read the number of steps from a inputbox, file, etc..

I wont post more information. I want to see how people think about this.

The first to make an example will win a free beer at my house. (trip not included)

Hint. you dont need a lot of lines to make it.

Here's my attempt

While 1
    $steps = Number(InputBox("How many steps", "(30 max)"))
    If @error Or $steps = 0 Then ExitLoop
    $n = 0;
    
    While $n < 2 ^ $steps - 1
        $tot = 0
        $j = $n
        $res = ''
        For $k = 1 To $steps
            $count = $k
            $bit = BitAND($j, 1) + 1

            $res &= Number($bit) & ', '
            $tot += $bit
            If $tot >= $steps Then ExitLoop
            $j = BitShift($j, 1)
        Next

        If $tot = $steps Then
            ConsoleWrite($steps & " steps:" & StringLeft($res, StringLen($res) - 2) & @CRLF)
            If $bit = 2 And $count = $steps - 1 Then ExitLoop
        EndIf

        $n += 1
        
    WEnd
WEnd

Edited May 25, 2008 by martin

[qsek]

hehe damn too slow, i should finished this before my dinner . Heres my solution:

$numstairs = 4
ConsoleWrite("Input Total steps of the stairs:"&$numstairs& @CRLF)
ConsoleWrite("Program output:"& @CRLF)

Dim $rec = 0, $String[100], $nums[101], $numsteps = 0

EvalSteps($numstairs)
ConsoleWrite("Combinations: " &$numsteps& @CRLF)

Exit


func EvalSteps($tmpnum)
        $rec += 1 ; recursive Level
        for $i = 1 to 2
            if $tmpnum - $i > 0 then
                $nums[$rec] = $tmpnum
                $String[$rec] = $String[$rec-1] & $i&"-"
                $tmpnum -= $i
                EvalSteps($tmpnum)
                $tmpnum = $nums[$rec]
            Elseif $tmpnum - $i = 0 then
                $String[$rec] = $String[$rec-1] &$i
                ConsoleWrite($String[$rec]&@CRLF)
                $numsteps += 1
                ExitLoop
            endif
        next
        $rec -= 1
EndFunc

Thats a really nice task.

But i sense anyhow that there must be a much more simple method to solve this. You will post it later on, wont you?

Edited May 25, 2008 by qsek

[qsek]

@ martin: hmm if i enter 14 steps in your script, i get 2738 combinations.

On mine there are only 610 combinations. Which one is right?

[martin]

@ martin: hmm if i enter 14 steps in your script, i get 2738 combinations.

On mine there are only 610 combinations. Which one is right?

That sounds bad for my beer.

Oh dear, I'm producing duplicates. Looks like you get the beer!

[qsek]

Yes i figured out that too. If i search the whole list for one existing combination, i find sometimes two.

besides if my solution is right, i have some speed results for 30 Steps:

Input Total steps of the stairs:30
Program output:
Combinations: 1346269
>Exit code: 0   Time: 42.026

42 secs with this code:

ProcessSetPriority(@AutoItPID,4)
$numstairs = 30
ConsoleWrite("Input Total steps of the stairs:"&$numstairs& @CRLF)
ConsoleWrite("Program output:"& @CRLF)

Dim $rec = 0, $String[100], $nums[110], $numsteps = 0,$tick = @sec, $Lastnumsteps = 0

EvalSteps($numstairs)
ConsoleWrite("Combinations: " &$numsteps& @CRLF)

Exit

func EvalSteps($tmpnum)
        $rec += 1 ; recursive Level
        for $i = 1 to 2
            if $tmpnum - $i > 0 then
                $nums[$rec] = $tmpnum
                $String[$rec] = $String[$rec-1] & $i&"-"
                $tmpnum -= $i
                EvalSteps($tmpnum)
                $tmpnum = $nums[$rec]
            Elseif $tmpnum - $i = 0 then
                $String[$rec] = $String[$rec-1] &$i
                $numsteps += 1
;~              if $tick <> @sec then
;~                  ConsoleWrite($String[$rec]&" (processed: "&$numsteps&", per Second: "&$numsteps-$Lastnumsteps &")"&@CRLF)
;~                  $Lastnumsteps = $numsteps
;~                  $tick = @sec
;~              Endif
;~              if isInt($numsteps/1000) then $tick = @sec
                ExitLoop
            endif
        next
        $rec -= 1
EndFunc

[Linux]

Good job!

this is what i came with

ProcessSetPriority(@AutoItPID, 2)

Global $numstairs = 20

Global $total_combinations = 0, $total_Func_Used = 0;,$tick = @sec
ConsoleWrite("Total steps of the stairs:" & $numstairs & @CRLF)
ConsoleWrite("Program output:" & @CRLF)
Climb("", 0)
Func Climb($String, $Step)
    $total_Func_Used += 1
    If $Step + 1 = $numstairs Then
        ConsoleWrite($String & "1" & @CRLF)
        $total_combinations += 1
        Return
    ElseIf $Step + 2 = $numstairs Then
        ConsoleWrite($String & "2" & @CRLF)
        $total_combinations += 1
        Climb($String & "1-", $Step + 1)
        Return
    Else
        Climb($String & "1-", $Step + 1)
        Climb($String & "2-", $Step + 2)
    EndIf
    #cs
    if $tick <> @sec then
      ConsoleWrite(" (processed: "&$total_combinations&", per Second: "&$total_combinations-$Lastnumsteps &")"&@CRLF)
      $Lastnumsteps = $total_combinations
      $tick = @sec
     Endif
    if isInt($numsteps/1000) then $tick = @sec
    #ce
EndFunc   ;==>Climb
ConsoleWrite("total combinations = " & $total_combinations & @CRLF & "Total Funcs Used : " & $total_Func_Used & @CRLF)

This was made in 20 minutes. the official version may be diferent, since i dont remember anymore the source.

The best way to solve is problem is with recusive language, that is a function, that calls itself inside it. this create a func, inside a func, inside a func. Its hard to imagine to someone with low imagination. Is like pointing the webcam to the monitor, and see a monitor, inside a monitor, etc...

There are other examples, but this is a beauty because is so simple

14 steps:

total combinations = 610

Total Funcs Used : 986

+>03:06:55 AutoIT3.exe ended.rc:0

>Exit code: 0 Time: 1.161

20 Steps:

total combinations = 10946

Total Funcs Used : 17710

+>03:07:47 AutoIT3.exe ended.rc:0

>Exit code: 0 Time: 9.724

Edited May 26, 2008 by Linux

[qsek]

Wow, you even improved this. Just comment out the ConsoleWrites in the climb Func. They slow this out very much.

I get ~22 secs for 30 Steps at your script

I think its because you solved the problem of "reminding" the previous step variable when going back in recursion, cause normally the $Step varaible (and the $String too) are being overwritten everytime you call the Climb function (well, at least i expierienced that behaviour). I use an Array to store this data.

But im still not sure how you do this. It looks like it uses a "local" $Step variable in every recursion level of the function.

Hey but tomorrow i will post another interesting Task, very similar like this, i will link it in this topic.

A friend (computer science student) came out with that as i told him your task.

Edited May 26, 2008 by qsek

[Linux]

yes, the speed gain is because i use 2 IF in every recursion, and you use 2x 2 IF = 4 in every recursion. this is what takes more time. the less IF you put, the faster will get.

I dont store data, i just output them.

i look forward to see your problem.

Edit: Yes, when you create a new recursion, imagine that 2 new Variables are created. Ex: $String_34512 $Step_34512

this way you dont store it. you recieve, make the ifs, and then send the data as parameter to the next recursion. simple

but I notice you made a lot of improvements. Me to. before i got to this code, I had to make several codes, and add debug lines to know if other methods could be faster/shorter

Edited May 26, 2008 by Linux

[qsek]

here is my task: The Bar and the ants

[qsek]

nice one hubertus. Didnt thought, that the mathematical solution would be so simple.

Edited May 27, 2008 by qsek

[SadBunny]

Wow, you even improved this. Just comment out the ConsoleWrites in the climb Func. They slow this out very much.

I get ~22 secs for 30 Steps at your script

Just to try out my brand new (well, new... I bought it 6 days ago which probably makes it obsolete junk by now ) shiny AMD phenom quadcore set, I tried Linux' script too. With consolewrites it took just under 8 seconds, without it it's 0.882 sec...

[qsek]

@SadBunny: You probably did it with 20 Steps. Set $numstairs to 30 and it will take much longer

Besides you wont get any faster results, cause the autoit process only uses one Core. I have a AMD Opteron Dual Core.

Edited May 27, 2008 by qsek

[SadBunny]

Yes I did - I just copypasted the code without looking into it

With 30, it takes about 15 seconds.

Maybe if you change the au3 code to fully utilize the power of my GPU too it works faster

/edit: see if it also takes 20 minutes to code a 3d simulation that shows directdraw textures of the actual steps being taken, and Lara Croft running up and down those stairs. With the 'nude' patch ofcourse... *drool* old times, old times

Edited May 27, 2008 by SadBunny

[Zepx]

Very useful, thanks for the infos.

[Linux]

VERY IMPRESSIVE! I dindnt have time to check it slowly, but this is a very fast script! GOOD JOB! I'm