Support NeoGAF

[lorebringer]

I need help picking a data structure for one my projects for school if you guys and gals don't mind offering some advice.

My first problem is I need to create an adjacency list that is provided by a text file at the start of the main function. The input looks like this:

a:bcd
b:ad
c:a
d:ab

and so on. The character before the : is the vertex, and the points listed after it at the adjacent vertices. Originally I was thinking of creating a class that stored a character (the vertex) and a vector of the adjacent vertices. My problem with this is I have no idea how many vertices the user will need to enter. I was trying to avoid the use of pointers, but the more I think about it, the more I'm uncertain as to whether that'll be possible. Would it be wise to user pointers in this problem so I can create new pointers to Nodes as the user needs them and store the information according? (That seems like a big Yes to me after typing this all out :I)

Assuming C++ rather than C because you mention vector:
Yes you're going to need to dynamically allocate memory here because you have no idea of the input size. Couple of things to watch out for:

Since it looks like they can give you repeat data (i.e. a:bc, b:ad) make sure to check if you have created the vertex already and reuse the same one rather than create a new one if so. The easiest way to locate the existing vertex is probably to store the pointers to each one in a map. You could implement traversal of the existing graph to locate them but that's way more time consuming and outright won't work if the graph is not connected. Another thing to consider is that you could read all the input lines into a string vector and from there allocate to an array or something as you now know the input size but that's essentially the same thing.

 

[Hari Seldon]

Taking a C++ class concurrently with a Python class through coursera.

I had C++ years ago, but my god what a shitty fucking language when it is stacked up against Python or even Java.

I code in straight C every day at work, but all the layers upon layers of bullshit in C++ make it fucking terrible. I just want to get through this class and forget this shit.

Do people still write applications in C++? If so, why?

 

[tuffy]

Do people still write applications in C++? If so, why?

Mostly because it generates fast code and isn't quite as low-level as C, I'd imagine.

But I still consider it a classic example of the second-system effect.

 

[Pirabear]

With the semester wrapping up, are their any sites or books that give beginner assignments for C++? I'm not at the level I want and would like to remain semi-productive over break.

 

[Hari Seldon]

Mostly because it generates fast code and isn't quite as low-level as C, I'd imagine.

But I still consider it a classic example of the second-system effect.

Yeah you are right on the nose with that Second-System effect link. I also find that I am thinking more "strategically" while coding in python than in C++. I am worrying about the big picture more and how my code is interacting than worrying about stupid syntax and picking which of the 2000 different ways I can do something in C++. Seems like there is always just 1 right way to do something in Python.

 

[tuffy]

Yeah you are right on the nose with that Second-System effect link. I also find that I am thinking more "strategically" while coding in python than in C++. I am worrying about the big picture more and how my code is interacting than worrying about stupid syntax and picking which of the 2000 different ways I can do something in C++. Seems like there is always just 1 right way to do something in Python.

I've had a lot of luck using Python for much of a program's user-facing bits, and using Python's C API for critical sections that do a lot of calculations and need to be fast. It's a nice compromise mixing the ease of a high-level language with the speed of a low-level one.

 

[CrunchyB]

Do people still write applications in C++? If so, why?

+ Existing C++ code base, too much work porting everything
+ Easy to integrate with other software, also written in C++ or C
+ Many interesting techniques to optimize performance

Spoiler

this is not really a plus. Most languages perform fine without voodoo

But you're right, C++ is a horrible mess of a language. You write C++ code because you have to, not because you want to. At least that's my opinion.

 

[Hari Seldon]

I've had a lot of luck using Python for much of a program's user-facing bits, and using Python's C API for critical sections that do a lot of calculations and need to be fast. It's a nice compromise mixing the ease of a high-level language with the speed of a low-level one.

Yeah I haven't dug into using the Python C API. I read about the feature and it sounded very attractive since I'm fairly fluent in C already. I'm going to be messing with a machine learning application shortly and it sounds like the number crunching for that will be a prime candidate for the boost I can get in C.

 

[BriareosGAF]

I've had a lot of luck using Python for much of a program's user-facing bits, and using Python's C API for critical sections that do a lot of calculations and need to be fast. It's a nice compromise mixing the ease of a high-level language with the speed of a low-level one.

In the old days we did this with Tcl/Tk and C. Oh how I fondly remember using VisualTcl to make layouts on a SparcStation 64 that I was connected to over my university's 28.8k dialup from my home Linux box, running X remotely. With a custom compiled WindowMaker WM so I didn't have to use the crappy fvwm2 they had installed.

*sniff*

 

[Nesotenso]

Taking a C++ class concurrently with a Python class through coursera.

I had C++ years ago, but my god what a shitty fucking language when it is stacked up against Python or even Java.

I code in straight C every day at work, but all the layers upon layers of bullshit in C++ make it fucking terrible. I just want to get through this class and forget this shit.

Do people still write applications in C++? If so, why?

Which course are you taking for C++ ? I am looking to sharpen my skills.

 

[Hari Seldon]

Which course are you taking for C++ ? I am looking to sharpen my skills.

A local community college online course. The Python class I am taking is through coursera. The coursera class is like 10,000x better than the community college class, so this is going to be the last class I ever pay for in my life.

 

[Tomat]

Assuming C++ rather than C because you mention vector:
Yes you're going to need to dynamically allocate memory here because you have no idea of the input size. Couple of things to watch out for:

Since it looks like they can give you repeat data (i.e. a:bc, b:ad) make sure to check if you have created the vertex already and reuse the same one rather than create a new one if so. The easiest way to locate the existing vertex is probably to store the pointers to each one in a map. You could implement traversal of the existing graph to locate them but that's way more time consuming and outright won't work if the graph is not connected. Another thing to consider is that you could read all the input lines into a string vector and from there allocate to an array or something as you now know the input size but that's essentially the same thing.

Thanks, I think I'm going to try your "read as a string and then allocate from there" method. And yes, I am using C++.

 

[Harpuia]

GAF, what's a good book for C++? I'd love to carry around my huge textbook but ain't no way that is happening haha! I'm looking for something for a beginner, not some kinda reference book.

 

[Spoo]

GAF, what's a good book for C++? I'd love to carry around my huge textbook but ain't no way that is happening haha! I'm looking for something for a beginner, not some kinda reference book.

Difficult to escape the text-book size when your language is as bloated as C++. A great beginner text is always the Dietel & Dietel books, but again, it's huge, and costly.

 

[Mabef]

Hi duders. I'm a newb with a C++ question.
I'm trying to make a game of connect four. The game board is stored in an array, with individual -'s, x's, and o's representing the pieces/lack thereof. The output is meant to eventually resemble this:

- - - - - - -
- - - - - - -
- - - - - - -
- - o - - - -
- - x - - x -
- x x o - o -

I'm having trouble starting. What I want to do is create the 'starting' array (all dashes) through a function. The function will take in dimensions, create an array accordingly, fill the array elements with dashes, then return the array to the main function.

Previously I built the array within the main, but my teacher is trying to make us use functions for more stuff so I thought I'd try using one. What I thought would work doesn't.

#include <iostream>
using namespace std;

string buildBoard (int, int);

int main()
{
    int ROWS = 6, COLS = 7;
    string board = buildBoard(ROWS, COLS);
       
    return 0;
}


string buildBoard(int ROWS, int COLS)
{
    string board[ROWS][COLS];
    
    for (int y = 0; y < ROWS; y++)
    {
        for (int x = 0; x < COLS; x++)
            board[x][y] = "a ";
    }
    return board;
}

I get this error for the last line, 'return board':
error: conversion from 'std::string (*)[(((long unsigned int)(((long int)COLS) - 1)) + 1u)]' to non-scalar type 'std::string' requested

What's the deal, yo?

 

[Mondriaan]

I need help picking a data structure for one my projects for school if you guys and gals don't mind offering some advice.

My first problem is I need to create an adjacency list that is provided by a text file at the start of the main function. The input looks like this:

a:bcd
b:ad
c:a
d:ab

and so on. The character before the : is the vertex, and the points listed after it at the adjacent vertices. Originally I was thinking of creating a class that stored a character (the vertex) and a vector of the adjacent vertices. My problem with this is I have no idea how many vertices the user will need to enter. I was trying to avoid the use of pointers, but the more I think about it, the more I'm uncertain as to whether that'll be possible. Would it be wise to user pointers in this problem so I can create new pointers to Nodes as the user needs them and store the information according? (That seems like a big Yes to me after typing this all out :I)

You could use a (possibly sparse) 2 dimensional array where the values are 0 to indicate no-adjacency and 1 to indicate adjacency. IIRC one of the cool things about this matrix is that you can perform dot product with this matrix with itself n times to determine whether you can reach a node in n+1 hops.

You would probably want one other array to map your indices to vertex characters.

 

[lorebringer]

Hi duders. I'm a newb with a C++ question.
I'm trying to make a game of connect four. The game board is stored in an array, with individual -'s, x's, and o's representing the pieces/lack thereof. The output is meant to eventually resemble this:

The problem is that a 2d array of string is not a string, but your code is trying to cast between them. You need to intialise each array separately in a loop:

#include <iostream>
[B]using std::string;[/B]

[B]string**[/B] buildBoard (int, int);

int main()
{
    int ROWS = 6, COLS = 7;
    [B]string**[/B] board = buildBoard(ROWS, COLS);

    //DO STUFF

[B]    //clean up after yourself
    for(int i = 0; i < ROWS; ++i)
    {
        delete[] board[i];
    }
    delete[] board;[/B]

    return 0;
}

[B]string**[/B] buildBoard(int ROWS, int COLS)
{
    [B]string**[/B] board = [B]new string* [ROWS];[/B]

    [B]//watch out for x, y order here[/B]
    for (int y = 0; y < ROWS; y++)
    {
        [B]board[y] = new string[COLS];[/B]
        for (int x = 0; x < COLS; x++)
            board[B][y][x][/B] = "a ";
    }
    return board;
}

Other stuff in there:
- You should probably avoid using namespace std, a lot of junk you don't need is included then and it gets hard to remember which parts are where and what's part of std and what isn't.
- A 2d string array is an array of arrays (or more specifically, a pointer to an array of pointers), so your return types have to match.
- Always remember to delete or delete[] after you use new.
- Careful of x, y order when iterating through arrays, you had them in the opposite order at first, which will cause a crash. The outer loop is the first array index, inner is the second.

Hope that helps.

 

[Mabef]

The problem is that a 2d array of string is not a string, but your code is trying to cast between them. You need to intialise each array separately in a loop:

...

Other stuff in there:
- You should probably avoid using namespace std, a lot of junk you don't need is included then and it gets hard to remember which parts are where and what's part of std and what isn't.
- A 2d string array is an array of arrays (or more specifically, a pointer to an array of pointers), so your return types have to match.
- Always remember to delete or delete[] after you use new.
- Careful of x, y order when iterating through arrays, you had them in the opposite order at first, which will cause a crash. The outer loop is the first array index, inner is the second.

Hope that helps.

I'll be honest, that stuff is over my head. But I think I kind of get it. Lemme try to repeat it back:

Since 2d arrays are actually a mishmash of arrays and pointers, C++ functions won't be nice about receiving/returning them unless I use double pointers (new to me) in both creating 2d arrays, and in creating the functions using them. Also, putting data into a double pointer'd 2d array requires different syntax, like new, and later delete. Which, yes, are also new to me, and are why I'd probably have to take a different route.

I appreciate the in-depth reply, though. Before you responded, I was already looking up 'pointers' thinking they'd help. I was grasping the concept, then all this double pointer stuff showed up and my head a-sploded.
I asked a classmate about the assignment and she said we're supposed to make the array a global variable. I'm actually kind of disappointed . Program is working fine, though.

 

[leroidys]

Programming assignments that don't work because the teacher never tested them on the campus boxes are so frustrating.

 

[Slavik81]

Since 2d arrays are actually a mishmash of arrays and pointers, C++ functions won't be nice about receiving/returning them unless I use double pointers (new to me) in both creating 2d arrays, and in creating the functions using them. Also, putting data into a double pointer'd 2d array requires different syntax, like new, and later delete. Which, yes, are also new to me, and are why I'd probably have to take a different route.

Nobody uses arrays in C++ like that. In fact, pretty much nobody uses arrays. But if they did, it would probably look more like this:

#include <iostream>
using namespace std;

void buildBoard (string*, int, int);

int main()
{
    const int ROWS = 6, COLS = 7;
    string board[ROWS][COLS];
    buildBoard(&board[0][0], ROWS, COLS);

    return 0;
}


void buildBoard(string* board, int ROWS, int COLS)
{
    for (int y = 0; y < ROWS; y++)
    {
        for (int x = 0; x < COLS; x++)
            board[(COLS-1)*x+y] = "a ";
    }
}

I appreciate the in-depth reply, though. Before you responded, I was already looking up 'pointers' thinking they'd help. I was grasping the concept, then all this double pointer stuff showed up and my head a-sploded.
I asked a classmate about the assignment and she said we're supposed to make the array a global variable. I'm actually kind of disappointed . Program is working fine, though.

Yeah, passing arrays around is terrible in C++. Hence why std::vector (or a custom class, like a Board object), is generally used instead. For a short example problem, a global isn't going to hurt you. But it's worth knowing that 'real' programs don't have calls that look like what lorebringer suggested.

Spoiler

Or rather, they shouldn't.

 

[rpmurphy]

Doing some Java coding at the moment, and I was wondering if there is something in the Java library or some other open-source library that is good for storing text in memory and doing sed-like regex matching capabilities? I'm trying to parse error logs.

 

[nan0]

Doing some Java coding at the moment, and I was wondering if there is something in the Java library or some other open-source library that is good for storing text in memory and doing sed-like regex matching capabilities? I'm trying to parse error logs.

Maybe java.util.regex.Pattern?

 

[rpmurphy]

Maybe java.util.regex.Pattern?

I know Pattern and Matcher exist, but I'm not familiar enough with it enough to know if it can do stuff like return the line number where the matching string is found or at least the beginning index so that I can run another regex on the all of the text after the match, etc.

 

[lorebringer]

Yeah, passing arrays around is terrible in C++. Hence why std::vector (or a custom class, like a Board object), is generally used instead. For a short example problem, a global isn't going to hurt you. But it's worth knowing that 'real' programs don't have calls that look like what lorebringer suggested.

Spoiler

Or rather, they shouldn't.

Real men just use pointers! In all seriousness I'm far more used to C

Spoiler

(it shows)

so this is much better advice. I was going to create the array in main and pass it in but I wanted to modify the example as little as possible.

 

[Dinokill]

Is there a way to use negative number for node labels in the boost graph library?.

I want to use add_edge(-1, 1, maze) but I get an out of range error.

Can anybody help me? This project is due in 4 days.

 

[survivor]

Why are templates so confusing in C++?

I have to use them for a simple assignment implementing a generic Matrix but I'm still not sure how to do that. So say I have Matrix.h file, am I supposed to put all my declarations and definitions there and then just not have a Matrix.cpp file?

I was reading this Stack Overflow question and the top answer offered 2 more suitable alternatives. The first method makes sense although I haven't see .tpp extension before (quick Google says I can just use .cpp instead I think). The second method also makes sense, but it doesn't feel like it's a practical way.

 

[Spoo]

Why are templates so confusing in C++?

I have to use them for a simple assignment implementing a generic Matrix but I'm still not sure how to do that. So say I have Matrix.h file, am I supposed to put all my declarations and definitions there and then just not have a Matrix.cpp file?

I was reading this Stack Overflow question and the top answer offered 2 more suitable alternatives. The first method makes sense although I haven't see .tpp extension before (quick Google says I can just use .cpp instead I think). The second method also makes sense, but it doesn't feel like it's a practical way.

I've no idea what a .tpp extension is, but yeah, you want your template code in a .h file (both implementation and declaration) because of the way they work, which is a bit confusing, but fundamentally has to do with the fact that the code is generated for a specific instance by the compiler when it's used with a particular type.

 

[SolKane]

Why are templates so confusing in C++?

I have to use them for a simple assignment implementing a generic Matrix but I'm still not sure how to do that. So say I have Matrix.h file, am I supposed to put all my declarations and definitions there and then just not have a Matrix.cpp file?

I was reading this Stack Overflow question and the top answer offered 2 more suitable alternatives. The first method makes sense although I haven't see .tpp extension before (quick Google says I can just use .cpp instead I think). The second method also makes sense, but it doesn't feel like it's a practical way.

For a small class you can just move the function definitions into the header file and leave out the implementation file. So for your case just use Matrix.h and leave out Matrix.cpp, but make sure you include the template declaration with every function in the header file. You don't need to use a .tpp file. Here's a good example of what the class declaration would look like:

template<class T> class X {
   public:
      T operator+(T);
};

template<class T> T X<T>::operator+(T arg1) {
   return arg1;
};

http://publib.boulder.ibm.com/infoc...oc/language/ref/class_templ_decl_and_defn.htm

 

[Master Milk]

Is there a preferred compiler for C++?

 

[usea]

Is there a preferred compiler for C++?

I've always used gcc via mingw (I'm on windows). I know a lot of people just use visual studio though.

I don't think it matters much for simple things.

 

[BriareosGAF]

Is there a preferred compiler for C++?

All of the interesting work in C family languages is happening in Clang these days. You should write some dodgy code and compare the warnings you get at various levels in clang, gcc, and cl (visual studio), should be an interesting experiment. Comparing code-gen at various optimization levels would also be educational.

 

[V_Arnold]

Hey folks! A quick javascript-related question!

Is there any reliable way to test how fast an operation actually is? The reason I ask is that I am about to write the basics for my combat system (in a strategy-rpg hybrid, will talk about it later in the Indie thread once it is in beta stage ), and looking at how flexible the objects are in JavaScript, I was thinking about clumping all of my objects (my units, enemy units, ai handlers, etc) into an array and passing that along as we go.

That approach is fine with the draw method, since I can just go through the whole array and use every object's draw(context) function, but with updating, things might go tricky. So would JS be prone to a serious slowdown if I start passing along dozens of objects as arguments between functions?

 

[usea]

Hey folks! A quick javascript-related question!

Is there any reliable way to test how fast an operation actually is? The reason I ask is that I am about to write the basics for my combat system (in a strategy-rpg hybrid, will talk about it later in the Indie thread once it is in beta stage ), and looking at how flexible the objects are in JavaScript, I was thinking about clumping all of my objects (my units, enemy units, ai handlers, etc) into an array and passing that along as we go.

That approach is fine with the draw method, since I can just go through the whole array and use every object's draw(context) function, but with updating, things might go tricky. So would JS be prone to a serious slowdown if I start passing along dozens of objects as arguments between functions?

I'm fairly sure that javascript is pass by value, but your objects and such are just references (basically the same way java and C# work) so you're not really going to incur a penalty. In fact, passing an array of 1000 objects to a function will cost the same as passing an array with one thing in it.
http://stackoverflow.com/questions/...a-pass-by-reference-or-pass-by-value-language

 

[V_Arnold]

I'm fairly sure that javascript is pass by value, but your objects and such are just references (basically the same way java and C# work) so you're not really going to incur a penalty. In fact, passing an array of 1000 objects to a function will cost the same as passing an array with one thing in it.

This should be completely fine. In JavaScript as in many languages, all objects that you pass around are actually references to objects. So when you pass an array of 1000 objects into your update function you're actually just passing a single value which is the location of the array in memory. The reference itself is passed by value, so you can't change where the original one points to, but any object you pass will be very low overhead. So no, you shouldn't have any issues as long as you're not recreating objects explicitly.

Thank you, that sounds great

 

[lorebringer]

Hey folks! A quick javascript-related question!

Is there any reliable way to test how fast an operation actually is? The reason I ask is that I am about to write the basics for my combat system (in a strategy-rpg hybrid, will talk about it later in the Indie thread once it is in beta stage ), and looking at how flexible the objects are in JavaScript, I was thinking about clumping all of my objects (my units, enemy units, ai handlers, etc) into an array and passing that along as we go.

That approach is fine with the draw method, since I can just go through the whole array and use every object's draw(context) function, but with updating, things might go tricky. So would JS be prone to a serious slowdown if I start passing along dozens of objects as arguments between functions?

This should be completely fine. In JavaScript as in many languages, all objects that you pass around are actually references to objects. So when you pass an array of 1000 objects into your update function you're actually just passing a single value which is the location of the array in memory. The reference itself is passed by value, so you can't change where the original one points to, but any object you pass will be very low overhead. So no, you shouldn't have any issues as long as you're not recreating objects explicitly.

Edit: Curse you usea!

 

[Mr_Appleby]

I know Pattern and Matcher exist, but I'm not familiar enough with it enough to know if it can do stuff like return the line number where the matching string is found or at least the beginning index so that I can run another regex on the all of the text after the match, etc.

afaik java Pattern knows nothing of line numbers (which are just counts of \n) so depending on your need you'll likely have to split the text file in some manner and run pattern matches on the resulting tokens. matches() only returns a boolean.

something like;

-get next token from file, increment char count by size of token
-if token is \n, increment line count, reset char count
-run pattern match on token. if found return line count, char count.

if your pattern is expected to cross multiple lines or use spaces then the method of grabbing chunks would have to change, or use smaller patterns to find chunk starts to run larger patterns on. Just thoughts.

 

[leroidys]

So I have some mysql homework stuff, and I am supposed to detect stock splits on some pretty giant databases of stock records.

What I have is essentially this (the math for it is a little different, but the query will basically look like this:

             SELECT A.TransDate 
             FROM pricevolume A, pricevolume B 
             WHERE DATEDIFF(B.transdate, A.transdate) = 1  AND 
                   A.ticker = 't' and B.ticker = 't' AND         
                   // 't' is my ticker var, based on user input
                   A.ClosePrice = B.OpenPrice  * 2;

This is the best way I could think of to do it, but the only problem is that it is SLOW AS ALL HELL.

Can anyone think of a better way to do this, without having to reference two different versions of the table maybe, or JUST selecting the next day instead of searching every single tuple from the B table for a DATEDIFF of 1?

 

[FerranMG]

Hi guys, I have a problem I hope you can help me solve.

I'm programming in Java a Pacman player. Currently I need it to eat n dots using the optimal path.
The approach I have chosen doesn't work because it finds memory limitations, and I'm thinking maybe I'm doing something inefficiently because I'm pretty new to Java.

I want to, somehow, get a list of all possible combinations of elements in a set.
For example, if the original set were {0, 1, 2}, I would want {0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}.
Things get messy when I use n >= 10.

I'm using a recursive algorithm and ArrayLists.
Each possible combination is stored in a list, and then each list is stored in a list of list.

I have the feeling that, since I can't use pointers, I'm either loading the lists with too much information, or creating too many temporal lists in the recursive algorithm.

Any thoughts or ideas? I don't know now what approach to try.

 

[usea]

Hi guys, I have a problem I hope you can help me solve.

I'm programming in Java a Pacman player. Currently I need it to eat n dots using the optimal path.
The approach I have chosen doesn't work because it finds memory limitations, and I'm thinking maybe I'm doing something inefficiently because I'm pretty new to Java.

I want to, somehow, get a list of all possible combinations of elements in a set.
For example, if the original set were {0, 1, 2}, I would want {0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}.
Things get messy when I use n >= 10.

I'm using a recursive algorithm and ArrayLists.
Each possible combination is stored in a list, and then each list is stored in a list of list.

I have the feeling that, since I can't use pointers, I'm either loading the lists with too much information, or creating too many temporal lists in the recursive algorithm.

Any thoughts or ideas? I don't know now what approach to try.

So much of this makes little sense to me.

What do you mean you can't use pointers? You said you're using Java. All non-primitives (any class you make, anything made with "new", etc) are all 'pointers'. They're references. You're not copying things every time you pass them to a method.

What does an optimal path in pacman have to do with finding all combinations?

When you say you need to find all combinations, the examples you showed were permutations (ie: order matters. {1,2,3} != {3,2,1}). Also curly braces {} usually indicates sets, which means order would not matter. Which is it? Do you want to find permutations, or combinations? Do they need to be the same length as the input set?

For discussion's sake, for 10 items, if you're trying to find all length-10 permutations, there's like 3.6 million of them.

You could definitely adjust your algorithm so it doesn't keep all the permutations in memory at once, which would get rid of the out-of-memory error. But it would still take a very long time to run.

What exactly are you trying to do?

 

[Mondriaan]

Hi guys, I have a problem I hope you can help me solve.

I'm programming in Java a Pacman player. Currently I need it to eat n dots using the optimal path.
The approach I have chosen doesn't work because it finds memory limitations, and I'm thinking maybe I'm doing something inefficiently because I'm pretty new to Java.

I want to, somehow, get a list of all possible combinations of elements in a set.
For example, if the original set were {0, 1, 2}, I would want {0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}.
Things get messy when I use n >= 10.

I'm using a recursive algorithm and ArrayLists.
Each possible combination is stored in a list, and then each list is stored in a list of list.

I have the feeling that, since I can't use pointers, I'm either loading the lists with too much information, or creating too many temporal lists in the recursive algorithm.

Any thoughts or ideas? I don't know now what approach to try.

Technically you're finding permutations, not combinations. Also, it looks like you're looking for permutations that contain all n elements. The number of n element permutations for a set of n (distinct) elements is equal to n factorial.

So, for n = 10, you would have 3628800 lists. It should be clear that generating all these lists is not going to scale.

Iterating through all the permutations would only require n iterators, but you will probably want to cull out permutations with some kind of heuristic (for instance merging some elements into a single element) because looping through all the permutations will be expensive time-wise.

 

[Mondriaan]

What exactly are you trying to do?

My guess is that this is an optimal path-finding problem where every dot is an element.

I would forget about optimal and instead look for a good enough solution. Probably make only the big dots, straight line segments of little dots, and dots at intersections into elements, and then try to form groups based on proximity to the big dots (have groupings prefer little dots that are far away from other big dots).

 

[Hari Seldon]

I just want to re-iterate how much I love Python. Wanted my data backend for a game to exist as an xml database. Trivial to handle this in Python. Wanted a data structure of a dictionary with another nested dictionary as the value, trivial again in python. Just love this language. Seems like every scenario you can dream up you can make happen.

 

[usea]

My guess is that this is an optimal path-finding problem where every dot is an element.

I would forget about optimal and instead look for a good enough solution. Probably make only the big dots, straight line segments of little dots, and dots at intersections into elements, and then try to form groups based on proximity to the big dots (have groupings prefer little dots that are far away from other big dots).

Like, finding the optimal path that hits every pellet from the get-go? Basically a hamiltonian path? But the pellets don't come anywhere close to forming a fully-connected graph. The vast majority of pellets cannot be adjacent in such a path. Most pellets only connect to 2 others.

If that's indeed what FerranMG is trying to do, then yeah I would definitely abandon that brute-force approach. In fact, it can't even work because afaik you can't actually create such a path on most pacman boards. It's impossible to visit every pellet only once; you'll have to occasionally walk over spots where you've already eaten the pellet. Intersections contain a pellet in the middle of them, which means you could never visit an intersection twice. Since there are multiple intersections, and they have more than 2 ways in/out, you cannot solve a pacman board by visiting every pellet-vertex only one time.

In other words, I don't think that's a good way to model the problem, as I understand it. I'm sure I'm missing something since not much was explained.

 

[lorebringer]

Hi guys, I have a problem I hope you can help me solve.

I'm programming in Java a Pacman player. Currently I need it to eat n dots using the optimal path.

Just wanted to chime in here and say that this problem is more difficult than you probably think it is and usually just a good approximation is fine. That being said, if you really want to do pathfinding for pacman eating n dots, then you should represent each "edge dot" (dots that have no neighbour on one side or junction points) on your map as a node with edge weights between them being a tuple storing the amount of squares to move through to get there and dots that exists on the path between. Then you can just run normal pathfinding using Djikstra. You'll need to mark each node with the cost of movement and dots eaten to get there via each path. Once a node has been visited with a number of dots eaten > n, you don't need to move on from it. Your solution is the path to the node with the smallest dot count >= n.

Quick and dirty explanation and there's probably a cleaner way to explain and implement but whatever, it's not a trivial problem. If you just want decent behaviour, you could do a greedy algorithm, just pick the path that minimises distance and dots eaten each time.

In other words, I don't think that's a good way to model the problem, as I understand it. I'm sure I'm missing something since not much was explained.

It's not really but you can definitely model each sequence of dots as a path. It gets messier than standard pathfinding also because path cost effectively increases after traversing once.

 

[Slavik81]

Is there a preferred compiler for C++?

The visual studio compiler has a number of oddities. For example, it mangles class and struct names differently, which has unfortunate implications. Its warnings are also a bit unfortunate: it's missing some good ones, and will warn about some perfectly reasonable things. It doesn't have much in the way of c99 support, and the C++11 support is lacking. However, it's nicely integrated with Visual Studio so it's probably the easiest to start using. Microsoft's suite of tools are definitely its greatest strength.

gcc is quite good. It has ok C++11 support, and good warnings. It's the standard for Linux and is usable on Windows with mingw.

clang is new, but its focus on understandable error messages and C++11 support has found it quite a few fans. I'm not sure its optimizations are as good as gcc or msvc, but unless you're writing commercial software that's unlikely to matter.

There's a few more, like Intel's compiler. But I'd say those are the big three.

Do people still write applications in C++? If so, why?

Yes. I know the parts that are bullshit well enough to avoid them. The language itself is very powerful, if rather verbose.

 

[FerranMG]

Thanks for the answers, I'll try to reply to some of the comments.

What do you mean you can't use pointers? You said you're using Java. All non-primitives (any class you make, anything made with "new", etc) are all 'pointers'. They're references. You're not copying things every time you pass them to a method.

Didn't know that (or had forgotten about it), thanks.

What does an optimal path in pacman have to do with finding all combinations?

When you say you need to find all combinations, the examples you showed were permutations (ie: order matters. {1,2,3} != {3,2,1}). Also curly braces {} usually indicates sets, which means order would not matter. Which is it? Do you want to find permutations, or combinations? Do they need to be the same length as the input set?

What exactly are you trying to do?

Technically you're finding permutations, not combinations. Also, it looks like you're looking for permutations that contain all n elements. The number of n element permutations for a set of n (distinct) elements is equal to n factorial.

So, for n = 10, you would have 3628800 lists. It should be clear that generating all these lists is not going to scale.

Iterating through all the permutations would only require n iterators, but you will probably want to cull out permutations with some kind of heuristic (for instance merging some elements into a single element) because looping through all the permutations will be expensive time-wise.

You're right, I was looking for permutations, and square brackets would have been better.

I was indeed trying to find the optimal path for PacMan to eat all the dots using a somehow brute force approach.
However, in this case (n >= 10) the pathfinding algorithm didn't even start, the program run out of memory just by generating all the permutations of the order in which to eat the dots.
I thought my approach was less "brute force" than it actually is, but it seems it's not.

My guess is that this is an optimal path-finding problem where every dot is an element.

I would forget about optimal and instead look for a good enough solution. Probably make only the big dots, straight line segments of little dots, and dots at intersections into elements, and then try to form groups based on proximity to the big dots (have groupings prefer little dots that are far away from other big dots).

In my problem there are no big dots.

Like, finding the optimal path that hits every pellet from the get-go? Basically a hamiltonian path? But the pellets don't come anywhere close to forming a fully-connected graph. The vast majority of pellets cannot be adjacent in such a path. Most pellets only connect to 2 others.

If that's indeed what FerranMG is trying to do, then yeah I would definitely abandon that brute-force approach. In fact, it can't even work because afaik you can't actually create such a path on most pacman boards. It's impossible to visit every pellet only once; you'll have to occasionally walk over spots where you've already eaten the pellet. Intersections contain a pellet in the middle of them, which means you could never visit an intersection twice. Since there are multiple intersections, and they have more than 2 ways in/out, you cannot solve a pacman board by visiting every pellet-vertex only one time.

In other words, I don't think that's a good way to model the problem, as I understand it. I'm sure I'm missing something since not much was explained.

I'm looking for an optimal path that hits every pellet, yeah.
It's not a hamiltonian path, though. Depending on how you look at it (I mean, depending on what is the definition of a state in this problem):
1) if the states are just the PacMan location, then you are allowed to be in the same state twice.
2) if the states contain, for example, the PacMan location and the location of all the remaining dots, then you would not be allowed to revisit a state, but also you would not need to visit all the nodes in the tree that represents the state space.

Just wanted to chime in here and say that this problem is more difficult than you probably think it is and usually just a good approximation is fine. That being said, if you really want to do pathfinding for pacman eating n dots, then you should represent each "edge dot" (dots that have no neighbour on one side or junction points) on your map as a node with edge weights between them being a tuple storing the amount of squares to move through to get there and dots that exists on the path between. Then you can just run normal pathfinding using Djikstra. You'll need to mark each node with the cost of movement and dots eaten to get there via each path. Once a node has been visited with a number of dots eaten > n, you don't need to move on from it. Your solution is the path to the node with the smallest dot count >= n.

Quick and dirty explanation and there's probably a cleaner way to explain and implement but whatever, it's not a trivial problem. If you just want decent behaviour, you could do a greedy algorithm, just pick the path that minimises distance and dots eaten each time.

It's not really but you can definitely model each sequence of dots as a path. It gets messier than standard pathfinding also because path cost effectively increases after traversing once.

I'm required to find the optimal solution, and I've also to use A*. I know a good approximation would be easier, but for this case it's ok if the algorithm spends even hours finding the optimal path for a large number of dots in the board.



So, what I'm going to try now is to ditch the former approach (ie, create and store all the permutations of n dots).
Instead, I will try to define each state as the location of the PacMan and the remaining number of dots. Each state (or node) will have a g values (number of moves that takes for the PacMan to get to that state), and h value (an heuristic, that would be for example the number of remaining dots, or maybe the minimum Manhattan distance to eat all dots (both of them are admissible)), and run the A* algorithm using as the final state one of the n possible states in that PacMan eats the last dot on the board.

I anyone is interested, I'll let you know how it goes.
If I haven't made myself clear in any point, feel free to ask.

 

[lorebringer]

I'm required to find the optimal solution, and I've also to use A*. I know a good approximation would be easier, but for this case it's ok if the algorithm spends even hours finding the optimal path for a large number of dots in the board.

Ok that makes it much more feasible, I had thought you were making a game, and therefore would find a shorter run time on the algorithm preferable to an exact solution. I had also thought that n could be less than the number of dots on the board. This isn't the case?

I think your plan of representing state is ok but you might want to consider a state representation of (pacmanLocation, edgesVisited). We can take advantage of a property of pacman boards related to dots which is that from a square containing a dot, the move to an adjacent dot will always be optimal. i.e. there's no point in stopping halfway down a hallway and coming around to it from the other side later, you'll still use the same number of steps or more (I think this holds but I'm not bothered proving it). With that in mind, can you define nodes as existing on the end dots of contiguous lines of dots?

e.g.

----|*|----
+****+***+
-----------

Node dots replaced with + symbol. Before you start your pathfinding, you can construct a list of edges that have to be visited as node pairs (startNode, endNode). g(x) should always be the number of steps moved so far, and f(x) should probably be related to number of edges left, possibly sum of manhatton dist between you and them? I think that would be admissable as well, maybe not. individual dots are irrelevant (you need to define some edges as (a, a) to account for single dot case).

Then as soon as you find a state where there are no edges left you should have an answer (assuming my suggested f(x) is actually admissable). Hope that helps, I only thought about this for a few minutes on paper so I could have some detail horribly wrong.

 

[Zeouterlimits]

Anyone know any good vbscript resources for someone new to the language?

I have to make a custom Outlook form (easy) and have it also generate a useful unique reference number, so I'm going to have to my hands down and dirty with vbscript.

 

[Chris R]

So I have some mysql homework stuff, and I am supposed to detect stock splits on some pretty giant databases of stock records.

What I have is essentially this (the math for it is a little different, but the query will basically look like this:

             SELECT A.TransDate 
             FROM pricevolume A, pricevolume B 
             WHERE DATEDIFF(B.transdate, A.transdate) = 1  AND 
                   A.ticker = 't' and B.ticker = 't' AND         
                   // 't' is my ticker var, based on user input
                   A.ClosePrice = B.OpenPrice  * 2;

This is the best way I could think of to do it, but the only problem is that it is SLOW AS ALL HELL.

Can anyone think of a better way to do this, without having to reference two different versions of the table maybe, or JUST selecting the next day instead of searching every single tuple from the B table for a DATEDIFF of 1?

Have you tried making a view using a self-join that has the info you need and then query that?

 

[Zoe]

So I have some mysql homework stuff, and I am supposed to detect stock splits on some pretty giant databases of stock records.

What I have is essentially this (the math for it is a little different, but the query will basically look like this:

             SELECT A.TransDate 
             FROM pricevolume A, pricevolume B 
             WHERE DATEDIFF(B.transdate, A.transdate) = 1  AND 
                   A.ticker = 't' and B.ticker = 't' AND         
                   // 't' is my ticker var, based on user input
                   A.ClosePrice = B.OpenPrice  * 2;

This is the best way I could think of to do it, but the only problem is that it is SLOW AS ALL HELL.

Can anyone think of a better way to do this, without having to reference two different versions of the table maybe, or JUST selecting the next day instead of searching every single tuple from the B table for a DATEDIFF of 1?

Maybe I'm alone in this, but I really dislike using implicit joins. You should analyze the query to make sure it isn't faster to declare it explicitly.

Edit: damn, new page. Here's rhfb's suggestion.

Have you tried making a view using a self-join that has the info you need and then query that?