Tag Archives: C - Page 2

C Gaussian Elimination Implementation

Posted by on 9 December, 2008 8 comments

A simple gaussian elimination implemented in C.

To simplify, I hard coded the linear system

10 x1 + 2 x2 + 3 x3 + 4 x4 = 5
6 x1 + 17 x2 + 8 x3 + 9 x4 = 10
11 x1 + 12 x2 + 23 x3 + 14 x4 = 15
16 x1 + 17 x2 + 18 x3 + 29 x4 = 20

into the AB float matrix.

/* 
 * Description: Solve a hard coded linear system by gaussian elimination
 * Author: Silveira Neto
 * License: Public Domain
 */
 
#include <stdio.h>
#include <stdlib.h>
 
#define ROWS 4
#define COLS 5
 
/**
 * Linear System, Ax = B
 *
 * 10*x1 +  2*x2 +  3*x3 +  4*x4 = 5
 *  6*x1 + 17*x2 +  8*x3 +  9*x4 = 10
 * 11*x1 + 12*x2 + 23*x3 + 14*x4 = 15
 * 16*x1 + 17*x2 + 18*x3 + 29*x4 = 20
 */
float AB[ROWS][COLS] = {
    {10,  2,  3,  4,  5},
    { 6, 17,  8,  9, 10},
    {11, 12, 23, 14, 15},
    {16, 17, 18, 29, 20}
};
 
/* Answer x from Ax=B */
float X[ROWS] = {0,0,0,0};
 
int main(int argc, char** argv) {
    int row, col, i;
 
    /* gaussian elimination */
    for (col=0; col<COLS-1; col++) {
        for (row=0; row<ROWS; line++){
            float pivot =  AB[row][col]/AB[col][col];
            if(row!=col) {
                for(i=0; i<COLS; i++) {
                    AB[row][i] = AB[row][i] - pivot * AB[col][i];
                }
 
            }
        }
    }
 
    /* X = B/A and show X */
    for(row=0; row<ROWS; line++) {
        X[row] = AB[row][ROWS] / AB[row][row];
        printf("%3.5f ", X[row]);
    }
    printf("n");
 
    return (EXIT_SUCCESS);
}

Before the gaugassian elimination, AB is

10  2  3  4  5
 6 17  8  9 10
11 12 23 14 15
16 17 18 29 20

and after it is 

10.00000 0.00000 0.00000 0.00000 2.82486
0.00000 15.80000 0.00000 0.00000 3.92768
0.00000 0.00000 15.85443 0.00000 3.85164
0.00000 0.00000 0.00000 14.13174 3.35329

that corresponds to

10 x1 = 2.82486
15.80000 x2 = 3.92768
15.85443 x3 = 3.85164
14.13174 x4 = 3.35329

The solution vector is X = (x1, x2, x3, x4). We get it by X=B/A.

The program output, X, is

0.28249 0.24859 0.24294 0.23729

Benchmarking:
I’m this serial implementation over one node of our cluster, a machine with 4 processors (Intel Xeon 1.8 Ghz) and 1Gb RAM memory. I tried random systems from 1000 to 5000 variables and got the average time.

gaugassian elimination serial

JavaFX, rectangular collision detection

Posted by on 30 October, 2008 7 comments

In a game I wrote some years ago we handled simple rectangular collisions. Given the points:

We did:

// returning 0 means collision
int collision(int ax, int ay, int bx, int by, int cx, int cy, int dx, int dy){
	return ((ax > dx)||(bx < cx)||(ay > dy)||(by < cy));
}

I’ll show here a little demo about how implement simple rectangular collisions on JavaFX.
First I created a movable rectangle using the same idea of draggable nodes I already had posted before.

import javafx.input.MouseEvent;
import javafx.scene.geometry.Rectangle;
 
public class MovableRectangle extends Rectangle {
    private attribute startX = 0.0;
    private attribute startY = 0.0;
 
    public attribute onMove = function(e:MouseEvent):Void {}
 
    override attribute onMousePressed = function(e:MouseEvent):Void {
        startX = e.getDragX()-translateX;
        startY = e.getDragY()-translateY;
        onMove(e);
    }
 
    override attribute onMouseDragged = function(e:MouseEvent):Void {
        translateX = e.getDragX()-startX;
        translateY = e.getDragY()-startY;
        onMove(e);
    }
}

In the main code I some important things:

  • colide, a color that represents the collision effect. White means no collision and gray means collision.
  • rec1 and rec2, the two rectangles that can collide.
  • checkcollision() the function that checks and handles a possible collision.

Here is the main code:

import javafx.application.Frame;
import javafx.application.Stage;
import javafx.scene.geometry.Rectangle;
import javafx.scene.paint.Color;
import javafx.input.MouseEvent;
 
var colide = Color.WHITE;
 
function checkcollision():Void {
    if (
        (rec1.getBoundsX() > rec2.getBoundsX() + rec2.getWidth()) or
        (rec1.getBoundsX() + rec1.getWidth() < rec2.getBoundsX()) or 
        (rec1.getBoundsY() > rec2.getBoundsY() + rec2.getHeight()) or 
        (rec1.getBoundsY() + rec1.getHeight() < rec2.getBoundsY())
    ) {
        colide = Color.WHITE
    } else {
        colide = Color.LIGHTGRAY
    }
}
 
var rec1: MovableRectangle = MovableRectangle {
    x: 10, y: 10, width: 50, height: 60, fill: Color.RED
    onMove: function(e:MouseEvent):Void {
        checkcollision()
    }
}
 
var rec2: MovableRectangle = MovableRectangle {
    x: 100, y: 100, width: 70, height: 30, fill: Color.BLUE
    onMove: function(MouseEvent):Void {
        checkcollision()
    }
}
Frame {
    title: "Rectangular Collisions", width: 300, height: 300
    closeAction: function() { 
        java.lang.System.exit( 0 ); 
    }
    visible: true
 
    stage: Stage {
        fill: bind colide
        content: [rec1, rec2]
    }
}

Try it via Java Web Start:

Java Web Start

Some considerations:

  • You can use rectangular collisions to create bounding boxes to handle collisions in more complex shapes or sprites. Is a common approach in 2d games to avoid more expensive calculations.
  • There are space for optimizations.
  • In this case I’m using only two objects. Some problems raises when I have N objects to handle.

More generally, we can code:

function collission(ax, ay, bx, by, cx, cy, dx, dy): Boolean {
    return not ((ax > dx)or(bx < cx)or(ay > dy)or(by < cy));
}
 
function hitnode(a: Node, b:Node): Boolean{
    return (collission(
        a.getBoundsX(), a.getBoundsY(),
        a.getBoundsX() + a.getWidth(), a.getBoundsY() + a.getHeight(),
        b.getX(), b.getY(),
        b.getX() + b.getWidth(), b.getY() + b.getHeight()
    ));
}

This way we can pass just two bounding boxes to hitnode and easily check collision of a node against a list of bounding boxes nodes.
Using the same approach I also wrote this function to test if a Node is inside another Node:

function inside (ax, ay, bx, by, cx, cy, dx, dy):Boolean{
    return ((ax > cx) and (bx < dx) and (ay > cy) and (by < dy));
}
 
function insidenode(a:Node,b:Node):Boolean{
    return (inside(
        a.getBoundsX(), a.getBoundsY(),
        a.getBoundsX() + a.getWidth(), a.getBoundsY() + a.getHeight(),
        b.getBoundsX(), b.getBoundsY(),
        b.getBoundsX() + b.getWidth(), b.getBoundsY() + b.getHeight()
    ));
}

Soon I’ll post game examples showing how to use this method and others collission detection methods.

Downloads:

Anúncio do NetBeans 6.5 Beta

Posted by on 13 August, 2008 2 comments

O Netbeans.org anunciou a disponibilidade do NetBeans IDE 6.5 Beta. Abaixo a tradução do anúncio:

O NetBeans IDE 6.5 introduz várias novas funcionalidades, incluindo uma IDE robusta para PHP, deputação de JavaScript para o Firefox e IE, e suporte a Groovy e Grails. Esse lançamento também inclui várias melhorias para o desenvolvimento em Java, Ruby e Rails, e C/C++. Dentre as melhorias no Java destacam-se: suporte nativo ao Hibernate, importação de projetos do Eclipse, e compilação no salvamento.

Links:

Outros destaques:

  • PHP
    • Completação de código
    • Consertos rápidos e checagem semântica
    • Suporte a FTP
    • Depuração com Xdebug
    • Suporte a Web Services populares
  • Ajax/JavaScript
    • Suporte a depuração no Firefox e IE
    • Monitoramento cliente de HTTP
    • Vêm com as bibliotecas mais populares de JavaScript
  • Java
    • Suporte a Groovy/Grails
    • Compilação/Deploy no momento do salvamento
    • Importação e sincronização de projetos do Eclipse
    • Suporte nativo a Hibernate
    • Gerador de CRUD JSF agora com Ajax
  • Banco de Dados
    • Melhorias no editor
  • C/C++
    • Melhorias na completação de código e destaque de erros
    • Desenvolvimento remoto
  • Ruby
    • Suporte aos Testes Ruby
    • Melhoria no suporte a Rake
  • GlassFish V3 “Prelude”
    • Menor tamanho, inicialização e deployment mais rápido
    • Suporte a scripting, inclusive jRuby

O NetBeans IDE 6.5 final está planejado para ser lançado em Outubro de 2008. Como sempre, é bem vindo e nós encorajamos seu feedback sobre sua experiência usando a IDE NetBeans. Visite nossas listas de email ou faça uma postagem no seu blog.

Pointers to functions in C++

Posted by on 16 March, 2008 No comments

I need to implements some codes in C++. Just remembering some concepts like pointers to functions.

A simple example:

#include <stdlib.h>
#include <iostream>

using namespace std;

double evalFunction(double (*f)(double), double param){
    return f(param);
}

double function(double x){
    return x/2;
}

int main(int argc, char** argv) {
    cout << function(5.0) << endl;
    cout << evalFunction(function, 5.0) << endl;
    return (EXIT_SUCCESS);
}

Gerando permutações

Posted by on 19 January, 2008 No comments

Muitas vezes para resolver uma única instância de um problema é mais rápido ataca-lo com força bruta do que encontrar um algoritmo geral com uma boa ordem de complexidade. Permutações são de grande utilidade nesse tipo de abordagem.

Permutações em Prolog:

Esse é um código em Prolog que o Wladimir Araujo passou na cadeira de IA.

select(X, [X|Xs], Xs).
select(X, [Y|Ys], [Y|Zs]) :- select(X, Ys, Zs).
 
permutar([], []).
permutar(Xs, [Z|Zs]) :-
    select(Z, Xs, Ys),
    permutar(Ys, Zs).

Permutações em Python:
Esse é um código de um certo Michael Davies que eu tirei daqui. Ele gera uma lista com todas as permutações de uma lista. Muito bonitinho. :)

def all_perms(str):
    if len(str) <=1:
        yield str
    else:
        for perm in all_perms(str[1:]):
            for i in range(len(perm)+1):
                yield perm[:i] + str[0:1] + perm[i:]

Um exemplo de uso:

>>> for p in all_perms(['a','b','c']):
	print p
['a', 'b', 'c']
['b', 'a', 'c']
['b', 'c', 'a']
['a', 'c', 'b']
['c', 'a', 'b']
['c', 'b', 'a']

Outras implementações:
Em outras linguagens o código para gerar permutações geralmente é muito grande, então eu preferi deixar alguns links.

XII Maratona Brasileira de Programação

Posted by on 23 September, 2007 2 comments

Logo da Maratona Brasileira de Programação

Esse sábado eu participei, junto com o Carlos Pontual e o Heraldo Carneiro, da décima segunda edição da Maratona Brasileira de Programação.

Maratona Brasileira de Programação

A sede do Ceará na competição ia ser em Sobral, com o pessoal da Engenharia da Computação da UFC, mas acabou sendo na Unifor. Uma pena, eu queria ter viajado pra conhecer o curso novo.

Embora antigamente eu tenha competido na OBI (Olimpíada Brasileira de Informática), eu nunca havia competido na Maratona Brasileira de Computação. Enquanto a OBI é uma competição voltada para alunos do ensino médio e básico a maratona é voltada para alunos do ensino superior da graduação e mestrado. Pelas minhas contas já faziam aí uns 3 anos que eu não competia.

Para quem não conhece esse tipo de competição, funciona assim: uma pessoa ou uma equipe (dependendo da competição) tem um certo tempo para resolver uma série de problemas usando programação. A correção do programa é automatizada. Seu programa é testado através de uma bateria de testes e deve retornar as respostas corretas. É uma ótima forma de melhorar seus conhecimentos sobre grafos, lógica, programação dinâmica, estruturas de dados, programação etc. Também é uma ótima oportunidade para conhecer ou rever o pessoal dos cursos de computação.

Heraldo Carneiro, Silveira Neto e Carlos Pontual

Bem, vamos aos problemas que nós fizemos:

  • Varetas, problema H, era um problema bem simples. Esse nós fizemos em C e foi aceito de primeira.
  • Histórico, problema E, também um problema não muito complicado. Mas foi por ele que nós nos enrolamos. Nós resolvemos o problema em Java e submetemos, mas a correção deu runtime error para ele. Nós re analisamos o problema, modificamos o programa e mandamos novamente e ganhamos outro runtime error. Como nós estávamos bem confiantes que nossa resposta estava certa nós refizemos o programa em C e submetemos. Dessa vez o programa passou sem problemas. Mais Tarde ficamos sabendo que devido a um erro da correção automática, não havia como um programa em Java ter acertado essa questão. Isso fez que passemos 1 hora e 44 minutos nesse problema.
  • Rouba, problema B, basicamente um problema para simular um jogo de cartas. O Heraldo pegou esse problema e fez ele em Java. Depois de 3 submissões e 3 time limit exceeded da correção automática, nós estávamos certos que nosso programa estava correto. Nós já haviamos feitas varias otimizações de velocidade no programa. Havia agora três alternativas: ou abandonar o problema e tentar outra questão ou continuar a otimizar o programa ou refaze-lo em C. Até tentamos sair do problema, mas ele não saiu da cabeça do Heraldo :). Refaze-lo em C implicaria em implementar uma série de estruturas na unha, o que iria ser muito chato e não havia certeza que isso ia resolver nossa vida.Por fim o Heraldo fez mais um última pequena otimização no programa e ele passou.

Nós ainda tentamos sem sucesso resolver os problemas Mário (o problema do armário hehehe) e o Zak.

Algumas estatísticas (parciais) da sede do Ceará:

Problema Submissões Aceitos
Histórico 27 9 (33%)
Rouba 17 6 (35%)
Tubos 1 0
Volei 1 0
Zak 6 2 (33%)
bolhas 4 0 (0%)
caixas 23 5 (22%)
mario 8 2 (25%)
olimp 0 0
varetas 17 10 (59%)

Equipes e problemas resolvidos:

Equipe Resolvidos Problemas
UECE – Camila, Tainara, Leonilia 6 Rouba (7/207), mario (1/172), Histórico (1/41), caixas (1/233), varetas (1/49), Zak (2/273)
UECE – Die aphthe schmerzen 5 Rouba (1/161), mario (2/0-), Histórico (1/47), caixas (2/223), varetas (1/35), Zak (4/186)
AVL Team 5 Rouba (1/135), mario (1/277), Histórico (1/77), caixas (5/296), varetas (1/67)
Os Entrevistados 4 Rouba (1/90), Tubos (1/-), Histórico (1/79), caixas (2/182), varetas (1/66)
GOF 4 Rouba (2/73), Histórico (5/151), Caixas (5/289), Varetas (1/39)
Eupodiatamatando 3 Rouba (4/181), Mário (4/-), Histórico (3/143), Varetas (1/39)
UECE – n^n 2 Rouba (1/-), Histórico (1/90), caixas (1/-), varetas (2/122)
UECE – n! 2 Histórico (2/206), varetas (1/61)
unifor2 2 Histórico (2/206), varetas (1/61)
Mazela.cpp 1 Vôlei (1/-), Histórico (4/-), caixas (7/-), varetas (1/71)
unifor1 1 Histórico (2/-), Varetas 6

Observações: A equipe Singularidade de Sobral não estava presente lá, eu não sei se eles competiram. As equipes da UECE tiveram a boa idéia de colocar o nome da faculdade no nome da equipe.

Eu gostei muito dos resultados. Tivemos muitas equipes com bons resultados. Isso demonstra que os esforços, principalmente do Joel Uchôa, em divulgar e particularizar a competição estão sendo frutíferos. Todas as universidades conseguiram bons resultados. Ano que vem eu espero ver mais universidades competindo.

Sugestões para a organização:

  • Linguagens: segundo o Joel Uchôa me informou há planos para inserir novas linguagens na competição. Fica minha sugestão para que Python e Ruby sejam incluídas.
  • Java: me parece que há um longo histórico de problemas com a correção de programas em Java, sendo inclusive o uso desta desaconselhado por alguns. Eu espero que isso seja melhorado na próxima edição. Eu e minha equipe tivemos sérios problemas por conta disso mas nem por isso tenho planos de usar outra linguagem na próxima edição.
  • Distribuição: há uma distribuição GNU/Linux própria para a competição o Maratona Linux. Ele tem várias sacadas legais como redes separadas para que nenhuma equipe possa usar a Internet ou enxergar as outras equipes, boot remoto etc. Porém é necessário boot pelo disquete o que tem sido uma fonte constante de problemas. O sistema de janelas WindowMaker também é fonte de confusão com usuários iniciantes, se é realmente necessário um sistema minimalista eu recomendaria o Fluxbox, XFCE ou Icewm.
  • Correção: eu não gosto do esquema de correção da Maratona. Eu prefiro o da OBI. Na OBI há varias baterias de testes, cuidadosamente preparadas para filtrar cada tipo de erro ou algoritmos. Cada acerto em uma bateria resulta em pontuação. Já na maratona ou se acerta uma questão completamente ou ela está totalmente errada. Isso impede algoritmos mais triviais, algoritmos com complexidade alta (os não polinomiais) e impede também usar técnicas de Inteligência Artificial. Acho que isso interfere muito na forma de se elaborar os problemas e de se resolver os problemas. No universo dos problemas reais, nem tudo pode ser resolvido em tempo e espaço polinomial. Esse é o universo em que vivemos.

Fotos:


almoço Almoço Maratona Brasileira de Programação Maratona Brasileira de Programação Maratona Brasileira de Programação Maratona Brasileira de Programação Mesa desorganizada Maratona Brasileira de Programação Maratona Brasileira de Programação Maratona Brasileira de Programação Maratona Brasileira de Programação Maratona Brasileira de Programação Maratona Brasileira de Programação Heraldo Carneiro Maratona Brasileira de Programação balões laboratório computadores Maratona Brasileira de Programação Joel Uchôa Maratona Brasileira de Programação Heraldo Carneiro Silveira Neto Carlos Pontual Maratona Brasileira de Programação confraternização Maratona Brasileira de Programação confraternização

bônus: um vídeo que eu fiz quando já estava bem cansado. Aqui.

A Maratona Brasileira de Programação é uma realização da Sociedade Brasileira de Computação, USP, Fundação Carlos Chagas, IBM e diversas universidades e voluntários por todo o Brasi.