I thought about it a bit and changed my algorithm. Now I check every word that is one letter different from the current word instead of following every path to the end. Each letter change is a new level and I move down the level checking all new words against the target. When the target is found this is the shortest path.
I could put the dictionary into a hash and speed it up, but I am more interested in the algorithm.
Thanks...
davidcollins001
Last Activity: May 8 '11, 09:10 PM
Joined: Mar 6 '08
Location:
-
Thank you for pointing out the errors, I would have expected to get more errors not allocating memory properly but it seemed to work and is fixed now. Also the head of the list is fixed. I knew about the (extensive) memory leak I will fix that when I understand the algorithm.
About the algorithm, this method I am using seems to work. However, it is slow and won't always find the quickest path unless I search every word in the dictionary,...Leave a comment:
-
letter exchange algorithm
Hi,
I came across a neat problem that I have been trying to code to improve my programming problem solving skills. It is quite simple but I am struggling to get my head around it. Any help would be much appreciated.
The problem is the following: a starting word, such as head, is transformed into a second word, such as tail, by way of changing a single letter at a time. All intermediate words must be in the dictionary.... -
C stack and main()
Hi,
I am trying to write a stack walking program to trace back along the stack for a process that the trace function is called from. I am doing it the cheating way, in that I have a ruby program (not mine) that fills in an array with the names of functions and arguments, arg types and arguments offset from that frames ebp for all of the functions on the stack. So far I have been able to get it working correctly for all functions except... -
I have only briefly looked at mutexes, but don't they only enforce only one process to be allowed into the region much the same as a semaphore?
I have managed to figure out how to get the processes to take turns. For completeness and for anyone else who is wondering I did it with 3 semaphores:
[CODE]
sem[0] = 1
sem[1] = 0
sem[2] = 1
[\CODE]
proc 1
[CODE]
while(condition )...Leave a comment:
-
Thankyou both for replying, I should have said I am using C.
Raghu, I already have a working version of what you suggest. I don't much like the idea of using sleep to synchronise processes, I don't feel like it is true synchronisation . I would really like it so that the first process waits forever if the second was never started, instead of doing all the work on its own. It is probably a bit contrived but I would like to be able to...Leave a comment:
-
semaphores
Hi,
Firstly please excuse the long ramblingness. I need some conceptual help, I am trying to make two programs that are exactly the same but take it in turns to execute something, so the output looks something like the following:
...Code:setup semaphores, etc . . proc 1 doing first thing proc 2 doing next thing proc 1 doing next thing proc 2 doing next thing proc 1 doing
-
message queue and signal notifiers
Hi,
I am trying to implement a blocked or synchronous method of message passing using signal interrupts. So far I have the following:
server.c
{
msgget(queue)
msgrcv (queue mtype)
while(data to send) {
msgsnd(data)
kill(client, SIGUSR1)
}
close queue
}
client.c
{
sigaction(catch SIGUSR1)
msgget(queue)... -
Thanks for your reply. I was going to say that it isn't working still, but it is. I changed the size values in the malloc and strncpy for the return value of the snprintf (accounting for \0) function and changed size for snprintf.
I didn't realise the string libraries were so unsafe, I though the *n* functions rectified that!
David...Leave a comment:
-
sorry, I did allocate for newdir I just forgot to put it in the code snippit:
...Code:/* copy filename to new string to recurs into later */ if((newdir = (char *)malloc(strlen(dir_path)+1)) == NULL) fatal(0, "malloc");Leave a comment:
-
strncpy memory corruption
Hi,
I am writing a small program to basically copy ls. I would like to copy a string so I thought I would use strncpy but I
am getting the following error:
I thought I would be able to debug this but i have been through the man pages and can't figure it out. Doing the same thing with strcpy works fine. The reason I wanted to use strncpy is because it is safe (as far as I am aware) I have seen a few posts to say... -
If you are going to declare a 2D array of strings you need to allocate memory for the string (using malloc) otherwise everytime you read a string with fgets it will be overwritten.
You cannot tell fgets the length of the string that it will get before it gets it. If you allocate a suitable size string then use the same length with fgets it will read no
more than that.
You may want to replace the second last...Leave a comment:
-
Thank you :) Problem solved - it now sorts correctly.
I always try to avoid hardcoding where possible, but I didn't even realise that I was doing it when I was using sizeof!Leave a comment:
-
Thank you, that makes it clearer for me to understand what is going on.
I get a bus error, but if I set return to 0 and print the pointers that get sent to the compare function I get the following:
...Code:int compare_keyword(void const *x, void const *y) { printf(">>>> %s\t%d\t", (*(Record **)x)->keyword, ((Record *)x)->other_data); printf(">>>>Leave a comment:
-
Hi,
I think it is because you don't allocate space for the string. The next time you read a string from stdin you put it in the same location. If you use malloc again to allocate memory for "arr" it should work.
I added the following lines marked by ">" in your main. It worked when I compiled it :)
...Code:int main(int argc, char** argv) { message *node;Leave a comment:
-
qsort and list of structures
Hi,
I am trying to get more to grips with pointers in C so I am trying to make a program that reads a file, places the data in a struct then sorts it using qsort. I have just about got my head around forming the array of pointers to structs but I can't seem to get it to qsort at all. I have looked at some other code that I have found but I can't seem to figure it out.
I need help with the details of the "compare_keywor d"...
No activity results to display
Leave a comment: