Sunday, January 31, 2016

A fast way to find out whether two elements in matrix share the same diagonal

Let's have the following matrix:

     1 2 3 4 5
     -----------
1 | 0 0 0 0 0
2 | 0 0 1 0 0
3 | 0 0 0 0 0
4 | 1 0 0 0 0
5 | 0 0 0 0 0

with two points: (x1, y1) = (2, 3) and (x2, y2) = (4, 1).

The fastest way to find out whether these two points share the same diagonal is the result of this expression:

bool result = (x1 + y1 == x2 + y2) or (x1 - y1 == x2 - y2)

Now let's complicate the task. Given matrix n x n with m points, find the minimum number of diagonals which contain at least two points. The first line of the input contains: n m. The next m lines contain points with coordinates (xi, yi).

Saturday, January 16, 2016

dmalloc: compiling and installing a dynamic (shared) library

See the previous post: dmalloc: compiling and installing a static library

"dmalloc.h:484:7: error: expected identifier or..." problem is already solved in that post.

Now let's compile and install a shared library

dmalloc-5.5.2]$ ./configure --enable-shlib

dmalloc-5.5.2]$ make shlib
...
gcc -g -O2 -DHAVE_STDARG_H=1 -DHAVE_STDLIB_H=1 -DHAVE_STRING_H=1 -DHAVE_UNISTD_H=1 -DHAVE_SYS_MMAN_H=1 -DHAVE_SYS_TYPES_H=1 -DHAVE_W32API_WINBASE_H=0 -DHAVE_W32API_WINDEF_H=0 -DHAVE_SYS_CYGWIN_H=0 -DHAVE_SIGNAL_H=1 -I. -I. -c dmalloc_argv.c -o ./dmalloc_argv.o
rm -f dmalloc
gcc -o aout dmalloc.o dmalloc_argv.o compat.o env.o \
-L.
mv aout dmalloc
rm -f libdmalloc.so libdmalloc.so.t
ld -shared --whole-archive -soname libdmalloc.so -o libdmalloc.so.t libdmalloc.a arg_check.o compat.o dmalloc_rand.o dmalloc_tab.o env.o heap.o chunk.o error.o malloc.o
ld: libdmalloc.a(arg_check.o): relocation R_X86_64_32 against `.rodata.str1.8' can not be used when making a shared object; recompile with -fPIC
libdmalloc.a(arg_check.o): error adding symbols: Bad value
Makefile:259: recipe for target 'libdmalloc.so' failed
make: *** [libdmalloc.so] Error 1


Tuesday, January 12, 2016

dmalloc: compiling and installing a static library

dmallochttp://dmalloc.com/

Installation (on Fedora 21 x86_64)

$ uname -irs

Linux 3.18.3-201.fc21.x86_64 x86_64

$ tar -zxvf dmalloc-5.5.2.tgz
dmalloc-5.5.2]$ cd dmalloc-5.5.2/
dmalloc-5.5.2]$ ./configure
configure: configurations for the dmalloc library
configure: build utilities
checking for gcc... gcc
...
checking for strtok... yes
configure: creating ./config.status
config.status: creating Makefile
config.status: creating conf.h
config.status: executing dmalloc.h.2 commands
config.status: executing settings.h commands
configure: 
configure: Please check-out Makefile and conf.h to make sure that
configure: sane configuration values were a result.
configure: 
configure: You may want to change values in settings.h before
configure: running 'make'.
configure: 
configure: To run the basic library tests, you can execute:
configure:   make light
configure: or
configure:   make heavy
configure:

dmalloc-5.5.2]$ make
rm -f dmalloc.h dmalloc.h.t
cat ./dmalloc.h.1 dmalloc.h.2 ./dmalloc.h.3 > dmalloc.h.t
mv dmalloc.h.t dmalloc.h
rm -f arg_check.o
gcc -g -O2  -DHAVE_STDARG_H=1 -DHAVE_STDLIB_H=1 -DHAVE_STRING_H=1 -DHAVE_UNISTD_H=1 -DHAVE_SYS_MMAN_H=1 -DHAVE_SYS_TYPES_H=1 -DHAVE_W32API_WINBASE_H=0 -DHAVE_W32API_WINDEF_H=0 -DHAVE_SYS_CYGWIN_H=0 -DHAVE_SIGNAL_H=1  -I. -I.  -c arg_check.c -o ./arg_check.o
In file included from /usr/include/string.h:634:0,
                 from arg_check.c:33:
dmalloc.h:484:7: error: expected identifier or ‘(’ before ‘__extension__’
 char *strndup(const char *string, const DMALLOC_SIZE len);
       ^
Makefile:362: recipe for target 'arg_check.o' failed
make: *** [arg_check.o] Error 1