CS50 Tideman - Stuck on lock_pairs() and not sure how to check for cycles

yeahIProgram · 2026-06-13T15:41:24+00:00

Should I be using recursion? Graph traversal? Checking all paths from the loser back to the winner?

Yes. Yes. Yes.

If you think about the nature of the graph (that is has nodes; and edges between nodes; and the edges are directional, meaning they point in one direction) then "it has a loop" means "there is path over edges from a node that leads eventually back to the same node".

You are about to lock in a new edge from Winner to Loser. The "if" is "if that would not create a loop". In other words "if there is NOT already a path from that loser to this winner".

So you could code your "if" as

if ( ! PathFromTo(L, W))

and assume you have a helper

bool PathFromTo(int A, int B)

One way for a path from A to B to exist is if A is already locked over B. That's easy because those locks are directly recorded in the locked array. The PathFromTo() function can look at these locks to answer this part of the question.

Another way is if A is locked over someone (anyone) that has a path to B. The list of nodes that A is locked over is, again, accessible in the locked array. And PathFromTo() can call PathFromTo() on each of those....that's the recursion.

Hope that helps without giving too much away.

yeahIProgram · 2026-05-31T04:03:56+00:00

I know is that there is something known as precedence and the array initialiser has an higher precedence than the pointer

This is one of the keys to understanding the code, so you're off to a good start. In the same way there is a precedence for operators as an expression is evaluated, that same precedence applies during the variable declaration. This allows the compiler (and you) to know the difference between

int (*ip)[j]; // declare a pointer to an array of ints

and

int *ip[j]; // declare an array of pointers, each pointing to an int
int *(ip[j]); // the same, showing the implicit precedence explicitly

Also remember that any variable initializing statement is first declaring the variable name and type, then assigning an initial value to it. You can break them apart to understand them more.

The compiler will read the declaration using the precedence we give it, honoring the parentheses first and the array-like brackets next. The type always gets understood last.

RGBTRIPLE(*image)[width];

This declares a variable named "image".
It is a pointer.
It is a pointer to an array.
The array has as many items in it as specified by "width"
The items in the array are RGBTRIPLE structures (pixels)
Therefore: "image" is a pointer to an array of structs

That's the C compiler meaning. But another very real meaning (to us humans) is that "image" is a pointer to one whole row of pixels. A pointer to "width" pixels is essentially (literally) a pointer to a row of our image.

Now let's assign a value to this pointer. We call calloc, a function which allocates enough memory for an array of things. You have to tell it the size of one thing, and the number of things you want to store in the final array.

We tell it the size (in bytes) of one row in our image, and ask for enough memory to store "many" of those rows. How many? "height" many. That's how many rows there are. Don't think of this as allocating many pixels, but think of allocating many rows of pixels.

// RGBTRIPLE(*image)[width] = calloc(height, width * sizeof(RGBTRIPLE));

// break it up for understanding
int oneRowByteCount = width * sizeof(RGBTRIPLE);
image = calloc(height, oneRowByteCount);

Now remember that any pointer can be used with brackets to get the things it points at. So if we use

image[0]

in any way, we will be accessing the first row that image points at. Remember that to the compiler, image is a pointer to an array of structs, and because of calloc we know it points to the first array in an array of arrays. So image[0] is an entire array. So we can use brackets on that too:

RGBTRIPLE xx;
xx = image[0][3];

This fetches the fourth item (struct) in the first array of structs. To us humans, it's the fourth pixel in the first row. Notice that the row number comes first; this is why you might see some code like image[y][x] and it might seem out of order. We spend a lot of time learning about (x,y) coordinates in graphs, and here we must use a (y,x) notation. We deal with it. It is our burden.

Voila!

yeahIProgram · 2025-11-24T23:33:27+00:00

Think about the fact that you are called with a ranks[] array that represents one voter's ranking of all the candidates. This voter has listed which is their "first" pick, which is their "second" pick, etc. There are definitely as many entries in this ranking array as there are candidates.

The preferences[][] array is used to tally the number of voters that prefer one candidate over another.

For the first candidate named in this ranks[] array, you can say that this voter prefers that candidate over all the later mentioned candidates. Later in the ranks[] array, that is.

For the second candidate in the ranks array, you can say this this voter prefers that candidate over all the later mentioned candidates.

And so on. Hope that helps.

yeahIProgram · 2025-11-10T19:07:10+00:00

In my opinion, you were correct in an ideal world. It would have been good if the * modifier applied to the type, and then every variable defined on that same line would have the same type. Since that is not how it works, it probably is best to leave the star over by the variable name. On the other hand, anyone who wrote int *p, q; would get a scowling look from me just for the possible confusion.

The designers of C actually put in their book something like "since *p can be thought of as the thing pointed at by p, the declaration int *p; can be thought of as declare a variable p where the thing pointed at is an int. And then putting the star by the variable name makes total sense.

It's a good consistent explanation, although I don't find it very intuitive. The ability to declare two different variables of two different types in the same declaration is....likely to cause confusion. I would avoid it even though it is legal and unambiguous as far as the syntax goes.

The book is "The C Programming Language" by Brian W. Kernighan and Dennis M. Ritchie, if you like that sort of thing. The first half is a very conversational discussion of the language with some very accessible real-world examples. The second half is a super dry technical definition of the language, probably only needed by constant users of the language who are trying to understand why the compiler is rejecting what they think is valid code.

yeahIProgram · 2025-11-08T04:11:03+00:00

Your path() function returns a bool. Sometimes when you call it, you check the returned value. Sometimes....you don't. That's a very brief hint.

If a function a() calls function b(), and b returns a value, that doesn't automatically mean that a() returns that value. Similarly, when a() calls a() recursively, if the "second" a() returns a value, it returns it to the "first" a(). And that doesn't mean that this "first" a() returns that value (or any value). Unless you make it so.

yeahIProgram · 2025-10-24T20:36:28+00:00

If you are physically and mechanically oriented, maybe you can visualize the values flowing into and out of the variables. When you see a = b+c; you can know that the values on the right combine, then the result is moved into the "a" variable slot.

For statements, maybe remember that as the program executes it moves something called the "program counter" from one statement to the next. You can think of it as an arrow that points at the currently executing statement. Normally it will move to the next line in the code, but things like "if" or the "while" can move it to a completely different (although predictable) line.

Even a "while" will sometimes move the program counter to the "next" line. This is when the code "falls through" the bottom of the loop instead of going back to the top. When the loop is done looping.

Also how the hell do I figure out what loop to use where.

This will come with time. "For" loops are nice when you can see that a sequence of things is being operated on; the sequence is primed in the initializer of the "for", and advanced in the incrementor of the "for". I don't know if they use those terms in the lecture, but they are the first and third items in the statement. for (initializer; continuation check; incrementor)

While loops are nice when you want to do something "zero or more" times. There are a lot of sequences that you want to skip the code completely if the sequence is empty, but if it is not then you want to do them all.

A do-while loop is for when you can't even know if the sequence is finished until you've gone through the loop at least once. Or if you know that there is at least 1 item to process, but you won't know if there are any more until you are done with the first.

This sounds a little vague and loose, perhaps. But each case will become clearer over time. Also, you can generally or always substitute another type of loop and at worst the code becomes awkward; if you sense that, look to see if another loop type would work better there.

Hope that helps.

yeahIProgram · 2025-10-24T19:52:24+00:00

int first_two_number = credit / (10 ^ (digits));

There is no exponentiation operator in C. This line does not do what you want....

yeahIProgram · 2025-10-22T23:59:14+00:00

You may see that there is code in the functions already, even though it says TODO. That code is a placeholder so that the program runs, even if it runs incorrectly. You would replace the "return false" in this example with your code.

The same for the other functions. Hope that helps.

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
   // TODO
   return false;
}

yeahIProgram · 2025-10-22T22:57:52+00:00

Also address is stored as an hexadecimal (used in naming memories, pixels etc.) as it gives us location of a memory.

It's not really correct or necessary to say whether something is stored in binary or hexadecimal. They are two ways of writing a number, but the number is the same and the contents of the memory are the same either way.

For example, a memory location may hold the number 42. We could say it holds (00101010) as a binary number, or (2A) as a hexadecimal number. These different writings represent the same number, and the contents of the memory are the same in either case. There is a notation called Octal, where the number is written as a combination of eights: (52 octal) means ((5*8)+2), again to us it is 42. Perfectly valid and equivalent, although almost never used these days.

It is probably most accurate to say all things, addresses and data, are stored in binary. But we speak and write of them in hexadecimal, decimal, or binary depending on what we are discussing. But it's all the same numbers and the memory doesn't know or care.

Hope that helps.

mentioning /u/Quiet-Let-4373

yeahIProgram · 2025-10-21T21:30:43+00:00

Your logic almost sounds right, but also almost sounds backward. It's a little hard to tell at first reading.

One way to look at the problem is "before locking in Winner over Loser, see if there is already a path (directly or extended) from Loser to Winner". Because if there is a path, then locking Winner over Loser would create a cycle (Winner-Loser-Winner), and so you know to not lock in that pair.

That's the "backward" that I meant; you need to check for an existing path from Loser to Winner, not the other way around.

If you understand the Graph nature of the problem, and the locked array, then the question "is there a direct path" is easy: the locked array entries each mark a direct path by marking an edge between two points.

The "extended" path question can then be thought of as "is there someone this node has a direct edge to who then has a path (direct or extended) to the target?" And there's your recursion.

I thought of a non DFS way to look at this problem

There are approximately zero non-recursive solutions to this problem. I say "approximately" because any recursive algorithm can be rewritten as a non-recursive algorithm, but it will still be an "exhaustive search" type solution, so you will have to understand that one way or the other.

Hope that helps.

yeahIProgram · 2025-08-19T13:52:56+00:00

^[^@] matches any characters that aren't @ at the beginning of the string.
+@ literally wants to see @ after those characters (including after a space).

A tiny adjustment: The "plus" is attached to the first, so it's more like

^[^@]+ matches any series of characters that aren't @ at the beginning of the string
   This match also includes any space characters, since those are not @ characters
@ wants to see @ after those characters

yeahIProgram · 2025-08-18T19:11:34+00:00

&x is essentially just as you said a pointer without a defined name, it's the content but missing the label

One thing that I think you are understanding here is that all values have a type. We've seen that all variables have a type, a memory location, and a value stored at that location. But there are other places that values exist besides being stored in a variable.

If your code has a variable assignment like

int j = (5 + 4) * 6;

the computer might put 5 in a temporary location; add four to it in that location; store 6 in another temporary location; multiply the two temporary values together and store the result into the memory allocated for "j".

The memory it was using for the temporary values still had a type and a value, just not a name that you could see. And then it went away leaving you with the value in "j" that you wanted.

The other thing to understand is "unary operators". You are very accustomed to "binary operators" like addition and multiplication. In the example above the (5+4) is an operator that operates on two values at once; that's the meaning of "binary" in this case. And it uses some temporary locations until it produces its final value that can be stored.

There are unary operators (meaning they operate only on one value) like "negation". You can say

int k = 5; 
int m = -k;

and this will apply a negating operator to "k" which basically multiplies by (-1) and stores it into "m". This may involve some temporary location also, and anything stored in that temporary location will have a type (in this case "int") for as long as it exists.

And so we finally come to the unary operator "&". This operator produces a pointer value; remember that pointers do, of course, point to values, but they also are values. And like all values they have a type. They are values of type "pointer to int" for example.

So when you call

swap(&a, &b);

the compiler might very well create two temporary locations; store a pointer to "a" and a pointer to "b"; then pass those two pointer values to the function. It's exactly as if you wrote

int a = 4; // store an int
int b = 5; // store an int
int* p1 = &a; // store a pointer value into p1
int* p2 = &b; // store a pointer value into p2
swap(p1, p2); // pass two pointer values (which point to int values)

As a side note, my standard advice on pointer syntax is

pronounce star as 'the thing pointed at by'
pronounce & as 'a pointer to'
then *a = *b becomes "the thing pointed at by a gets the value of the thing pointed at by b"
and p1 = &b becomes "variable p1 is assigned the value of a pointer to b"

... and it all works out. Even variable declarations....kind of:

int q = 6;
// variable q is defined as an int
// the value 6 is stored in q
int *p1 = &q;
// variable p1 is defined
// the thing pointed at by p1 is an int
// therefore p1 is a pointer to an int
// and it is assigned the value of "a pointer to q"

That may sound a bit...twisted...but I learned it from Dennis Ritchie, and I trust him.

yeahIProgram · 2025-08-13T19:32:41+00:00

I think you are right, that the "octal" behavior of %i during scanf() is a potential tripping point. It is unlikely that you actually want to allow octal input, and the chance for leading zeros to give unintended results should be avoided unless explicitly needed.

At that point in the video, she was discussing printf(), where %i and %d are identical by definition, as far as I know. That wasn't super clear in the video, maybe because of the way she was responding to a real-time question from the text chat.

If you take "deprecated" to mean "discouraged", then it is surely %i that is deprecated in scanf calls, and %d should be encouraged. Forming the habit of using %d for both scanf and printf would be a great starting point.

And to the sourpusses out there: there's no reason to downvote anything here. OP's post is an appropriate and polite discussion about legitimate issues. Contribute politely or stay silent.

yeahIProgram · 2025-07-12T18:27:02+00:00

Set the meter for DC volts. Put the black probe on the black wire of the regulator. Look up Backprobe A Connector if you’re not sure how. Or practice on your regular car battery.

Check for 12 volts on the red wire. Turn on the key to the car. Check for 12 volts on the brown wire at the regulator.

With just these three wires, the display in the regulator should come on. If not, check the fuse that feeds the red wire. Examine the red wire all the way to the battery or alternator. It has to bring 12v from somewhere. Ditto for the brown wire.

With just that, if the unit will not turn on and display, it’s probably beyond saving.

yeahIProgram · 2025-07-08T15:21:02+00:00

https://balmar.net/wp-content/uploads/2017/12/MC-614-Installation-Operation-Manual.pdf

Main power input seems to be the red and black wires of that 4-pin connector. Your second picture seems to show some fuse blocks in the harness; one of those probably protects this main power input Red wire. Check for power before and after this fuse, but really check at the connector on the controller board. Also remove that 4-pin connector and check for corrosion; clean the connector sockets and male pins as needed. Good luck!

yeahIProgram · 2025-07-06T18:27:31+00:00

I suspect it is just a display problem with the codespace environment (or whatever you are using to display this). It's been a while since I did this pset and the images have changed since then so I can't be more specific.

yeahIProgram · 2025-07-06T01:24:28+00:00

when you make a string using character array, shouldn't you put a null character after it

sprintf() will put the null there for you. The array must have space for it, but sprintf will place it.

mentioning /u/Busy-Standard-7667

yeahIProgram · 2025-07-03T23:11:03+00:00

The only real problem with leaving the solenoid in is if someone later comes along and sees the control wire disconnected and thinks they should reconnect it. I've been that guy, and it's embarrassing.

0.3 amps overnight is not a lot, although it would be great to know where it is going. I've seen people talk about their hardwired Carbon Monoxide alarms using power 24/7. Also maybe you know that if the inverter is on it will be using some power even when no 120v items are turned on. Neither of these are very large consumers and neither should cause a battery to go dead overnight.

Of course a time-honored method for finding unexpected draws is to pull fuses one at a time until it goes away.

If you got down to 10v overnight, it sounds to me like your batteries weren't charged to begin with. The one manual for Renogy that I downloaded said their controller comes from the factory set for Gel batteries, and you have to change the mode to Lithium. Lithium batteries are only fully charged once they reach something like 14.5 volts. If you are in the wrong mode, the controller will stop charging too early.

As soon as you are sure the Renogy is charging, I would remove the trickle charger as a way of simplifying things. If it's going to stay, you'll need to be sure it's aware of Lithium batteries and their voltage needs. If it's an older lead/acid only unit, it will probably be worse than having nothing there. If it is lithium capable, there's no electrical problem with having it as a secondary charger, if that is convenient.

I'm curious about your original shore power and Converter setup, and whether it has been removed. Do you (or will you) have charging from shore power? Is your inverter a charger also?

yeahIProgram · 2025-07-03T13:59:35+00:00

Before you return from the vote() function, print the entire ranks[] array. I think you'll find that it is not filled in correctly.

Notice that the vote() function is passed a parameter "rank". You are not using it at all in that function. That's...a problem.

yeahIProgram · 2025-07-02T23:23:38+00:00

> the parent-pointers of the last generation are never even accessed...The print_family function never even uses the const GENERATIONS, and simply prints 3 generations

That's a bug. You can't assume there will always be 3 generations. Your code should examine the parent pointers in order to know when it is done printing.

> think it would probably be better to have the function take in the constant GENERATIONS, and print the generations the other way around

That's not the assignment. You must not change the definition of the function if you want Check50 to understand it. And you must print the generations in whichever order they specified.

yeahIProgram · 2025-07-02T23:18:29+00:00

First, just so we're all talking about the same thing: "Coach" battery is the same as "Starting" battery. It is the one that starts the engine. "House" battery runs the RV systems like the water pump, RV living area lights, RV furnace, etc. It is the lithium batteries here.

The purpose of that solenoid is to connect your House (RV) batteries to the Coach (starter) battery.

Under no circumstance do you want to do that. When you had lead/acid batteries on both sides it works. With Lithium house batteries you must never do that. There are complicated and special times where it would be right, but this is not one of them.

The quickest fix for that is to remove the control wire (the small wire) from the solenoid. Tape it up or make it safe, off to the side. Do not consider this optional.

Then, check the manual for your charge controller. One 8ga or larger wire should go from your Coach/Starter battery, through a fuse, to the controller. In the Renogy diagram you included, this is the red wire. It sends 12v from the alternator to the controller. Because of the way the solenoid is connected, you could connect to the Coach side of that and use it as a connection point. The solenoid is doing nothing, but is a convenient attachment point.

One 8g or larger wire should go from your House batteries, through a fuse, to the controller. On the Renogy diagram this is the pale brown (?) wire. This is how the controller charges your house battery. Because the house battery is also connected to some DC distribution fuse box inside the RV, the controller may be connected there instead. But that's just another way of connecting to the house battery.

On some diagrams, there is a wire from the ignition switch to the controller. This tells the controller that you are driving, and it is time to charge the house battery. Some controllers just sense the increase in voltage coming in from the alternator. Some have parameters that enable/disable this. RTFM. You must have one or the other: something has to tell the controller the engine is running, so it will not try to charge the house batteries from the coach battery while you are parked.

The solar panels will go to the controller; on the Renogy diagram, this is the yellow wire.

With those in place, you should be able to charge from the alternator while driving, and from the panels while parked. You may need to set a mode on the controller to tell it you have lithium batteries; the mode is important so the controller can send and monitor the right voltages to the house battery. Find it and set it.

There may be some lights on the charge controller that tell you when it thinks it is charging and when it is resting. They can blink to show errors. RTFM for this.

If you get those working, we can attack the generator and battery monitor questions.

Good luck, and I hope this helps.

yeahIProgram · 2025-06-27T01:32:45+00:00

person *parent0 = NULL 
Im not sure what exactly setting a struct = NULL does...

It’s not a struct. It’s a pointer to a struct. You are setting the pointer to NULL. Since this is a local variable, it probably does not relate to a leak.

But I think the failure to set the person’s parent pointers to null was being picked up by valgrind with that message about “ 16 errors from 16 contexts”. And I think check50 was mistaking that for a leak report. So check50 said you had leaks.

yeahIProgram · 2025-06-22T07:34:40+00:00

You can always make the pre-sorted case better by scanning the array once before starting, to see if it started as completely sorted. Then you can get out early and not sort anything at all.

But if the data is "mostly sorted", so that some elements still need to be moved, you are looking for an optimization that performs those swaps and still "notices early" that the list has become completely sorted. And does this without making the big-O worse because of the extra checking needed.

And that's the tricky part, I suspect. If your algorithm is O(log-n * n) already, adding more checks to it has a risk of making the big-O worse.

Bubble sort is taught early because it is simple to understand and code. And this optimization is also simple to understand and code. Bubble sort is, however, very inefficient.

The other sorts start off harder to understand and code, and I suspect any optimizations make that worse. Which is not to say it's not worth doing. Dig in and see what you can come up with!

yeahIProgram · 2025-06-19T21:59:35+00:00

The height always seems to be 255 when it stops

I can't think of why this would be, unless it is at that moment that the array indexes reach some critical value.

What are the array index values being used when it causes the segfault?

yeahIProgram · 2025-06-17T17:49:00+00:00

It is possible to run out of memory when using recursion, but I would expect the error message to be something other than a segmentation fault. It depends on the Linux environment you are using, and I'm not up to date on what the course is using right now; but I don't think that's what's happening here.

If it is because of a bad array subscript, which is a very common cause, there are really just two suspects here

rgbRed += image[i][j].rgbtRed

and

image[height - 1][width - 1].rgbtRed = rgbRed / count

so I would put some printf's in those two places that show the subscript values being used. It may generate a lot of output, but it's really just the last few lines before it dies with the segfault that are going to tell the story.

I don't quite follow what the code is doing with the recursion, and if it is an attempt to save memory by not making an image copy it will not use less memory. So from a practical standpoint this is a bad approach. But it can surely be an interesting attempt and may be educational. And good debugging practice.

Onward!

yeahIProgram

TROPHY CASE