Divisió de polinomis amb Emacs Lisp

Per passar l’estona es poden fer moltes coses: llegir un llibre, escoltar música, veure la tele o escriure programes, entre moltes d’altres.

Per circumstàncies diverses, aquests darrers temps he pogut dedicar moltes estones a escriure programes i, un cop escrits, he pensat que els puc aprofitar per fer-ne un post al bloc de tecnologia.

En aquesta ocasió, es tracta d’un programa que fa la divisió entre dos polinomis. Al programa se li entrega una llista amb els coeficients numèrics del numerador (amb zero per als coeficients nuls) i una llista amb els del denominador. Cal que el grau del polinomi del numerador sigui major o igual que el del denominador.

Amb aquestes condicions, només cal aplicar el conegut algorisme de divisió de polinomis. Un exemple il·lustra el procediment:

Donats e numerador i denominador:

 N: x^3 + -12*x^2 + -42
 D: x + -3

La resposta és:

 Q: x^2 + -9*x + -27
 R: -123

Vet aquí el procediment. Cada parell és (coeficient, grau):

    (1,3)  (-12,2)  (0,1)  (-42,0) | (1,1) (-3,0) 
   -(1,3)   -(-3,2)                  (1,2)(-9,1) (-27,0)
    -------------
       0    (-9,2)   (0,1)  
           -(-9,2) -(27,1)
    ----------------------
                0  (-27,1) (-42,0)
                  -(-27,1) -(81,0) 
    ------------------------------
                        0  (-123,0)

Un exemple numèric diferent (aquí només indico el coeficients):

 6   5   4  3   2   1     | 1  2 3
-6 -12 -18                  6 -7 0 24
----------
    -7 -14  3   2   1
     7  14 21
---------------------
           24   2   1
            0   0   0
---------------------
           24   2   1
          -24 -48 -72
---------------------
              -46 -71

Es tracta d’implementar l’algorisme anterior. A manca d’alguna altre cosa, aquest cop he fet servir Emacs Lisp, el llenguatge d’extensió que porta incorporat l’Emacs. Al tractar-se d’un algorisme essencialment recursiu resulta senzill d’implementar amb un dialecte de Lisp com l’Emacs Lisp.

Bé, doncs és això:

(progn
  (setq coefs (list))
  (setq rest (list))

  (defun show-poly (poly)
    (if (>= (length poly) 1)
	(progn
	  (setq exponent (1- (length poly)))
	  (insert (format "(%s*(x^%d))" (car poly) exponent))
	  (if (> exponent 0)
	      (progn
		(insert "+")
		(show-poly (cdr poly)))))))

  (defun get-quotient (num den)
    (setq lnum (length num))
    (setq lden (length den))
    (setq quotient (list))

    (setq high-coef-num (car num))
    (setq high-coef-denom (car den))
    (setq coef (/ high-coef-num high-coef-denom))

    (dotimes (i lden)
      (setq quotient (append quotient (list (- (nth i num) 
                                      (* coef (nth i den)))))))
    (dotimes (i (- lnum lden))
      (setq quotient (append quotient (list (nth (+ lden i) num)))))

    (newline)
    (insert "Last rest: ")
    (show-poly quotient)
    (newline)
    (cons coef quotient))

  (defun divide (numerator denominator)
    (setq lnum (length numerator))
    (setq lden (length denominator))
    
    (if (>= lnum lden)   
	(progn 
          (setq pair (get-quotient numerator denominator))
          (setq coefs (append coefs (list (car pair))))
          (divide (cdr (cdr pair)) denominator))))

  ;; main
  (newline)
  (newline)
  (insert "Polynomial division")
  (newline)
  (setq num '(1 2 1))
  (setq den '(1 1))
  (newline)
  (insert "divide")
  (newline)
  (show-poly num)
  (newline)
  (insert "by")
  (newline)
  (show-poly den)
  (newline)
  (divide num den)
  (newline)
  (insert "Quotient: ")
  (show-poly coefs)
  (newline))

Per a executar el programa copieu el codi anterior a un buffer de l’Emacs i executeu-lo amb C-x C-e (la seqüència control-x control-m).

El programa calcularà la divisió del polinomi x² + 2x + 1 per x + 1, resultat x + 1 i rest 0. Per a provar amb altres polinomis n’hi ha prou de canviar el parell de línies

  (setq num '(1 2 1))
  (setq den '(1 1))

El codi també està al meu GitHub

I, per acabar, encara que aquests dies han donat per algun altre joc amb Python que segurament també publicaré, espero que els propers posts siguin una mica més sucosos (en cartera: programació funcional amb javascript i underscore.js. A veure quan cau!).

Un puzzle 3×3 (versió amb Python i versió amb C)

Després d’una llarga aturada, reprenc el blog amb un un puzzle fet amb python (i amb C)

Segur que recordeu els puzzles en que una imatge es trosseja en NxN – 1 quadrets dins un marc de NxN (és dir, amb un espai lliure). Aleshores, movent quadrets a l’espai que queda lliure es pot aconseguir reordenar la imatge.

En el post d’avui he implementat el cas d’un puzzle de 3×3, tot molt simplificat i en mode text. Com sempre, estic desenvolupant sobre una màquina Linux. En concret, sobre el meu vell i petit eCAFÉ EC-800-H20G/S, amb Lubuntu 10.10, una maquineta minúscula amb un SO antic que, per circumstàncies personals, m’ha fet molta companyia aquests darrer mes.

  puzzle resolt    puzzle desordenat
  +---+            +---+
  |123|            | 38|
  |456|            |245|
  |78 |            |761|
  +---+            +---+

El programa ha de
1. generar un puzzle desordenat
2. mostrar el puzzle
3. demanar quin número es vol moure
4. veure si es pot moure
5.  si no es pot moure, dir-ho i tornar al punt 2
6.  si es pot moure, fer el moviment.
7.    comprovar si ha guanyat
8.      si ha guanyat acabar eljoc
9.      si no ha guanyat, tornar al punt 2.

Amb Python, l’algorisme anterior és d’implementació gairebé directa, fixeu-vos en el bloc main.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import random
import sys

def genera_puzzle(puzzle):
  for i in range(0,9):
    repeat = True
    while repeat:
      j = random.randint(0,8)
      if puzzle[j] == 10:
        puzzle[j] = i
        repeat = False
  
  return puzzle

def mostra_puzzle(puzzle):
  print "+---+"
  print "|%d%d%d|" % (puzzle[0], puzzle[1], puzzle[2])
  print "|%d%d%d|" % (puzzle[3], puzzle[4], puzzle[5])
  print "|%d%d%d|" % (puzzle[6], puzzle[7], puzzle[8])  
  print "+---+"
  print "\n"

def demanar_numero():
  valid = False
  while not valid:
    in_value = raw_input("(1-9) or q? ")
    if len(in_value) == 1:
      if in_value in "12345678qQ":
        valid = True

  if in_value == 'q' or in_value == 'Q':
    print "\nGame interrupted\n"
    sys.exit(0)

  return int(in_value)


def obtenir_posicio(num, puzzle):
  pos = []

  for row in range(0, 3):
    for column in range(0, 3):
      if num == puzzle[row * 3 + column]:
        pos = [row, column]
        break

  return pos     


def verifica_numero(num, puzzle):
  valid = False
  pos = []
  
  pos = obtenir_posicio(num, puzzle)
  valid = verifica_posicio(pos, puzzle)

  return valid

def verifica_posicio(pos, puzzle):
  valid = False
  row = pos[0]
  column = pos[1]
  
  if (row - 1) >= 0:
    if puzzle[(row - 1) * 3 + column] == 0:
      valid = True

  if (row + 1) = 0:
    if puzzle[(row * 3) + (column - 1)] == 0:
      valid = True

  if (column + 1) = 0:
    if puzzle[(row - 1) * 3 + column] == 0:
      puzzle[(row - 1) * 3 + column] = num
      puzzle[(row * 3) + column] = 0

  if (row + 1) = 0:
    if puzzle[(row * 3) + (column - 1)] == 0:
      puzzle[(row * 3) + (column - 1)] = num
      puzzle[(row * 3) + column] = 0

  if (column + 1) <= 2:
    if puzzle[(row * 3) + (column + 1)] == 0:
      puzzle[(row * 3) + (column + 1)] = num
      puzzle[(row * 3) + column] = 0    
  
  return puzzle

def es_puzzle_completat(puzzle):
  s = ''.join(map(lambda (x): str(x), puzzle))
  if s == '123456780':
    return True
  else:
    return False


if __name__ == "__main__":
  puzzle = [10 for x in range(0, 9)]
  final = False
  puzzle = genera_puzzle(puzzle)
  while not final:
    final = False
    mostra_puzzle(puzzle)
    num = demanar_numero()
    if verifica_numero(num, puzzle):
      puzzle = moviment(num, puzzle)
      if es_puzzle_completat(puzzle):
        print "\nWell done!!\n"
        mostra_puzzle(puzzle)
        final = True

Topt i ser un programa molt curt, té algun detall bonic: per exemple, l’us d’una funció lambda a la verificació de puzzle completat. Amb una sola línia es transforma es transforma un array numèric en una cadena de text. En total, 155 línies de codi.

I això mateix, com queda amb C?Amb C són 230 línies

#ifndef PUZZLE
#define PUZZLE
#include 
#include 
#include 
#include 
#include 

#define TRUE 1
#define FALSE 0

int puzzle[] = {10,10,10,10,10,10,10,10,10};

typedef struct POS {
  int row;
  int column;
} T_POS;

int randint(int range) {
  return random() % (range + 1);  
}

void genera_puzzle(int puzzle[]) {
  int i;
  int j;
  int repeat;
  for(i = 0; i < 9; i++) {
    repeat = 1;
    while (repeat) {
      j = randint(8);
      if (puzzle[j] == 10) {
        puzzle[j] = i;
        repeat = 0;
      }
    }
  }
}

void mostra_puzzle(int puzzle[]) {
  printf("+---+\n");
  printf("|%d%d%d|\n", puzzle[0], puzzle[1], puzzle[2]);
  printf("|%d%d%d|\n", puzzle[3], puzzle[4], puzzle[5]);
  printf("|%d%d%d|\n", puzzle[6], puzzle[7], puzzle[8]);
  printf("+---+\n");
  printf("\n");
}

int demanar_numero() {
  int valid = FALSE;
  char *line;
  char c;

  while(!valid) {
    line = readline("(1-9) or q (quit)? ");
    if (strlen(line) == 1) {
      if ((strcmp(line, "q") == 0) || (strcmp(line, "Q") == 0)) {
	  valid = TRUE;
          free(line);
          printf("\nGame interrupted\n");
          exit(0);
      }
  	
      c = line[0];
      free(line);

      if ((c == '0') || (c == '1') || (c == '2') ||
          (c == '3') || (c == '4') || (c == '5') ||
          (c == '6') || (c == '7') || (c == '8')) {
        valid = TRUE;      
      }       
    }
  }
  
  return (c - '0');
}


T_POS obtenir_posicio(int num, int puzzle[]) { 
  T_POS pos;
  int row;
  int column;

  for(row = 0; row < 3; row++) {
    for(column = 0; column = 0) {
    if (puzzle[(row - 1) * 3 + column] == 0) {
      valid = TRUE;  
    }
  }

  if ((row + 1) = 0) {
    if (puzzle[(row * 3) + (column - 1)] == 0) {
      valid = TRUE;
    }
  }

  if ((column + 1) = 0) {
    if (puzzle[(row - 1) * 3 + column] == 0) {
      puzzle[(row - 1) * 3 + column] = num;
      puzzle[(row * 3) + column] = 0;
    }
  }

  if ((row + 1) = 0) {
    if (puzzle[(row * 3) + (column - 1)] == 0) {
      puzzle[(row * 3) + (column - 1)] = num;
      puzzle[(row * 3) + column] = 0;
    }
  }

  if ((column + 1) <= 2) {
    if (puzzle[(row * 3) + (column + 1)] == 0) {
      puzzle[(row * 3) + (column + 1)] = num;
      puzzle[(row * 3) + column] = 0;
    }
  }
}

int es_puzzle_completat(int puzzle[]) {
  char solved[]="123456780";
  char actual[10];
  int i;
 
  for(i = 0; i < 9; i++) {
    actual[i] = puzzle[i] + '0';
  }
  actual[9] = 0;

  if (strcmp(solved, actual) == 0) {
    return TRUE;
  } else {
    return FALSE;
  }
}

int main(int argc, char *argv[]) {
  int final = 0;
  int num;
  genera_puzzle(puzzle);
  while(!final) {
    final = 0;
    mostra_puzzle(puzzle);
    num = demanar_numero();
    if (verifica_numero(num, puzzle)) {
      moviment(num, puzzle);
      if (es_puzzle_completat(puzzle)) {
        printf("\nWell done!!\n");
        mostra_puzzle(puzzle);
        final = 1;
      }
    }
  }
}

#endif

I el makefile corresponent

all: puzzle clean

puzzle: puzzle.o
	gcc -g -lreadline -o puzzle puzzle.o

puzzle.o: puzzle.c
	gcc -g -c puzzle.c

clean:
	-rm *.o *~

Amb C també és força directe, però cal fer la gestió d’espai de memòria que amb Python ve donada.

Remarcar l’us de la llibreria readline per a fer l’entrada per teclat. Aquesta és la forma més recomanable de fer entrades per teclat a una aplicació de consola a Linux. Les aplicacions curses tenen també un sistema propi i segur per fer entrades per teclat que eviten el perill de desbordament del buffer d’entrada si es fa servir gets(), o scanf(), o qualsevol sistema que demani un buffer d’entrada de mida especificada.

Finalment, aquest puzzle bàsic es pot ampliar senzillament amb:
– incrementant a dimensions NxN amb N > 3
– afegint interfície gràfica: amb Tkinter, o Pygame, a la versió amb Python; Fent servir Glade a la versió C.

Finalment, el codi de les dues versions (C i Python) es pot descarregar del meu GitHub