Euler #26

https://projecteuler.net/problem=26 => Reciprocal cycles

Este ha costado un poco más sacarlo, y ha sido gracias al número 1/17 cuando me he dado cuenta que un número sí que se podía repetir en el periodo (asumí que no). Sabiendo eso, la comprobación para ver si estamos empezando un nuevo periodo solo debe tener en cuenta si estamos repitiendo un resto. Veamos una implementación en Python:

from decimal import Decimal, getcontext

getcontext().prec = 40

def Div(D, d):
 return (D/d, D%d)

def GetPeriod(d):
 period = []
 remainders = []
 index = 0
 c, r = Div(1, d)
 if r == 0:
  return []
 if c != 0:
  period.append(c)
 while True:
  D = 10*r
  c, r = Div(D, d)
  if r == 0:
   return []
  period.append(c)
  if r in remainders:  
   return period[period.index(c):index]
  index += 1
  remainders.append(r)

 return period


longestList = []
longestInt = 1
for a in range(1, 1000):
 period = GetPeriod(a)
 if len(period) > len(longestList):
  longestList = period
  longestInt = a

print "Longest period for ", longestInt, " => ", longestList, " (len: ", len(longestList), ")"

Baúl de los recuerdos: "Euroconversor"

1 de enero de 2002... entra en vigor el Euro en España. La de código que se escribió en los meses previos para adaptar lo que no estaba preparado. Recuerdo que, con la tontería, me dio por escribir una pequeña utilidad, "Eurocalculadora", que se pusieron de moda en 2001. Todo el mundo tenía una en su web, yo hice una para "desktop" en Python+Glade.

Glade era un editor de interfaces de usuario en GTK que guardaba la descripción de la misma en un XML que posteriormente se podía parsear con el lenguaje que tuviera "bindings" a GTK y libglade.

En Windows (W2000, si no recuerdo mal)

En Linux (gestor de ventanas, IceWM)

No es un código del que sentirse orgulloso, pero bueno, eran mis primeros pasos con Python :)



euroconversor.py:

from funciones import interfaz
app=interfaz.EuroConversor()
  app.a_correr()

uno.glade

<?xml version="1.0"?>
<GTK-Interface>
<project>
  <name>Aplicacion</name>
  <program_name>aplicacion</program_name>
  <directory></directory>
  <source_directory>src</source_directory>
  <pixmaps_directory>pixmaps</pixmaps_directory>
  <language>C</language>
  <gnome_support>False</gnome_support>
  <gettext_support>False</gettext_support>
</project>
<widget>
  <class>GtkWindow</class>
  <name>window1</name>
  <signal>
    <name>destroy</name>
    <handler>on_window1_destroy</handler>
    <last_modification_time>Thu, 08 Aug 2002 16:22:11 GMT</last_modification_time>
  </signal>
  <title>Conversor</title>
  <type>GTK_WINDOW_TOPLEVEL</type>
  <position>GTK_WIN_POS_CENTER</position>
  <modal>False</modal>
  <allow_shrink>False</allow_shrink>
  <allow_grow>False</allow_grow>
  <auto_shrink>False</auto_shrink>
  <widget>
    <class>GtkVBox</class>
    <name>vbox2</name>
    <homogeneous>False</homogeneous>
    <spacing>0</spacing>
    <widget>
     <class>GtkLabel</class>
      <name>label1</name>
      <label>Euro Conversor:
Introduzca la cantidad a convertir</label>
      <justify>GTK_JUSTIFY_CENTER</justify>
      <wrap>False</wrap>
      <xalign>0.5</xalign>
      <yalign>0.5</yalign>
      <xpad>10</xpad>
      <ypad>10</ypad>
      <child>
        <padding>0</padding>
 <expand>True</expand>
 <fill>True</fill>
      </child>
    </widget>
    <widget>
      <class>GtkHBox</class>
      <name>hbox2</name>
      <homogeneous>False</homogeneous>
      <spacing>0</spacing>
      <child>
 <padding>0</padding>
 <expand>True</expand>
 <fill>True</fill>
      </child>
      <widget>
 <class>GtkLabel</class>
 <name>label2</name>
 <label>Pesetas</label>
 <justify>GTK_JUSTIFY_RIGHT</justify>
 <wrap>False</wrap>
 <xalign>0.5</xalign>
 <yalign>0.5</yalign>
 <xpad>5</xpad>
 <ypad>5</ypad>
 <child>
   <padding>0</padding>
   <expand>True</expand>
   <fill>True</fill>
 </child>
      </widget>
      <widget>
 <class>GtkEntry</class>
 <name>entry1</name>
 <can_focus>True</can_focus>
 <signal>
   <name>key_press_event</name>
   <handler>on_entry1_key_press_event</handler>
   <last_modification_time>Mon, 12 Aug 2002 13:18:49 GMT</last_modification_time>
 </signal>
 <editable>True</editable>
 <text_visible>True</text_visible>
 <text_max_length>0</text_max_length>
 <text></text>
 <child>
   <padding>5</padding>
   <expand>False</expand>
   <fill>True</fill>
 </child>
      </widget>
    </widget>
    <widget>
      <class>GtkHBox</class>
      <name>hbox3</name>
      <homogeneous>False</homogeneous>
      <spacing>0</spacing>
      <child>
 <padding>0</padding>
 <expand>True</expand>
 <fill>True</fill>
      </child>
      <widget>
 <class>GtkLabel</class>
 <name>label3</name>
 <label>Euros</label>
 <justify>GTK_JUSTIFY_RIGHT</justify>
 <wrap>False</wrap>
 <xalign>0.5</xalign>
 <yalign>0.5</yalign>
 <xpad>5</xpad>
        <ypad>5</ypad>
 <child>
   <padding>0</padding>
   <expand>True</expand>
   <fill>False</fill>
 </child>
      </widget>
      <widget>
 <class>GtkEntry</class>
 <name>entry2</name>
 <can_focus>True</can_focus>
 <signal>
   <name>key_press_event</name>
   <handler>on_entry2_key_press_event</handler>
   <last_modification_time>Mon, 12 Aug 2002 13:18:59 GMT</last_modification_time>
 </signal>
 <editable>True</editable>
 <text_visible>True</text_visible>
 <text_max_length>0</text_max_length>
 <text></text>
 <child>
   <padding>5</padding>
   <expand>False</expand>
   <fill>True</fill>
 </child>
      </widget>
    </widget>
  </widget>
</widget>
</GTK-Interface>

__init__.py

__all__ = ["interfaz", "conversiones"]

conversiones.py

def validar_entrada1( texto ):
    try:
         return str(long(texto))
    except ValueError:
         return ""

def validar_entrada2( texto ):
    try:
         return str(float(texto))
    except ValueError:
         return ""

def pelas_a_euros( entrada ): #Aquí viene lo que han tecleado
    return "%.2f" % (float(entrada)/166.386)

def euros_a_pelas( entrada ): #Aquí viene lo que han tecleado
    return "%d" % (float(entrada)*166.386)

interfaz.py

import libglade, gtk
from funciones import conversiones

class EuroConversor:
    def __init__(self):
        self.arbol = libglade.GladeXML( "aplicacion.glade", "window1" )
        self.caja1 = self.arbol.get_widget( "entry1" )
        self.caja2 = self.arbol.get_widget( "entry2" )

        manejadores = { "on_entry1_key_press_event" : self.pasar,
                        "on_entry2_key_press_event" : self.pasar,
                       }
        self.arbol.signal_autoconnect( manejadores )
        self.arbol.signal_connect( "on_window1_destroy", self.salir )

    def a_correr(self):
        gtk.mainloop()

    def salir(self, obj):
        print "Saliendo..."
        gtk.mainquit()

    def pasar(self, obj, ev):
        """  En 'obj' viene el objeto que llama (la caja de texto),
             En 'ev' viene el evento, dir(ev) = keyval, send_event, state, string, time, type, window
        """
        nombre = libglade.get_widget_name( obj )
        if nombre == "entry1":
           entrada_validada1 = conversiones.validar_entrada1(obj.get_text() + ev.string)
           if entrada_validada1:
                self.caja2.set_text( conversiones.pelas_a_euros( entrada_validada1 ) )
           else:
                self.caja1.set_text( "" )
                self.caja2.set_text( "" )
        elif nombre == "entry2":
           entrada_validada2 = conversiones.validar_entrada2(obj.get_text() + ev.string)
           if entrada_validada2:
                self.caja1.set_text( conversiones.euros_a_pelas( entrada_validada2 ) )
           else:
                self.caja1.set_text( "" )
                self.caja2.set_text( "" )

Baúl de los recuerdos: "Power Helper"

De vez en cuando toca alguna intervención nocturna y uno aprovecha para revisar cosas pendientes... tenía un directorio con backups antiguos y rebuscando, rebuscando... he encontrado algunos programillas que hice hace tiempo.

Ahí va uno, que en su día llamé "Power Helper", era un script en Tcl/Tk que servía para controlar los perfiles de rendimiento de la CPU, administración de energía. Lo usé mucho tiempo en un portátil que tenía.



No recuerdo cuándo escribí este programa, pero sería entre 2001 y 2003, que fue una época en la que estuve experimentando con muchos lenguajes de script.

Me llamó mucho la atención en su día Tcl. Su estilo muy similar a una shell y sus tipos de datos eran bastante curiosos.

#!/usr/bin/wish

set governors [exec cat /sys/devices/system/cpu/cpu0/cpufreq/scaling_available_governors]

proc show_message {tit mes} {
    tk_messageBox -icon info -title $tit -message $mes
}

proc show_governor {} {
    show_message "Rendimiento"  "Perfil de rendimiento: [exec cat /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor]"
}

proc show_Batería {} {
    show_message "Batería"  "Estado de la batería:\n[string trim [exec acpi]]\n[exec cat /proc/acpi/battery/BAT1/state]"
}

proc show_cpu {} {
    show_message "CPU"  "Información CPU:\n[exec cat /proc/cpuinfo]"
}

proc Hibernar {} {
    exec /bin/echo 4 > /proc/acpi/sleep
}

proc set_governor {g} {
    exec cpufreq-set {-g} "$g"
    show_governor
}

button .show -text {Perfil de rendimiento} -width 30 -command show_governor
pack .show -padx 5 -pady 3

foreach {g} $governors {
    button .g$g -text "Cambiar a perfil $g" -width 30 -command "set_governor $g"
    pack .g$g -padx 5 -pady 3
}

button .batstate -text "Estado de la batería" -width 30 -command show_Batería
pack .batstate -padx 5 -pady 3

button .cpu -text "Información CPU" -width 30 -command show_cpu
pack .cpu -padx 5 -pady 3

button .hibernar -text "Hibernar" -width 30 -command Hibernar
pack .hibernar -padx 5 -pady 3

button .end -text {Salir} -width 30 -command exit
pack .end -padx 5 -pady 3

wm title . "Power helper"

Euler #25

https://projecteuler.net/problem=25 => 1000-digit Fibonacci number

Volvemos a intentar cumplir los nuevos propósitos: vamos a probar con un lenguaje que no conocemos: Go.

Primera aproximación, por fuerza bruta, tras varias horas, no obtenemos resultado alguno:

package main

import ("math"
        "fmt")

func fib(n int) int {
    if n <= 2 {
        return 1
    }
    return fib(n-1) + fib(n-2)
}

func main() {
    nDigits := 1000
    limit := int(math.Pow(10, float64(nDigits) - 1)) - 1    
    index := 1
    for {
        num := fib(index)
        if num > limit {
            fmt.Printf("Index => %d\n", index)
            return
        }
        index++
    } 
}

El problema es que cada vez que iteramos, se empieza todo de nuevo. La mejora que vamos a intentar es ir guardando los números de Fibonacci que vamos generando en algún tipo de estructura de datos. Al igual que con C cuando manejamos enteros muy grandes, nos volvemos a encontrar con problemas de desbordamiento, hay que utilizar números enteros de precisión arbitraria (definidos en el package math/big de Go). Al implementarlo, de nuevo, me siento desbordado con los detalles del lenguaje y me doy por vencido, como en el anterior intento, que dejé la implementación en Perl sin hacer.

Implementamos en Python:

fib_numbers_cache = {}

def fib(num):
 if num in fib_numbers_cache:
  return fib_numbers_cache[num]
 if num <= 2:
  fibNum = 1
 else:
  fibNum = fib(num - 1) + fib(num - 2)
 fib_numbers_cache[num] = fibNum
 return fibNum

n = 1
n_digits = 1000
fib_num_max = 10**(n_digits - 1) - 1
while True:
 fn = fib(n)
 if fn > fib_num_max:
  print "END: ", n, "=>", fn
  break
 n += 1

Tras varios intentos de implementar las cosas en distintos lenguajes, siempre vuelvo al que más me gusta, que es Python ;)

Euler #24

https://projecteuler.net/thread=24 => Lexicographic permutations

En el anterior problema me propuse utilizar lenguajes con los que no estuviese muy familiarizado, y este problema lo empecé a hacer con Perl... pero es que no me gusta nada, nada, nada.

Al final, a fuerza bruta y en Python:

def get_permutations (arr):
 if len(arr) < 2:
  return [[arr]]
 elif len(arr) == 2:
  return [[arr[0], arr[1]], [arr[1], arr[0]]]
 else:
  permuts = []
  for a in arr:
   arr2 = arr[:]
   arr2.remove(a)
   for p in get_permutations(arr2):
    p.insert(0, a)
    permuts.append(p)
  return permuts

res = get_permutations([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
print res[999999]

Con el módulo itertools se hace en prácticamente una línea, pero no vale así, es trampa :D

En el foro de Euler comentan varias formas alternativas de afrontar el problema.