ProjectEuler.cmd/Problem14.cmd at master · Oatworm/ProjectEuler.cmd · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
@ECHO OFF
SETLOCAL EnableDelayedExpansion

:: Project Euler Problem 14
:: The following sequence is defined for the set of positive integers:
:: n -> n/2 if n is even
:: n -> 3n+1 if n is odd
:: Which starting number, under one million, produces the longest chain?

:: NOTE: This script overwhelms CMD's recursion stack, which supports up to
:: 455 recursions (we need at 525). To get around this, go here:
:: http://people.sju.edu/~ggrevera/cscCV/stack/
:: Download editbin, copy the CMD binary from %systemroot%\system32 to the
:: extracted folder, modify the binary, then re-run the script.

SET _MaxCount=0
SET _MaxChain=0
SET _Next1=1
SET _Count1=0

FOR /L %%G IN (500000,1,999999) DO (
	CALL :CreateChain %%G
	ECHO:%%G :: !_Count%%G!
	IF !_Count%%G! GTR !_MaxCount! (
		SET _MaxCount=!_Count%%G!
		SET _MaxChain=%%G
	)
)

ECHO:
ECHO:%_MaxChain% has the longest chain with !_MaxCount! steps.
GOTO :EOF

:CreateChain
SET _Step=%1
IF %_Step% EQU 1 GOTO ChainDone

IF NOT DEFINED _Next%_Step% (
	IF NOT "%_Step:~8,1%"=="" (
		SET _IsBig=1
	) ELSE SET _IsBig=0

	IF !_IsBig! EQU 0 (
		SET /A _IsOdd=_Step %% 2
		IF !_IsOdd! EQU 1 (
			SET /A _Next%_Step% = _Step*3
			SET /A _Next%_Step% += 1
			CALL :CreateChain !_Next%_Step%!
		) ELSE (
			SET /A _Next%_Step% = _Step/2
			CALL :CreateChain !_Next%_Step%!
		)
	) ELSE (
		SET _IsOdd=%_Step:~-1%
		SET /A _IsOdd=_IsOdd %% 2
		IF !_IsOdd! EQU 1 (
			CALL :BigMul %_Step% 3 _Next%_Step%
			CALL :BigAdd1 !_Next%_Step%! _Next%_Step%
			CALL :CreateChain !_Next%_Step%!
		) ELSE (
			REM Multiplying by 5, then taking the 0 off the end
			REM Same as multiplying by 0.5 (or dividing by 2)
			CALL :BigMul %_Step% 5 _Next%_Step%
			SET _tmp=!_Next%_Step%!
			SET _tmp=!_tmp:~0,-1!
			SET _Next%_Step%=!_tmp!
			CALL :CreateChain !_Next%_Step%!
		)
	)

	IF DEFINED _Count!_Next%_Step%! (
		SET /A _Count%_Step%=_Count!_Next%_Step%!+1
	)
)
:ChainDone
GOTO :EOF

:BigMul
SETLOCAL EnableDelayedExpansion
:: Heavily simplified version of the integer-only algorithm used here:
:: http://www.robvanderwoude.com/files/multiply_3rdparty_bat.txt
:: Taking advantage of the fact we're only multiplying by 3 or 5.
	SET _BigNum=%1
	SET _MulBy=%2
	SET _Carry=

	FOR %%G IN (0,1,2,3,4,5,6,7,8,9) DO (
		SET _BigNum=!_BigNum:%%G=%%G !
	)

	FOR %%G IN (!_BigNum!) DO SET /A _BigCnt+=1 & SET _Big_!_BigCnt!=%%G
	FOR /L %%G IN (%_BigCnt%,-1,1) DO (
		SET /A _tmp=!_Big_%%G! * %_MulBy% !_Plus! !_Carry!
		SET _Carry=
		SET _Plus=
		IF !_tmp! GTR 9 SET _Carry=!_tmp:~0,1!& SET _tmp=!_tmp:~-1!& SET _Plus=+
		SET _MulResult=!_tmp!!_MulResult!
	)

	IF DEFINED _Carry SET _MulResult=!_Carry!!_MulResult!

ENDLOCAL & SET %3=%_MulResult%
GOTO :EOF

:BigAdd1
SETLOCAL EnableDelayedExpansion
:: Just need to add 1 to a really big number, so let's keep this simple...
	SET _BigNum=%1
	IF DEFINED _BigNum SET _Digit=%_BigNum:~-1,1%
	SET /A _Digit+=1
	IF %_Digit% EQU 10 (
		SET _BigNum=%_BigNum:~0,-1%
		SET _AddResult=!_AddResult!0
		IF DEFINED _BigNum (
			CALL :BigAdd1 !_BigNum! _AddResult
		) ELSE SET _AddResult=1!_AddResult!
	) ELSE (
		SET _AddResult=%_BigNum:~0,-1%%_Digit%!_AddResult!
	)
ENDLOCAL & SET %2=%_AddResult%
GOTO :EOF