C code:

#include <stdio.h>
#include <math.h>

/* Prints the n-th fraction in Cantor's enumeration. */ void print_fraction(int n) { int d = (-1 + sqrt(1 + 8 * n)) / 2; /* Diagonals to skip */ int e = n - d * (d + 1) / 2; /* Extra steps after the skip. */ int v1 = e <= 1 ? d + e : d + 2 - e; int v2 = e <= 1 ? 1 : e;

printf("%d / %d\n", d % 2 == 0 ? v1 : v2, d % 2 == 0 ? v2 : v1); }

int main() { size_t i; for (i = 1; i < 20; i++) { print_fraction(i); } }

Output:
1 / 1
1 / 2
2 / 1
3 / 1
2 / 2
1 / 3
1 / 4
2 / 3
3 / 2
4 / 1
5 / 1
4 / 2
3 / 3
2 / 4
1 / 5
1 / 6
2 / 5
3 / 4
4 / 3

It is already given that the loop is formed at the second node of the linked list, i.e. the second node has two incoming links, one from the first and the other from the last node. The address of the last node that links to the second node and forms the loop needs to be found.

/* Solution to a problem asked at:
   http://www.orkut.co.in/Main#CommMsgs?cmm=1027&tid=5470285126748556338

Author: Susam Pal */

#include <stdio.h> #include <stdlib.h>

struct node { int data; struct node *next; };

/* Detects the loop and returns the address to the last node that links to the second node, i.e. head->next. Consumes O(1) memory and O(n) time. */ struct node *last_node(struct node *head) { struct node *p1; struct node *p2;

p1 = p2 = head->next; while (p1->next != p2->next->next) { p1 = p1->next; p2 = p2->next->next; } return p1; }

struct node *create_node(int data) { struct node *p; p = (struct node *) malloc(sizeof *p); p->data = data; return p; }

int main() { struct node *p; struct node *head; struct node *second; struct node *second_node;

p = head = create_node(1); p = p->next = create_node(2); p = p->next = create_node(3); p = p->next = create_node(4); p = p->next = create_node(5); p = p->next = create_node(6); p = p->next = create_node(7); p->next = head->next; /* Loop to second node */

p = last_node(head); printf("Last node has address %p and data %d.\n", p, p->data); return 0; }

Output from my system:
Last node has address 0x7330d0 and data 7.

#include <iostream>
#include <string>
using namespace std;

#include "STAF.h" #include "STAFString.h"

int main(int argc, char **argv) { STAFString name("foo"); STAFHandlePtr handle;

int rc = STAFHandle::create(name, handle); if (rc != 0) { cerr << "Could not create STAF handle; error code: " << rc << endl; return 1; }

STAFResultPtr result = handle->submit("127.0.0.1", "VAR", "RESOLVE STRING {STAF/Env/DUMMY}"); if (result->rc != 0) { cerr << "Could not run STAF command; error code: " << rc << endl; return 1; }

STAFString output = result->result; cout << "Output: " << output.buffer() << endl; }

Output:
C:\MixedBag\debug>echo
%DUMMY%
Why__does__it__break

C:\MixedBag\debug>STAFExperiments.exe Output: Why__does__it__break/Env/DUMMY}}

The '/Env/DUMMY' at the end is garbage. The results are not '\0'-terminated in the result-buffer. The correct way to get the output is as follows:
cout << "Output: " << string(output.buffer(), output.length()) << endl;

Today, I learnt how to create an aggregate function in PostgreSQL function that wraps the functionality provided by other PostgreSQL aggregate functions. In this attempt, I created a cv() function that calculates the coefficient of variation. Effectively, cv(x) is equivalent to stddev(x) / avg(x).

Table to be used for verifying the function

susam@nifty:~/math$ createdb statistics
susam@nifty:~/math$ cat perf.sql
CREATE TABLE performance
(
    name VARCHAR,
    duration DOUBLE PRECISION
);

INSERT INTO performance VALUES ('RAND', 101.0);
INSERT INTO performance VALUES ('ZERO', 157.0);
INSERT INTO performance VALUES ('NONE', 209.0);
INSERT INTO performance VALUES ('TEST', 176.0);
INSERT INTO performance VALUES ('UNIT', 197.0);
INSERT INTO performance VALUES ('LOAD', 193.0);
INSERT INTO performance VALUES ('FREE', 198.0);
susam@nifty:~/math$ psql statistics
psql (8.4.3)
Type "help" for help.
statistics=# \i perf.sql
DROP TABLE
CREATE TABLE
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
statistics=# select * from performance;
 name | duration
------+----------
 RAND |      101
 ZERO |      157
 NONE |      209
 TEST |      176
 UNIT |      197
 LOAD |      193
 FREE |      198
(7 rows)

statistics=#

Extracting details required to create the function

statistics=# SELECT aggtransfn, aggfinalfn, aggtranstype::regtype, agginitval
statistics-# FROM pg_aggregate
statistics-# WHERE aggfnoid='stddev(double precision)'::regprocedure;
  aggtransfn  |     aggfinalfn     |    aggtranstype    | agginitval
--------------+--------------------+--------------------+------------
 float8_accum | float8_stddev_samp | double precision[] | {0,0,0}
(1 row)

statistics=# SELECT aggtransfn, aggfinalfn, aggtranstype::regtype, agginitval
statistics-# FROM pg_aggregate
statistics-# WHERE aggfnoid='avg(double precision)'::regprocedure;
  aggtransfn  | aggfinalfn |    aggtranstype    | agginitval
--------------+------------+--------------------+------------
 float8_accum | float8_avg | double precision[] | {0,0,0}
(1 row)

statistics=#

The function

susam@nifty:~/math$ cat cv.sql
CREATE OR REPLACE FUNCTION finalcv(double precision[])
RETURNS double precision
AS $$
    SELECT float8_stddev_samp($1) / float8_avg($1);
$$ LANGUAGE SQL;

CREATE AGGREGATE cv(double precision)
(
    sfunc = float8_accum,
    stype = double precision[],
    finalfunc = finalcv,
    initcond = '{0, 0, 0}'
);

susam@nifty:~/math$

Usage and verification:

susam@nifty:~/math$ psql statistics
psql (8.4.3)
Type "help" for help.

statistics=# select stddev(duration), avg(duration) from performance;
      stddev      |       avg
------------------+------------------
 37.1682147873178 | 175.857142857143
(1 row)

statistics=# select stddev(duration) / avg(duration) as cv from performance;
        cv
-------------------
 0.211354592616754
(1 row)

statistics=# \i cv.sql
CREATE FUNCTION
CREATE AGGREGATE
statistics=# select cv(duration) from performance;
        cv
-------------------
 0.211354592616754
(1 row)

statistics=#

Bessel's correction

I checked whether Bessel's correction was used in the stddev() function of PostgreSQL. Yes, it was used.

susam@nifty:~$ octave -q
octave:1> std([101, 157, 209, 176, 197, 193, 198], 0)
ans =  37.168
octave:2> std([101, 157, 209, 176, 197, 193, 198], 1)
ans =  34.411
octave:3>

The std() function in MATLAB and GNU Octave applies Bessel's correction when invoked with the second argument as 0.

A list of how zero length regex is handled in various tools, programming languages, etc. All of them compile the zero length regex pattern and the regex matches all strings. It makes sense to me because if the regex pattern is a substring of a given string, it should match the given string. Zero length string ("") is a substring of every string.

grep

susam@swift:~\$ echo -ne "foo\nbar\n" | grep ""
foo
bar

Perl

susam@swift:~\$ perl -e 'print(("foo" =~ //) .  "\n")'
1

Python

susam@swift:~\$ python
Python 2.5.2 (r252:60911, Jan  4 2009, 21:59:32)
[GCC 4.3.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> re.compile('').search('foo')
<_sre.SRE_Match object at 0x7fc6c5a2c510>

Java

susam@swift:~\$ cat RegexExperiment.java
import java.util.regex.Pattern;
import java.util.regex.Matcher;

public class RegexExperiment
{
    public static void main(String[] args)
    {
        System.out.println(Pattern.compile("").matcher("foo").find());
    }
}
susam@swift:~\$ javac RegexExperiment.java && java RegexExperiment
true

Scheme:

susam@swift:~\$ mzscheme
Welcome to MzScheme v4.0.1 [3m], Copyright (c) 2004-2008 PLT Scheme Inc.
> (regexp-match "" "foo")
("")

LISP:

susam@swift:~\$ clisp
  i i i i i i i       ooooo    o        ooooooo   ooooo   ooooo
  I I I I I I I      8     8   8           8     8     o  8    8
  I  \ `+' /  I      8         8           8     8        8    8
   \  `-+-'  /       8         8           8      ooooo   8oooo
    `-__|__-'        8         8           8           8  8
        |            8     o   8           8     o     8  8
  ------+------       ooooo    8oooooo  ooo8ooo   ooooo   8

Welcome to GNU CLISP 2.44.1 (2008-02-23) <http://clisp.cons.org/>

Copyright (c) Bruno Haible, Michael Stoll 1992, 1993 Copyright (c) Bruno Haible, Marcus Daniels 1994-1997 Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998 Copyright (c) Bruno Haible, Sam Steingold 1999-2000 Copyright (c) Sam Steingold, Bruno Haible 2001-2008

Type :h and hit Enter for context help.

[1]> (regexp:match "" "foo") #S(REGEXP:MATCH :START 0 :END 0)

libpcre3:

susam@swift:~\$ ls -l /usr/lib/libpcre.so*
lrwxrwxrwx 1 root root     17 May  3 15:15 /usr/lib/libpcre.so -> libpcre.so.3.12.1
lrwxrwxrwx 1 root root     17 Jan  6 14:57 /usr/lib/libpcre.so.3 -> libpcre.so.3.12.1
-rw-r--r-- 1 root root 162816 Jul 14  2008 /usr/lib/libpcre.so.3.12.1
susam@swift:~\$ cat pcre.c
#include <stdio.h>
#include <string.h>
#include <pcre.h>

#include <stdio.h>
#include <string.h>
#include <pcre.h>

int main(int argc, char **argv)
{
    pcre *p;
    char *re = "";
    char *s  = "foo";
    const char *errmsg;
    int errpos;
    int ovector[10];
    int ret;

    p = pcre_compile(re, 0, &errmsg, &errpos, NULL);
    ret = pcre_exec(p, NULL, s, strlen(s), 0, 0,
                    ovector, sizeof ovector / sizeof *ovector);

    printf(ret < 0 ? "no match\n" : "match\n");
}

susam@swift:~\$ gcc -lpcre pcre.c && ./a.out
match
Newer | Older
RSS