Tag Archive for 'function'

Partition Function

The problem is to enumerate all the ways in which a given number can be written as sum of two or more positive integers. For example 5 can be written as [4, 1], [3, 1, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1], [2, 2, 1] and [3, 2].

I used a recursion to solve the problem. The recursion works like this. Write 5 as 4 + 1. Recurse for 4. 5 can also be written as 3 + 2. Recurse for 3. We are done!

Below is a piece of code written in Java to do the same. I use a map to store pre-computed values. Using the code, I have found the answer for 60. It takes a minute though.

There is this problem on project euler – Problem 76 – which requires one to find the number of ways 100 can be partitioned. Using the above code, I get a heap space error for 100. I suppose instead of enumerating all the ways, to solve the project euler problem, I should try to just count all the possibilities. This might me much quicker.

Here is the java code for the above recursion.

 

    /**
     * Find all the ways of writing a given number as sum of positive integers
     *
     * @param n the number whose partitions are to be found
     * @return the set of all the partitions of the number
     */
    public static List<List<Integer>> partitionFunction(int n) {
        return NumberRepresentations.partitionFunction(n, 1, new HashMap<Integer, Map<Integer, List<List<Integer>>>>());
    }

    /**
     * Find all the ways of writing a given number as sum of positive integers
     *
     * @param number the number whose partitions are to be found
     * @param minValue the minimum value of any partition number
     * @return the set of all the partitions of the number
     */
    private static List<List<Integer>> partitionFunction(int number, int minValue,
            Map<Integer, Map<Integer, List<List<Integer>>>> preComputedValues) {
        if (preComputedValues.containsKey(number)) {
            List<List<Integer>> prePartitions = preComputedValues.get(number).get(minValue);
            if (prePartitions != null) return prePartitions;
        }

        List<List<Integer>> partitions = new ArrayList<List<Integer>>();
        partitions.add(Arrays.asList(number));
        if (number == 1) return partitions;

        int rightVal;
        for (int leftVal = number - 1; leftVal >= (rightVal = number - leftVal); leftVal--) {
            if (rightVal < minValue) continue;
            for (List<Integer> leftNumbers : NumberRepresentations.partitionFunction(leftVal, rightVal,
                    preComputedValues)) {
                List<Integer> tempList = new ArrayList<Integer>(leftNumbers);
                tempList.add(number - leftVal);
                partitions.add(tempList);
            }
        }

        Map<Integer, List<List<Integer>>> prePartitions = preComputedValues.get(number);
        if (prePartitions == null) preComputedValues.put(number,
                prePartitions = new HashMap<Integer, List<List<Integer>>>());
        prePartitions.put(minValue, partitions);

        return partitions;
    }

Popularity: 6% [?]

Project Euler : Quadratic Producing Longest Prime Sequence

Problem 27 done! Ah well, nothing spectacular as such, but solved none the less. It’s a happy feeling.

The problem required one to find a quadratic of the form x^2 + a \times x + b, with the condition |a| < 1000, |b| < 1000 which produces the longest sequence of primes starting with x = 0.

Let us call f(x) = x^2 + a \times x + b

The first thing you notice is that the values of b must belong to the set of primes and they must always be positive.

f(0) = b, and hence b has to be a prime

The next thing to notice is that the values of a are influenced by that of b.

f(1) = 1 + a + b is a prime \Rightarrow a = [prime] – (1+b)

So all I did was to generate primes. Set b as one of the primes. Let a iterate over the other primes and form a polynomial function for each combination. This polynomial function was evaluated for ascending values of x and the longest sequence of primes recorded in each case. I used the commons-math-2.1 library by Apache commons to evaluate the quadratic function.

I did one additional thing. The problem mentions that the quadratic function n^2 + n + 41 generates a sequence of 40 primes. You must have noted that these polynomials cannot produce a sequence longer than the value of the constant term, which is b in our case (to see this, evaluate the expression with x = b). So for 0 < b < 41 the above is the best quadratic there is. Thus we need to begin at 41.

Below is my solution which runs in 1600ms on my laptop. Not good enough though :( .

public class Problem_27 {
	public static UnivariateRealFunction getPrimeNumberFunction() throws FunctionEvaluationException {
		PrimeNumbers primeGenerator = new PrimeNumbers(100000);
		List<Integer> primes = primeGenerator.getPrimeNumbers();
		int upperLimit = primeGenerator.getPrimeIndex(997);
		int lowerLimit = primeGenerator.getPrimeIndex(41);

		double[] coefficients = new double[3];
		coefficients[2] = 1;
		MaxObject<UnivariateRealFunction> maxLength = MaxObject.init();

		Stopwatch sw = new Stopwatch();
		sw.start();
		for (int i = upperLimit; i >= lowerLimit; i--) {
			coefficients[0] = primes.get(i);
			for (int j = 0; j < upperLimit; j++) {
				coefficients[1] = primes.get(j) - coefficients[0] - 1;
				UnivariateRealFunction quadratic = new PolynomialFunction(coefficients);
				maxLength.compare(quadratic, Problem_27.getSeriesLength(quadratic, primes));
			}
		}
		sw.stop();
		System.out.println(sw);

		return maxLength.getMaxObject();
	}

	private static int getSeriesLength(UnivariateRealFunction function, List<Integer> primes)
	        throws FunctionEvaluationException {
		for (int i = 0; true; i++) {
			int value = (int) function.value(i);
			if (value < 0 || !primes.contains(value))
				return i;
		}
	}
}

Popularity: 8% [?]

A Logger In C

Now I am working on this fair scheduling for my B Tech Project (BTP). Already having written a 1000 lines of code, it is a great pain to debug it. More so if you do not know which function might have caused the error. I needed a logger which could log all the events. The events include entering a function, any important calculation/decision it makes, any return values, so that if my program breaks down I can exactly pinpoint the source of error simply looking at the log file generated.

I have no idea if any inbuilt logging functionality exists for C programs or not. Either way, I did not have much time to google up and learn how to use it. I decided to make my own logger, a simple one, which would serve my purpose. It hardly took me 10 minutes to get over with it.

One of the important functionalities that I wanted my logger to have is indentation. The log should be properly indented, just the same way as we indent the code. When the program control enters a new function, the logging should get indented to right, and when it leaves the function, the logging should get indented by the same amount to the left. So I defined two macros, $$INDENT$$ and $$OUTDENT$$. To make them work, I defined a global variable – $$logIndent$$. The $$logIndent$$ would at any given time contain the amount of space by which the log has to be indented. Obviously, I initialized it with 0. Also defined is a global variable called $$indentVal$$ which is the amount of spaces with which the indentation should take place. I like the value to be 2. The two macros are

#define INDENT logIndent += indentVal
#define OUTDENT logIndent -= indentVal

int indentVal = 2;
int logIndent = 0;

I defined another macro called $$SPACES$$ which would print the number of spaces to produce the required indentation.

int tempIndent;
FILE *logFile;
#define SPACES for(tempIndent = 0; tempIndent < logIndent; tempIndent++) fprintf(logFile, " ");

Obviously $$tempIndent$$ is a globally declared temporary variable and $$logFile$$ is the file pointer to the file where the log has to be written. I initialize the $$logFile$$ pointer in the $$main()$$ part of my program.

And finally coming to the logger, I created a custom $$printf()$$ statement using the $$vprintf()$$ command. I call my logger as $$LogThis()$$. Its declaration is as follows

void LogThis(const char *format, ...);

It is constructed as follows

void LogThis(const char *format, ...) {
  va_list args;
  va_start(args, format);
  SPACES;
  vfprintf(logFile, format, args);
  va_end(args);
}

That’s it ! To use this logger, I have to do the following in my function :

#include <stdio .h>
#include <stdarg .h>
void TestLogger() {
  int returnVal;
  float retVal;

  LogThis("<testlogger>\n");
  INDENT;

  /**
   *  Inside the function do whatever you want to
   */

  LogThis("Returns: %d, %f\n", retrunVal, retVal)

  OUTDENT;
  LogThis("</testlogger>\n");
}

Done ! A well indented log will be produced. This has really helped me debug the code. I do not have to gdb from the last point that worked in my program. Instead, I know which function the program control was in when it threw an error. I need to gdb from that function onwards only, thus reducing the debuging time considerably. Also, in case of errors, I can increase the debugging data for that particular function, thus eliminating the need to use gdb at all.

Popularity: 3% [?]

php – Sessions

After a long long time I was back to coding in php. And by long time, I mean atleast 24 months ! Believe me, it wasn’t easy. More so because of the higher standard I have set for myself. My code this time shall be much neater and easier to read than it ever was.

The past four years of my life has been spent coding. And when you code so long, you modify your habits to get tuned to the proper way of coding. As it is said, a person spends more time reading a code than writing it. So this time I am taking special care of writing simpler and smaller functions so as to make the code more readable. Also, since I have been reading a lot of OOP these days, I am intent on providing an abstraction layer for the user, so that at the top most level coding should appear like writing a few english sentences rather than some cryptic mysqli_select_db things.

This is the first time I am trying to code in php following the OOP structure. Also, though this might seem strange, it is the first time I am using session variables in my design! Below is a trivia I had not known earlier, and spent 2 hours trying to understand what was wrong in my seemingly proper and correct code.

A session created with session_start will only be available to pages within the directory tree of the page that first created it.

i.e. If the page that first creates the session is /dir1/dir2/index.php and the user then goes to any page above dir2 (e.g. /dir1/index.php), session_start will create a new session rather than use the existing one.

Also I found the following class to be useful.

< ?php
class Session {
public static function Init() {
self::Commence();
}

public static function Set($fld, $val) {
self::Commence();
$_SESSION[$fld] = $val;
}

public static function un_set($fld) {
self::Commence();
unset($_SESSION[$fld]);
}

public static function Destroy() {
self::Commence();
unset($_SESSION);
session_destroy();
}

public static function Get($fld) {
self::Commence();
return $_SESSION[$fld];
}

public static function is_set($fld) {
self::Commence();
return isset($_SESSION[$fld]);
}

private function Commence() {
if(!isset($_SESSION['ready'])) {
session_start();
$_SESSION['ready'] = TRUE;
}
}
}
?>
Reblog this post [with Zemanta]

Popularity: 2% [?]

php5 OOP – Function Overloading

PHP

PHP

Starting php4, object oriented concepts have been made available to the programmer. Though not well developed, they paved the way for a more complete implementation of the OOP basics in the php5 version. However, one thing that remains lacking is the ability ot overload the functions.

Overloading of functions is quite an useful feature. In the simplest form, it gives you the freedom to declare a class with more than one constructors.

Not to get disheartened though, we have a simple enough way to work around this short coming. In php, when a call is made to a function that does not exist, then the control searches for the __call() function. We make use of this to carve out the over loading feature that we need.

Below, I am writing the code for a Register class which has two variables – name and pass. The constructor is being overloaded here.

class Register {
private $name;
private $pass;

public function Register() {
$num = func_num_args();
$args = func_get_args();

$funcName = 'Register'.$num;
$this->__call($funcName, $args);
}

private function Register0() {
$this->name = '';
$this->pass = '';
}

private function Register2($name, $pass) {
$this->name = $name;
$this->pass = $pass;
}

public function __call($funcName, $args) {
$this->call_user_func_array(array($this, $funcName), $args);
}

public function setName($name) {
$this->name = $name;
}

public function setPass($pass) {
$this->pass = $pass;
}
} // Register

// regA is using the Register2() constructor
$regA = new Register('Anu', '@#$#@$@$');

// regB is using the Register0() contructor
// and subsequently setting the values of name, pass
$regB = new Register();
$regB->setName('Anu');
$regB->setPass('@#$#@$@$');
Reblog this post [with Zemanta]

Popularity: 2% [?]

Variadic Functions

C is a beautiful language. Though I have been using it for a few years now, I have yet completely mastered it. Just now, I stumbled across what are called variadic functions.

Have you ever wondered how to write functions that take in variable numbers or arguments? Take for instance printf() or scanf(). Both have been implemented in C. These are called variadic functions.

Problem: To construct a function which can take variable number of inputs, eg; printf()

Solution:

Its a simple matter of using built in macros defined in the stdarg.h library. It provides the following macros:

  • va_list: The list of argument
  • va_start: Initializes va_list to the first unnamed argument
  • va_arg: Takes the current variable and the type
  • va_end: Called at the end

Through a self explaining example I would like to demonstrate the usage of these macros. Let us define a new function called PBAPrint() which imitates the printf() function.  For example,

PBAPrint(“df”, 12, 2.2) outputs: int = 12 float = 2.2

PBAPrint is implemented as follows:


void PBAPrint(char *format, ...) {
  va_list ap;

  va_start(ap, format);

  while(*format) {
    if(*format == 'd')
      printf("int = %d ", va_arg(ap, int));
    else if(*format == 'f')
      printf("float = %f ", va_arg(ap, float));
    else {
      printf("unsupported format ");
      break;
    }
    format++;
  }

  va_end(ap);

  return;
}

But apparently things are much more simpler when using C++.

Popularity: 1% [?]