A test to use for cs50 Tideman problem. Run as "./tideman a b c d e f g h i < Tideman_test.txt"

lock_results.txt

Here are the pairs, in my codes sorted order, that should be locked or not locked. The end is the winner.
This is considering the order of my pairs specifically. If your tied pairs are ordered different, the winner my be different.
(winner -> loser)
Locked g -> h
Locked e -> h
Locked e -> f
Locked i -> c
Locked b -> g
Locked b -> h
Locked d -> g
Locked d -> h
Locked f -> h
Locked g -> i
Did not lock c -> d
Locked c -> e
Locked c -> f
Did not lock c -> g
Locked c -> h
Locked d -> e
Locked d -> f
Locked b -> f
Locked a -> h
Locked e -> a
Did not lock e -> b
Did not lock a -> d
Did not lock e -> g
Did not lock a -> c
Did not lock e -> i
Locked f -> a
Did not lock f -> g
Locked b -> d
Did not lock a -> b
Did not lock c -> b
Locked i -> a
Did not lock i -> b
Did not lock a -> g
Did not lock i -> d
Locked i -> f
Locked i -> h

Winner = b

Tideman_test.txt

9
i
b
c
d
e
f
g
h
a
e
f
g
h
i
a
c
b
d
g
h
i
c
a
d
e
b
f
f
e
d
a
b
g
i
h
c
a
d
b
i
c
g
e
f
h
e
f
g
h
i
d
a
c
b
e
c
b
a
d
g
i
h
f
i
f
b
d
a
c
g
e
h
c
b
a
d
g
e
h
f
i

If I have all pairs sorted from highest to lowest but the order is slightly different from yours
does this mean I have a logical mistake in the add_pairs function or in the sort function?

Hi. Just run "check50 cs50/problems/2021/x/tideman" - green line it's ok пт, 19 февр. 2021 г. в 12:37, Laziv <notifications@github.com>:

…

***@***.**** commented on this gist. ------------------------------ If I have all pairs sorted from highest to lowest but the order is slightly different from yours does this mean I have a logical mistake in the add_pairs function or in the sort function? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <https://gist.github.com/2379634e87f24399ed1ed12c4c2e8c9a#gistcomment-3637193>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AFTLOBYBLRTNBOTA43HJA4DS7Y5O5ANCNFSM4OZVAAXA> .

thank you for the test, i don't seem to get what's wrong with my code:

bool iscycle(int W, int L, int pair_rank)
{
if (pair_rank < 0)
{
return false;
}
else if ((L == pairs[pair_rank - 1].winner || locked[L][pairs[pair_rank - 1].winner]) && locked[pairs[pair_rank - 1].winner][pairs[pair_rank - 1].loser] )
{
if (((pairs[pair_rank - 1].loser == W) || locked[pairs[pair_rank - 1].loser][W]))
{
return true;
}
else
{
return iscycle(W, pairs[pair_rank - 1].loser, pair_rank - 1);
}
}
return iscycle(W, L, pair_rank - 1);

Hi Nick, first of all thank you so much for not only your gist about clarifying lock_pairs but also for many questions you've taken the time to answer in Facebook and Discord. I finished and submitted successfully Tideman, everything working ok for check50. I then had the idea of re-running this test and was baffled to see no winner and lots of pairs locked when they shouldn't have been. I know that this test is to TEST the program at its max but... I wonder what's wrong and why is it right in some way if it passed the check50 test. Any ideas? I could share privately the code if you would like to take a look at it and share your thought. Thanks!!

How come a -> b pair goes almost to the end? It's in the beginning of the preferences array. Isn't it the first pair with strength 5?

Thank you so much. Your test case saved me from going insane trying to figure out why my recursive function was wrong.

I found the winner to be "a". same data but sort slightly different:
Locked g h - winning margin 9
Locked e h - winning margin 7
Locked i c - winning margin 5
Locked e f - winning margin 5
Locked d h - winning margin 3
Locked b h - winning margin 3
Locked b g - winning margin 3
Locked f h - winning margin 3
Locked d g - winning margin 3
Locked g i - winning margin 3
Locked e b - winning margin 1
Locked b f - winning margin 1
Locked a b - winning margin 1
Locked a c - winning margin 1
NOT Locked i b - winning margin 1
NOT Locked c d - winning margin 1
NOT Locked c e - winning margin 1
Locked c f - winning margin 1
NOT Locked c g - winning margin 1
Locked c h - winning margin 1
Locked a d - winning margin 1
Locked d e - winning margin 1
Locked d f - winning margin 1
NOT Locked e a - winning margin 1
NOT Locked f a - winning margin 1
NOT Locked i d - winning margin 1
Locked a g - winning margin 1
Locked e g - winning margin 1
Locked a h - winning margin 1
Locked e i - winning margin 1
NOT Locked f g - winning margin 1
NOT Locked i a - winning margin 1
Locked i f - winning margin 1
NOT Locked c b - winning margin 1
NOT Locked b d - winning margin 1
Locked i h - winning margin 1

so the result is different based on different sorting

@timurleblebici I got "a"as the winner as well. Am I doing something wrong ?

no, nothing is wrong, a is also a winner

....and to pass check50 you have to find the winner only by looking at locked[] and candidates array otherwise last 2 tests will fail. check50 only provides locked array and candidates array to the tested program so if you are using any other data the test fails.

Thank you, this test helped me too to finish tideman!

why wont the test work on mine

Thanks! Your test is very useful, it gave me a deep thought about what's a cycle. I used this test to adjust my function and it worked, though my pairs and which pairs are locked, which are not is a bit different from yours.

Thanks for the test file man, problem is that using your test data my cycle check results to segmentation fault and I dont know where is the problem.

bool notcyclical(int winner, int loser, int locked_pairs)
{
    if (locked_pairs < 2)
    {
        return true;
    }

    for (int i = 0; i < locked_pairs; i++)
    {
        //check if the winner of current pair is a loser of locked pairs
        if (winner == pairs[i].loser)
        {
            return notcyclical(pairs[i].winner, loser, locked_pairs);
        }
    }

    //this if statement is only satisfied when cycle is detected
    if (winner == loser)
    {
        return false;
    }

    return true;
}

Thanks,

Nicknapoli82! After reading your pin gist about lock_pair function and using this test I have solved this tideman.

My problem is:
I use recursion in my code, and I checked by using debug 50 that my code correctly discovers that a cycle is being closed, which does not happen until the recursive function has called itself at least one time. I would like this recursive function to then return "true" (= cycle has been found), and immediately go back to the caller function (lock_pairs), i.e. without that its "earlier branches" complete the loop though all the candidates.

The problem is: It will actually go back to the "earlier branches" of itself (because this is how recursion is meant to work!), and will overwrite "true" by "false" in the process. So the caller function (lock_pairs) will never know that a cycle actually has been found.

• for the time being, my program delivers the usual faults, i.e. everything works correctly except that cycles are not detected;
• I found something like to "throw an exception" or "try and catch function" to make all branches of the recursion quit immediately. But I wasn't able to implement it;
• maybe it is possible without this "immediate quit" - I just don't see how

Any help is highly appreciated!

Your function I presume, will only call itself when it did not find a loop yet and if it stil has nodes to check. It will get a return value false only if it is returned from a depth where no nodes where leftto check. And it gets a return value true if there is a loop found. When it gets a return value true it should return THAT value to and not check further. So the return value true “bubbles” up to the first call. Succes. Ed

…

Op 12 sep. 2021 om 03:45 heeft steffan77 ***@***.***> het volgende geschreven: ***@***.*** commented on this gist. My problem is: I use recursion in my code, and I checked by using debug 50 that my code correctly discovers that a cycle is being closed, which does not happen until the recursive function has called itself at least one time. I would like this recursive function to then return "true" (= cycle has been found), and immediately go back to the caller function (lock_pairs), i.e. without that its "earlier branches" complete the loop though all the candidates. The problem is: It will actually go back to the "earlier branches" of itself (because this is how recursion is meant to work!), and will overwrite "true" by "false" in the process. So the caller function (lock_pairs) will never know that a cycle actually has been found. for the time being, my program delivers the usual faults, i.e. everything works correctly except that cycles are not detected; I found something like to "throw an exception" or "try and catch function" to make all branches of the recursion quit immediately. But I wasn't able to implement it; maybe it is possible without this "immediate quit" - I just don't see how Any help is highly appreciated! — You are receiving this because you commented. Reply to this email directly, view it on GitHub, or unsubscribe.

Thanks for the hint EdPrins, really helped me. I was able to figure out this "recursion" finally.

But it still was quite a headache because what happened next was that my program stopped checking whenever a return value "false" was coming back from further down in the regression (instead of going through the rest of the for-loop).

Everybody who is struggling with how "recursion" works should absolutely watch these:
Overview of recursion:
https://video.cs50.io/mz6tAJMVmfM
Overview of call stacks:
https://www.youtube.com/watch?v=aCPkszeKRa4

And thanks also the initial poster Nicknapoli!

Thanks for the hint EdPrins, really helped me. I was able to figure out this "recursion" finally.

But it still was quite a headache because what happened next was that my program stopped checking whenever a return value "false" was coming back from further down in the regression (instead of going through the rest of the for-loop).

Everybody who is struggling with how "recursion" works should absolutely watch these: Overview of recursion: https://video.cs50.io/mz6tAJMVmfM Overview of call stacks: https://www.youtube.com/watch?v=aCPkszeKRa4

And thanks also the initial poster Nicknapoli!

Can u pls tell me where can i find the hint given by OP. I can only find link for this test

Can u pls tell me where can i find the hint given by OP. I can only find link for this test

Yes, actually you find this post "A Way to Look at Tideman Lock Pairs" by nicknapoli here
https://gist.github.com/nicknapoli82/6c5a1706489e70342e9a0a635ae738c9

Thanks man!

If using the test mentioned by OP , I am getting different lock pairs array then does that mean that my lock pairs algorithm is wrong? I am not saying about the winner but just the lock pairs array

I also had differing lock pairs in this test at first. I then changed my sorting algorithm from "selection sort" to "bubble sort", which gave me the same results as the OP has posted here. So the answer to your question above is "may be, but not neccessarily".

You can also use check50 to check your results.

Actually, the influence of the order of the tied pairs, even on who the winner is, is discussed here above
Mahantesh1729 commented on 12 Sep 2020

is this the flaw in tideman? Since we get different winner if the tied pairs are ordered different

and OP replying

Yea. I would say this is the flaw in the tideman algorithm. Though in an actual election there would certainly be few candidates with many votes. The probability of ties in that case would be extremely small.

The reason is that there are many tied pairs that have the same winning margin in this test case here by OP. And depending on which sorting algorithm you use you may get a different order for these pairs.

But as I said, check50 may be helpful.

This may be a silly question but how do I use the test case provided? I've created the text file Tideman_test.txt and ran using "./tideman a b c d e f g h i < Tideman_test.txt"

but i just get the following output:

tideman/ $ ./tideman a b c d e f g h i < Tideman_test.txt
Number of voters: Rank 1: Rank 2: Rank 3: Rank 4: Rank 5: Rank 6: Rank 7: Rank 8: Rank 9:
Rank 1: Rank 2: Rank 3: Rank 4: Rank 5: Rank 6: Rank 7: Rank 8: Rank 9:
Rank 1: Rank 2: Rank 3: Rank 4: Rank 5: Rank 6: Rank 7: Rank 8: Rank 9:
Rank 1: Rank 2: Rank 3: Rank 4: Rank 5: Rank 6: Rank 7: Rank 8: Rank 9:
Rank 1: Rank 2: Rank 3: Rank 4: Rank 5: Rank 6: Rank 7: Rank 8: Rank 9:
Rank 1: Rank 2: Rank 3: Rank 4: Rank 5: Rank 6: Rank 7: Rank 8: Rank 9:
Rank 1: Rank 2: Rank 3: Rank 4: Rank 5: Rank 6: Rank 7: Rank 8: Rank 9:
Rank 1: Rank 2: Rank 3: Rank 4: Rank 5: Rank 6: Rank 7: Rank 8: Rank 9:
Rank 1: Rank 2: Rank 3: Rank 4: Rank 5: Rank 6: Rank 7: Rank 8: Rank 9:

@Shanahando I am in the same boat as you. I cannot get this test to work and I think it may have to do with CS50 switching from using their IDE to the cloud codespace... I really hope someone knows a workaround because I have been stuck on locked pairs for far too long.

Can anyone explain what this error means? I assumed that as there is only one root of the locked pairs graph, there is only one winner.

Thanks for providing this data set and your locked_pairs explanation! It was super helpful and I got the 100 for this seemingly endless problem.
For what it's worth, my algorithm found "e" as the victor.

Does anyone know how to use a txt file like this with debug50, so that we can see each step of the functions as they execute?
I tried running debug50 tideman a b c d e f g h i < Tideman_test.txt , but that did not work

THANKS I WAS ALMOST TO GIVE UP BUT YOUR TEST CODE HELPED ME NOTICE SOMETHING IN MY CODE THAT WAS NOT WORKING IN A SPECIFIC CASE