Proof of Concept: Randomize a list

Well, the idea was essentially that RvS allows up to 30~32 maps or so all stored as a pair of assicated arrays loaded from the servers configuration file. One array that holds the game types (e.g. tango hunt, hostage rescue, misson et. al.) and the other the actual maps to load, i.e. GameType[0]=first maps gametype and Maps[0]=first map to load.

I took a moment the other day (before my gfx card went fuzzy) to write a small program that would generate a new configuration file with a maplist specified from another file, the prototype works fine but I didn’t know how I could archive my real goal: randomly populate the maplist from that file.

Here is a proof-of-concept algorithm that takes a list of items and returns a new list containing the same values but sorted into a ‘random’ order.


#!/usr/bin/env python

import random

def unsort(list, index):
    "return a copy of list reordered randomly"

    new_list = []
    table = []

    while len(new_list) != index:
        r = random.randint(0, index)
        try:
            if r not in table:
                table.append(r)
                new_list.append(list[r])
            else:
                continue
        except IndexError:
            pass
    return new_list

if __name__ == "__main__":
    li = [1,2,3,4,5]
    print unsort(li, len(li))

This took me about 10 minutes of thinking at work today and about 12 or 14 hours later I’ve made a test script in Python since that is the language I’ve been using for stuff latly. Basically the problem is the only way to randomly map items from one list into another is if you access elements in the list at random. But if you access a list at a random index and push it into a new list you can get duplicates. So a table (list) is used to store random numbers we have already generated. If the current number is not referenced in the table we can assume that we have not copied the element at that index in the list into the new list, if it does exist we need to try again. One bad thing is the algorithm is designed to run until completion, which can take an arbitrary amount of time to ‘unsort’ any given set. In theory, it could loop forever! However it would be trivial to modify it to abort the randomization process after a given time frame (such as >N iterations or seconds, which ever comes first) and just append remaining elements onto the end of the new list.

Here is a few test runs:

Terry@Dixie$ ./unsort.py
[3, 5, 4, 1, 2]
Terry@Dixie$ ./unsort.py
[3, 5, 2, 1, 4]
Terry@Dixie$ ./unsort.py
[4, 1, 2, 3, 5]
Terry@Dixie$ ./unsort.py
[5, 4, 1, 2, 3]
Terry@Dixie$ ./unsort.py
[5, 2, 4, 1, 3]
Terry@Dixie$ ./unsort.py
[3, 2, 1, 4, 5]
Terry@Dixie$ ./unsort.py
[4, 5, 3, 2, 1]
Terry@Dixie$

Odds are the PRNG is being seeded with the system time by default or making use of /dev/random on my FreeBSD laptop and that is good enough for me. And these results are random enough for me because I dunno how to write first class pseudo random number generators hehe.

randomly sorting lists

Was hashing out a very quick program to take a list of maps from a file and to replace the ones in the config file with those but sorted into a fairly random pattern.

Then I realized that I have no bloody idea how to randomly sort, ehh unsort a list of strings.

My notes scribbled in file:

##################################################
# Randomize the contents of a list -- algorithmic ideas
#
# input; list of N items to be randomized
# storage: table T to hold previously generated random numbers
#
# loop until done where each item in list is sorted into new list
# generate random number R between 0 and N
# store N in a table T if not already done so then
# if N is not in table T
# new list[R] = current item in loop
# else if N is in table continue to next iteration
#
# List will probably have to be a temporary to be generated from input list
#
# result expected: loop once per each item in the input list creating
#

That is the best I can think of when you consider the number of distractions:

birds screeching
mother shouting (at me, dog, and bird)
dozen pans falling
going AFK every X minutes
walking out in the cold to check the car cover
sorting pans back onto shelf
et alii

Is it a wonder I *usually* don’t touch an ounce of code until I am THE ONLY MORON AWAKE in this house ? I think not !

rf.c revisited

Got bored, so I revisited an old program I wrote like last year. One of the very first ones I set out to write in C in fact. I admit there is no practical need for this program haha. The only reason I wrote it is that I found it some one annoying that the cat program was made to concatenate files and print them to stdout. But is all so often just used to print out a lone file when less -F does the same thing. For the fun of it I basically added the ability to mimic the head and tail commands with an implicit number of lines to print (e.g. like head -n / tail -n ) while still keeping to the basic function of outputing a lone file, later I made it handle multiple files just for fun.

I was remembering today the sfalloc() macro I had defined early on. Some thing like

#define sfalloc( _type, _ptr ) 
(_type *)malloc( sizeof(_ptr) )

The main point of it was to ensure I wrote sizeof(foo) instead of sizeof(int) or some thing. And to get it to compile with a C++ compiler. I was thinking about making a new version of it for one of my header files that would use the cast only if __cplusplus was defined or better yet the new operator instead for use in code I would want to be compatible with both C and C++ but why bother for such a small program? Althouhg it would be a good spot to test it out in if I did hehe. Besides MSVC++ is a pain in the ass any way for compiling C99 code (imho).

My favorite non standard extensions to the C standard library on BSD and GNU systems is deffo err(), errx(), warn(), warnx(), and related routines in err.h namely because they are major time savers imho. Since a unix like system is assumed unistd is included and getopt(3) used for parsing argv rather then doing it manually.

I didn’t use the various linked list macros provided by BSD boxes because I wanted to avoid them, in case I ever decided to build the app on Windows or DOS. It also was the first time I ever used a linked list in a C program so I wanted to give it a go hehe. I’m really glad I did to because it was a really good excuse to learn how to use the GNU Debugger at the time 😉

One of the changes I made today was ensuring it would compile fine without assuming a C99 environment, I also ran it by gcc42 with -std=c89 -ansi and -pedantic-errors in the hopes of catching any thing I might’ve visually missed.

the ‘final’ version of the old program

/*-
* Copyright (C) 2007
* [my name ]. All rights reserved.
*
* permission to use, copy, modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/


#if __STDC_VERSION__ >= 199901L
/* inline functions were added in C99 */
#else
#define inline /* protect me */
#endif

#define MALLOC_FAILED "Unable to initialize memory at __LINE__ n"

/* magic number for debugging read_bottom() and clean_up() */
#define NOMEM ((struct lnpos *)0xDEADBEEF)

#include <err.h>
#include <errno.h>
#include <limits.h>
#include <locale.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

/* For storing end of line characters */
typedef struct lnpos {
long eol;
struct lnpos *next;
struct lnpos *prev;
} LNPOS;


static inline FILE *open_file( char * );
static inline void read_all( FILE *, int );
static void read_top( FILE *, int );
static void read_bottom( FILE *, int );
static inline void clean_up( LNPOS * );
static inline void be_verbose( char * );
static inline void usage( void );


static const char *this_progname;


/*
* rf - read file to standard out v2.0 -- see changes.log for details
*/
int
main( int argc, char *argv[] ) {

char *errp;
int b_flag = 0, s_flag = 0, t_flag = 0, v_flag = 0;
int ch, f, lncnt = 0;
FILE *fp;


setlocale( LC_ALL, "" );
this_progname = argv[0];

while ( (ch = getopt( argc, argv, "b:st:v" )) != -1 ) {
switch ( ch ) {
case 'b':
/* Mimic tail(1) -n */
b_flag++;
lncnt = strtol( optarg, &errp, 10 );
if ( *errp || lncnt <= 0 ) {
errx( EXIT_FAILURE,
"Improper line count -- %sn", optarg );
}
break;
case 's':
/* Suppress -v when given multiple files. */
s_flag++;
v_flag = 0;
break;
case 't':
/* Mimic head(1) -n */
t_flag++;
lncnt = strtol( optarg, &errp, 10 );
if ( *errp || lncnt <= 0 ) {
errx( EXIT_FAILURE,
"Improper line count -- %sn", optarg );
}
break;
case 'v':
/* Append file names -- be_verbose() */
v_flag++;
break;
case '?':
default:
usage();
/* NOTREACHED */
}
}
argc -= optind;
argv += optind;

if ( argc < 1 ) {
usage();
}

/* Handle multiple files */
for ( f = 0; f < argc; f++ ) {
fp = open_file( argv[f] );

if ( (!t_flag) && (!b_flag) ) {
read_all( fp, lncnt );
} else if ( t_flag ) {
read_top( fp, lncnt );
} else if ( b_flag ) {
read_bottom( fp, lncnt );
} else {
usage();
/* NOTREACHED */
}

if ( (v_flag != 0) || (argc > 1) ) {
/* Don't suppress if not set */
if ( s_flag == 0 ) {
be_verbose( argv[f] );
v_flag++;
} else {
v_flag = 0;
}
}

fclose( fp );
}

return EXIT_SUCCESS;
}


/* Simple fopen wrapper to keep the if...else if...else blockage from getting
* ugly. Since doing other wise would defeat the purpose of it in this program.
* open_file() halts the program if fopen failed.
*/
static inline FILE *
open_file( char *arg ) {

FILE *fto;

fto = fopen( arg, "r" );
if ( fto == NULL ) {
errx( EXIT_FAILURE, "File can not be opened or"
" does not exist -- %sn", arg );
}

return fto;
}


/*
* print out an open file to standard output
*/
static inline void
read_all( FILE *fp, int lncnt ) {

while ( (lncnt = fgetc( fp )) != EOF ) {
printf( "%c", lncnt );
}
}

/*
* Read n lines from the top of the file.
*/
static void
read_top( FILE *fp, int lncnt ) {

int c = 0;
int f = 0;

while ( (c < lncnt) && (f != EOF ) ) {
f = fgetc( fp );
printf( "%c", f );
if ( f == 'n') {
c++;
}
}
}


/*
* Read n lines from the bottom of the file
*/
static void
read_bottom( FILE *fp, int lncnt ) {

int fin = 0, i;
long int eolnum = 0;
long int where;
struct lnpos *cur = NULL;
struct lnpos *root = NULL;
struct lnpos *last = NULL;

/* initiate the linked list */

root = malloc( sizeof(root) );
root->eol=0;
if ( root == NULL ) {
err( EXIT_FAILURE, MALLOC_FAILED );
}
root->next = NOMEM;
root->prev = NOMEM;
cur = root;

cur->next = malloc( sizeof(cur->next) );
cur->next->eol = 0;
if ( cur->next == NULL ) {
err( EXIT_FAILURE, MALLOC_FAILED );
}
cur->next->prev = cur;
cur->next->next = NOMEM;
cur = cur->next;


/*
* read the file, count every end of line and store them in a new
* member of our linked list.
*/
while ( (fin = fgetc( fp )) != EOF ) {
if ( fin == 'n' ) {
eolnum++;
cur->eol = ftell( fp );
cur->next = malloc( sizeof(cur->next) );
cur->next->eol = 0;
if ( cur->next == NULL ) {
err( EXIT_FAILURE, MALLOC_FAILED );
}
cur->next->prev = cur;
cur->next->next = NOMEM;
cur = cur->next;
}
}

/* double check last nodes prev is up to date before marking the end */

cur->next = malloc( sizeof(cur->next) );
cur->next->eol = 0;
if ( cur->next == NULL ) {
err( EXIT_FAILURE, MALLOC_FAILED );
}
cur->next->prev = cur;
cur->next->next = NOMEM;
cur = cur->next;
last = cur;

/* print out the rest of file from the given offset. */
for ( i = 0; i < lncnt; ) {
if ( cur->prev != NOMEM ) {
if ( cur->eol ) {
i++;
}
cur = cur->prev;
}
}


where = fseek( fp, cur->eol, SEEK_SET );
if ( where != 0 ) {
err( EXIT_FAILURE, "Could not seek through the filen" );
}
read_all( fp, lncnt );
clean_up( root );

}

static inline void
clean_up( LNPOS *root ) {

/* Free linked lists memory */
struct lnpos *cur = root;
while ( cur->next != NOMEM ) {
cur = cur->next;
if ( cur->prev != NOMEM ) {
free( cur->prev );
cur->prev = NOMEM;
}
}
free( cur ); /* free the end node */
}

static inline void
be_verbose( char *fname ) {

printf( "n==> %s <==n", fname );
}

static inline void
usage( void ) {

fprintf( stderr, "usage: %s [-t count | -b count] "
"[-v] [file ...]n", this_progname );
exit( EXIT_FAILURE );
}

The simple makefile compiles it:

gcc -Wall -Wpointer-arith -Wcast-qual -Wcast-align -Wconversion
-Waggregate-return -Wstrict-prototypes -Wmissing-prototypes
-Wmissing-declarations -Wredundant-decls -Winline -Wnested-externs
-std=c99 -march=i686

and Makefile.optimize adds the -fforce-mem -fforce-addr -finline-functions -fstrength-reduce -floop-optimize -O3 options for when testing is done, program works fine. FreeBSD’s lint implementation also doesn’t spew any serious messages.

GCC42

I was installing a program last night on my laptop that needed several GNUStep stuff, so I found out the hardway that it needed GCC v4.2.x’s Objective C compiler…

It took maybe 3 1/2 to 4++ hours to build lang/gcc42 but I suppose it’s a good thing. I always wanted to give it a test drive and it seems to have included the Fortran and Java (gcj) compilers with it.

The only good things I can say is one of my C programs built fine with the C Compiler (/usr/local/bin/gcc42) and I got to thumb through the source code in /usr/ports/lang/work/gcc-*/ while I waited. The parts I saw were quite well documented to and a pleasure to read.

One nice thing I suppose, a successful build of a compiler collection is probably a good stress-test for my laptops hardware :

Mxing a code squishy

Well, last night I got an alpha grade (imho) release set up on source forge and today I got it posted on forums.pcbsd.org.

It is some what ahead and behind schedule in the same regard, I originally planned to release a mock-up (non functional but ‘looks’) around the new year. Instead I’ve taken a few weeks to push on a head to some thing that actually works.

I had also road mapped a beta with a few more features then are currently ready to be released between Jan 2008 and June 2008 but it’s more likely that I’ll hit a 1.0 by June… hehe. So I’m both behind and ahead of my time goals. Software Schedules are not really some thing I believe in setting in stone, so much as setting a point on the calendar some where between when I expect to be done by and when I think it should be done by.

Since making use of SVN was not in my original plans I do have a bit to consider now.

I want to continue coding so I can keep the pace of development going. But I need to consider the chances of bugs being found in any one that actually tries the snapshot I released. And I do not want to muck with merging branches later if that happens… The stuff I released is not complete but it should be fairly stable, or I wouldn’t have let it hit SVN >_>.

What I am thinking is to limit my self to continuing things in the trunk that need to be done without effecting the released code much. Which is copied to the tags directory so it’s saved in SVN. Then after about a weak or so, go back to un-restrained work. So I can deal with things like redoing the NPM_DisplayDialog the way I would like to redo it.

Before I am willing to bump status to Beta, I want to have NPM able to update the ports tree (portsnap/cvsup/csup) and configure ports. I tested the config gui awhile back before taking the code to sourceforge but I never got it fully working. I need to figure out just how I am going to get a connection between checkboxes and options that I can parse back out of the GUI.

I should also make it look for stored configurations rather then just in the makefile.[0]. Those two things are really what I am interested in coding feature wise. I also want to remove the dependancy on psearch because it really is a simple app and we might get a slight performance boost.

I also want to fix the translation systems up a bit, work on another prototype of the NPM_MainWindow user interface style and do some concept art for NPM’s configuration dialog. I don’t expect a GUI way of changing NPM’s settings to be released until RC status though.

NPM test 1, phase 1 results

I was a little disatisified with the phase 0 results. What I had done was checkout a copy of the sources onto the test machine end removed the diagnostic messages of echoing the command and arguments to be run in the background. A few oversites later namely a missing equals sign and the lack of –verbose switches (as can be seen in the video’s uninstall segment) I basically got it working but not quite happy with it.

Sat down tonight after watching a movie and set to work on getting her working smoothly out of the source tree. After that was done and with a little poking at portupgrade later…. I ran a group of live tests to check for the ‘it actually works’ factor with the core things and got no show stoppers. The only bad things I can say is I don’t care much for the port{upgrade,install} output dots and the occasional lag in updating the QTextEdit widget but it’s probably no slower then doing it from my shell.

here is a copy of the last commit message from editing source code:

CODE PASSES FOLLOWING TEST CASES:

update package listing (right listview)
view pkg_info for selected package (xevil)
remove selected package (xevil)
search ports tree (for xevil)
install port (xevil)

xevil was selected because it is one of the ports I have installed that is a suitable test case (small, fast/easy to install/deinstall) and one of the time wasters I have setup that I can live without if I frag it on there install.

I’m going to upgrade the development status on source forge to Alpha shortly and tomorrow I hope to have a file release ready op, Most of what remains is logistics really, before the Alpha Release the following needs to be compelete:

0/ make demo video (I would write the script now if it was a quarter after 4am’ish) — couldn’t get mic working, just as well with my house…

1/ mini faq thingy uploaded to website and update the sites download page

2/ readme file generated with basic testing instructions blah blah — also included a template for a desktop icon.

3/ update trunk/src/const.py NPM_VERSION – probably will get bumped to “0.48.Xa” ore “0.48.Xpre” and clean up some of the comments

4/ read SVN handbook on tagging and branching and put it to work – I want the alpha release split off the trunk.

5/ get file release prepared — done and done!

6/ forum post typed up for forums.pcbsd.org – done

7/ get my ass back to coding — what I should be doing lots of hehe.

Hooooooaaaaahhhhhhhhhhhhh !!! Now if I can get audio working in XVidCap and enough silence to do it with my crappy mic, this gonna be a nice start.

Sadly most of this is gonna have to wait until after dark…

fucking family already has given me a headache and it’s only 1617 local..

Test 1, Phase 0

booted my test machine

set up for video taping

svn’d a copy of npm source

edited source to prepare for test

began test.

Not 100% what I wanted but this is the first live test of install and deinstall operations.

Video Sample

I tested doing a portinstall of xgalaga, confirmed it ran, and then removed it. The pkg_delete operations output left a little bit to be desired! But hey, it did work…

I want to prep a script and get the code ready for a small battery of live tests under real world conditions. Once the code is suitably able to pass an acceptible amount of the tests… Alpha release.

Before I video the next one through I want to have a properly written out and planned script to follow for the video. I also really would like to try and get my Mic working (not tested yet) so I could use voice over and some background music wouldn’t hurt if it didn’t add more then a few megabytes to the out file.

Currently tests will take the first priority and continuing feature implementation will take secondary until the Alpha release is ready op.

I want to triple check but I think I’ll be able to host the video on the website for download and I can probably upload it to YouTube. Using rapidshare for this one was just to make it available (temporarily). The final one made for the alpha release will be much better.

My main concern though is getting NPM ready hehe.

Another night spent working on NPM…

Some of the stuff done to night

begin of internal docs

prepping files for translation (wrapping more strings, now using QKeySequence e.t.c.)

trying to get set up for translations (including the beginning of the German one).

rewriting the display dialog to remove usage of Qt Designer / pyuic generated code.

To be honest, I think I could run a live fire test tomorrow with a 2 minutes worth of changes.

Neolious coding

Oh baby has tonight been a full head of steam. I’ve been slugging through the options systems and the subroutines for actually doing the installations. A mock up of the style #2 GUI which is one of the ones I posted back in december when I did three different concept drawings. She is almost ready for a live test, I think as soon as I correct the item selection code to work properly (not tied to mouse position) it will finally be time for that Alpha Release, two weeks later then originally planned but hey it’s still is more feature complete on the inside then previously planned for it xD

Here is a screen shot of Neo running during a test run of the mock up from the trunk.

Free Image Hosting at www.ImageShack.us

I solved most of the layout issues and I think it will probably be playing with the spacers and splitters to finish the rest of getting it to ‘look nice’. The main window is hand written but the display dialog is an extended sub-class of a prototype made in QT Designer.

What I am thinking is to have 3 drop-in modules each implementing the NPM_MainWindow class. Where each module implements one of the user interface styles and the programs init code loads the appropriate module. The advantage being the freedom to do any thing desired with the main window, while preserving the rest of things that have been done. Technically user created UI could be allowed to be loaded. I really want to play with the dock window stuff in Qt4… lol.

I need to start setting up the documentation (internal first, then the manual), ironing out the key commands, and setting up for the german translation in addition to my remaining to do’s but all of that is non-critical as far as getting an experimental release out there. I think goal for Beta time would be getting the portsnap/csup/cvsup stuff sorted out and a settings + about + help dialog in the run. A better website design would be nice too… hahaha

I know what I can’t figure out today, I can figure out in the days to come.

Hooah !

Nights labour

Spent most of the night working on the port searching code and options module. I think the options module is now almost like what I originally envisioned of it. Aside from being integrated into the not yet written settings dialog and no read/write accessor methods wrapping around the configuration dictionary keys.

So far across the various prototypes, tests, and mock ups I’ve written over 3,000 lines of code (wc -l *.py for each directory gives sums adding to >3700L). The way I work I guess is a bit heavy on files but it tests the hell out of things 🙂

So far the current working system is almost 700 lines of Python code. Aside from not being very feature complete yet (for my tastes) I think it is coming along quite nicely and maybe should be marked higher then the pre-alpha status I set on sourceforge… But I guess I have higher expectations of my own work then I do others lol. The > 700 lines of code in the SVN now represents the work done in R&D by the previous coding. One thing I like about SVN and CVS as opposed to manually backing things up with cp/tar is there is no fear about ‘accidentally’ deleting files permanently before they serve their use hehe.

I’m hoping to soon have enough files for a quick snapshot that can handle the basic pkg_* commands and searching the local ports tree. I have tried to keep both the quality of the code and the programs design as high as possible at every phase but I don’t really consider myself a good programmer. Just someone that knows what he wants and can wrap his head around it piece by piece until it all falls into place.

Hmm, why do I feel more like a Japanese Beaver then a Spider right now? Haha/