Wednesday, April 13, 2011

Project Euler - Problem 4 - Tcl

#A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91  99.
#Find the largest palindrome made from the product of two 3-digit numbers.
proc problem4 {} {
 set palindrom_found FALSE
 set current_palindrom [expr 999*999]

 while { $palindrom_found == FALSE } {
  set current_palindrom [next_polindrom $current_palindrom -1]

  for { set idx 999 } { $idx > 900 } {incr idx -1} {
   if { ( $current_palindrom % $idx ) == 0   &&   ($current_palindrom / $idx) < 1000 } {
    puts "$idx*[expr $current_palindrom / $idx]=$current_palindrom"
    set palindrom_found TRUE
    break
   }
  }
 }
}

#****f* math/next_polindrom
# FUNCTION
#  Generates the next polindrom according to a given polindrom.
#
# INPUTS
#  pre_polindrom:
#   * TBD
#  direction:
#   * (+n) - next (n) polindrom up
#   * (-n) - next (n) polindrom down
#
# RESULT
#  * int - The consecutive (n) polinom from the given number/polinom.
#  * {} - error with parameters or none found.
#
# EXAMPLE
#  TBD
#
# NOTES
# * Good for solving problem-4. Jumps from 100000 to 9999 (see BUGS).
#
# BUGS
#  * Wrong sequance: {... 102201 101101 100001 9999 9889 9779 ... }
#
# SYNOPSIS
proc next_polindrom { pre_polindrom direction } {
 # SOURCE
 # E.g. pre_polindrom ==> 123000
 set polindrom_len [expr round( ceil( log10( $pre_polindrom ))) ]
 set polindrom_mid_len [expr ($polindrom_len / 2) + ($polindrom_len % 2)]
 set digits_to_align [expr $polindrom_len - $polindrom_mid_len]

 set polindrom_core $pre_polindrom  ; # E.g. polindrom_core ==> 123000
 while { $digits_to_align > 0} {
  set polindrom_core [expr $polindrom_core / 10]

  incr digits_to_align -1
 }  ; # E.g. polindrom_core ==> 123

 incr polindrom_core $direction  ; # E.g. (of +1): polindrom_core ==> 124

 set splited_polindrom_core [split $polindrom_core {}]  ; # E.g. splited_polindrom_core ==> {1 2 3}

 set splited_reversed_polindrom_core [lreverse $splited_polindrom_core]  ; # E.g. splited_reversed_polindrom_core ==> {3 2 1}
 set splited_reversed_polindrom_core [lrange $splited_reversed_polindrom_core [expr $polindrom_len % 2] end]  ; # E.g. for 123000: {3 2 1} ==> {3 2 1}, for 12300: {3 2 1} ==> {2 1}
 set reversed_polindrom_core [join $splited_reversed_polindrom_core {}]  ; # E.g. splited_reversed_polindrom_core ==> {321}

 set next_polinom "$polindrom_core$reversed_polindrom_core"

 return $next_polinom
 ######
}

#Solution-4: 993*913=906609

No comments:

Post a Comment