• Hey, guest user. Hope you're enjoying NeoGAF! Have you considered registering for an account? Come join us and add your take to the daily discourse.

Programming |OT| C is better than C++! No, C++ is better than C

leroidys

Member
so strlcpy isn't part of the standard c library
but strncpy is... is the latter a safe replacement of strcpy?

I ask because anecdotally I was told strncpy is also unsafe. But I couldn't use strlcpy due to linking issues.

What are you using it for? I would just use snprintf (automatically null terminates).

strlcpy wouldn't link with the -lbsd flag?

What makes you think your workflow is bad?

Well I approach it like I do with c program, where I constantly recompile and test. With python, it's a pain in the ass because I have to reimport everything I'm working on every single time I make a change.
 

injurai

Banned
What are you using it for? I would just use snprintf (automatically null terminates).

strlcpy wouldn't link with the -lbsd flag?

doing threading with pthread.h and semaphore.h

and no -lbsd is not working.

strncpy is doing the job just fine, since I'm in a critical section I'm not wanting to print inside of it.
 

leroidys

Member
doing threading with pthread.h and semaphore.h

and no -lbsd is not working.

strncpy is doing the job just fine, since I'm in a critical section I'm not wanting to print inside of it.

It doesn't print to a stream, it copies it into a buffer that you give it. strncpy is fine, but if you want a safer alternative, snprintf is it.
 

injurai

Banned
It doesn't print to a stream, it copies it into a buffer that you give it. strncpy is fine, but if you want a safer alternative, snprintf is it.

awesome, learned something new.

ultimately it comes down to the overhead in this instance, as I want to push as much out of the critical section as I can. So if that is just a print redirect, print is exactly what I'm trying to take out. Then again strncpy might have just as much over head... I have really done any testing or reading up on this to know.

it's nice to know safe alternatives when using c strings. C strings are nothing to be afraid of but I swear there can be some piss poor instruction in books on how to handle strings.
 

leroidys

Member
awesome, learned something new.

ultimately it comes down to the overhead in this instance, as I want to push as much out of the critical section as I can. So if that is just a print redirect, print is exactly what I'm trying to take out. Then again strncpy might have just as much over head... I have really done any testing or reading up on this to know.

it's nice to know safe alternatives when using c strings. C strings are nothing to be afraid of but I swear there can be some piss poor instruction in books on how to handle strings.

Yeah, the thing that makes it a pain in the ass is you have no idea how your functions are actually implemented and what other functions they call, how much context switching is involved, etc. In this case, both are writing into a fixed buffer, so I don't think the efficiency should be very different. Just be sure to malloc (if you have to at all) outside of the critical section, as that's a very slow call. If you're using strncpy, but sure to null terminate your string somehow.
 

injurai

Banned
Yeah, the thing that makes it a pain in the ass is you have no idea how your functions are actually implemented and what other functions they call, how much context switching is involved, etc. In this case, both are writing into a fixed buffer, so I don't think the efficiency should be very different. Just be sure to malloc (if you have to at all) outside of the critical section, as that's a very slow call. If you're using strncpy, but sure to null terminate your string somehow.

strncpy you specify the length, so right now my implementation isn't worrying about null terminating. Now when I do go to print it I probably should be null terminating but It seems the formatting is taking care of everything.

but now that you mention it I'm surprised I'm not getting output errors. Using a non-null-terminated array and formatting with %s
 
Well I approach it like I do with c program, where I constantly recompile and test. With python, it's a pain in the ass because I have to reimport everything I'm working on every single time I make a change.

What do you mean reimport everything? Doesn't sound like something you should have to do.
 

leroidys

Member
What do you mean reimport everything? Doesn't sound like something you should have to do.

  1. Edit 'thing.py'
  2. Save 'thing.py'
  3. 'python thing.py'
  4. goto 1



Yeah... Seems a little odd.

Say I have a python module, stuff.py. I have a bunch of functions in that module, which I want to test one at a time.

Code:
$python
>>>>import stuff
>>>>stuff.doStuff(argument)
>>>>                       ^some errors, you fail

At this point, if I again type in "import stuff", it doesn't actually update the version of stuff that it imported.

So I can just ctrl+d the python interpreter and start over, import, and retype my function call, or I can use a reimport command, but that won't update the references to stuff in any other modules that I have imported instances of. It's really annoying. If I have long arguments I'm trying to test on specific functions, I'm copy/pasting stuff in the terminal window a lot, which means using the mouse, which sucks.
 

Slavik81

Member
Write an actual python script for your tests. Maybe 'test_stuff.py'.

Edit the program. Edit the test. Run the test. Repeat.
Or TDD it, and edit the test before the program.
 

iapetus

Scary Euro Man
At this point, if I again type in "import stuff", it doesn't actually update the version of stuff that it imported.

So don't use the interactive interpreter - do exactly what Slavik81 was suggesting; edit a test file (with all the imports in it) and run it from the command line.

[Edit: Beaten. :)]
 

leroidys

Member
Write an actual python script for your tests. Maybe 'test_stuff.py'.

Edit the program. Edit the test. Run the test. Repeat.
Or TDD it, and edit the test before the program.

Yeah, that makes sense. So you guys don't have a live python interpreter running? It seems like that's what most people at my school do, though I don't really have any idea why. It seems like such a pain in the ass to write a script for every test case, but I guess it will probably save me time in the long run.

Anyway, thanks for the input everyone.
 

iapetus

Scary Euro Man
Yeah, that makes sense. So you guys don't have a live python interpreter running? It seems like that's what most people at my school do, though I don't really have any idea why. It seems like such a pain in the ass to write a script for every test case, but I guess it will probably save me time in the long run.

It will save a *lot* of time, because you're likely to want to run the same tests more than once over the life of a program. Look into test driven design. Also look into testing frameworks for Python - can't help with that personally, but I'd be shocked and horrified if there weren't a way of making writing sets of tests a lot easier and more powerful.
 

Slavik81

Member
Yeah, that makes sense. So you guys don't have a live python interpreter running? It seems like that's what most people at my school do, though I don't really have any idea why. It seems like such a pain in the ass to write a script for every test case, but I guess it will probably save me time in the long run.
I don't use the interactive interpreter, no. The method I described is exactly how I wrote my only real python project: guardonce (a tool to switch back and forth between include guards and pragma once in C/C++ headers).

Though, I'm admittedly a python newbie, so if anyone wants to take a look and give me advice, that would be great. I've been meaning to give it a few touch-ups before calling it 'done'.

Also look into testing frameworks for Python - can't help with that personally, but I'd be shocked and horrified if there weren't a way of making writing sets of tests a lot easier and more powerful.
I've tried a few, but I just ended up using the standard unittest framework. It's simple and available with just 'import unittest'.

Others might be better, but since it's built into the language, it's the simplest to start with.

Yeah, that makes sense. So you guys don't have a live python interpreter running? It seems like that's what most people at my school do, though I don't really have any idea why. It seems like such a pain in the ass to write a script for every test case, but I guess it will probably save me time in the long run.

Anyway, thanks for the input everyone.
You can just add new cases to the same script.
 

Tristam

Member
Heck, in C#, it might depend on the way you're accustomed to adding the key and value. With the Dictionary<K,V> class (the modern .NET hashtable), your outcome may differ depending upon what approach you use, so if you're asking from one perspective, and the candidate answers from another, you might simply miss each other.

For example:

Code:
var table = new Dictionary<int, string>();
table.Add(1, "Hello"); // adds key-value
table.Add(1, "World");  // ArgumentException for same key


var table2 = new Dictionary<int, string>();
table2[1] = "Hello"; // adds key-value
table2[1] = "World"; // writes over existing value

If you are a developer accustomed to writing to the dictionary via the first code snippet, then you would expect the second Add to fail. If you are accustomed to writing with the second snippet, you would expect it to succeed. Sure, ideally, the person would know both (as should you), but to be honest, I'm not going to grill somebody over this particular distinction, I have larger problems to worry about for a senior level developer.

Never written any code in C#, and just looked up hash tables as I didn't know exactly what they were, but it seems that hash tables are what languages use under the hood to implement, among other things, associative arrays/dictionaries/hashes. The example makes it seem as though there's a 1:1 relationship between a hash table's buckets and a hash's keys--if that were the case, I don't think you would ever have to worry about collision, as any 'collision' that occurred would be intentional.
 

tuffy

Member
  1. Edit 'thing.py'
  2. Save 'thing.py'
  3. 'python thing.py'
  4. goto 1
Alternatively, one can replace step 3 with: "python -i thing.py"

This drops you into interactive mode for additional testing without have to re-type everything in thing.py every time.
 
You don't need to understand how it works to get that question right, though. Just to apply a very small amount of common sense.

Ah, I was thinking more on a lower level. How the hashes work, how hash collision works, why it can be important to declare a set size of the hashmap, load factor, etc.
 

Hylian7

Member
So really dumb question coming up.

I'm currently looking for my first developer job and had an interview for one that seemed promising yesterday. It was a Java developer position.

In the interview I got the usual "So tell me about yourself, etc."

After that came the more difficult part. She wrote some input and output patterns of strings and asked me to identify the pattern. I did that part with no problem, then she asked me to go to the whiteboard and implement a method that would take a String input and come up with the correct output. I got kind of nervous and tried to do it an overcomplicated and convoluted way first, then changed a bunch of things and sat there and tried to make sure it was right. She said the approach I went for (two for loops) would work but was much more complicated than it needed to be. I also had some mistakes I didn't catch immediately.

The next question was with an object called "Room" which had method for getting rooms to the for cardinal directions, and a boolean method isExit(). It was a maze and I needed to write a method that would return the exit room from any room in the maze. I tried to approach it with two recursive methods that would check all the directions and stop if it was the exit. It was only after I thought I was done I realized my mistake: It would basically end up going in circles. She asked how I could circumvent this problem and my answer was to keep an array of all the vertexes and mark them checked. She said this was also convoluted and unnecessary.

She asked what my biggest weakness was and I said it was overcomplicating things like I did in those two examples. I got to ask her questions next and asked how I did. Her answer was basically "I'll have to think about it, you know how to code but were overcomplicating things. Of course it is an interview and you were probably nervous, which happens to everyone."

This got me thinking: When I program I always tend to overcomplicate everything. How do you keep yourself from doing this? I don't end up coming up with the simpler solutions to a problem until much later on development. Yet I always hear about people able to write these O(log n) solutions on the first try and I usually never get that.
 

leroidys

Member
So really dumb question coming up.

I'm currently looking for my first developer job and had an interview for one that seemed promising yesterday. It was a Java developer position.

In the interview I got the usual "So tell me about yourself, etc."

After that came the more difficult part. She wrote some input and output patterns of strings and asked me to identify the pattern. I did that part with no problem, then she asked me to go to the whiteboard and implement a method that would take a String input and come up with the correct output. I got kind of nervous and tried to do it an overcomplicated and convoluted way first, then changed a bunch of things and sat there and tried to make sure it was right. She said the approach I went for (two for loops) would work but was much more complicated than it needed to be. I also had some mistakes I didn't catch immediately.

The next question was with an object called "Room" which had method for getting rooms to the for cardinal directions, and a boolean method isExit(). It was a maze and I needed to write a method that would return the exit room from any room in the maze. I tried to approach it with two recursive methods that would check all the directions and stop if it was the exit. It was only after I thought I was done I realized my mistake: It would basically end up going in circles. She asked how I could circumvent this problem and my answer was to keep an array of all the vertexes and mark them checked. She said this was also convoluted and unnecessary.

She asked what my biggest weakness was and I said it was overcomplicating things like I did in those two examples. I got to ask her questions next and asked how I did. Her answer was basically "I'll have to think about it, you know how to code but were overcomplicating things. Of course it is an interview and you were probably nervous, which happens to everyone."

This got me thinking: When I program I always tend to overcomplicate everything. How do you keep yourself from doing this? I don't end up coming up with the simpler solutions to a problem until much later on development. Yet I always hear about people able to write these O(log n) solutions on the first try and I usually never get that.

Try to write out a plan before you write a single line of code. For the rooms problem for example, try and relate it to other problems you may have encountered. In this case, it's a graph searching algorithm.

One thing that helped my code a lot was realizing how often state diagrams could improve my code, and actually drawing out some sort of automaton to represent how my program would proceed.

In terms of getting logn, nlogn, n, even n^2 solutions... it's honestly not that big of a deal outside of interviews as long as you're not writing something that's bigger than n^3, or working on some software that needs to be especially performant or has large inputs. Anyway, the best way to be able to reach these time complexities is honestly just to memorize and thoroughly understand a lot of of classic algorithms that perform in these times. Then you'll have a large array (lol) of tools to use, and you can apply these algorithms directly, or come up with some kind of modified version that would suit your needs.

Either that or be a theoretical math genius.

It will save a *lot* of time, because you're likely to want to run the same tests more than once over the life of a program. Look into test driven design. Also look into testing frameworks for Python - can't help with that personally, but I'd be shocked and horrified if there weren't a way of making writing sets of tests a lot easier and more powerful.

I don't use the interactive interpreter, no. The method I described is exactly how I wrote my only real python project: guardonce (a tool to switch back and forth between include guards and pragma once in C/C++ headers).

Though, I'm admittedly a python newbie, so if anyone wants to take a look and give me advice, that would be great. I've been meaning to give it a few touch-ups before calling it 'done'.


I've tried a few, but I just ended up using the standard unittest framework. It's simple and available with just 'import unittest'.

Others might be better, but since it's built into the language, it's the simplest to start with.


You can just add new cases to the same script.

Thanks, that testing framework is going to be tremendously helpful.
 

Kalnos

Banned
This got me thinking: When I program I always tend to overcomplicate everything.

Everyone does, I think, especially when they're put in front of someone and told to write on a whiteboard. Practice is really all you can do and the interviews are great practice.

Just keep applying
 

Slavik81

Member
Everyone does, I think, especially when they're put in front of someone and told to write on a whiteboard. Practice is really all you can do and the interviews are great practice.

Just keep applying
"If I had more time, I could have written a shorter letter." ~ (attributed to) Pascal
 

Granadier

Is currently on Stage 1: Denial regarding the service game future
Just as an update to my school situation.

On Friday I toured a university I was looking at transferring to. They recently built a new building dedicated to labs and research. The director of the computer engineering department took me through the building and showed me all of the different technology and classrooms they are utilizing throughout the building, and I was really impressed.

He also informed me that they are in the process of adding a Bachelor's of Science in Software Engineering major that will be available starting my junior year.

I am really excited and will be transferring for this fall semester as there will be no difference in tuition.
 

usea

Member
Just as an update to my school situation.

On Friday I toured a university I was looking at transferring to. They recently built a new building dedicated to labs and research. The director of the computer engineering department took me through the building and showed me all of the different technology and classrooms they are utilizing throughout the building, and I was really impressed.

He also informed me that they are in the process of adding a Bachelor's of Science in Software Engineering major that will be available starting my junior year.

I am really excited and will be transferring for this fall semester as there will be no difference in tuition.
The most important thing when deciding whether to transfer is figuring out how many credits will transfer.
 

Granadier

Is currently on Stage 1: Denial regarding the service game future
The most important thing when deciding whether to transfer is figuring out how many credits will transfer.

Thankfully the two schools are in the same system, so my credits transfer over completely.
 

Magni

Member
Professionally I'm a backend developer (Rails/Django), but I'm trying my hand at WP8 development for a personal project, and wow do I feel completely lost.

My app communicates with an API, it sends a request and get a response back. So far so good. But now, what do I do with the response? The JSON looks like this:

Code:
{
  "pagination": {},
  "data": [
    {...},
    {...},
  ]
}

I only care about the "data" array, each element corresponds to a "Payment" and I want to get a List<Payment>. In Rails I would do something like: response["data"].map { |p| Payment.new(p) } and be done with it, but here it's clearly something more complicated. Any pointers?

My code currently looks like this:

Code:
public List<Payment> GetPayments(int limit, DateTime before, DateTime after)
{
  string requestUri = "this is the API url with parameters";
  HttpWebRequest request = (HttpWebRequest)HttpWebRequest.Create(requestUri);

  request.BeginGetResponse(GetPaymentsCallback, request);
  return new List<Payment>();
}

void GetPaymentsCallback(IAsyncResult result)
{
  HttpWebRequest request = result.AsyncState as HttpWebRequest;
  if (request != null)
  {
    try
    {
      WebResponse response = request.EndGetResponse(result);
      // now what?                    
    }
    catch (WebException e)
    {
      // error stuff here
      return;
    }
  }
}
 

Water

Member
The next question was with an object called "Room" which had method for getting rooms to the for cardinal directions, and a boolean method isExit(). It was a maze and I needed to write a method that would return the exit room from any room in the maze. I tried to approach it with two recursive methods that would check all the directions and stop if it was the exit. It was only after I thought I was done I realized my mistake: It would basically end up going in circles. She asked how I could circumvent this problem and my answer was to keep an array of all the vertexes and mark them checked. She said this was also convoluted and unnecessary.
Is this the full problem description? I have a hard time coming up with a solution that doesn't involve keeping track of visited or fringe nodes, unless something more is known about the maze - e.g. that it's a regular grid where every room has four doors, or that it has no loops.
 
Alright this is the weirdest issue I've ever encountered. For an assignment I submitted it compiled and ran perfectly last night on the very same machine I'm typing on now. Today when I go to compile and run it throws a ton of errors about my use of std::vector and std::string saying use of undeclared identifier 'std'.

The files didn't change at all either. So.
 

Water

Member
Alright this is the weirdest issue I've ever encountered. For an assignment I submitted it compiled and ran perfectly last night on the very same machine I'm typing on now. Today when I go to compile and run it throws a ton of errors about my use of std::vector and std::string saying use of undeclared identifier 'std'.

The files didn't change at all either. So.
Same compiler as before? Same compiler arguments as before? Same environment variables set?
 

Chris R

Member
Professionally I'm a backend developer (Rails/Django), but I'm trying my hand at WP8 development for a personal project, and wow do I feel completely lost.

My app communicates with an API, it sends a request and get a response back. So far so good. But now, what do I do with the response? The JSON looks like this:

http://json.codeplex.com/

You need to deserialize the data you get back into a Payment object (if you are returning a list of Payment objects). Also you might want to look into the using a using block for some of this code, some of the web request classes get funky if you don't properly release/dispose of them...
 

usea

Member
Professionally I'm a backend developer (Rails/Django), but I'm trying my hand at WP8 development for a personal project, and wow do I feel completely lost.

My app communicates with an API, it sends a request and get a response back. So far so good. But now, what do I do with the response? The JSON looks like this:

Code:
{
  "pagination": {},
  "data": [
    {...},
    {...},
  ]
}

I only care about the "data" array, each element corresponds to a "Payment" and I want to get a List<Payment>. In Rails I would do something like: response["data"].map { |p| Payment.new(p) } and be done with it, but here it's clearly something more complicated. Any pointers?
You need to deserialize the json to an object. I strongly recommend using the excellent library json.net which is what everybody uses. You can get it via nuget package management, or from the website.

Once you have the json response as a string, you should deserialize it to an instance of a class you've defined, which matches the format of the response. For example:

Code:
public class FooResponse
{
	public object pagination { get; set; }
	public List<Payment> data { get; set; }
}

public class Payment
{
	public int Value { get; set; }
}
(I pretended your Payment class has a value field)

Then getting at your payments becomes:
Code:
string jsonResponse = GetResponseSomehow();
FooResponse responseObject = JsonConvert.DeserializeObject<FooResponse>(responseString);
List<Payment> payments = responseObject.data;

In this code, there's only one Payment class, which matches both the format of the data array in the json and also whatever you need it for in the rest of your code. In practice, I recommend having a different class for each purpose. One to match the json, and one to serve your own needs. You can define a map function to go between them.

By the way, in C# map is called Select, and it's available on basically any collection. It takes a lambda just like in ruby. filter is called Where.
 

Hylian7

Member
Is this the full problem description? I have a hard time coming up with a solution that doesn't involve keeping track of visited or fringe nodes, unless something more is known about the maze - e.g. that it's a regular grid where every room has four doors, or that it has no loops.

No, just a basic rundown. I'll give all I can remember about the problem though:

Code:
public class Room {
     public Room getN() {
          //Gets north room
     }
     public Room getS() {
          //Gets north room
     }
     public Room getE() {
          //Gets north room
     }
     public Room getW() {
          //Gets north room
     }
     public boolean isExit() {
          //returns whether the room is the exit or not
     }
}

That's the "Room" class. You have to write a method(s) that will tell you where the exit is from any room in the maze. The maze can be completely randomly generated, but will only have one exit.
 

Flai

Member
Heck, in C#, it might depend on the way you're accustomed to adding the key and value. With the Dictionary<K,V> class (the modern .NET hashtable), your outcome may differ depending upon what approach you use, so if you're asking from one perspective, and the candidate answers from another, you might simply miss each other.

For example:

Code:
var table = new Dictionary<int, string>();
table.Add(1, "Hello"); // adds key-value
table.Add(1, "World");  // ArgumentException for same key


var table2 = new Dictionary<int, string>();
table2[1] = "Hello"; // adds key-value
table2[1] = "World"; // writes over existing value

If you are a developer accustomed to writing to the dictionary via the first code snippet, then you would expect the second Add to fail. If you are accustomed to writing with the second snippet, you would expect it to succeed. Sure, ideally, the person would know both (as should you), but to be honest, I'm not going to grill somebody over this particular distinction, I have larger problems to worry about for a senior level developer.

Umm, I'm pretty sure that those aren't hash collisions. Hash collisions happen when two different keys produce the same hash (not necessarily exactly same, but 'hash % BUCKETS' is the same) and the hash map (in this case, Dictionary) must internally resolve the collision (IIRC, usually by using a list for all the value which produce the same hash). I'm not 100% sure about this though (or if you are talking about the same thing, although it seems like you arent).
 

Slavik81

Member
Is this the full problem description? I have a hard time coming up with a solution that doesn't involve keeping track of visited or fringe nodes, unless something more is known about the maze - e.g. that it's a regular grid where every room has four doors, or that it has no loops.
If you do a breath-first search you'll hit the end on one branch even if the others never terminate.

I'm not sure I'd call that simpler, though. Maybe there was a misunderstanding.
 

Magni

Member
http://json.codeplex.com/

You need to deserialize the data you get back into a Payment object (if you are returning a list of Payment objects). Also you might want to look into the using a using block for some of this code, some of the web request classes get funky if you don't properly release/dispose of them...

You need to deserialize the json to an object. I strongly recommend using the excellent library json.net which is what everybody uses. You can get it via nuget package management, or from the website.

Once you have the json response as a string, you should deserialize it to an instance of a class you've defined, which matches the format of the response. For example:

Code:
public class FooResponse
{
	public object pagination { get; set; }
	public List<Payment> data { get; set; }
}

public class Payment
{
	public int Value { get; set; }
}
(I pretended your Payment class has a value field)

Then getting at your payments becomes:
Code:
string jsonResponse = GetResponseSomehow();
FooResponse responseObject = JsonConvert.DeserializeObject<FooResponse>(responseString);
List<Payment> payments = responseObject.data;

In this code, there's only one Payment class, which matches both the format of the data array in the json and also whatever you need it for in the rest of your code. In practice, I recommend having a different class for each purpose. One to match the json, and one to serve your own needs. You can define a map function to go between them.

By the way, in C# map is called Select, and it's available on basically any collection. It takes a lambda just like in ruby. filter is called Where.

Thanks guys, I ended up using Json.net after watching these pretty good tutorials on Channel9: http://channel9.msdn.com/Series/Win...s/Part-26-Retrieving-a-Photo-from-Flickrs-API (along with chapters 27 and 28).
 

Water

Member
If you do a breath-first search you'll hit the end on one branch even if the others never terminate.

I'm not sure I'd call that simpler, though. Maybe there was a misunderstanding.
BFS uses a queue to keep track of the fringe nodes, it's not simpler by any means.
A solution occurred to me that does not involve explicitly keeping track of visited nodes, and will work with any maze, but it's almost too retarded to post. I seriously hope the interviewer wasn't looking for this - if she was, Hylian7 dodged a bullet when failing the interview.
Iterative deepening brute force recursion ¯\_(&#12484;)_/¯
 

leroidys

Member
BFS uses a queue to keep track of the fringe nodes, it's not simpler by any means.
A solution occurred to me that does not involve explicitly keeping track of visited nodes, and will work with any maze, but it's almost too retarded to post. I seriously hope the interviewer wasn't looking for this - if she was, Hylian7 dodged a bullet when failing the interview.
Iterative deepening brute force recursion ¯\_(&#12484;)_/¯

You can do a depth first search without needing another data structure hypothetically (the program's stack acts as your data structure). The weird thing about this question is that you are given an already made class, so if you can't augment rooms with a color or visited status or something, you need to keep an auxiliary data structure.
 

Chris R

Member
That isn't a dumb solution to mazes.

If you want something that is "dumb" just use the left hand rule (assuming the maze is simply connected). You will solve the puzzle no matter what.
 

Hylian7

Member
BFS uses a queue to keep track of the fringe nodes, it's not simpler by any means.
A solution occurred to me that does not involve explicitly keeping track of visited nodes, and will work with any maze, but it's almost too retarded to post. I seriously hope the interviewer wasn't looking for this - if she was, Hylian7 dodged a bullet when failing the interview.
Iterative deepening brute force recursion ¯\_(&#12484;)_/¯

Kind of doubt she was looking for that. That said I don't think I completely failed, like I said I think it was about 50/50. I still haven't gotten a call back, but they should call me back by tomorrow whether they are going further or not.
 
So, I graduated a year ago with a BS in Mathematics and minor in computer science. I always loved the programming and computer science courses, but since I left college, I haven't touched the stuff. I've got some spare time now so I've started fooling around with making an Android App (And I mean just started. Like 30 minutes ago). So I don't really know why I'm posting this except to say Hi and hopefully I'll be around here more often if I actually stick to my goal of relearning and improving on my knowledge. I'd love nothing more than to be able to make some simple apps, even if they only ever show up on my phone. I'm currently running through the "Building Your First App" guide on developer.android.com, so wish me luck that I don't get bored of this tomorrow!
 

Granadier

Is currently on Stage 1: Denial regarding the service game future
So, I graduated a year ago with a BS in Mathematics and minor in computer science. I always loved the programming and computer science courses, but since I left college, I haven't touched the stuff. I've got some spare time now so I've started fooling around with making an Android App (And I mean just started. Like 30 minutes ago). So I don't really know why I'm posting this except to say Hi and hopefully I'll be around here more often if I actually stick to my goal of relearning and improving on my knowledge. I'd love nothing more than to be able to make some simple apps, even if they only ever show up on my phone. I'm currently running through the "Building Your First App" guide on developer.android.com, so wish me luck that I don't get bored of this tomorrow!

Hi!

Android is fun. Here is a link to some website references if your looking for help or ideas.

2 major exams tomorrow, going to do horrible on both (well not great on one, horrible on the other). This semester sucks. :(

Yep it does. I got 61/100 on my Discrete midterm Thursday. Class average was 60.
Good luck on yours though!
 

tokkun

Member
That isn't a dumb solution to mazes.

If you want something that is "dumb" just use the left hand rule (assuming the maze is simply connected). You will solve the puzzle no matter what.

I was thinking the same thing, but I would hope that wasn't the intent, since that requires some domain knowledge about mazes, which is not generally applicable to programming.

Odds are that the intention was BFS or DFS, since mazes are the textbook example used to teach those algorithms.
 
You know, I really don't understand why more CS classes (at least out of what I've taken) don't have predefined test cases that you have to pass for your assignments. I've really only had one class that did that. It makes it easier for us and the grader...we know exactly what we need to produce, and the grader can more easily evaluate our code without having to comb over every inch of it. It would also, I assume, help students develop some good TDD habits.

My most recent assignment is up to about 8 separate classes spread out over various files. And the assignment description was rather vague on the required output, so I can only imagine that this will not be particularly enjoyable for the grader...
 

Chris R

Member
I was thinking the same thing, but I would hope that wasn't the intent, since that requires some domain knowledge about mazes, which is not generally applicable to programming.

Odds are that the intention was BFS or DFS, since mazes are the textbook example used to teach those algorithms.

It requires no knowledge of mazes, but rather sparsely connected graphs, something applicable to programming every now and then :)
 

Slavik81

Member
Iterative deepening brute force recursion ¯_(&#12484;)_/¯
That seems to just be 'breath-first, recalculating intermediate results when needed, rather than storing them'. Though, 'iterative deepening depth first' has a better ring to it than my description, for sure.

That isn't a dumb solution to mazes.

If you want something that is "dumb" just use the left hand rule (assuming the maze is simply connected). You will solve the puzzle no matter what.
I've never taken graph theory, so I'm not sure what 'simply connected' means, but can't that algorithm get you stuck in a loop if you start with one on your left?


I really think there was more to it. Something was not correctly said or understood.
 

Water

Member
That seems to just be 'breath-first, recalculating intermediate results when needed, rather than storing them'. Though, 'iterative deepening depth first' has a better ring to it than my description, for sure.
No, BFS has very different behavior. My suggestion is essentially iterative deepening depth first search but without backtracking prevention. Or sanity. Recursion is just an implementation detail; equivalent pseudocode is
Code:
loop L = 1.. infinity
  generate all possible NSEW movement combinations of length L
  attempt to walk each one; bail when walking over exit
So this genius algorithm will check locations like "north-south-north-south" for the exit over and over again.
 
Top Bottom