|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
On August 27 2012 19:58 KainiT wrote:
While I do admit obviously that my understanding of backtracking was stupid, I would still like to know why my algorithm doesn't work -.-
I will write the code like you suggested now but not knowing why the previous one didn't work is kind of destroying my nerves right now.
I don't have the compiler ready to test it, but from a quick look it would suggest that it's an endless recursion with:
If valid, move forward. If invalid, move backwards, repeat for infinity.
However, i haven't really looked into that code in detail.
|
On August 27 2012 20:01 Morfildur wrote:Show nested quote +On August 27 2012 19:58 KainiT wrote:
While I do admit obviously that my understanding of backtracking was stupid, I would still like to know why my algorithm doesn't work -.-
I will write the code like you suggested now but not knowing why the previous one didn't work is kind of destroying my nerves right now. I don't have the compiler ready to test it, but from a quick look it would suggest that it's an endless recursion with: If valid, move forward. If invalid, move backwards, repeat for infinity. However, i haven't really looked into that code in detail.
Yeah, most likely, but they program has some strange behaviour that I don't understand at all like suddenly printing 10 to 12 numbers per row after going back. Anyways I will now use my new understanding of recursion. Seems waaaaaaaaaaaay easier to debug. thx 
|
I am done now
Still don't know why the previous algorithm didn't work but it is great to see how easy it can be with proper recursion.
I think this is even a bit simpler than what you suggested cause I don't need dynamic storage.
int solve(int r, int c)
{
if(c==9)
{
++r;
c=0;
if(r==9)
{
return 1;
}
}
if(vordefiniertefelderarray[r][c]>0)
{
return solve(r,c+1);
}
for(int i=1; i<=9; ++i)
{
if(!check(r,c,i))
{
sudfeld[r][c]=i;
if(solve(r,c+1))
{
feldausgeben(sudfeld);
return 0;
}
}
}
sudfeld[r][c]=0;
return 0;
}
|
Hello! I hope this is the right thread to ask this. I finally want to learn how to program. So what I want to do is program a GUI with which the user can solve Sudokus
Program starts, empty suduko field opens, user klicks on a field and types in the number. He does that until he is finished. Then there is a button which starts the solving processs.
I guess it's pretty straightforward and will hopefully cover a lot of must know techniques (like recursion).
So, I have a LITTLE BIT of experience in JAVA and C#. For example I know the difference between a for- and while-loop (in case these constructs are still used, lol). But thats pretty much it. So my questions:
a) I normally use UBUNTU and I dont want to use WINE and a windows based IDE so the IDE (emacs?) would have to be available for Linux/Ubuntu
b) I dont want the IDE to be super complex. What I hate the most when using software is when it is so complex you cant really do anything unless you spend a shitload of time to figure out what to do (hello Photoshop). I want to spend my time learning the API and how to program and not reading a book on how to use the IDE.
+ Show Spoiler + ![[image loading]](http://upload.wikimedia.org/wikipedia/commons/6/6c/Eclipse_4.2_Juno_screenshot.png) Just look at this, wtf. A thousend buttons and symbols, omg
c) I want the programm to be portable (JAVA and JVM like). While it probably is fascinating to program something for an Assembler thats not what I want to do.
d) I want full control over the GUI. I dont want some windows like dialogue boxes. As a start this might be ok, but if I wont be able to fully customize the GUI I will be very disappointed.
So I hope you can help me getting started, I'd appreciate it. Thank you!
|
+ Show Spoiler +On August 27 2012 22:22 Djin)ftw( wrote:Hello! I hope this is the right thread to ask this. I finally want to learn how to program. So what I want to do is program a GUI with which the user can solve Sudokus Program starts, empty suduko field opens, user klicks on a field and types in the number. He does that until he is finished. Then there is a button which starts the solving processs. I guess it's pretty straightforward and will hopefully cover a lot of must know techniques (like recursion). So, I have a LITTLE BIT of experience in JAVA and C#. For example I know the difference between a for- and while-loop (in case these constructs are still used, lol). But thats pretty much it. So my questions: a) I normally use UBUNTU and I dont want to use WINE and a windows based IDE so the IDE (emacs?) would have to be available for Linux/Ubuntu b) I dont want the IDE to be super complex. What I hate the most when using software is when it is so complex you cant really do anything unless you spend a shitload of time to figure out what to do (hello Photoshop). I want to spend my time learning the API and how to program and not reading a book on how to use the IDE. + Show Spoiler + Just look at this, wtf. A thousend buttons and symbols, omg c) I want the programm to be portable (JAVA and JVM like). While it probably is fascinating to program something for an Assembler thats not what I want to do. d) I want full control over the GUI. I dont want some windows like dialogue boxes. As a start this might be ok, but if I wont be able to fully customize the GUI I will be very disappointed. So I hope you can help me getting started, I'd appreciate it. Thank you!
Check out Qt. One of the best GUI programs available. Completely cross platform and open source. It includes it's own sdk with a c++ compiler, and there's also the option to write apps in markup language like xml.
|
Just a forewarning, solving sudokus might be a bit too complex for beginner programmers.
|
Hm so QT is an extension to C++ with a WYSIWYG editor? Hm. I have no idea what programming language is the most popular atm, but C++ seems a bit outdated. Or is it still used?
On August 27 2012 23:10 dottycakes wrote:
Just a forewarning, solving sudokus might be a bit too complex for beginner programmers.
Yeah well.. maybe I'll work on a chess GUI then if I should fail, thats no problem.
|
On August 27 2012 23:32 Djin)ftw( wrote:Hm so QT is an extension to C++ with a WYSIWYG editor? Hm. I have no idea what programming language is the most popular atm, but C++ seems a bit outdated. Or is it still used? Show nested quote +On August 27 2012 23:10 dottycakes wrote:
Just a forewarning, solving sudokus might be a bit too complex for beginner programmers. Yeah well.. maybe I'll work on a chess GUI then if I should fail, thats no problem.
As far as I am concerned c++(or even C) is still the most used language for big software projects like an operating system or Starcraft(:D) and people like myself start with it cause other languages are appearantly based on the C syntax as well.
If you just want to make a sudoku solver with gui c++ is certainly not a very good choice for that as c# or java will be much better suited.
|
Hm after a bit of research I think I'll learn Python and probably use DrPython. xD I'm too chobo for C/JAVA and emacs/eclipse lol. Maybe I'll look into this later. Thanks anyway!
|
On August 27 2012 23:10 dottycakes wrote:
Just a forewarning, solving sudokus might be a bit too complex for beginner programmers.
only if you try an intelligent algorithm.. you can always just brute force the thing in a few lines of code, that's suitable for beginners as well.
|
On August 27 2012 23:32 Djin)ftw( wrote:
Yeah well.. maybe I'll work on a chess GUI then if I should fail, thats no problem.
As long as you stick with the GUI it should be fine, but if you also want to verify a valid move, or determine states like check, check-mate and pat that is a whole other ballgame. If you don't want to brute force that is...
|
Hi guys,
I'm looking for a really fast way to find and remove duplicates in two lists in Python.
Right now my implementation does it via simple brute force, but it's way too slow for my uses. The two lists can possibly have over 20,000 items each.
This is what I've been working on so far. The first part finds two matching items, sets their value to some random string, repeat, then remove_all( list_obj, text ) will remove all instances of the text afterwards.
+ Show Spoiler +left = [...]#really long list of strings
right = [...]#really long list of strings
for i in range(len(left)):
if left[i] == "SETTOBEREMOVEDexa01%44":
continue
for j in range(len(right)):
if left[i].split() == right[j].split():
left[i] = "SETTOBEREMOVEDexa01%44"
right[j] = "SETTOBEREMOVEDexa01%44"
continue
left = remove_all(left, "SETTOBEREMOVED%44" )
right = remove_all(right, "SETTOBEREMOVED%44" ) The reason I cannot use sets is that I need to see if there are duplicate values. A common example of the list would be, given a = [1,1,3,2,3,3,2,2]
b = [1,1,2,3,2] I need the following by the end a = [2,3,3]
b = [] whereas sets would return equal. No one seems to have a fast way to find it for non-unique lists.
The original lists need to be returned in the same order they're passed in, so sorting isn't an option. :s I think I didn't remove them directly because I believe there are issues with messing with the size of lists/arrays while you're iterating through.
I'm thinking of sorting and then removing from all lists simultaneously ... but I can't imagine sorting would make things faster.
As far as I know, this seems to be the only way to do it. Any help would be appreciated! Right now my application hangs for 90s before completing. I would like to reduce it to around 10s if possible. If it can't be done, then it's fine. Thanks ^^
|
Not sure what you mean about removing duplicates. Do you mean the difference between a and b?
|
Blisse:
My first thought is that the fastest implementation will still involve sorting both lists first. Since you need to return the lists in original order, then as you sort the lists, you build/maintain a map from old=>new for each array. Once you have both arrays sorted, you iterate through them consecutively, removing items that are duplicates. The remaining arrays you restore to a final return array via the initial array index maps you created.
|
With ~20,000 items I can't imagine this taking more than a few seconds on decent hardware properly implemented.
|
On August 28 2012 10:28 Blisse wrote:Hi guys, I'm looking for a really fast way to find and remove duplicates in two lists in Python. Right now my implementation does it via simple brute force, but it's way too slow for my uses. The two lists can possibly have over 20,000 items each. This is what I've been working on so far. The first part finds two matching items, sets their value to some random string, repeat, then remove_all( list_obj, text ) will remove all instances of the text afterwards. left = [...]#really long list of strings
right = [...]#really long list of strings
for i in range(len(left)):
if left[i] == "SETTOBEREMOVEDexa01%44":
continue
for j in range(len(right)):
if left[i].split() == right[j].split():
left[i] = "SETTOBEREMOVEDexa01%44"
right[j] = "SETTOBEREMOVEDexa01%44"
continue
left = remove_all(left, "SETTOBEREMOVED%44" )
right = remove_all(right, "SETTOBEREMOVED%44" ) The reason I cannot use sets is that I need to see if there are duplicate values. A common example of the list would be, given a = [1,1,3,2,3,3,2]
b = [1,1,2,3,2] I need the following by the end a = [2,3,3]
b = [] whereas sets would return equal. No one seems to have a fast way to find it for non-unique lists. The original lists need to be returned in the same order they're passed in, so sorting isn't an option. :s I think I didn't remove them directly because I believe there are issues with messing with the size of lists/arrays while you're iterating through. I'm thinking of sorting and then removing from all lists simultaneously ... but I can't imagine sorting would make things faster. As far as I know, this seems to be the only way to do it. Any help would be appreciated! Right now my application hangs for 90s before completing. I would like to reduce it to around 10s if possible. If it can't be done, then it's fine. Thanks ^^
1) Why don't you just use "None" as your "stringtoremove"?
2) There is no point in continuing to go through the 'j' loop once you have already found a match.
3) I haven't tested it yet, but it seems that your example is wrong according to your code. I think it should be a = [3, 3], b = [].
Will think about it more later.
|
On August 28 2012 13:12 waxypants wrote:
1) Why don't you just use "None" as your "stringtoremove"?
2) There is no point in continuing to go through the 'j' loop once you have already found a match.
3) I haven't tested it yet, but it seems that your example is wrong according to your code. I think it should be a = [3, 3], b = [].
Will think about it more now.
Good catch! I didn't notice it. I'll look at some of your other suggestions. Thanks!
+ Show Spoiler +a = [1,1,3,2,3,4,2]
b = [1,1,2,3,4] into a = [3,2]
b = []
On August 28 2012 12:34 meatpudding wrote:
Not sure what you mean about removing duplicates. Do you mean the difference between a and b?
Basically I want to remove anything that appears in both, but if it appears twice in a and once in b, there has to be a copy remaining in a.
|
I think your new example is wrong also since you said the order must be maintained. I think it should be a = [3, 2] and b =[]
|
On August 28 2012 13:29 waxypants wrote:I think your new example is wrong also since you said the order must be maintained. I think it should be a = [3, 2] and b =[]
Oops, I got too caught up trying to fix the other one I didn't notice. :s
I can't use "None" because that can be a possible item in the list.
+ Show Spoiler +
def panels_sec_remove_all_duplicates(self, evt):
left = [..]
right = [..]
for i in range(len(left)):
if left[i] == "xae2134eei:nOne":
continue
for j in range(len(right)):
if right[i] == "xae2134eei:nOne":
continue
if left[i].split() == right[j].split():
left[i] = "xae2134eei:nOne"
right[j] = "xae2134eei:nOne"
break
edit:
Well, it's an array of strings. Strings being sentences, lines, newlines.
However, there's no guarantee that the sentences or lines are spaced properly, so the comparison should disregard spacing for the most part.
Using the None type throws an exception on None.split() . I guess I should just catch that and continue. :s
|
I meant the None type. You said it was an array of strings. So maybe you should clarify the possible types in the list. If you really meant that it was an array of values that could either be strings or None, then you could use use [] or any number (like 0). Basically, something that is guaranteed to fail the "==" test. I know I'm being really picky but you need to be very precise about your contraints when you are asking people to help optimize some arbitrary algorithm.
|
|
|
|
|
|
EPT
