Re: Rosetta Code
Posted: 28 Dec 2014, 02:37
thanks @kon
done
done
I'm pretty sure you mean bored.jNizM wrote:Reminder for some boring guys
That is almost exactly what my solution was, I just got distracted at work and forgot to update the page :/
Code: Select all
Found := FindOneToX(100), FoundList := ""
Loop, 10
FoundList .= "First " A_Index " found at " Found[A_Index] "`n"
MsgBox, 64, Stern-Brocot Sequence
, % "First 15: " FirstX(15) "`n"
. FoundList
. "First 100 found at " Found[100] "`n"
. "GCDs of all two consecutive members are " (GCDsUpToXAreOne(1000) ? "" : "not ") "one."
return
class SternBrocot
{
__New()
{
this[1] := 1
this[2] := 1
this.Consider := 2
}
InsertPair()
{
n := this.Consider
this.Push(this[n] + this[n - 1], this[n])
this.Consider++
}
}
; Show the first fifteen members of the sequence. (This should be: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3,
; 5, 2, 5, 3, 4)
FirstX(x)
{
SB := new SternBrocot()
while SB.MaxIndex() < x
SB.InsertPair()
Loop, % x
Out .= SB[A_Index] ", "
return RTrim(Out, " ,")
}
; Show the (1-based) index of where the numbers 1-to-10 first appears in the sequence.
; Show the (1-based) index of where the number 100 first appears in the sequence.
FindOneToX(x)
{
SB := new SternBrocot(), xRequired := x, Found := []
while xRequired > 0 ; While the count of numbers yet to be found is > 0.
{
Loop, 2 ; Consider the second last member and then the last member.
{
n := SB[i := SB.MaxIndex() - 2 + A_Index]
; If number (n) has not been found yet, and it is less than the maximum number to
; find (x), record the index (i) and decrement the count of numbers yet to be found.
if (Found[n] = "" && n <= x)
Found[n] := i, xRequired--
}
SB.InsertPair() ; Insert the two members that will be checked next.
}
return Found
}
; Check that the greatest common divisor of all the two consecutive members of the series up to
; the 1000th member, is always one.
GCDsUpToXAreOne(x)
{
SB := new SternBrocot()
while SB.MaxIndex() < x
SB.InsertPair()
Loop, % x - 1
if GCD(SB[A_Index], SB[A_Index + 1]) > 1
return 0
return 1
}
GCD(a, b) {
while b
b := Mod(a | 0x0, a := b)
return a
}
Code: Select all
Str := "For the Sequence with Base[ " . SternBrocot[1] . ", " . SternBrocot[2] . " ]:`n"
Str .= "First ten Numbers in the Sequence:`n[ "
Loop 9
Str .= SternBrocot[A_Index] . ", "
Str .= SternBrocot[10] . "]`n`n"
Str .= "100th Number in the Sequence:`n" . SternBrocot[100] . "`n`n"
If (firstGCD := SternBrocot.gcdBelow(num := 1000))
Str .= "The first consecutive Entries whose Greatest Common Divisor is not 1 starts at:`n" . firstGCD
Else
Str .= "There are no consecutive Entries in the Sequence whose GCD is not 1 in sequence below Entry:`n" . num
Msgbox % Str
class SternBrocot
{
static Init := SternBrocot.__New(1,1)
__New(num1,num2)
{
This.base := {__Get:SternBrocot.Get}
This.Remove(SternBrocot.MinIndex(),SternBrocot.MaxIndex())
This.Push(num1)
This.Push(num2)
}
Get(Num)
{
c := Ceil(This.MaxIndex()/2)
a := Ceil(Num/2-c)
Loop % a
This.Push(This[c++]+b:=This[c],b)
return This[Num]
}
gcdBelow(Num)
{
If (This.MaxIndex()<Num+1)
This[Num+1]
while ((A_Index<=Num)&&(gcd(This[A_Index],This[A_Index+1])=1))
a:=A_Index
return (a=Num?0:a+1)
}
}
gcd(a,b)
{
while b
b := Mod(a |0x0, a := b)
return a?1:a
}
I agree. I like the changes you made to take advantage of __Get().nnnik wrote:I think that is among the things where AHK can really shine:
Code: Select all
; Unit Tests====================================================================================
UT := []
UT[1] := gcd(7, 14) = 7 ? "Pass" : "Fail"
UT[2] := gcd(7, 15) = 1 ? "Pass" : "Fail"
UT[3] := SternBrocot[11] = 5 ? "Pass" : "Fail"
UT[4] := SternBrocot[1000] = 11 ? "Pass" : "Fail"
UT[5] := SternBrocot.gcdBelow(1000) = 0 ? "Pass" : "Fail"
; 999 and 1000 should be the last pair checked by gcdBelow
; (Not very important, but I *think* this is how the task is written.)
UT[6] := SternBrocot.HasKey(1001) = 0 ? "Pass" : "Fail"
; Enter an incorrect number at SternBrocot[1001] to check if gcdBelow() works.
SternBrocot[1001]
SternBrocot[1001] := 22 ; gcd(11, 22) = 11
UT[7] := SternBrocot.gcdBelow(1001) = 1000 ? "Pass" : "Fail"
SternBrocot.__New(1, 1)
UT[8] := SternBrocot.Find(1, 1) = "First 1 found at 1.`n" ? "Pass" : "Fail"
UT[9] := SternBrocot.Find(2, 3) = "First 2 found at 3.`nFirst 3 found at 5.`n" ? "Pass" : "Fail"
UT[10] := SternBrocot.Find(3, 0) = "First 3 found at 5.`n" ? "Pass" : "Fail"
;===============================================================================================
UTList := ""
for i, Val in UT
UTlist .= "Unit test " i ": " Val "`n"
MsgBox, 64, Unit Tests, % UTList
;===============================================================================================
Title := "Stern-Brocot sequence with base[ " . SternBrocot[1] . ", " . SternBrocot[2] " ]"
Str := "First fifteen numbers in the sequence:`n[ "
Loop 14
Str .= SternBrocot[A_Index] . ", "
Str .= SternBrocot[15] . "]`n`n"
Str .= SternBrocot.Find(1, 10)
Str .= SternBrocot.Find(100, 0) "`n"
If (firstGCD := SternBrocot.gcdBelow(num := 1000))
Str .= "The first consecutive entries whose greatest common divisor is not 1 starts at:`n" . firstGCD
Else
Str .= "GCDs of all consecutive entries in the sequence are 1. Checked up to entry:`n" num
Msgbox, 64, % Title, % Str
return
class SternBrocot
{
static Init := SternBrocot.__New(1,1)
__New(num1,num2)
{
This.base := {__Get:SternBrocot.Get}
This.Remove(SternBrocot.MinIndex(),SternBrocot.MaxIndex())
This.Push(num1)
This.Push(num2)
}
Get(Num)
{
c := Ceil(This.MaxIndex()/2)
a := Ceil(Num/2-c)
Loop % a
This.Push(This[c++]+b:=This[c],b)
return This[Num]
}
gcdBelow(Num)
{
This[Num]
while ((A_Index<Num)&&(gcd(This[A_Index],This[A_Index+1])=1))
a:=A_Index
return a=Num-1?0:a+1
}
Find(From, To)
{
Loop
{
while This[n := A_Index] != From
continue
s .= "First " From " found at " n ".`n"
} until From++ >= To
return s
}
}
gcd(a,b)
{
while b
b := Mod(a | 0x0, a := b)
return a
}
Code: Select all
CoordMode, mouse, client
t := new honeyComb()
return
GuiClose:
esc::
ExitApp
class Honeycomb{
__new(hxn_Width=80, hxn_Height=60, hxn_Columns=5, hxn_Rows=4){
this.char_init()
this.hxn_init(hxn_Width, hxn_Height, hxn_Columns, hxn_Rows)
this.wndw_init()
this.hFont := this.createFont(round(hxn_Height*.6), round(hxn_Width*.35))
this.selectObject(this.wndw.hDC, this.hFont) ;set the font color to red
DllCall("SetTextColor", "Ptr", this.wndw.hDC, "UInt", 0x0000FF)
for key, val in this.hxn.array ;draw all hexagons
this.hxn_draw(key)
DllCall("SetTextColor", "Ptr", this.wndw.hDC, "UInt", 0x000000) ;set the font color to black
}
char_init(){ ;sets up the char array - used to assign each hxn a random character (letter)
this.char := {}
this.char.selected :=
this.char.array := []
loop 26
this.char.array.push(chr(a_index + 64))
}
hxn_init(hxn_Width, hxn_Height, hxn_Columns, hxn_Rows){ ;sets up the array of hexagons
this.hxn := {} ,this.hxn.array := {}
this.hxn.width := hxn_Width ,this.hxn.height := hxn_Height
this.hxn.rowCount := hxn_Rows ,this.hxn.colCount := hxn_Columns
w := this.hxn.width ,h := this.hxn.height
oX := 10 ,oY := 10
pts := {} ,orig_Y := 10
pts.x := [] ,pts.y := []
pts.x.push(round(w * .25)) ,pts.y.push(0)
pts.x.push(round(w * .75)) ,pts.y.push(0)
pts.x.push(w) ,pts.y.push(round(h * .5))
pts.x.push(round(w *.75)) ,pts.y.push(h)
pts.x.push(round(w *.25)) ,pts.y.push(h)
pts.x.push(0) ,pts.y.push(round(h *.5))
FuncObj := ObjBindMethod(this, "hkey_handler")
loop % this.hxn.colCount
{
if !(a_index & 1)
oY += h/2
loop % this.hxn.rowCount
{
random, charIndex, 1, % this.char.array.maxIndex() ;get rnd char for the new hxn
char := this.char.array[charIndex]
this.hxn.array[char] := {} ;create new hxn object, add it tohxn.array, w/ the key being its rnd char
this.hxn.array[char].char := char
this.hxn.array[char].isFresh := 1
pos := 0
varSetCapacity(hxnPoints, 48, 0) ;build the array of pts structures to be used in the createpolygonrgn call
loop % pts.x.maxIndex()
{
numPut(pts.x[a_index] + oX, hxnPoints, pos + 0, "int")
numPut(pts.y[a_Index] + oY, hxnPoints, pos + 4, "int")
pos += 8
}
this.hxn.array[char].rgn := DllCall("CreatePolygonRgn", "Ptr", &hxnPoints, "Int", 6, "Int", 1)
Hotkey, % char,% FuncObj
this.char.array.Remove(charIndex)
oY += h
}
oY := orig_Y, oX += w * .75
}
FuncObj := ObjBindMethod(this, "mouse_handler")
Hotkey, ~LButton, % FuncObj
}
hxn_draw(key,fillcolor=0x00FFFF){
brush := this.createBrush(fillColor) ;fill the hexagon
this.selectObject(this.wndw.hDC, brush)
DllCall("FillRgn", "Ptr", this.wndw.hDC, "Ptr", this.hxn.array[key].rgn, "Ptr", brush)
this.deleteObject(brush)
brush := this.createBrush(0x000000) ;frame the hexagon
this.selectObject(this.wndw.hDC, brush)
DllCall("FrameRgn", "Ptr", this.wndw.hDC, "Ptr", this.hxn.array[key].rgn, "Ptr", brush, "Int", 1, "Int", 1)
this.deleteObject(brush)
DllCall("SetBkColor", "Ptr", this.wndw.hDC, "UInt", fillColor) ;draw the hexagons char
this.hxn_getCharPos(key, cx, cy)
DllCall("TextOut", "Ptr", this.wndw.hDC, "Int", cX, "Int", cY, "Str", this.hxn.array[key].char, "Int", 1)
}
hxn_getCharPos(key, ByRef x, ByRef y){
;get the char width
VarSetCapacity(tSize, 8, 0)
DllCall("GetTextExtentPoint32", "Ptr", this.wndw.hDC, "Str", key, "Int", StrLen(key), "Ptr", &tSize)
tWidth := NumGet(tSize, 0, "Int")
tHeight := NumGet(tSize, 4, "Int")
;get the bounding box of the hxn rgn
VarSetCapacity(rect, 16, 0)
DllCall("GetRgnBox", "Ptr", this.hxn.array[key].rgn, "Ptr", &rect)
;calc the position of the char within the hxn
x := (this.hxn.width / 2) - (tWidth / 2) + NumGet(rect, 0, "int")
y := (this.hxn.height / 2) - (tHeight / 2) + NumGet(rect, 4, "int")
}
hxn_getRgn(x,y){
for key, value in this.hxn.array
{
if (DllCall("PtInRegion", "Ptr", this.hxn.array[key].rgn, "Int", x, "Int", y)) && this.hxn.array[key].isFresh
{
this.hxn_draw(key, 0xFF00FF)
Hotkey, %key%,, off
this.hxn.array[key].isFresh := 0
this.char.selected .= key "," ;if mouse is used to select a hgn, add it to the list
break
}
}
}
hkey_handler(){
this.hxn_draw(A_ThisHotkey, 0xFF00FF) ;fill the hexagon with the 2nd color..
Hotkey, % A_ThisHotkey, off ;remove this hotkey now that we've already 'used' this hexagon
this.hxn.array[A_ThisHotkey].isFresh := 0
this.char.selected .= A_ThisHotkey "," ;if key is used to select hgn, add it to the list
this.game_getStatus()
}
mouse_handler(){
MouseGetPos, mx, my ;gets the current mouse postion
this.hxn_getRgn(mx,my) ;checks if mouse click was inside a hex rgn/if so, draw it
this.game_getStatus() ;checks if game is over
}
game_getStatus(){ ;checks if game is over
for key, val in this.hxn.array ;if game is over, display list of selected chars
if this.hxn.array[key].isfresh ; and play again dlg box.
return
selected := this.char.selected
selected := SubStr(selected,1, StrLen(selected)-1)
MsgBox, 0x4, Game Over, % "Order of selected hexagons: " selected "`nPlay again?"
IfMsgBox No
ExitApp
Reload
}
wndw_init(){ ;sets up and displays the window
this.wndw := {}
this.wndw.width := round(this.hxn.width * (this.hxn.colCount - 1)) + 20
this.wndw.height := round(this.hxn.height * (this.hxn.rowCount + .5)) + 20
gui, show, % "w" this.wndw.width " h" this.wndw.height, Honeycombs
this.wndw.hWnd := WinExist("A")
this.wndw.hDC := DllCall("GetDC", "Ptr", this.wndw.hWnd)
}
createBrush(color){
return DllCall("CreateSolidBrush", "UInt", color)
}
createFont(height,width,weight=800){
return DllCall("CreateFont"
,"Int", height
,"Int", width
,"Int", 0
,"Int", 0
,"Int", weight
,"UInt", 0
,"UInt", 0
,"UInt", 0
,"UInt", 0
,"UInt", 0
,"UInt", 0
,"UInt", 0
,"UInt", 0
,"Str", 0)
}
selectObject(dc, obj){ ;internal method
return DllCall("SelectObject", "Ptr", dc, "Ptr", obj)
}
deleteObject(obj){ ;used for gdi cleanup
return DllCall("DeleteObject", "Ptr", obj)
}
__Delete(){
DllCall("ReleaseDC", "Ptr", this.wndw.hWnd, "Ptr", this.wndw.hDC) ;release the window DC
this.deleteObject(this.hFont) ;delete the font
for key, val in this.hxn.array ;delete all of the hxn regions
this.deleteObject(this.hxn.array[key].rgn)
}
}
Code: Select all
;returns divisors for 1 .. n
divisores(num)
{
serie := ""
loop % num
if !mod(num,a_index)
serie .= a_index ","
return serie
}
;return quantity of common factors
gcd(serieA,serieB)
{
emComum := 0
loop,parse,serieA,csv
if A_LoopField in %serieB%
emComum += 1
return emComum
}
phi(num)
{
phicount := 0
numA := divisores(num)
loop % num
{
numB := divisores(A_Index)
fim := gcd(numA,numB)
if (fim = 1)
phicount += 1
}
return phicount
}
; returns 0 or 1
isAchilles(n) {
pw := isPowerfull(n)
if !pw
return 0
loop, parse, pw, `n
ttt := A_Index
if (ttt = 2)
return 0
if mod(n,(ceil(sqrt(n))**2)) ; ---------------------------
;if mod(n,(foo**3)) ; HERE IS THE PROBLEM. HOW TO KNOW IF
return 1 ; A NUMBER HAS A INTEGER CUBIC ROOT? EX: 216 and 1000
return 0
}
; returns 0 or 1
isPowerfull(n)
{
ttt := factor(n)
sort,ttt,N U D`n
loop,parse,ttt,`n
if mod(n,A_LoopField**2)
return false
return ttt
}
; NOT USING UNTIL NOW BUT POSSIBLY WILL
; factoring integers from https://rosettacode.org/wiki/Prime_decomposition#AutoHotkey
; return each factor by line Ex: 100 = 2 `n 2 `n 5 `n 5
factor(n)
{
if (n = 1)
return
f = 2
while (f <= n) ;Floor(sqrt(n)))
{
if (Mod(n, f) = 0)
{
next := factor(n / f)
return, % f "`n" next
}
f++
}
}
; NOT USING UNTIL NOW BUT POSSIBLY WILL
; list(0) / count(1) of prime numbers
; ex: msgbox % PrimesLiCo(100,1) - return a list
; MsgBox % PrimesLiCo(100,0) - return a number
PrimesLiCo(max,listar:=0) {
primos := ""
countPrimes := -1
loop %max%
{
numero := A_Index
apoio := maxDivisor := Floor(Sqrt(numero))
loop %maxDivisor%
{
if (apoio=1)
{
if listar
primos := primos . numero ","
else
countPrimes += 1
break
}
if mod(numero,apoio)
apoio -= 1
else
break
}
}
if listar
return primos
else
return countPrimes
}
out := "First 50 Achilles:`n"
loop
{
;if isPowerfull(A_Index)
if isAchilles(A_Index)
{
out .= A_Index ", "
Acount += 1
if (Acount = 50)
break
}
}
MsgBox % out
ExitApp
^q::
ExitApp
jNizM wrote: ↑19 May 2016, 07:22Reminder for some bored* guys
- Tasks not implemented in AutoHotkey
- AutoHotkey examples needing attention