The best/most complex/most interesting program you've ever written.

[chrisname]

Post descriptions of, snippets from, or even downloads of the best/most complex/most useful or most interesting program you've ever written.

Mine's a drawing program I made a while ago; I got a lot of help making it from the good folks right here =]

Alternatively; post programs other people have created that you liked, or thought were really good achievements.

For this; I link you to this video: http://www.youtube.com/watch?v=uWhvY3lPlQ4
It's a program written in C++ to solve a rubik's cube (a real one, inputted via webcam, or a generated one).

From the video description:
"CV Rubik is a C++ application that solves a 3x3 Rubik's cube. It uses a webcam to "look" at a Rubik's cube and generate a step by step solution in 3D graphics.
CV Rubik draws on knowledge from different fields of computer science such as Computer Vision, Artificial Intelligence and 3D Graphics."

There's also another program I liked which was AI; it was called polyworld I think.

"Polyworld is a cross-platform (Linux, Mac OS X) program written by Larry Yaeger to evolve Artificial Intelligence through natural selection and evolutionary algorithms."

I was watching TV and it was in a program I was watching about the future (which involved ASIMO -- I have never felt more compelled to hug something that wasn't alive in my life).

[jsmith]

Quite a while back (almost a year) someone posted a homework assignment where the goal was to have the user enter an integer N, and then output all possible sets of integers i1, i2, ... in such that i1 < i2 < ... < in and i1 + i2 + ... + in = N. Some folks provided solutions that were in excess of 40 lines of code to compute and output the result sets.

Here's mine (for N=10):

#include <iostream>
#include <string>
#include <boost/lexical_cast.hpp>

void Run( const std::string& v, int tgt, int start ) {
    for( ; tgt >= 2 * start + 1; ++start )
        Run( v + ' ' + boost::lexical_cast<std::string>( start ), tgt - start, start + 1 );
    std::cout << v << ' ' << tgt << std::endl;
}

int main() {
    Run( std::string(), 10, 1 );
    getchar();
}

[helios]

I've recently written a compiler for a subset of C that produced machine code for a virtual stack machine (also by me).
I was thinking of adding a second, special purpose language to a scripting language. The language had to portable, so loading a binary module was not an option. It also had to be interpreted, but parsed only once, so pure interpretation was also unsuitable.
I decided to use a stack machine when I realized compiling for a register machine was more complicated. It involved moving the stack to the compiler and the instructions couldn't be isolated. On the other hand, the multiplication operator compiled for a stack machine always looks the same regardless of what other operations there are in the expression. I later found that many virtual machines that aren't emulators are stack machines. Most notably, the JVM.

I think the most interesting program I've heard of is one that uses an array of cameras aimed at a person's face to build a geometry of their face in real time. It doesn't require any sensor like motion capture, but it does require that the cameras are mounted on a structure, and IIRC the person has to keep their face in the focal point.

[chrisname]

A 14-line program and a compiler :O

And I'm working on adding more colours...

Jsmith; could you not just cheat and delete all the whitespace? Have it on one line?

Helios; that camera program sounds pretty intelligent. Could the cameras move?

[helios]

Could the cameras move?

No. They were aimed at a single point. Imagine a hollow sphere with cameras on the inner surface aimed at the center. Now remove all the cameras except for a cone and put someone's head at the apex. That's kind of what it looks like.

[chrisname]

Oh. Maybe they could do that for version two...

[jsmith]

@chrisname:

Well, my goal was to write the program using a "reasonable" coding standard. Otherwise yes, I could have even eliminated <string> since <iostream> includes it on every compiler I know of.

I also could have gotten rid of the getchar(); at the end because I wrote it on Un*x, but I included it because the OP was using windows.

On the subject of compilers/VMs, I once wrote a program that implemented a simple CPU (with some 'extended' instructions) whose 'binary' instructions could be formed using only alphanumeric characters so that you could pass the entire program to the simulator as a command-line parameter.

The point of the program was to abuse in the worst way possible GCC's implementation of pointer-to-virtual-member functions. The "simulator" class had one method for every instruction in the instruction set, but the trick was that absolutely nowhere in the program did I ever explicitly call any of them, or even reference their names. The trick was knowing how GCC implemented pointers-to-virtual-member-functions.

Great fun.

So much so I later decided to write an assembler for the language because it was too hard to hand-code the "binary" code :) (Ironically I coded the assembler in very structured C so that it would be maintainable.)

[chrisname]

:O
You wrote a virtual CPU to use with a VM? That sounds... excellent.

Any chance you hhave a download link?

If anyone remembers, a few months ago (or less, it may be); I was going to write an en/decoding program. I've just realised a way of doing it, so I'm going to try it now.

By "delete all whitespace" I meant like this:

#include <iostream> 
#include <string> 
#include <boost/lexical_cast.hpp>
void Run( const std::string& v, int tgt, int start ) { for( ; tgt >= 2 * start + 1; ++start ) Run( v + ' ' + boost::lexical_cast<std::string>( start ), tgt - start, start + 1 ); std::cout << v << ' ' << tgt << std::endl;} int main() { Run( std::string(), 10, 1 ); getchar();}

SEVERE obfuscation; but I certainly shortened it!
Anyone who says they can still read it is lying.

[JCED]

:D

It's readable, you just have to be really patient with the programmer that wrote it.

I would definitely not bother reading anything that was written like that, though.

[helios]

You wrote a virtual CPU to use with a VM?

Um... "CPU" and "machine" are synonyms in computer science.

[chrisname]

Shhhhhh. I'm no computer scientist.

Then again I'll be looking for a college this time next year, or have already found one, so I'm glad I have the time to start now.


So he made a VM? I'd still love to try it.

[jsmith]

I'll dig around for it. I know I still have the assembler. But keep in mind that it is much more an obfuscated program than a 'vm'. Here is a program that demonstrates the basic principle.

#include <cassert>
#include <cstdlib>
#include <iostream>

class Cpu {
  public:
    virtual int dummy( int, int ) {}
  private:
    virtual int add_( int a, int b ) { return a + b; }  /* A */
    virtual int sub_( int a, int b ) { return a - b; }  /* B */
    virtual int mul_( int a, int b ) { return a * b; }  /* C */
    virtual int div_( int a, int b ) { return a / b; }  /* D */
    virtual int mod_( int a, int b ) { return a % b; }  /* E */
    virtual int and_( int a, int b ) { return a & b; }  /* F */
    virtual int or_( int a, int b )  { return a | b; }  /* G */
    virtual int xor_( int a, int b ) { return a ^ b; }  /* H */
};

int main( int argc, char* argv[] ) {
    typedef int (Cpu::*Memfun)( int, int );

    union {
        Memfun fn;
        unsigned char ptr[6];
    } u;

    Cpu    cpu;

    u.fn = &Cpu::dummy;

    assert( argc == 4 );

    int p1 = atoi( argv[ 1 ] );
    int p2 = atoi( argv[ 3 ] );
    char op = argv[2][0];

    assert( op >= 'A' && op <= 'H' );

    u.ptr[0] = 1 + 4 * ( op - 'A' + 1 );  // Don't look here!

    std::cout << "The answer is " << ( (cpu.*(u.fn))( p1, p2 ) ) << std::endl;
}

NOTE: this program may not work on any compiler other than gcc, and even then I won't guarantee it will work with all versions of gcc. It exploits an internal detail of how gcc implements pointers to virtual member functions. [A note of interest is that the pointer to member function is actually 6 bytes long, not 4.]

g++ --version
g++ (GCC) 3.3.3 20040412 (Red Hat Linux 3.3.3-7)
Copyright (C) 2003 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Compile with

g++ main.cpp -o cpu

To run,

cpu <number> <letter> <number>

where each <number> is an integer, and <letter> is one of A, B, C, D, E, F, G, or H.
Each letter defines a mathematical operation as commented.

Note that nowhere does the program source actually reference any member function
except dummy, which is an empty function, yet all of the member functions are called.
(Note that the member functions are even private, but still called :)

EDIT: also, a little endian architecture is required to run properly.

[chrisname]

Wow. I can't wait until when (if?) I get to the level where something like that is possible.

Nothing interests me more than CPUs. I was actually going to try and make RAM in Electronis but you need silicon and loads of chemicals and precision souldering. I keep making errors with my souldering.

[tition]

I am currently working on my most interesting and practically only programming project ever - a program to do algebra for me :). That is my main dream project (if we are to exclude the usual dream to make a 3D mmorpg game, which I will never do).

Lately the code has grown quite a bit, so I got to learn some things how to manage longer code the hard way :) Last bug was 20+ hours of debugging... The good part is that with math stuff you always have alternative ways to check your program's output (for example, if your formulas are formulas that count things, you better get non-negative integers. So far I have nailed the integrality part down; now working to make them positive :).

[chrisname]

Thats good. How do you invoke it? I was playing around with the new keyword with 16kb char* arrays. I came out with something that stores 8 files of 256kb in total (max) and then writes its command line args to the file, almost like virtual RAM. The big advantage is that now I finally understand how - but more importantly, why - to use pointers. Anyway so them I made another executable to clear it and another to read the RAM and return it's ASCII value using int(mychar). The problem there is that you have to do it character by character, and it isn't really Random Access.

I then made a 'graphics card' with its own 256kb of 'memory' which it reads and writes, and then prints to a console window. Theres also a program that takes a 'hard drive partition' and then stores data to it, in files like 0.hd0 for hd0,0.

It was really quite fun making that.
I'm going to try and emulate something like a CPU, albeit very basically. I'll try some kind of instruction set.

[Gregor]

that all is verry interesting! Loving the GCC exploit, would love to try and compile that myself if you find and share the code.

damn helios, whats with the serious reinventing? Hope you got payed for that.

And tition, you will have tons of fun writing that, specially if this is the first time you're writing a parser. I use wolframbeta. Neat result display + its parser is OP.

cheers

[demosthenes2k8]

Don't you mean Wolfram|Alpha?
Beta is a spoof of it.

[Alan]

If anyone knows the programming language Befunge... I made a compiler for my own version.
Ots a Grid based language where the flow is directed by directional characters

>, v, <, ^

It is a stack-based language.

Here is the code to write hello world

> "!dlroW ,olleH"v
  @!,,,,,,,,,,,,,<

It starts at the >, then pushes Hello, World! into the stack in reverse, so when they are popped with the , character they are in normal order.

The ! character calls

cin.get();

Then the @ character calls

exit(0);

The compiler is 241 lines in total here is the commented structure of main()

int main () {
  int line = 1; // set the line (y coordinate) to 1 (first line)
  int p = 0; // set the position in the line (x coordinate) to 0.
  DIR dcur = EAST; // set the current direction to EAST... DIR is a int typedef
  /* ======== PROGRAM VARS ======== */
    stack <int> svar; // the program stack
  /* ============================== */
    if(isblank(getVarStr(file)[0]) || isnull(getVarStr(file)[0])) // if line[0] is empty or '\0'
      err("No initial insructions: Execution failed"); // throw error... err(const char*)
    bool string_mode = false; // not in string mode...
    while(true) { // program loop
      randSeed(); // invokes random seed: srand(time(NULL));
         char curp = seek(line, p); // char current cursor position
         if(!string_mode)
             setdir(&dcur, line, p); // set the direction based on curp... ^^^
           if(istrampoline(curp)) // if # symbol (means skip next call):
             jumpp(dcur, &line, &p); // *p+=2;
           else // if 'curp' is normal (not '#')
             nextp(dcur, &line, &p); //  ++*p
         trypush(seek(line, p), &svar); // if 'curp' is number 0-9: svar.push(curp-'0');
    /* ========================= parse 'curp' =============== */
   /* ... */

[chrisname]

Jsmith, I'm learning ASM. Any chance you could find your assembler? I'd love to test it.

At the moment I use GAS, which is good, but I'm not familiar with AT&T syntax, having learned the Intel way. I can read and write AT&T, but I make more mistakes.

[jsmith]

I do have the assembler source.

PM me with your email address and I will email it to you directly.