Wednesday, November 13, 2013

Problem 64 - Tcl

Tcl is a weird little language. It's not all that bad once you get used to it, but things like how everything is actually a list of strings, and calculations need to be wrapped in an expr lead to some weird stuff. But, after plenty of difficulty, I managed to solve problem 64 using Tcl. Part of the added difficulty was my lack of prior exposure to continued fractions, which resulted in me having to derive the method entirely from the single given example, which caused me to state the method incorrectly more than once. Also, I messed up my strange method of storing a pair of numbers in a list a couple times (to check for repeats, I checked for repeats of what I call in the code m and b, by storing m * (10^(1 + the order of magnitude of b) + b in a list...its an effective method, despite any oddness. (and me forgetting the +1 at first, causing some false positives). The solution is a tad slow, taking about 3 seconds, but I feel like that is probably mostly Tcl's fault...as I said, everything is a list of strings apparently, which gives me no confidence in the speed of code written in the language.
proc nextTerm {N m b} {
    set d [expr {$N - ($b ** 2)}]
    set d [expr {int($d/ $m)}]
    set k [expr {ceil((2 * $b) / $d)}]
    set bp [expr {($k * $d) - $b}]
    if [expr {$bp ** 2 > $N}] {
        set k [expr {$k-1}]
        set bp [expr {($k * $d) - $b}]
    }
    return [list $d $bp]
}

proc mag {x} {
    if [expr {$x < 10}] {
        return 100
    } else {
        set b [expr {$x / 10}]
        set g [mag $b]
        return [expr {10 * $g}]
    }
}

set ans 0
for {set N 2} {$N <= 10000 } {incr N} {
    set a0 [expr {int(sqrt($N))}]
    if [expr {!($a0 * $a0 == $N)}] {
        set done -1
        set b $a0
        set m 1
        set coeffs {}
        while {$done == -1} {
            set data [nextTerm $N $m $b]
            set m    [lindex $data 0]
            set b    [lindex $data 1]
            set mg   [mag $b]
            set v    [expr {($m * $mg) + $b}]
            set done [lsearch $coeffs $v]
            if [expr {$done == -1 }] {
                lappend coeffs $v
            }
        }
        set l [llength $coeffs]
        if [expr {$l % 2 == 1}] {
            incr ans
        }
    }
}
puts $ans

No comments:

Post a Comment