10 replies to this topic

[smorgasboard]

Found an interesting way to learn coding, that is by solving problems at

http://projecteuler.net/

 

Solved till 13 by getting help from #ahk IRC and made a repertoire of the same will surely help in the long run.

 

Reached

http://projecteuler.net/problem=14

 

made the code for the same, i.e.

#NoEnv  ; Recommended for performance and compatibility with future AutoHotkey releases.
; #Warn  ; Enable warnings to assist with detecting common errors.
SendMode Input  ; Recommended for new scripts due to its superior speed and reliability.
SetWorkingDir %A_ScriptDir%  ; Ensures a consistent starting directory.
compare := 0
count := 0
number := 2
Loop, 1000000
{
K := number
						Loop,
						{
									if ( K = 1 )
									{
										count := Count + 1
									sofar .= ans k "        " count "`n"
									;MsgBox, %sofar% 
									compare := compare > count ? compare : count
									MsgBox, %sofar%And the highest so far as per the requirement of the problem is %compare%
									Clipboard := compare
									TrayTip, %number%, %compare%
									
									count := 0
									break
									}
											Loop
											{
														if ( K = 1 )
														{
														;MsgBox reached %ans% finally
														break
														}	
											rem := mod(k, 2) 
											;MsgBox	%k% leaves a remainder  %rem%	
	
														if ( rem = 0 )
														{
														ans .= k "->"
														n := k//2
														;MsgBox %k% results in %n%
														K := N
														count := count + 1
														}
														else
														{
														ans .= k "->"
														n := 3*k + 1
														;MsgBox %k% results %n%
														K := N
														count := count + 1
														}
											}
							}
ans :=
number := number + 1
}

that runs fine but i think to loop  for 1000000 times will be something not elegant. so i think if the code could assign every number it's  value like 

 

eg. for 2 it is 2 ->1     2    ====> here if i could assign

 

2 for the number 2 &

1 for the number 1

 

for 3 it is 3->10->5->16->8->4->2->1     8     ====> here if i could assign

 

8 for the number 3,

7 for the number 10, ***

6 for the number 5,

5 for the number 16,

4 for the number 8,

3 for the number 4, **

2 for the number 2,

2 for the number 1,

 

So basically if the script could check for a number whether it's value is already cached somewhere then use that value and in case it's value is not assigned then generate it's value as per the current script. For example for 4, as the value of 4 has already been assigned ** 3 then use this value and move to 5, 5 also done which has the value 6, so move to 7, since 7 is not done it generates the value for 7 like 7->22->11->34->17->52->26->13->40->20->10 ( already generated so no need to move further just add 10 from ( 7->22->11->34->17->52->26->13->40->20 ) and add 7 from *** to get 17. so on forth.

 

 

In this manner there script can run through 1000000 times without hogging much resources. How to do that if possible? Thanks as usual in advance

 

 

 

[VxE]

Spoiler

/*
	Collatz sequences

	N -> N/2 (if N is even)
	N -> 3N + 1 (if N is odd)
*/

#NoEnv
SetBatchLines, -1
trials := 1000000 ; change this
maxlen := 0 ; but not this
results := [{sequence:"1",length:1}]
Loop % trials - 1
{
	N := K := A_Index + 1
	L := 1
	results[K] := {}
	results[K].sequence := N
	While K < N := N & 1 ? 3 * N + 1 : N >> 1
		L++, results[K].sequence .= "," N
	results[K].sequence .= "," results[N].sequence
	results[K].length := L + results[N].length
	if ( maxlen < results[K].length )
	{
		maxlen := results[K].length
		longest := results[K].sequence
	}
	if !mod( A_Index, 3577 )
		tooltip % Round( A_Index * 100.0 / trials, 2 ) "%"
}
tooltip
msgbox % longest

The number under 1 million that gives the longest sequence is 837799.

[smorgasboard]

@VXE

Jaw Dropping code always from you.  Wish i could decipher your code!

if i am able to discern it i  shall add comments for your approval.

thanks..

[MasterFocus]

As always VxE, clever ternary (using & and >>).

Related: http://rosettacode.o...ence#AutoHotkey

( I would link this thread but I have just discovered that over 30 pages from that topic are now missing!   )

[VxE]

If you prefer, you can swap (x&1) with Mod(X,2) and (x>>1) with (x//2). The speed won't change significantly.

@smorgasboard: the crux of my code is the memoization scheme. Since each sequence is being calculated in order, when a sequence's N value goes below its starting value, we know the rest of that sequence has already been calculated. So the code simply appends the previously calculated sequence, adds its length, and moves on to the next number.

[strobo]

@VxE
    Nice code and effective memoization scheme. Though, for this task the
    whole .sequence property is superfluous, i.e. an array
    sequ_starting_element_To_sequ_length would support all the relevant information
    and costs much less memory. To print the longest sequence at the
    end just calculate the desired sequence again.

[smorgasboard]

@VxE i commented the lines that i could not understand.

#NoEnv  ; Recommended for performance and compatibility with future AutoHotkey releases.
; #Warn  ; Enable warnings to assist with detecting common errors.
SendMode Input  ; Recommended for new scripts due to its superior speed and reliability.
SetWorkingDir %A_ScriptDir%  ; Ensures a consistent starting directory.
/*
	Collatz sequences

	N -> N/2 (if N is even)
	N -> 3N + 1 (if N is odd)
*/

#NoEnv
SetBatchLines, -1
time := A_now
trials := 1000000 ; change this
maxlen := 0 ; but not this
results := [{sequence:"1",length:1}] ; what does this line do?
Loop % trials - 1
{
	N := K := A_Index + 1
	L := 1
	results[K] := {} ; and this ?
	results[K].sequence := N ; and this?
	While K < N := Mod(N, 2) ? 3 * N + 1 : N // 2 ; it seems as if it runs the following line with the condition that While K is less than N where N is equal to 3n+1 OR n/2 depending upon n being odd or even respectively, right?
		L++, results[K].sequence .= "," N ; results[K].sequence ; same from above cannot discern.
	results[K].sequence .= "," results[N].sequence ; same as line 17..
	results[K].length := L + results[N].length ; almost same...
	if ( maxlen < results[K].length ) ; it seems as if %results[K].length% is some number?
	{
		maxlen := results[K].length
		longest := results[K].sequence
	}
	if !mod( A_Index, 3577 ) ; why specifically 3577?
		tooltip % Round( A_Index * 100.0 / trials, 2 ) "%"
}
tooltip
elapsed := A_now - time
msgbox %longest% in %elapsed%

mm...unable to understand the "[]" and "." stuff at all. Also googled memoization and it seems exactly what i asked. thanks again..

[just me]

What about this, is it a bit more clear?

 

Spoiler

/*
	Collatz sequences

	N -> N/2 (if N is even)
	N -> 3N + 1 (if N is odd)
*/
#NoEnv
SetBatchLines, -1
Trials := 1000000 ; change this, if you want
MaxLen := 0       ; but not this
; Results is an array of associative arrays containing the keys Sequence, Length, and Suffix
; Initialize the results array for the number 1
Results := [{Sequence: 1, Length: 1}]
Loop, % (Trials - 1)
{
   ; Initialize K & N
   N := K := A_Index + 1                                    
   ; Initialize the length
   L := 1                                                   
   ; Initialize the new sequence
   Sequence := K
   ; As long as the new value of n is not a member of the result array
   While !Results.HasKey(N := N & 1 ? 3 * N + 1 : N >> 1)
      ; increase the length and add N to the sequence
      L++, Sequence .= "," . N
   ; Store the new sequence in the array
   Results[K] := {Sequence: Sequence}
   ; N is a member of the result array, so add its length to the current length
   Results[K].Length := L + Results[N].Length
   ; and store N as suffix
   Results[K].Suffix := N
   ; If MaxLen is less than the current length
   If (MaxLen < Results[K].Length)
      ; store the current length in MaxLen and the current key in Longest
      MaxLen := Results[K].Length, Longest := K
   If !Mod(A_Index, 10000)
      ToolTip, % Round(A_Index * 100.0 / Trials, 2) . "%"
}
ToolTip
; Set N to the number stored in Longest
N := Longest
; Store the sequence of N in Result
Result := Results[N].Sequence
; As long as Results[N] has a key Suffix
While (N := Results[N].Suffix)
   ; Add the sequence of the suffix to th result
   Result .= "," . Results[N].Sequence
; Done!!!
Gui, Add, Edit, w800 h600 vEdit
GuiControl, , Edit, %Result%
Gui, Show, , %Longest% -> Length: %MaxLen%
Return
GuiClose:
ExitApp

[MasterFocus]

If you don't need the sequence, it's a bit faster:

(I have AHK 1.0 installed here, so I didn't use real arrays)

#NoEnv
SetBatchLines, -1
trials := 1000000 ; change this
maxlen := 0 ; but not this
L1 := 1
Loop % trials - 1
{
    N := K := A_Index + ( L := 1 )
    While ( K < N := N & 1 ? 3 * N + 1 : N >> 1 )
        L++
    L%K% := L + L%N%
    if ( maxlen < L%K% )
        maxlen := L%K%, longest := K
    if !mod( A_Index, 7000 )
        tooltip % Round( A_Index * 100.0 / trials, 2 ) "%"
}
tooltip
;listvars
msgbox % "Longest is " longest " with a " maxlen "-long sequence."

[guest3456]

longest tab spacing ever?

[GeekDude]

VxE: Your code is amazing! I'm not sure why I didn't write mine like that. Yours executes in around 6 seconds (with fluff stripped out), while mine does it in 10.

 

Edit: Excuse the lack of indentation, it seems the forum strips out tab characters.

Prob14()
{
Collatz := []
Loop, 999999
{
n := A_Index, Chain := 1
While (n != 1)
{
if Mod(n,2)
{
if (Collatz[n])
{
Chain += Collatz[n]
break
}
n := 3*n+1
}
else
n /= 2
Chain++
}
if (Mod(A_Index, 2))
Collatz[A_Index] := Chain
if (Chain > Largest)
Largest := Chain, Answer := A_Index
}
return Answer
}