Proyecto Euler: problema 1
Hola, siguiendo el notable ejemplo de Aureliano, me voy a poner a resolver problemas del proyecto euler con la restriccion de publicar las soluciones solo en php.
A continuacion el problema nro 1;
Encontrar la suma de todos los numeros naturales multiplos de 3 o 5 y menores de 1000.
Ejemplo; si sumaramos todos los multiplos de 3 o 5 menores de 10 nos daria 23. 3+5+6+9
<?
$sum=0;
for($i=1;$i<1000;$i++){
if((!($i%3))||(!($i%5))) {
$sum+=$i;
}
}
echo $sum."\n";
?>
Finalmente, la respuesta es; 233168
Saludos
Clase Spider para obtener metas y contenido sin html tags de una web
Hola, estaba trabajando en un pequeño buscador de sitios webs, y me tope con el problema de que no habia ninguna script por ahi que limpie correctamente una web de los html tags para obtener solo el codigo, los meta y el titulo. Por ello me puse a escribir una clase que haga estas cosas.
Quedaron algunas pequeñas funcionalidades por crear, pueden verse en los comentarios de la script, como arreglar acentos y usar fsockopen si no hay libreria curl, tambien algunas funcionalidades un poco mas importantes como obtener todos los alts de las imagenes y obtener todas las links. No obstante creo que funcionara de maravillas para lo que necesito.
Ejemplo de uso;
$webFetch=Spider::getWebFull('http://technorati.com/');
print_r($webFetch);
//@author Eugenio Fage
abstract class Spider {
public function getWebFull($url){
$htmlCode=self::getWebCode($url);
if($htmlCode=='') return array();
$return['title']=self::getTitle($htmlCode);
$return['metas']=self::getMetas($htmlCode);
$return['text']=self::justText($htmlCode);
return $return;
}
public function getWebCode($url){
//@todo si no existen las curl functions usar fsockopen
$ch = curl_init();
curl_setopt ($ch, CURLOPT_URL, $url);
curl_setopt($ch, CURLOPT_FOLLOWLOCATION, true);
curl_setopt($ch, CURLOPT_RETURNTRANSFER, true);
curl_setopt($ch, CURLOPT_USERAGENT, "Mozilla/4.0 (compatible; MSIE 5.01; Windows NT 5.0)");
$data = curl_exec ($ch);
curl_close ($ch);
return $data;
}
public function getTitle($html,$charset=null){
//@todo corregir acentos sin usar multi byte functions
$arr=array();
preg_match_all('@(<title>(.*)</title>)@i',$html,$arr);
$arr=$arr[2];
//el titulo no va a ser mas largoque 100 caracteres
return(substr(strip_tags($arr[0]),0,110));
}
public function getMetas($html,$charset=null){
//@todo corregir acentos sin usar multi byte functions
$arr=array();
preg_match_all('@(meta\sname=\"(.*)\"\scontent=\"(.*)\"[ /]*>)@i',$html,$arr);
$meta=$arr[2];
$content=$arr[3];
unset($arr);
while(($unMeta=array_pop($meta))){
$metas[strtolower($unMeta)]=array_pop($content);
}
while(($unMeta=array_pop($meta))){
$metas[strtolower($unMeta)]=array_pop($content);
}
preg_match_all('@(meta\scontent=\"(.*)\"\sname=\"(.*)\"[ /]*>)@i',$html,$arr);
$meta=$arr[3];
$content=$arr[2];
unset($arr);
while(($unMeta=array_pop($meta))){
$metas[strtolower($unMeta)]=array_pop($content);
}
return $metas;
}
public function justText($html,$charset=null){
//@todo corregir acentos sin usar multi byte functions
$html=str_replace('>','> ', $html);
$buscar=array('@<!--.*?-->@si','@<script[^>]*?>.*?</script>@si','@<style[^>]*?>.*?</style>@si');
$html = preg_replace($buscar, ' ', $html);
$html = preg_replace('@<.*?>@si', ' ', $html);
$html=str_replace('<',' ',$html);
$html=str_replace('>',' ',$html);
$html=html_entity_decode(strip_tags($html));
$html=str_replace(array('<','>','>','<',"\t",chr(13),chr(10),chr(160)),' ',$html);
while(strpos($html,' ')!==false){
$html=str_replace(' ',' ',$html);
}
return substr($html,0,1500);
}
}
Benchmarking de funciones
Hola, en muchos blogs en los que se habla de optimizacion en el codigo php puede leerse que la funcion include es mas rapida que require y que include_once.
Asi mismo tambien se sabe que incluir un archivo con su ruta completa es mas rapido que incluir un archivo sin su ruta correspondiente. A continuacion voy a comentar como se llega a estas conclusiones por medio de una herramienta de benchmark, aunque no es necesario hacer un benchmark para saber todo esto, basta con leer el manual de php y saber algo de sistemas operativos
1) Primero les copiare el objeto Benckmark, que es el que voy a usar para los testeo.
<?php
/**
* Benchmarking for PHP applications
*
* Benchmark class provides an easy way to meassure the performance
* of different parts of your PHP applications. You can get any
* counters as you want in the same page execution, and get the output
* via html output or file.
*
* LICENCE
* ========
* copyright (c) 2000 Patxi Echarte [patxi@eslomas.com]
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public License
* version 2.1 as published by the Free Software Foundation.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Lesser General Public License for more details at
* http://www.gnu.org/copyleft/lgpl.html
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*
* @package Benchmark
* @category Benchmarking
* @version $Id: Benchmark.class.php,v 1.2 2005/06/07 $
* @author Patxi Echarte <patxi@eslomas.com>
*/
class Benchmark{
var $__start_times; //contendrá los tiempos de inicio para cada contador
var $__stop_times;
var $__delta_points;
/**
* Constructor
*
* @access public
*/
function Benchmark(){
$this->_start_times = array();
$this->_stop_times = array();
$this->_delta_points = array();
}
/**
* Inicializa un contador interno de benchmarking. Se le puede asignar un nombre
* específico para llevar diferentes contadores en la misma petición
*
* @param string $name nombre del contador, por defecto 'default'
* @access public
*/
function timingStart ($name = 'default') {
$this->_start_times[$name] = explode(' ', microtime());
}
/**
* Detiene un contador de benchmarking.
*
* @param string $name nombre del contador, por defecto 'default'
* @access public
*/
function timingStop ($name = 'default') {
$this->_stop_times[$name] = explode(' ', microtime());
}
/**
* Devuelve el tiempo transcurrido para el contador que se indique, hasta
* el momento actual si no se ha detenido ya el contador, o hasta el
* momento en el que se detuvo en contador
*
* @param string $name nombre del contador, por defecto 'default'
* @return int número de milisegundos transcurridos
* @access public
*/
function timingCurrent ($name = 'default') {
if (!isset($this->_start_times[$name])) {
return 0;
}
if (!isset($this->_stop_times[$name])) {
$stop_time = explode(' ', microtime());
}
else {
$stop_time = $this->_stop_times[$name];
}
// do the big numbers first so the small ones aren't lost
$current = $stop_time[1] - $this->_start_times[$name][1];
$current += $stop_time[0] - $this->_start_times[$name][0];
return $current;
}
/**
* Añade un punto intermedio en el contador, de forma que el contador
* continúa activo y cuando lo visualicemos obtengamos su información
* y la de todos sus puntos intermedios
*
* @param string $txt identificador de texto para el punto, por defecto ''
* @param string $name nombre del contador, por defecto 'default'
* @access public
*/
function addDeltaPoint($txt='',$name='default'){
if(!is_array($this->_delta_points[$name]))
$this->_delta_points[$name] = array();
$this->_delta_points[$name][] = array('texto' => $txt, 'time' => explode(' ',microtime()));
}
/**
* Devuelve un array con el contenido de todos los puntos intermedios de
* ejecución del contador que se indique. Su formato es:
* array(texto=>nombre del punto, time=> milisegundos).
* De esta forma obtenemos para un contador lo que le ha costado llegar a cada
* punto intermedio desde el anterior, teniendo una imagen clara de que tareas
* han costado más y cuales menos.
*
* @param string $name nombre del contador, por defecto 'default'
* @return array con los puntos y los milisegundos que ha costado llegar a ellos
* @access public
*/
function getDeltaPoints($name='default'){
if(!is_array($this->_delta_points[$name])) return;
$ini = array($this->_start_times[$name][0],$this->_start_times[$name][1]);
foreach($this->_delta_points[$name] as $id => $point){
$delta = $point['time'][1] - $ini[1];
$delta += $point['time'][0] - $ini[0];
$result[] = array(texto => $point['texto'], 'time' => $delta);
$ini = $point['time'];
}
return $result;
}
/**
* Devuelve una tabla HTML con el contenido de todos los puntos intermedios
* para el contador indicado.
*
* @param string $name nombre del contador, por defecto 'default'
* @return string con el contenido de la tabla html
* @access public
*/
function getDeltaPointsHtmlTable($name='default'){
if(!is_array($this->_delta_points[$name])) return;
$ini = array($this->_start_times[$name][0],$this->_start_times[$name][1]);
$res = '';
$res = '<table border="1">';
foreach($this->_delta_points[$name] as $id => $point){
$delta = $point['time'][1] - $ini[1];
$delta += $point['time'][0] - $ini[0];
$res .= "<tr><td>$point[texto]</td><td>$delta</td></tr>";
$ini = $point['time'];
}
$res .= "<tr><td><b>Total</b></td><td>" . $this->timingCurrent($name) . "</td></tr></table>";
return $res;
}
/**
* Escribe en el archivo que se indique una nueva línea al final del archivo,
* con el contenido de cada punto intermedio, en forma de incrementos sobre
* el punto anterior. Cada valor se escribe separado por comas para poder ser
* leido fácilmente con CSV
*
* @param string $name nombre del contador, por defecto 'default'
* @param string $file nombre del archivo a escribir, por defecto '/tmp/phpbenchmarck.log'
* @access public
*/
function saveDeltaPointsToFile($name='default',$file='/tmp/phpbenchmarck.log'){
if(!is_array($this->_delta_points[$name])) return;
$ini = array($this->_start_times[$name][0],$this->_start_times[$name][1]);
foreach($this->_delta_points[$name] as $id => $point){
$delta = $point['time'][1] - $ini[1];
$delta += $point['time'][0] - $ini[0];
$result[] = number_format($delta,8,",",".");
$ini = $point['time'];
}
$line = implode(';',$result);
//abro el fichero y escribo la línea con LOCK!!!
$fp = @fopen($file, 'a');
@flock($fp, LOCK_EX);
@fputs($fp,$line."\n");
@flock($fp, LOCK_UN);
}
}
?>
2) Bien, ahora voy a crear una carpeta llamada includes, donde voy a meter archivos del tipo unNumero.php, y cada archivo contendra 3 asignaciones y una operacion de suma.
Yo voy a meter uno 100 archivos, con la siguiente scritp, ustedes en sus casa pueden usar el bloc de notas, jajaja
for ($i=0;$i<99;$i++){
$caracteres=array('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o');
shuffle($caracteres);
$var1='$'.array_shift($caracteres).array_shift($caracteres).array_shift($caracteres);
$var2='$'.array_shift($caracteres).array_shift($caracteres).array_shift($caracteres);
$var3='$'.array_shift($caracteres).array_shift($caracteres).array_shift($caracteres);
$out='<? '.$var1.'='.rand().'; '.$var2.'='.rand().'; '.$var3.'='.$var1.'+'.$var2.'; ?>';
$file=fopen('includes/'.$i.'.php','w');
fwrite($file,$out);
fclose($file);
}
3) Testeando el tiempo de respuesta, ahora necesitamos crear 3 archivos;
require.php: este se encargara de usar la funcion require
<?php
include('Benchmark.class.php');
$bench=new Benchmark();
$bench->timingStart('test');
escribir();
$mInicio=memory_get_usage();
for ($i=0;$i<99;$i++){
require('includes/'.$i.'.php');
}
$mFin=memory_get_usage();
$bench->addDeltaPoint('fin de test require', 'test');
echo 'requiere uso: '.($mFin-$mInicio).' bytes<br>';
$bench->saveDeltaPointsToFile('test','require.log');
$bench->timingStop();
function escribir(){
for ($i=0;$i<99;$i++){
$caracteres=array('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o');
shuffle($caracteres);
$var1='$'.array_shift($caracteres).array_shift($caracteres).array_shift($caracteres);
$var2='$'.array_shift($caracteres).array_shift($caracteres).array_shift($caracteres);
$var3='$'.array_shift($caracteres).array_shift($caracteres).array_shift($caracteres);
$out='<? '.$var1.'='.rand().'; '.$var2.'='.rand().'; '.$var3.'='.$var1.'+'.$var2.'; ?>';
$file=fopen('includes/'.$i.'.php','w');
fwrite($file,$out);
fclose($file);
}
}
?>
Luego el archivo inlcude_once.php que testeara la funcion include_once;
<?php
include('Benchmark.class.php');
$bench=new Benchmark();
$bench->timingStart('test');
escribir();
$mInicio=memory_get_usage();
for ($i=0;$i<99;$i++){
include_once('includes/'.$i.'.php');
}
$mFin=memory_get_usage();
$bench->addDeltaPoint('fin de test include_once', 'test');
echo 'include_once uso: '.($mFin-$mInicio).' bytes<br>';
$bench->saveDeltaPointsToFile('test','include_once.log');
$bench->timingStop();
function escribir(){
for ($i=0;$i<99;$i++){
$caracteres=array('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o');
shuffle($caracteres);
$var1='$'.array_shift($caracteres).array_shift($caracteres).array_shift($caracteres);
$var2='$'.array_shift($caracteres).array_shift($caracteres).array_shift($caracteres);
$var3='$'.array_shift($caracteres).array_shift($caracteres).array_shift($caracteres);
$out='<? '.$var1.'='.rand().'; '.$var2.'='.rand().'; '.$var3.'='.$var1.'+'.$var2.'; ?>';
$file=fopen('includes/'.$i.'.php','w');
fwrite($file,$out);
fclose($file);
}
}
?>
Y por ultimo include.php que testeara la funcion include;
<?php
include('Benchmark.class.php');
$bench=new Benchmark();
$bench->timingStart('test');
escribir();
$mInicio=memory_get_usage();
for ($i=0;$i<99;$i++){
include('includes/'.$i.'.php');
}
$mFin=memory_get_usage();
$bench->addDeltaPoint('fin de test include', 'test');
echo 'include uso: '.($mFin-$mInicio).' bytes<br>';
$bench->saveDeltaPointsToFile('test','include.log');
$bench->timingStop();
function escribir(){
for ($i=0;$i<99;$i++){
$caracteres=array('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o');
shuffle($caracteres);
$var1='$'.array_shift($caracteres).array_shift($caracteres).array_shift($caracteres);
$var2='$'.array_shift($caracteres).array_shift($caracteres).array_shift($caracteres);
$var3='$'.array_shift($caracteres).array_shift($caracteres).array_shift($caracteres);
$out='<? '.$var1.'='.rand().'; '.$var2.'='.rand().'; '.$var3.'='.$var1.'+'.$var2.'; ?>';
$file=fopen('includes/'.$i.'.php','w');
fwrite($file,$out);
fclose($file);
}
}
?>
Bien, espero que hagan las pruebas y veran que el include es el mas rapido y menos costoso, ademas si agregamos la ruta completa, cosa que yo no hice en los ejemplos, veran que el tiempo de carga es todavia menor.
Saludos, Eugenio
Solucion de los expertos del problema anterior de los buscadores
Hola, ya ha terminado el primer round de codejam, segun lo que lei los mejores 840 pogramadores pasaran al segundo round.
Si entran a http://code.google.com/codejam/contest podran ver los problemas y las resoluciones propuestas por los programadores.
Como particularidad al problema de los buscadores, que comente en el post anterior me gustaria mostrarle algunos datos;
De los top 20, el que menos tardo en resolver el problema marco unos 10 minutos, mientras que al que mas tardo le tomo unas 2 horas la resolucion dle problema. El promedio de resolucion del problema de los top 20 fue de 36 minutos.
De esos 20 programadores catorce usaron C++, cuatro usaron JAVA, uno uso Haskell y uno uso LISP.
A continuacion voy a copiar la solucion propuesta por el que califico primero, su apodo es rem.
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <ctime>
using namespace std;
typedef long long int64;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<double> vd;
#define _CRT_SECURE_NO_WARNINGS
#define For(i,a,b) for (int i(a),_b(b); i <= _b; ++i)
#define Ford(i,a,b) for (int i(a),_b(b); i >= _b; --i)
#define Rep(i,n) for (int i(0),_n(n); i < _n; ++i)
#define Repd(i,n) for (int i((n)-1); i >= 0; --i)
#define Fill(a,c) memset(&a, c, sizeof(a))
#define MP(x, y) make_pair((x), (y))
#define All(v) (v).begin(), (v).end()
template<typename T, typename S> T cast(S s) {
stringstream ss;
ss << s;
T res;
ss >> res;
return res;
}
template<typename T> inline T sqr(T a) { return a*a; }
template<typename T> inline int Size(const T& c) { return (int)c.size(); }
template<typename T> inline void checkMin(T& a, T b) { if (b < a) a = b; }
template<typename T> inline void checkMax(T& a, T b) { if (b > a) a = b; }
char buf[1024*1024];
int main() {
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);
gets(buf);
For(test, 1, atoi(buf)) {
int s, q;
map<string,int> num;
gets(buf);
s = atoi(buf);
Rep(i, s) {
gets(buf);
num[buf] = i;
}
gets(buf);
q = atoi(buf);
vi dp(s, 0);
Rep(i, q) {
gets(buf);
assert(num.count(buf) > 0);
int id = num[buf];
Rep(j, s)
if (j != id)
checkMin(dp[j], dp[id]+1);
dp[id] = 1000000;
}
printf("Case #%d: %d\n", test, *min_element(All(dp)));
}
exit(0);
}
Saludos!
Mi primera participacion en CODEJAM
No solo mi primera presentacion en el google codejam, si no tambien mi primer post. Lamentablemente no pude clasificar por que falle. Cometi el error de intentar resolver los problemas con ansi c, lo cierto es que no soy muy bueno con el y perdi mucho tiempo, por lo que opte por usar PHP.
A continuacion voy a traducir el problema, y voy a mostrarles la solucion que propuse, el algoritmo funciona correctamente y resuelve el problema.
Hay una leyenda urbana que dice que si buscas Google en Google el universo hara implosion. Tenemos un secreto para contarte… es cierto! por favor no lo intentes o le cuentes a alguien. Bien, solo estamos bromeando.
Esto es cierto en un universo muy muy lejano. En ese universo, si buscas el nombre del buscador en que te encuentras ese universo se destruira.
Para combatir con esto, tenemos una interesante solucion. Todas las busquedas esran puestas juntas. Seran pasadas a un sistema central que decide que decide que busqueda va a cada buscador. El sistema central manda una serie de busquedas a un buscador, y puede cambiar a otro buscador en cualquier momento. Las busquedas son procesadas en el orden que se van recibiendo. El sistema central nunca enviara una busqueda que sea igual al nombre del buscador en el que esta, en ese caso debera cambiar de buscador. Para reducir costos, el numero de cambios de buscador a buscador debe ser minimo.
Como entrada para resolver este problema contaremos con un archivo, que tendra el siguiente formato;
En la primer linea dira la cantidad de casos a resolver, luego nos describiran los N casos,de la siguiente forma;
numero de buscadores
buscadores1
buscadores2
buscadoresN
numero de busquedas
busqueda1
busqueda2
busquedaNEjemplo;
2
5
Yeehaw
NSM
Dont Ask
B9
Googol
10
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol
5
Yeehaw
NSM
Dont Ask
B9
Googol
7
Googol
Dont Ask
NSM
NSM
Yeehaw
Yeehaw
GoogolY la salida de este ejemplo seria;
Case #1: 1
Case #2: 0
La solucion que yo propuse es la siguiente;
Casos::loadData("datos.in");
$i=1;
while(($caso=array_shift(Casos::$Casos))){
echo 'Case #'.$i.': '.$caso->calcular()."\r\n";
$i++;
}
class Caso{
public $engines=array();
public $querys=array();
public function calcular(){
$aux=$this->engines;
$total=0;
while (($qry=array_shift($this->querys))){
$aux=$this->quitar($qry,$aux);
if(count($aux)==0){
$aux=$this->quitar($qry,$this->engines);
$total++;
}
}
return $total;
}
public function quitar($qry,$unaArr){
$aux=array();
while(($aEng=array_shift($unaArr))){
if($qry!=$aEng){
array_push($aux,$aEng);
}
}
return $aux;
}
}
abstract class Casos{
public static $Casos=array();
public function loadData($file){
$archivo = file($file);
$i=0;
for($m=0;$m<$archivo[0];$m++){
$caso=new Caso();
$i++;
$totalEng=$archivo[$i];
for($j=0;$jengines,$archivo[$i]);
}
$i++;
$totalQry=$archivo[$i];
for($j=0;$jquerys,$archivo[$i]);
}
array_push(self::$Casos,$caso);
}
}
}
Para el que quiera el problema original en ingles puede hacerlo en http://code.google.com/codejam/