Sign in to follow this  
Followers 0
Linux

The Steps Problem

16 posts in this topic

#1 ·  Posted (edited)

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 by Linux

You can help! Donate to AutoIt! or, visit ClimatePREDICTION.netMy posts:Travian Bot Example (100+ servers) BETAHow to Host you code/app for free! (unlimited team number) (Public or Private)"Sir, we're surrounded!" "Excellent. We can attack in any direction!"

Share this post


Link to post
Share on other sites

#2 ·  Posted (edited)

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 by martin

Serial port communications UDF Includes functions for binary transmission and reception.printing UDF Useful for graphs, forms, labels, reports etc.Add User Call Tips to SciTE for functions in UDFs not included with AutoIt and for your own scripts.Functions with parameters in OnEvent mode and for Hot Keys One function replaces GuiSetOnEvent, GuiCtrlSetOnEvent and HotKeySet.UDF IsConnected2 for notification of status of connected state of many urls or IPs, without slowing the script.

Share this post


Link to post
Share on other sites

#3 ·  Posted (edited)

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 by qsek

Teamspeak 3 User Viewer - Quick and functional TS3 Query script, which shows online users.Cached Screenshot Deleter - Deletes older Fraps Screenshots if they exceed a specified limit.Unresolved Topics:Intercept and modify dragdrop text behaviour in scite

Share this post


Link to post
Share on other sites

@ 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?


Teamspeak 3 User Viewer - Quick and functional TS3 Query script, which shows online users.Cached Screenshot Deleter - Deletes older Fraps Screenshots if they exceed a specified limit.Unresolved Topics:Intercept and modify dragdrop text behaviour in scite

Share this post


Link to post
Share on other sites

@ 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!


Serial port communications UDF Includes functions for binary transmission and reception.printing UDF Useful for graphs, forms, labels, reports etc.Add User Call Tips to SciTE for functions in UDFs not included with AutoIt and for your own scripts.Functions with parameters in OnEvent mode and for Hot Keys One function replaces GuiSetOnEvent, GuiCtrlSetOnEvent and HotKeySet.UDF IsConnected2 for notification of status of connected state of many urls or IPs, without slowing the script.

Share this post


Link to post
Share on other sites

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

Teamspeak 3 User Viewer - Quick and functional TS3 Query script, which shows online users.Cached Screenshot Deleter - Deletes older Fraps Screenshots if they exceed a specified limit.Unresolved Topics:Intercept and modify dragdrop text behaviour in scite

Share this post


Link to post
Share on other sites

#7 ·  Posted (edited)

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 by Linux

You can help! Donate to AutoIt! or, visit ClimatePREDICTION.netMy posts:Travian Bot Example (100+ servers) BETAHow to Host you code/app for free! (unlimited team number) (Public or Private)"Sir, we're surrounded!" "Excellent. We can attack in any direction!"

Share this post


Link to post
Share on other sites

#8 ·  Posted (edited)

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 by qsek

Teamspeak 3 User Viewer - Quick and functional TS3 Query script, which shows online users.Cached Screenshot Deleter - Deletes older Fraps Screenshots if they exceed a specified limit.Unresolved Topics:Intercept and modify dragdrop text behaviour in scite

Share this post


Link to post
Share on other sites

#9 ·  Posted (edited)

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 by Linux

You can help! Donate to AutoIt! or, visit ClimatePREDICTION.netMy posts:Travian Bot Example (100+ servers) BETAHow to Host you code/app for free! (unlimited team number) (Public or Private)"Sir, we're surrounded!" "Excellent. We can attack in any direction!"

Share this post


Link to post
Share on other sites

#11 ·  Posted (edited)

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

Edited by qsek

Teamspeak 3 User Viewer - Quick and functional TS3 Query script, which shows online users.Cached Screenshot Deleter - Deletes older Fraps Screenshots if they exceed a specified limit.Unresolved Topics:Intercept and modify dragdrop text behaviour in scite

Share this post


Link to post
Share on other sites

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... :)


Roses are FF0000, violets are 0000FF... All my base are belong to you.

Share this post


Link to post
Share on other sites

#13 ·  Posted (edited)

@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 by qsek

Teamspeak 3 User Viewer - Quick and functional TS3 Query script, which shows online users.Cached Screenshot Deleter - Deletes older Fraps Screenshots if they exceed a specified limit.Unresolved Topics:Intercept and modify dragdrop text behaviour in scite

Share this post


Link to post
Share on other sites

#14 ·  Posted (edited)

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 by SadBunny

Roses are FF0000, violets are 0000FF... All my base are belong to you.

Share this post


Link to post
Share on other sites

Very useful, thanks for the infos.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0