Recortes de codigo / Code Snippets

Monday, January 4, 2021

Showing how virtual methods & inheritance work in C++

#include<iostream>

using namespace std;

class Base {
   public: virtual void f() { cout << "Base" << endl; }
};

class D1 : public Base {
   void f() { cout << "D1" << endl; }
};

class D2 : public Base { 
   void f() { cout << "D2" << endl; } 
};

void pointer(Base *b)    { b->f(); }
void reference(Base &b)  { b.f();  }
void base(Base b)        { b.f();  }

#define test_pointer(x)   cout << "pointer   " #x << ": "; pointer(x);
#define test_reference(x) cout << "reference " #x << ": "; reference(x);
#define test_base(x)      cout << "base      " #x << ": "; base(x);

void test_objects() {
    cout << "-- test_objects --" << endl;
    D1 d1;
    D2 d2;
    
    test_pointer(&d1); test_pointer(&d2);   // D1 D2
    test_reference(d1); test_reference(d2); // D1 D2
    test_base(d1); test_base(d2);           // Base Base
}

void test_pointer_to_base_class() {
    cout << "-- test_pointer_to_base_class --" << endl;
    Base *pd1 = new D1();
    Base *pd2 = new D2();
    
    test_pointer(pd1); test_pointer(pd2);       // D1 D2
    test_reference(*pd1); test_reference(*pd2); // D1 D2
    test_base(*pd1); test_base(*pd2);           // Base Base
    
    delete pd1;
    delete pd2;
}

void test_pointer_to_class() {
    cout << "-- test_pointer_to_class --" << endl;
    D1 *pd1 = new D1();
    D2 *pd2 = new D2();
    
    test_pointer(pd1); test_pointer(pd2);       // D1 D2
    test_reference(*pd1); test_reference(*pd2); // D1 D2
    test_base(*pd1); test_base(*pd2);           // Base Base

    delete pd1;
    delete pd2;
}

int main()
{
    test_objects();
    test_pointer_to_base_class();
    test_pointer_to_class();
}

Expected output:

-- test_objects --
pointer   &d1: D1
pointer   &d2: D2
reference d1: D1
reference d2: D2
base      d1: Base
base      d2: Base
-- test_pointer_to_base_class --
pointer   pd1: D1
pointer   pd2: D2
reference *pd1: D1
reference *pd2: D2
base      *pd1: Base
base      *pd2: Base
-- test_pointer_to_class --
pointer   pd1: D1
pointer   pd2: D2
reference *pd1: D1
reference *pd2: D2
base      *pd1: Base
base      *pd2: Base

See it working here

Other entries:

Saturday, May 9, 2020

Add 2 integers without using + operator

int sum(int a, int b) {
    int s = a ^ b;        // partial sum
    int c = (a & b) << 1; // carry
    
    // carry? 
    while( c != 0 ) {
        // yes -> sum it, recalc carry
        int newc = (s & c) << 1;
        s = s ^ c;
        c = newc;
    }
    
    return s;
}

Other entries:

Saturday, March 14, 2020

isPrime recursive

#include <iostream>
using namespace std;

int increments[] = { 2, 4 };

// Already beyond the square root? -> true (prime)

// (else)

// Divisible by current divisor?   -> false (not prime)

// (else)

// Calculate next divisor and recurse
bool isPrime(int n, int divisor, int incr) {
   return (divisor * divisor > n ) || 
          ( (n % divisor != 0) &&

            isPrime(n, divisor + incr, increments[incr == 2] )

          );
}
 
bool isPrime(int n) {
    return isPrime(n, 2, 1);
}

int main()
{
    for(int i = 2; i <= 100; i++ ) {
        if( isPrime(i) ) {
            cout << i << " ";
        }
    }
    cout << endl;

    return 0;
}

Other entries:

Sunday, March 1, 2020

Generate random numbers without repetition

Instead of controlling the repetition by inserting the already-generated-number in a set, create the set first, pick from there, and remove it for the next iteration,

e.g.:

import java.util.Random;

public class ControlRepetitionWithoutKeepingScore {

     public static void main(String []args) {

         int choices[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
         int sz = choices.length;
         Random random = new Random();
         
         for(int i = 0; i < choices.length; i++ ) {
             int pos = random.nextInt(sz);
             print(choices[pos]);
             
             choices[pos] = choices[sz-1];
             sz--;
         }
     }
}

Other entries:

Sunday, February 16, 2020

Shuffle characters in a String (java)

Converts chars to List --> Collections.shuffle --> String.join

import java.util.Collections;
import java.util.List;
import java.util.Arrays;

public class Shuffler {

     public static void main(String []args){
        String s = "012345";
        
        for( int i = 0; i < 10; i++) {
           System.out.println(shuffle(s));
        }
     }
     
     public static String shuffle(String s) {
        List<String> chars = Arrays.asList(s.split(""));
        Collections.shuffle(chars);
        return String.join("", chars);
     }
}

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: