Friday, June 19, 2015

Euler problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Answer 

First we can see that for any even Fibonacci number the sum of all the previous even and odd Fibonacci is equal.

each even Fibonacci number es preceded by 2 odd fib numbers. 
o o e o o e
1 1 2 3 5 8....

This means that we can transform each of the even Fibonacci in the sum of the 2 previous odd Fibonacci .

so n being any even Fibonacci and f(n) the sum of all even Fibonacci up to n we have:



Also the sum of all Fibonacci numbers up to fib(x) is equal to fib(x+2)-1 (I wont prove this because is not part of the question).

so given any number f we find x by calculating the closest Fibonacci  number fib(x) that is even and less than or equal to f . We then can finally compute  fib(x+2)-1.

The code:


long fibCalculation ( int i, double golden )
{

   
return pow ( golden, i ) / sqrt ( 5 ) + 0.5 ;
}


long findSumEvenFibUpto ( int number )
{

   
const double golden = ( 1 + sqrt ( 5 ) ) / 2 ;
   
long nearest = round ( log ( sqrt ( 5 ) * number ) / log ( golden ) ) ;
   
   
int fib = 0 ;
   
while ( ( fib = fibCalculation ( nearest -- , golden ) ) % 2 || fib > number ) ;
   
   
return ( fibCalculation ( nearest + 3 , golden ) - 1 ) / 2 ;
}

Euler problem 1

Problem:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

Answer

We just need to calculate the sum of all divisible by 3 then add the sum of all divisible by 5 and finally remove the sum of all divisible by 15 (both divisible by 3 and 5).

Code:


double gaussSum ( double number )
{
   
return ( number * ( number + 1 ) ) / 2 ;
}
//Proyect euler 1
int SumMulti3and5 ( int numero )
{  
   
int total = ( 3 * gaussSum ( numero / 3 ) ) + ( 5 * gaussSum ( numero / 5 ) ) ;
   
int menos = 15 * gaussSum ( numero / 15 ) ;

   
return total - menos ;
}

Saturday, June 13, 2015

Number to word spanish translator

This is an implementation of a number to word  translator with a divide and conquered approach.
Here are some enumeration y used for the tens, suffix and units:

Enums


package numberTranslator;

import java.util.Arrays;
import java.util.Comparator;


public enum ExSpanishSufix {

 
    ciento("s",2), 
    mil("",3),
    millon("es",6), 
    billon("es",9),
    trillon("es",12),
    quadrillion("es",15);
 
 
    private String plural;
    private int exponent;
    private long value;
 
    private ExSpanishSufix(String plural, int exponent){
  
        this.plural= plural;
        this.exponent=exponent;
        this.value=(long)Math.pow(10, exponent);
  
    } 
 
    public static ExSpanishSufix[] getSorted(){
  
        ExSpanishSufix[] values= ExSpanishSufix.values();
        Arrays.sort(values, 
          Comparator.comparing((ExSpanishSufix hex) -> hex.getExponent()));
  
        return values;
    }
 
    public String isPlural(long number){
  
        return this.name()+(number>1?plural:"");
    }
 
    public int getExponent(){
  
        return exponent;
    }
 
    public long getValue(){
  
        return value;
    }
 
 
}
package numberTranslator;

import java.util.Arrays;
import java.util.Comparator;

public enum SpanishDigits {

    cero(0), uno(1),dos(2),tres(3),cuatro(4),cinco(5),seis(6),siete(7),ocho(8),
    nueve(9), dies(10), once(11), doce(12), trece(13), catorce(14), quince(15);
 
    private int number;
 
    private SpanishDigits(int pnumber){
        number=pnumber;
    }
 
    public static SpanishDigits[] getSorted(){
  
        SpanishDigits[] values= SpanishDigits.values();
        Arrays.sort(values, 
            Comparator.comparing((SpanishDigits hex) -> hex.getNumber()));
        return values;
    }
 
 
    public int getNumber(){
  
        return number;
    }
 
}
package numberTranslator;

import java.util.Arrays;
import java.util.Comparator;

public enum SpanishTens {

    dies(10,"dieci"), veinte(20,"veinti"), treinta(30), cuarenta(40), 
    cincuenta(50), sesenta(60), setenta(70), ochenta(80), 
    noventa(90), cien(100);
 
    private int number;
    private String plural;
 
 
    private SpanishTens(int pnumber, String pplural){
  
        number= pnumber;
        plural=pplural;
  
    }
    private SpanishTens(int pnumber){
  
        this(pnumber,"");
    }
 
    public String isPlural(int pnumber){
  
        if(pnumber>number && plural!="")
            return plural;
  
        return name(); 
    }
 
    public static SpanishTens[] getSorted(){
  
        SpanishTens[] values= SpanishTens.values();
        Arrays.sort(values, 
            Comparator.comparing((SpanishTens des) -> des.getNumber()));
        return values;
    }
 
    public int getNumber(){
  
        return number;
    }
 
}

Interface 


package numberTranslator;

public interface ILangNumber {

    public ILangNumber add(ILangNumber number);
    public ILangNumber multiply(ILangNumber number);
    public ILangNumber divide(ILangNumber number);
    public ILangNumber pow(ILangNumber exponent);
    public long getNumber();
 
}
package numberTranslator;

public abstract class AbstractLangNumber implements ILangNumber {

    private long number;
    private String parseNumber;
 
    public AbstractLangNumber(long number){
   
        this.number=number;
        parseNumber=parseNumber(number);
  
    } 
 
    @Override
    public ILangNumber add(ILangNumber number) {
  
        long add= getNumber()+ number.getNumber(); 
        return createNumber(add);
    }

    @Override
    public ILangNumber multiply(ILangNumber number) {
  
        long mult= getNumber()*number.getNumber();
        return createNumber(mult);
    }

    @Override
    public ILangNumber divide(ILangNumber number) {
  
        long divide= getNumber()/number.getNumber();
        return createNumber(divide);
    }

    @Override
    public ILangNumber pow(ILangNumber exponent) {

        long pow= (long)Math.pow(getNumber(), exponent.getNumber());
        return createNumber(pow);
    }

    @Override
    public long getNumber() {
        return number;
    }
 
 
    abstract protected String parseNumber(long number);
 
    abstract protected ILangNumber createNumber(long number);

    @Override
    public String toString(){
  
        return parseNumber;
    }
}

Implementation 


package numberTranslator;

public class SpanishNumber  extends AbstractLangNumber{


    public static SpanishDigits[] digits= SpanishDigits.getSorted();
    public static SpanishTens[] tens= SpanishTens.getSorted();
    public static ExSpanishSufix[] exponents= ExSpanishSufix.getSorted();
 
    public SpanishNumber(long number) {
        super(number);
    }
 
    @Override
    protected String parseNumber(long number) {
  
        if(number == Long.MIN_VALUE)
            throw new IllegalArgumentException();
  
        StringBuilder sb= new StringBuilder();
        sb.append(getSing(number));
        format(Math.abs(number),sb);  
  
        return especialCases(sb.toString());
    }

    @Override
    protected ILangNumber createNumber(long number) {
        return new SpanishNumber(number);
    }
 

    private void format( long number, StringBuilder sb){

        if(number<=100)
            baseCase((int)number, sb);
        else
        {
    
            ExSpanishSufix suf= findSufix(number);
            long leading= number/suf.getValue();

            if(leading > 1) 
                format(leading, sb);

            sb.append((suf.getExponent() == 2 ? "" : " "))
            .append(suf.isPlural(leading)).append(" ");

            format( number % suf.getValue(), sb);
        }

    }

    private String especialCases(String numero){
        if(numero.isEmpty())
            return "cero";
 
        return numero.replaceAll("cincocientos", "quinientos")
        .replaceAll("nuevecientos", "novecientos")
        .replaceAll("sietecientos", "setecientos");
    }
 
    private void baseCase(int magnitud, StringBuilder sb) {
  
        if(magnitud<16)
            sb.append(magnitud>0?digits[magnitud].name():"");
        else
        {
            sb.append(tens[(magnitud/10)-1].isPlural(magnitud));
            getUnits(magnitud,digits,sb);
        }
    }
 
    private ExSpanishSufix findSufix(long number)
    {
        long expon= nearestPowerOf10(number);
  
        int suf=0;
  
        while(suf<exponents.length-1 && expon>=exponents[suf+1].getExponent())
           ++suf;

        return exponents[suf];
  
    }
 
    private String getSing(long numero){
   
        return numero<0?"menos ":"";
    }
 
    private void getUnits(int numero, SpanishDigits[] digits, StringBuilder sb){

        int residuo=numero%10;

        if(residuo!=0)
        { 
            String divisor= numero>30?" y ":"";
            sb.append(divisor).append(digits[residuo]);
        }
     }
 
    private int nearestPowerOf10(long number){
   
        int n = 0;
        long f[]={10000000000000000L,100000000,10000,100,10};
        for(int i =0, j=16; i<f.length; i++, j/=2)
        { 
            if(number>=f[i])
            { 
                number/=f[i];
                n+=j; 
            }
        }
        return  n;
    }
}

Friday, June 12, 2015

Exercise 6.2-2

6.2-2 Starting with the procedure MAX-HEAPIFY, write pseudocode for the procedure MIN-HEAPIFY(A, i), which performs the corresponding manipulation on a minheap. How does the running time of MIN-HEAPIFY compare to that of MAXHEAPIFY?

Answer 


The running time is the same we just need to find the smallest instead of the greatest.

Code in C++ (code is taken from a heap implementation I made, so A is not a parameter):


void Heap :: minHeapiFy ( unsigned index )
{
   
unsigned child = getLeft ( index ) ;

   
if ( child >= getHeapSize ( ) )
       
return ;

   
if ( child < getHeapSize ( ) - 1 && heapArray [ child ] > heapArray [ child + 1 ] )
       
++ child ;

   
if ( heapArray [ index ] > heapArray [ child ] )
   
{
        swap
( heapArray [ child ] , heapArray [ index ] ) ;
        minHeapiFy
( child ) ;
   
}
}

Exercise 6.1-7

Show that, with the array representation for storing an n-element heap, the leaves are the nodes indexed by :


Answer


We can define that a node at an index i is a leave if and only if



We can check if this definition holds for:


so we have: 



since the rest are greater the result of multiplying them by 2 will also be greater than n


Exercise 6.1-4

Where in a max-heap might the smallest element reside, assuming that all elements are distinct.

Answer 


Since all elements are distinct we have:


so the smallest most reside in any of the leaves.

Exercise 6.1-3

Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree.

Answer

The base case is trivial since is given by the definition of a max heap. Then we have that for any sub tree of size m so that the index of the root is i. The definition of a max heap can be applied recursively on the child's of i (2i and 2i+1) so by transitivity i most be the largest.

Thursday, June 11, 2015

List heap sort implementation in java

Code:


import java.util.Comparator;
import java.util.List;


public class Sort {

	
	private Sort(){throw new AssertionError();}
	
	
	private static <T extends Comparable<? super T>> 
	void heapify(Comparator<? super T> c, int index, List<T> arreglo, int size)
	{
		
		while(2*index+1<size)
		{
			int left= 2*index+1;
			
			if(left<(arreglo.size()-1) && compare(left,left+1,arreglo,c)<0)
				++left;
			
			if(compare(index,left,arreglo,c)>=0)
				break;
				
			exchange(arreglo, index, index=left);
		}
		
	}
	
	public static <T extends Comparable<? super T>> 
	void heapSort( List<T> arreglo, Comparator<? super T> c)
	{
		int last= arreglo.size()-1;
		
		for(int i= (arreglo.size()/2)-1; i>-1;--i)
			heapify(c, i, arreglo, last+1);
			
		while(last>0)
		{
			exchange(arreglo, last--, 0);
			heapify(c, 0, arreglo, last);
		}			
		
	}
	
	public static <T extends Comparable<? super T>> 
	void heapSort( List<T> arreglo)
	{
		heapSort( arreglo, (x,y)->x.compareTo(y));
	}
	
	private static <T extends Comparable<? super T>> 
	void exchange(List<T> arreglo, int index1, int index2)
	{
		arreglo.set(index2,arreglo.set(index1, arreglo.get(index2)));	
	}
	
	private static<T extends Comparable<? super T>> 
	int compare(int index, int index2, List<T> lista, Comparator<? super T> compare)
	{
		
		return compare.compare(lista.get(index),(lista.get(index2)));
		
	}
}

Friday, June 5, 2015

Problem 4-6 Monge arrays



Answers 

for a n x m matriz

a.

So we need to proof this:


The right implication is trivial as we can see that the left operand of the if only if is just a especial case of the monge definition. 

So to proof the left implication we assumed


and so we try to proof the monge definition by induction(fist on the rows as the hint suggested):

so we can use our assumption on k :



So using our inductive hypothesis we get:


For this to work l must be l=j+1 but when proving the same thing for the rows we then prove it for all possible k,l,j,i. 

b.

37 23 24 32 
21  6   7  10 
53 34 30 31 
32 13  9   6 
43 21 15  8

c. It can be proved by contradiction.

We make the assumption:  

being A[i,f(i)] and A[i+1,f(i+1)] the leftmost minimums, this must be false:

And so we prove it by contradiction 

d. 

This hold for all the odd rows:

So we just need to find the minimum between those bounds. 

The run time for finding all the leftmost minimums for the odd rows is given by the summation:

e.

Since each time the size is split to just the even rows and the merge step takes O(n+m), the run time
of the algorithm is given by the recurrence:


we analyse it using the recursion tree method and we can ignore the ceiling since it wont affect the asintotic behavior. The base case is O(1) since m is constant so assuming that n is a power of 2 there is lg(n) levels and each one takes m constant time so:




The code for the algorithm is:

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int findMin(int* array, int init, int finale){
    int index = 0;
   
    for (int min = INT_MAX; init < finale; ++init)
    {
        if (min > array[init])
        {
            min = array[init];
            index = init;
        }
    }
    return index;
}

void divideAndConquereMonge(int **matrizMonge, int* leftmost, int rows, int factor, int column){

    if (rows == 1)
        leftmost[0] = findMin(matrizMonge[0], 0, column);
    else
    {
   
        int mid = static_cast<int>(std::ceil(rows / 2.0));
        divideAndConquereMonge(matrizMonge, leftmost, mid, 2 * factor, column);

        for (int i = 1; i < rows - 1; i+= 2)
        {
            int dev = factor * i, end = leftmost[dev + factor] + 1;    
            leftmost[dev] = findMin(matrizMonge[dev], leftmost[dev - factor], end);
        }

        if (rows % 2 == 0)
        {
            int dev = factor * (rows - 1);
            leftmost[dev] = findMin(matrizMonge[dev], leftmost[dev - factor], column);
        }
    }
}

Rust 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
fn left_most_minimum(monge: &[i32], from: usize, to: usize) -> usize {
    let mut min = monge[from];

    (from + 1..to).fold(from, |m,i| {
        if monge[i] < min {
            min = monge[i];
            i
        } else {
            m
        }
    })
}

fn minimums(monge: &[i32], leftmost: &mut Vec<usize>, rows: usize, columns: usize, factor: usize) {
    if rows == 1 {
        leftmost[0] = left_most_minimum(monge, 0, columns) % columns;
    } else {
        let mid = rows - (rows / 2);
        minimums(monge, leftmost, mid, columns, 2 * factor);

        let map = |i, j| (i * columns) + j;

        let x_rows = (0..)
            .map(|x| factor * (2 * x + 1))
            .take_while(|&x| x < (rows - 1));

        for row in x_rows {          
            let (from, to) = (map(row, leftmost[row - factor]),
                              map(row, leftmost[row + factor] + 1));
                             
            leftmost[row] = left_most_minimum(monge,from,to) % columns;
        }

        if rows % 2 == 0 {
            let row = factor * (rows - 1);
            let (from, to) = (map(row, leftmost[row - factor]),
                              map(row, columns));
                               
            leftmost[row] = left_most_minimum(monge, from, to) % columns;
        }
    }
}

fn monge_left_most_minimums(monge: &[i32], rows: usize) -> Option<Vec<usize>> {
    
    let size = monge.len();
    if rows == 0 || size % rows != 0 { return None; }
    
    let mut left_mosts = vec![0; rows];
    minimums(&monge, &mut left_mosts, rows, size / rows, 1);
    Some(left_mosts)
} 

fn main() {
    let row = 7;
    let monge = vec![
        10, 17, 13, 28, 23,
        17, 22, 16, 29, 23,
        24, 28, 22, 34, 24,
        11, 13,  6, 17,  7,
        45, 44, 32, 37, 23,
        36, 33, 19, 21,  6,
        75, 66, 51, 53, 34,
    ];
    println!("{:?}", monge_left_most_minimums(&monge, row));
    
}