Recortes de codigo / Code Snippets: 2019

Monday, August 5, 2019

isPrime, optimization 4

Check every number and keep the previosly generated primes. Use them to test the following numbers.

const int PSIZE = 150000;
int primes[PSIZE];
int sz = 0;

bool isPrime4( int x ) {
  if(x < 2) return true;

  int limit = (int) sqrt(x);
  primes[sz] = limit+1;
  for(int *p = primes; *p <= limit; p++) {
      if( x % *p == 0 ) {
          return false;
      }
  }
  assert(sz < PSIZE);
  primes[sz++] = x;
     
  return true;
}

Other entries:

isPrime, optimization 3

Divisors start in 5. Skip the divisors that are multiple of 2 or 3.

bool isPrime3( int x ) {
  if( x == 2 || x == 3) {
      return true;
  }
  
  if( x % 2 == 0 || x % 3 == 0 ) {
      return false;
  }

  int divisor = 5;
  int delta = 2;
  int limit = (int) sqrt(x);
  while( divisor <= limit ) {
        if( x % divisor == 0 ) { 
            return false;
        }
        divisor += delta;
        delta = 6 - delta;
  }
  return true;
}

Other entries:

isPrime, optimization 1

It is not necessary to check divisors bigger than the square root of the number.

bool isPrime1( int x ) {
  int limit = (int) sqrt(x);
  for( int divisor = 2; divisor <= limit; divisor++ ) {
        if( x % divisor == 0 ) { 
            return false;
        }
  }
  return true;
}

isPrime, optimization 2

Only divide by odd numbers, until the square root of the number.

bool isPrime2( int x ) {
  if( x == 2 ) {
      return true;
  }
  if( x % 2 == 0 ) {
      return false;
  }

  int limit = (int) sqrt(x);
  for( int divisor = 3; divisor <= limit; divisor += 2 ) {
        if( x % divisor == 0 ) { 
            return false;
        }
  }
  return true;
}

Other entries:

Saturday, July 27, 2019

Sort java list, lambda comparators

import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.Comparator;
 
public class Person {
     String name;
     int age;
 
     public Person(String name, int age) {
         this.name = name;
         this.age = age;
     }
 
     public
     static void sort(List<Person> l, String title, Comparator<Person> comp) {
                                 
         Collections.sort(l, comp);
         
         System.out.println(title);
         for(Person p: l) {
             System.out.println(p.name + " " + p.age);
         }
     }
 
     public static void main(String []args){
         ArrayList<Person> l = new ArrayList<>();
         l.add(new Person("A", 30));
         l.add(new Person("B", 29));
         l.add(new Person("C", 28));
         l.add(new Person("D", 27));
 
         sort(l, "Sorting by name", (p1, p2) -> p1.name.compareTo(p2.name));
         sort(l, "Sorting by age", (p1, p2) -> (p1.age - p2.age));
     }
}

Friday, July 19, 2019

Merge 2 sorted lists, merged list has reversed order

     List mergeReverse2(List list1, List list2, List soFar) {
         if(list1 == null && list2 == null) { 
             return soFar;
         }
         List following;
         if(list1 == null || list1.dato > list2.dato) {
             following = list2.next;
             list2.next = soFar;
             return mergeReverse2(list1, following, list2);
         }
         if(list2 == null || list1.dato <= list2.dato) {
             following = list1.next;
             list1.next = soFar;
             return mergeReverse2(following, list2, list1);
         }
         
         return null;
     }

Other entries:

Merge 2 sorted lists

     List merge(List list1, List list2) {
         if(list1 == null && list2 == null) {
             return null;
         }
         if(list1 == null || list1.dato > list2.dato) {
             list2.next = merge(list1, list2.next);
             return list2;
         }
         if(list2 == null || list1.dato <= list2.dato) {
             list1.next = merge(list1.next, list2);
             return list1;
         }
         
         return null;
     }

Tuesday, July 9, 2019

isPrime, Naive Version

bool isPrime0( int x ) {
  for( int divisor = 2; divisor < x; divisor++ ) {
        if( x % divisor == 0 ) { 
            return false;
        }
  }
  return true;
}

Other entries:

Sunday, July 7, 2019

Fibonacci

Version iterativa

#include <iostream>
using namespace std;

int fibonacci( int n ) {
    if( n == 0 || n == 1 ) {
       return n;
    }
    
    //  prev2 -> prev1 -> fib (prev1 + prev2)
    int prev2 = 0;
    int prev1 = 1;
    int fib;
    for(int i = 2; i <= n; i++) {
        fib = prev1 + prev2;
        prev2 = prev1;
        prev1 = fib;
    }
    
    return fib;
}
 
int main() {
    for(int i = 0; i < 10; i++) {
        cout << "fib " << i << " = " << fibonacci(i) << endl;
    }

    return 0;
}

Decimal a binario

Version recursiva

#include <iostream>
using namespace std;

string binario(int x) {
    string s = (x > 1) ? binario(x / 2) : "";
    s += to_string(x % 2);
    return s;
}

int main() {
    for(int i = 0; i < 256; i++) {
        cout << i << " " << binario(i) << endl;
    }
}

Other entries: