Showing posts with label code. Show all posts
Showing posts with label code. Show all posts

08 January 2014

Abusing the C Preprocessor

On a whim, I thought of this idea after reading Cory Li's article on bytecode hacking for Battlecode, MIT's premier Independent Activities Period competition, and after reading some code of his bot, which won Battlecode 2012. Optimized code gets real messy real fast, so wouldn't it be nice if it could be (just a little) easier to write?

The C and sibling languages have a wonderful feature called preprocessing. This feature allows one to insert snippets of text character for character into another file, so as to save time and space writing redundant code. The most prevalent use of the preprocessor is for including header files:

#include <stdio.h>

int
main()
{
    printf("%s\n", "Hello, world!");
    return 0;
}

Another use of the preprocessor is to define macros. For example, in competitive programming, one iterates from 0 (inclusive) to N (exclusive) reasonably often, so why spend the time to type

for (int i = 0; i < N; ++i)
{
   // ...
}

when it can be compressed to

F(i, N)
{
   // ...
}

all with the simple macro

#define F(i, N) for (int i = 0; i < N; ++i)

Now it's great that C offers this, but what about languages that don't, such as Java? Is there a way to make the C preprocessor do this for us?

The answer, unsurprisingly, is yes! We can use cpp (that's c preprocessor)

cpp test.c

to find all the macros in our code, as defined by #define, replaces them with the value with which they are defined, and removes the #define. However, it leaves some junk in the code, namely some lines at the beginning of the files starting with #, so we have to remove those before giving the preprocessed file to javac.

So how do we put all of this together? We first write C-ified Java code Test.cjava with our macro

import java.util.*;

#define F(i, N) for (int i = 0; i < N; ++i)

public class Test {
    public static void main(String[] args) {
        F(i, 5) {
            System.out.println(i);
        }
        System.exit(0);
    }
}

and preprocess it with cpp to generate the almost-legitimate Java code. We can strip the aforementioned lines that start with # by passing the output of cpp to sed with a regex that deletes any line that starts with # and redirect the sanitized output to our desired Java file

cpp Test.cjava | sed '/^#/d' > Test.java

Finally, we compile Test.java and run it with java Test, which will produce the desired output

0
1
2
3
4

18 August 2013

Union Find

I never understood the point of union find (not after learning it in high school with Dr. Nevard, or even after learning about Kruskal's minimum spanning tree algorithm) until I saw this problem:

A journey to the Moon

The member states of the UN are planning to send two people to the Moon. But there is a problem. In line with their principles of global unity, they want to pair astronauts in such a way, that both are citizens of different countries.

There are N astronauts numbered with identifiers from 0 to N-1. They are qualified and trained to be sent to the moon. But the trouble is that those in charge of the mission haven’t been directly informed about the citizenship of each astronaut. The only information they have is that some particular pairs of astronauts belong to the same country.

Your task is to compute in how many ways they can pick a pair of astronauts satisfying the above criteria, to be sent to the moon. Assume that you are provided enough pairs to let you identify the groups of astronauts even though you might not know their country directly. For instance, if 1,2,3 are astronauts from the same country; it is sufficient to mention that (1,2) and (2,3) are pairs of astronauts from the same country without providing information about a third pair (1,3).


Input Format

The first line contains two integers, N and I separated by a single space. I lines follow. each line contains 2 integers separated by a single space A and B such that

0 ≤ A, B ≤ N-1

and A and B are astronauts from the same country.


Output Format

An integer containing the number of permissible ways in which a pair of astronauts can be sent to the moon.


Constraints

1<=N<=10^5

1<=I<=10^6


Sample Input

4 2
0 1
2 3


Sample Output

4

Explanation

As persons numbered 0 and 1 belong to same country and 2 and 3 belong to same country. So the UN can choose one person of 0,1 and one out of 2,3. So number of ways of choosing pair is 4.

This pre formatting sucks, but that's beside the point.

Here's my solution:

class DisjointSet(object):
    def __init__(self, vals):
        self.parents = {x: x for x in vals}
        
    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            return self.find(self.parents[x])
    
    def union(self, x, y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        self.parents[xRoot] = yRoot
        
    def sets(self):
        d = {}
        for child in self.parents:
            parent = self.find(child)
            if parent not in d:
                d[parent] = set()
            d[parent].add(child)
        return d        

N, L = map(int, raw_input().strip().split())
ds = DisjointSet(range(N))
for i in range(1, L+1):
    a, b = map(int, raw_input().strip().split())
    ds.union(a, b)

s = ds.sets()
acc = 0
if len(s) > 1:
    cumsum = [len(x) for x in s.values()]
    for i in range(len(cumsum)-2, 0, -1):
        cumsum[i] += cumsum[i+1]
    
    for i, x in enumerate(s.values()[:-1]):
        acc += len(x) * cumsum[i+1]
        
print acc

Maybe someday I will get proper code formatting for my blog.

09 December 2012

Back to Triple Displays


I nabbed two Dell Ultrasharp 2007s on ebay for $230 shipped. Unfortunately, the guy forgot to ship power and DVI cables; guess I'll be haggling the price down after finals week to compensate for the loss -_-. I also have to massage xmonad a bit to get display focusing and desktop switching just right.

Also I'm quite confident that I change setups as quickly as Bayley acquires new computers as a typical girl dumps her boyfriend. Not sure who I'm insulting =P.

Aaaaand before I forget, I'm posting my xorg.conf because I absolutely do not want to dig through the internet just to re-set up this configuration again.
# nvidia-settings: X configuration file generated by nvidia-settings
# nvidia-settings:  version 304.54  (buildmeister@swio-display-x86-rhel47-11)  Sat Sep 29 01:10:44 PDT 2012


Section "ServerLayout"

# Removed Option "Xinerama" "0"
    Identifier     "Layout0"
    Screen      0  "Screen0" 1200 0
    Screen      1  "Screen1" 3760 0
    Screen      2  "Screen2" 0 0
    InputDevice    "Keyboard0" "CoreKeyboard"
    InputDevice    "Mouse0" "CorePointer"
    Option         "Xinerama" "1"
EndSection

Section "Files"
EndSection

Section "InputDevice"

    # generated from default
    Identifier     "Mouse0"
    Driver         "mouse"
    Option         "Protocol" "auto"
    Option         "Device" "/dev/psaux"
    Option         "Emulate3Buttons" "no"
    Option         "ZAxisMapping" "4 5"
EndSection

Section "InputDevice"

    # generated from default
    Identifier     "Keyboard0"
    Driver         "kbd"
EndSection

Section "Monitor"

    # HorizSync source: edid, VertRefresh source: edid
    Identifier     "Monitor0"
    VendorName     "Unknown"
    ModelName      "DELL3007WFPHC"
    HorizSync       49.3 - 98.5
    VertRefresh     59.9 - 59.9
    Option         "DPMS"
EndSection

Section "Monitor"

    # HorizSync source: edid, VertRefresh source: edid
    Identifier     "Monitor1"
    VendorName     "Unknown"
    ModelName      "DELL 2007FP"
    HorizSync       30.0 - 83.0
    VertRefresh     56.0 - 76.0
    Option         "DPMS"
EndSection

Section "Monitor"

    # HorizSync source: edid, VertRefresh source: edid
    Identifier     "Monitor2"
    VendorName     "Unknown"
    ModelName      "DELL 2007FP"
    HorizSync       30.0 - 83.0
    VertRefresh     56.0 - 76.0
    Option         "DPMS"
EndSection

Section "Device"
    Identifier     "Device0"
    Driver         "nvidia"
    VendorName     "NVIDIA Corporation"
    BoardName      "GeForce GTX 460"
    BusID          "PCI:19:0:0"
EndSection

Section "Device"
    Identifier     "Device1"
    Driver         "nvidia"
    VendorName     "NVIDIA Corporation"
    BoardName      "GeForce GTX 460"
    BusID          "PCI:18:0:0"
    Screen          0
EndSection

Section "Device"
    Identifier     "Device2"
    Driver         "nvidia"
    VendorName     "NVIDIA Corporation"
    BoardName      "GeForce GTX 460"
    BusID          "PCI:18:0:0"
    Screen          1
EndSection

Section "Screen"
    Identifier     "Screen0"
    Device         "Device0"
    Monitor        "Monitor0"
    DefaultDepth    24
    Option         "Stereo" "0"
    Option         "metamodes" "nvidia-auto-select +0+0"
    SubSection     "Display"
        Depth       24
    EndSubSection
EndSection

Section "Screen"

# Removed Option "metamodes" "DFP-0: nvidia-auto-select +0+0 { Rotation=left }"
    Identifier     "Screen1"
    Device         "Device1"
    Monitor        "Monitor1"
    DefaultDepth    24
    Option         "Stereo" "0"
    Option         "metamodes" "DFP-0: nvidia-auto-select +0+0 { Rotation=left }"
    SubSection     "Display"
        Depth       24
    EndSubSection
EndSection

Section "Screen"

# Removed Option "metamodes" "DFP-1: nvidia-auto-select +0+0 { Rotation=left }"
    Identifier     "Screen2"
    Device         "Device2"
    Monitor        "Monitor2"
    DefaultDepth    24
    Option         "Stereo" "0"
    Option         "metamodes" "DFP-1: nvidia-auto-select +0+0 { Rotation=left }"
    SubSection     "Display"
        Depth       24
    EndSubSection
EndSection

Section "Extensions"
    Option         "Composite" "Disable"
EndSection

05 June 2012

C++ Don'ts, Part I

Hello! Today we will be talking about things not to do in C++! Today's topic will be linked lists, more specifically integer linked lists.

We can define a non-null node as follows:

template<int I_, typename T_>
struct Node {
    static const int value = I_;
    static const int size = 1 + Next::size;
    typedef T_ Next;
};

and the null node as follows:

struct End {
    static const int size = 0;
};

We then can implement getting the size of a linked list:

template<typename L_>
struct Size {
    static const int value = L_::size;
};

where L_ is either a Node or an End.

Recursive prints can be done as follows using specialization:

template<typename L_>
struct Print;


template<int I_, typename T_>
struct Print<Node<I_, T_> > {
    static void print() {
        std::cout << I_ << "\n";
        Print<T_>::print();
    }
};


template<>
struct Print {
    static void print() {}
};

See where this is going? Now go implement map, filter, and reduce. :)

14 May 2012

A short quiz on pointers

Just something I found in my downloads folder that I thought I should keep around. Includes are omitted.

void
f(void)
{
    int a[4];
    int *b = malloc(16);
    int *c;
    int i;

    printf("1: a = %p, b = %p, c = %p\n", a, b, c);

    c = a;
    for (i = 0; i < 4; i++)
        a[i] = 100 + i;
    c[0] = 200;
    printf("2: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
    a[0], a[1], a[2], a[3]);

    c[1] = 300;
    *(c + 2) = 301;
    3[c] = 302;
    printf("3: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
    a[0], a[1], a[2], a[3]);

    c = c + 1;
    *c = 400;
    printf("4: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
    a[0], a[1], a[2], a[3]);

    c = (int *) ((char *) c + 1);
    *c = 500;
    printf("5: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
    a[0], a[1], a[2], a[3]);

    b = (int *) a + 1;
    c = (int *) ((char *) a + 1);
    printf("6: a = %p, b = %p, c = %p\n", a, b, c);
}

int
main(int ac, char **av)
{
    f();
    return 0;
}

20 December 2011

Spot the Stupidity: Give me a sign


Spot the stupidity!

for (unsigned x = 0; x < GridSizeX; ++x) {
for (unsigned y = 0; y < GridSizeY; ++y) {
if ((unsigned)abs(x+y) % 2 == 1) {//modulo 2
glColor4f(1.0f,1.0f,1.0f, alpha); //white
} else {
glColor4f(0.0f,0.0f,0.0f, alpha); //black
}

glNormal3f(                  0,                  0, 1);
glVertex3f(    x*SizeX + world.minX,    y*SizeY + world.minY, 0);
glVertex3f((x+1)*SizeX + world.minX,    y*SizeY + world.minY, 0);
glVertex3f((x+1)*SizeX + world.minX,(y+1)*SizeY + world.minY, 0);
glVertex3f(    x*SizeX + world.minX,(y+1)*SizeY + world.minY, 0);

}
}


And this, ladies and gentlemen, is why you should not code at 3am.