search

exercism / python

Exercism exercises in Python.
https://exercism.org/tracks/python
MIT License
1.94k stars 1.29k forks source link

[Single Linked List] Head concept doesn't seem to match descriptions #3009

Closed tamireinhorn closed 2 years ago

tamireinhorn commented 2 years ago

Reading the descriptions for Linked Lists in general, and even in the cited documentation for the exercise give us the idea of a list that would work as [1,2,3] where 1 would be the head node and 3 would be the tail node, hence follow LIFO. However, all the tests seem to expect that the HEAD would be 3, and, for instance, any new node pushed into the list would be the new head. Given that even the exercise itself links to documentation which contradicts the expected results, either the explanation is not clear enough (or I'm not very good at understanding it) or the tests should be somewhat changed. I've confirmed that with a mentor as well.

github-actions[bot] commented 2 years ago

🤖   🤖

Hi! 👋🏽 👋 Welcome to the Exercism Python Repo!

Thank you for opening an issue! 🐍  🌈 ✨


​          ◦ If you'd also like to make a PR to fix the issue, please have a quick look at the Pull Requests doc.
             We  💙  PRs that follow our Exercism & Track contributing guidelines!


💛  💙  While you are here... If you decide to help out with other open issues, you have our gratitude 🙌 🙌🏽.
Anything tagged with [help wanted] and without [Claimed] is up for grabs.
Comment on the issue and we will reserve it for you. 🌈 ✨

BethanyG commented 2 years ago

Hi @tamireinhorn 👋🏽

Thanks for filing this issue. I don't have time at the moment, but will investigate when I do. Meanwhile, could you give me a little more detail? Which tests seem off to you, against which code? What would be your proposed changes?

tamireinhorn commented 2 years ago

For instance, this test: def test_non_empty_list_has_correct_head(self): sut = LinkedList([1, 2]) self.assertEqual(sut.head().value(), 2) clearly expects that THE LAST element of the list is the head. In my mind, the test should read: def test_non_empty_list_has_correct_head(self): sut = LinkedList([1, 2]) self.assertEqual(sut.head().value(), 1) . This test exemplifies this even better: def test_pushing_to_empty_list_changes_head(self): sut = LinkedList() sut.push(5) self.assertEqual(len(sut), 1) self.assertEqual(sut.head().value(), 5) It specifically expects that the head of the LL should change with a push, which doesn't seem to match the concept that I've read about. So I'd say this merely should be talking about the tail of the list, right? However, this would generate an inconsistency here: def test_non_empty_list_traverse(self): sut = LinkedList(range(10)) current = sut.head() for i in range(10): self.assertEqual(current.value(), 9 - i) current = current.next() self.assertIsNone(current) Since it seems to expect that a linked list built of range(10) should in fact be 10-> 9 -> ... -> 1

IsaacG commented 2 years ago

LinkedList.push() pushes elements to the head of the list. Whether intentional or not, LinkedList([a, b, c]) expects elements a, b, c to be pushed to the list ... in that order. Pushing a to a ll results in list(ll) = [a]. Pushing a then b results in list(ll) == [b, a]. And pushing a then b then c results in list(ll) == [c, b, a].

This means list(LinkedList([a, b, c])) = [c, b, a].

I have no idea if this is intentional or not, but this is how the exercise is currently set up.

tamireinhorn commented 2 years ago

Exactly. However, any conceptual aid that a student might seek about linked lists, even the one referenced in the README, will point them towards expecting list(LinkedList([3,4,5])) = [3, 4, 5]. You could argue that this exercise expects a stack implementation, but here's the catch: the exercise expects that the LL is set as: 5 (head) -> 4 -> 3 (tail). Any representation of the LL expected by the exercise winds up being very unintuitive for the reader. In this example, pop() would return the leftmost item, the HEAD of a list, even though we'd expect the tail to be the last item of it given the nomenclature. Furthermore, the student could build something such as: 3 (tail) -> 4 -> 5 (head) in order to better fit the examples given in the reference, but that would fail other tests, where it's expected (as should be) that head.next != None. It might very well be that the subset of people I've discussed this with are an exception, and that the exercise is perfectly clear to anyone else. However, given that any reference to LLs a student would find searching to know more about the concept (which, if they haven't seen before, they likely will) results in examples that would not pass our tests, I tend to think something in our exercise is not clear enough.

BethanyG commented 2 years ago

Hi @tamireinhorn 👋🏽

First - apologies for taking so long to get back to you. Things have been busy, but I also wanted to make absolutely sure that I had resources as well as an implementation consistent with a stack that passes all the tests. I agree that it is easy to get confused, as many resources on singly linked lists cover both stacks AND queues, which have somewhat "opposite" implementations of push and pop.

As the directions point out, we are implementing a LIFO/stack abstract data structure.

As I was coding, it was easiest to visualize a NewNode being added to the "top" or left-hand side of the LinkedList, thereby becoming the head Node. Having the head be at the left-hand side allows additions to be made in constant time. More details in the book excerpt further down.

The former head (OldNode) is "pushed" or moved right-ward or "down":

  1. NewNode becomes head: LinkedList.head is updated to NewNode.
  2. NewNode.next is then set to OldNode (the one that used to be LinkedList.head).
  3. LinkedList.size is updated to reflect a newly added Node.

So under those circumstances, whatever is pushed last is designated LinkedList.head. Because this is LIFO/Stack, LinkedList.pop() removes and returns LinkedList.head, and the steps above are done in reverse:

  1. LinkedList.head.value() gets assigned to a variable.
  2. LinkedList.head gets reassigned the Node returned from LinkedList.head.next()
  3. LinkedList.size is decremented by 1
  4. variable with former LinkedList.head Node.value() is returned.

So the big takeaway for a student (IMHO) is that in an array-like stack head points to the "left-most" position always for both push and pop purposes -- not the "end", or right-hand side as you might expect when working with pop() or append() on a list.

You can see my implementation here it is virtually a one-to-one copy of the stack example in the attached excerpt of Data Structures and Algorithms in Python, published by Wiley.

Stack with Singly Linked List.pdf

Since I'd never done a singly linked list before, I also went googling and found the following:

  1. Real Python: Linked Lists - which has a pretty detailed rundown of single, double, and circular linked lists, as well as the core Python deque.
  2. Towards Data Science: How to Implement a Linked List in Python.
  3. sanfoundry - which is an implementation without a whole lot of explanation.
  4. Koderdojo: Coding a Stack Using a Linked List in Python - which is also an implementation without much explanation.

TL;DR

This may be a confusing/challenging exercise, but the tests are correct, as are the instructions (but they do indeed leave a whole bunch of detail out). The credit link (this exercise was adapted from a Ruby exercise and we linked to it to give credit) is being confused for documentation when it shouldn't be.

  1. I do think we could do a better job with our instruction append, so that students are given links that are Python, and that also explain the difference between a queue and a stack, and direct them toward a non-list based stack. Maybe all or some of those links I found? We can't exactly point students to the Algo book, since it is $$$.

  2. We probably want to have a hints file that perhaps shows some diagrams or other more pointed examples, for students who are really stuck and really confused.

  3. We probably want to make it clearer that the source link is NOT documentation. We'd need to do that by raising and issue in exercism/problem-specifications.

  4. linked lists, stacks and queues aren't really straightforward if you've never seen them before. We may want to consider bumping the difficulty level on this to medium.

Thoughts? I know I took a while to get back to you (apologies!) - but I'd welcome a PR to add instructions_apped.md and/or hints.md for this exercise, should you want to take that on.

BethanyG commented 2 years ago

Hi @tamireinhorn -

I've submitted both an instruction append and a hints file in PR #3026. I'd welcome any thoughts or additions/edits you'd want to make. It also OK if you don't want to comment.

tamireinhorn commented 2 years ago

Perfect! I think it's much better and clearer now. I'll see if I can add a small representation with arrows as to what the LL should look like, what do you think?

Em qui, 28 de abr de 2022 21:18, BethanyG @.***> escreveu:

Hi @tamireinhorn https://github.com/tamireinhorn -

I've submitted both an instruction append and a hints file in PR #3026 https://github.com/exercism/python/pull/3026. I'd welcome any thoughts or additions/edits you'd want to make. It also OK if you don't want to comment.

— Reply to this email directly, view it on GitHub https://github.com/exercism/python/issues/3009#issuecomment-1112769195, or unsubscribe https://github.com/notifications/unsubscribe-auth/AI5HUYZHAJEWSANHMAPLH5DVHMTERANCNFSM5TLOBLQA . You are receiving this because you were mentioned.Message ID: @.***>

jeewonkoo commented 2 years ago

I found this issue on https://ovio.org/projects and would love to contribute! I am new to Github contribution but have coding experience in Python. Please let me know!

BethanyG commented 2 years ago

@tamireinhorn excellent! I think a diagram would be great - both in the append and the hints. I just can't remember the process for how we include them. I think we have a separate repo for images that get embedded into exercise files. I will hunt that process down, and we can get that in its own PR (so you get full credit for it). 😄

tamireinhorn commented 2 years ago

That works! I was thinking of a crude one done in the text itself, like (head) 3-> 2 -> 1 (tail)

Em dom, 1 de mai de 2022 12:42, BethanyG @.***> escreveu:

@tamireinhorn https://github.com/tamireinhorn excellent! I think a diagram would be great - both in the append and the hints. I just can't remember the process for how we include them. I think we have a separate repo for images that get embedded into exercise files. I will hunt that process down, and we can get that in its own PR (so you get full credit for it). 😄

— Reply to this email directly, view it on GitHub https://github.com/exercism/python/issues/3009#issuecomment-1114268286, or unsubscribe https://github.com/notifications/unsubscribe-auth/AI5HUY5QSWGWQZ4CCULJSSLVH2Q4RANCNFSM5TLOBLQA . You are receiving this because you were mentioned.Message ID: @.***>

BethanyG commented 2 years ago

@tamireinhorn - apologies for the delay in reply.

I was thinking of a crude one done in the text itself, like (head) 3-> 2 -> 1 (tail)

I didn't think of that! -- that would be much better on two counts:

  1. No elaborate process for adding an image.
  2. Clearer for those downloading the exercise to work locally.

Would you like to make those changes/add them in the existing PR, or do them as follow-on PR after the current docs are merged? Either works for me. Just let me know.

Thank you again for filing this issue, and for collaborating on the docs It is very much appreciated! 😄

BethanyG commented 2 years ago

Hi @jeewonkoo 👋🏽

Thank you for your interest in this issue and in exercsim.

I found this issue on https://ovio.org/projects and would love to contribute! I am new to Github contribution but have coding experience in Python. Please let me know!

We would love to have you as a contributor! However, places like ovio.org might not be the best place to look for issues, since we organize and use this repo in a very specific way.

Issues that are generally open for contribution are flagged with a [help wanted] tag. You can find our current list here in GitHub via filter or on our website under contributing.

Issues that are flagged with [bug] come from a variety of sources. Many are logged by our students, mentors, or regular contributors while using the Python track on our website. Some are connected to questions or problems encountered while using the site or completing an exercise (these are less "bug" and more "support request). Others are suggestions or recommendations for improving an exercise, tests, and other supporting documents (in which case, they may be discussed or open for a while while we decide what we want to do). Finally, some are technical or factual problems that have been found with documentation or tooling.

If an issue is a suggestion for improvement or technical/factual issue, we will typically discuss it with the poster and decide if they'd like to make the change in a PR themselves, or if the change might involve a maintainer. Many small, obvious, or contained problems can be immediately PR'd (although we prefer a filed issue first for tracking purposes).

If neither the OP or maintainer wants to take the work on (or the work is more detailed or involved), we may write it up as one or more formal issues, and tag them with [help wanted]- or we may tag them for maintainer attention. So an un-assigned issue doesn't mean "up for grabs" unless it is also tagged as [help wanted].

The TL;DR is that if you don't find anything you like on the [help wanted] list, but do find areas in our exercises, support documentation, tests, or other areas that need improvement or correction, you can propose changes in an issue filed here, and we will most likely agree to have you PR the work.

We will be filing additional issues in the next few weeks, but many of them will center around creating content or updating existing content. We may also have issues around updating our CI, cleaning up auto-responder code, or upgrading libraries and tooling. But it may also be a bit before all that gets done.

In the meanwhile, I would suggest getting more familiar with our platform, and with our contributing docs. And I will be happy to answer any questions you have, and help with any [help wanted] issue you'd like to tackle! 😄

tamireinhorn commented 2 years ago

Hi @BethanyG , sorry for the delay. I thought I had answered this one with my question, but it seems I didn't, so here goes: Where do we put it? I'm torn on whether the README would be ideal, given your PR and the fact that this could impart on the student the idea that a LL is always 3-> 2 -> 1 and NEVER 1 -> 2 -> 3. Given that, at least intuitively the second option was the one that came to me, it was very important to read that the implementation required the first, but that didn't mean that the concept didn't allow for it. What do you think?

BethanyG commented 2 years ago

@tamireinhorn

my apologies! I missed your question the first time around. 🤦🏽‍♀️

I think that repetition cannot hurt in these circumstances, so both the instructions and the hints could use the addition of the diagram.

For the instructions_append, maybe in the middle of the first paragraph? (rough example below, with existing PR text quoted):

While stacks and queues can be implemented using lists, collections.deque, queue.LifoQueue, and multiprocessing.Queue, this exercise expects a ["Last in, First Out" (LIFO) stack][Baeldung: The Stack Data Structure] (interactive example [here][LIFO Stack]) using a custom-made [singly linked list][singly linked list].

push and pop happen here

            |

(head) Node_3 -> Node_2 -> Node_1 (tail) -> None

This should not be confused with a [LIFO stack using a dynamic array or list][LIFO Stack Array], which may use a list underneath. Dynamic array based stacks have a different head position and different time complexity (Big-O) and memory footprint.

possible counter example here -- but this might confuse a student, so I am a bit conflicted about it....example below

                                                                push and pop happen here

                                                                  |

(tail) Node_1 -> Node_2 -> Node_3 (head)

For the hints file, maybe the second or third bullet point??

  • This challenge is about creating a [stack][Baeldung: The Stack Data Structure] using a [singly linked list][singly linked list].
  • Unlike stacks underpinned with lists, collections.deque, or queue.LifoQueue, we ask you create custom Node and LinkedList [classes][classes tutorial] to store and link elements.

(head) 3-> 2 -> 1 (tail)

  • [Real Python: Linked Lists][Real Python Linked Lists], [Towards Data Science: Demystifying the Linked List][towards data science demystifying the linked list], and [ADS Stack in Python][Koder Dojo Coding an ADS Stack in Python] can be helpful to review for details on implementation.

OR diagram here

  • Your LinkedList should accept a list argument to its constructor, but should not use a list to store nodes or elements.

What do you think? Do those two insertion points work? And if so, would you like to change the PR to reflect that, or would you like me to? We can also do the change in its own PR after I merge the existing ones.

tamireinhorn commented 2 years ago

I think the insertion points work, and I don't think it hurts to have the counterexample. It is possible that it will be confusing at first, but the explanation and the existence of two possibilities will stop the student from wrongly consolidating that a LL should always be LIFO. You've done it all, so if you could change the PR, I'd be very happy. Thank you so much for listening to my complaints on the issue!

BethanyG commented 2 years ago

Closing now that the PRs merged.

BethanyG commented 2 years ago

D'Oh! PRs not merged Reopening

BethanyG commented 2 years ago

Ok. This is finally merged! Closing this issue as resolved (for now 😄 ).

tamireinhorn commented 2 years ago

I'll add them, I'm currently in the midst of a moving process so later this week! I just don't know where exactly I'd put it, in hints, README, etc

Em seg, 2 de mai de 2022 13:11, BethanyG @.***> escreveu:

@tamireinhorn https://github.com/tamireinhorn - apologies for the delay in reply.

I was thinking of a crude one done in the text itself, like (head) 3-> 2 -> 1 (tail)

I didn't think of that! -- that would be much better on two counts:

  1. No elaborate process for adding an image.
  2. Clearer for those downloading the exercise to work locally.

Would you like to make those changes/add them in the existing PR, or do them as follow-on PR after the current docs are merged? Either works for me. Just let me know.

Thank you again for filing this issue, and for collaborating on the docs It is very much appreciated! 😄

— Reply to this email directly, view it on GitHub https://github.com/exercism/python/issues/3009#issuecomment-1114776164, or unsubscribe https://github.com/notifications/unsubscribe-auth/AI5HUY4I2RRUUIPSZOBL7QTVH7A67ANCNFSM5TLOBLQA . You are receiving this because you were mentioned.Message ID: @.***>