High level organization: why aren't we targeting a contest environment?

[ProtractorNinja]

Splitting off from #60:

@ProtractorNinja said:
Why are we forcing sample code to live in an example contest problem? This structure fits as a learning resource, but honestly, our goal right now should be to optimize for a contest environment. Wouldn't it be more useful to have a bare-bones DS/algorithm implementation for quick reference?

All the sample problem IO/format/etc. junk takes up a lot of space, complicates things when you're trying to find an algorithm during a contest -- it's tough enough thinking about the problem you're currently trying to solve -- and, generally speaking, requiring a sample problem makes contribution more challenging. They just aren't very useful for a contest environment.

Hence, I think that Algorithm and Data Structure sections should only require Description and Reference sections ("Applications", if actually relevant, should be a sub-section under Description), with Sample Problems as an optional extra for the HackPack++ except in cases of extreme relevance.

Here's a relevant problem: I poked around to test the claim that the Hack Pack didn't have any code for Dijkstra's Algorithm in it. The only sample code for Dijkstra's Algorithm is currently hiding in the graph section, on line 84 of a sample contest problem solution, denoted only by //dijkstra woohoo. That's not in the index (surprise!) and the Dijkstra chapter -- which is cluttered up with three example contest problems that add literally nothing in a contest environment except for confusion and cows -- doesn't contain any code or reference any code. It doesn't even explain how the algorithm works.

That's terrible.

[robertu94]

Just for sake of completeness lets remind ourselves of the reasons for two versions of the Hack Pack:

1. The Hack Pack++ version exists as a learning resource that one could use to learn the algorithms and problem types if they had not seen or heard about them before for use in a class like CPSC 481.
2. The Hack Pack version exists to be a quick programming reference with all extraneous details removed for use in a contest environment.

I believe that the bulk of these problems are symptoms of improper implementation instead of bad design. For example:

1. All submissions are required to have sample code that solves at least one of the problems. The Dijkstra section does not.
2. All sections are required to have index entries for key terms. The Dijkstra section only has one term.
3. All sections are required to have IO code removed in the minified version. The Dijkstra section does not.
4. All sections are required to have a description that explains how the algorithm works. The Dijkstra section does not.
5. If it does not already exist, I have planned on creating an issue to move the afore mentioned code in the Graph section under Dijkstra (issue Dijkstra Solution #64)

Now comes the question of how does this happen:

1. We have limited resources to conduct reviews and corrections, and occasionally stuff gets missed. Perhaps we could start using the style guides as a checklist before merging code to address this issue. Once the changes to the style guides are finished, I will go through and audit the sections for compliance using this method.
2. There previously was a solution to Dijkstra in this section, but it was removed because it was not explicitly licensed in a way that could be used in the Hack Pack. I have created issue Dijkstra Solution #64 to address this.
3. One of the ways that we get contributions is via students in CPSC 481 writing sections. Sometimes these students only take the class for one semester, and simply didn't have time to make corrections that were needed by the time that they finished. We have attempted to address this with a contribution deadline this semester.

Here are some of the reasons why we require sample IO:

1. It makes it much more likely that the code was tested. In the old resources prior to the Hack Pack, there were several examples were the sample code that were just wrong. These problems would have been found in testing, but because there was no IO they were never found.
2. It makes it easier to see what the required input to a problem might be. In the older resources prior to the Hack Pack, there was code that used an array that started with an index of 1 instead of 0. There were no comments to this regard, but this would have been noticed if there was sample IO for the code.
3. It provides a lightweight means of verifying that code was entered correctly. You could use the sample input and output to help verify if a problem was typed correctly.

The major reason why we require code to be part of a sample solution is because sometimes it is difficult to tell where code like this may be used. Consider flow problems, they are used to solve maximal matchings. Without extensive experience with graphs, I doubt that you would guess this, and does not meet the Hack Pack++'s goal of being a learning resource for inexperienced team members. For people with experience who just want the algorithm, they should use the Hack Pack, not Hack Pack++.

I believe that dropping the Sample problem requirement would be a mistake.

[mdclyburn]

Beside being handy for seeing obscure solutions to problems, what else are the contest problems doing for us? Sure, max flow problems may be one of the more elusive ones to pick out, but is that true for most contest problems? Or are we needlessly exploding the size of the Hack Pack?

[ProtractorNinja]

I'm concerned that our goals are focused in entirely the wrong place. Should we really give equal importance to "learning reference" and "contest aid"?

That is, how many times has anyone actually looked to the Hack Pack for learning so far? I suspect the answer is close to zero, yet we still seem to over-prioritize the Hackpack++ aspect. It's even holding us back by requiring far too much of each submission: saying "you must contribute a lot of good stuff" earns us "a lot of probably bad stuff" instead of the more optimal "just enough great stuff" (see almost every external submission so far for examples). Condensation is a maybe-step-two afterthought, as is obvious from the proposed LaTeX guidelines.

In the case of Dijkstra, for example, we can't put all the blame on our misguided contributor. Because of our guidelines for submission, he ended up writing a ton of useless cruft instead of what Marshall and I were looking for during the ICPC: how to do Dijkstra.

That's a big problem on our side. Shouldn't we be going for "make something that's extremely useful in a contest environment" first, with additional reference as an extra?

[mdclyburn]

Perhaps we should provide a structure to allow submitting separate pieces? Dr. Dean likes for his 481 students to author problems, correct? Perhaps they could elect to author the description and reference code or a problem for each section in the Hack Pack? This would make it a lot easier to get content into the Hack Pack. But it could also leave us with sections that are of inconsistent quality if submitted content isn't more carefully vetted.

As far as I can see it, this is a problem with focus and priority. I like the aspect of the Hack Pack++. References are really cool and useful, but, like @ProtractorNinja wrote, it keeps the Hack Pack from gaining content in a swift manner because it requires so much bulk (the biggest of that bulk being the sample/contest problem portion).

We should prioritize the description and reference code content of a section first. These would be the more helpful things to use in a contest environment. Then we could look into adding problems...

[ProtractorNinja]

I stand by the complaints I have already raised regarding the Hack Pack's current direction, and I can't fully approve of project-defining documents until those issues are resolved. Anything to add, @mdclyburn and @robertu94?

[robertu94]

I am content with prioritizing Hack Pack content over Hack Pack++, but I do not believe that sample problems with input and output are unnecessary for the reasons that I listed above. Yes, many problem types are more obvious than max flows. That does not mean that an implementation cannot not contain nuance that can be revealed by input/output code as well as via sample input.

I also would be fine with allowing piecemeal submission. I just hadn't broken down the issues further.

[mdclyburn]

I stand behind the idea of prioritizing Hack Pack content before Hack Pack++ is even considered. It might even be a more natural fit to the process. I also want to bring up the fact that we may not see much of anything come out of Dr. Dean's seminar this semester since it is not a variable credit course any longer (as of we had a high volume of high quality content before).

[ProtractorNinja]

Sample problems, sample data, full code, and unit tests are surely helpful in complex cases, but requiring them for every submission makes submission harder and bloats the hack pack.

Submission should be easy. Large code projects need tests and proof because the code will live on effectively forever, enduring changes and supporting the rest of the code base. Code like that, in a living environment, needs to continually prove itself. For our purposes, submissions only need to be "proven" once, during approval, because our delivery is a static document: unit tests and needlessly full-featured code samples are overkill unless context demands them. Because we have Github, all we need to solve our this-reference-code-doesn't-work problem is intelligent reviewers who actually investigate the code. "Give me a larger sample that shows this code works" is a fitting demand for submissions that need it, but currently, if I want to submit a cool Python function I found helpful at the last Mercer competition, my excitement to contribute will end up dead in the water before I even finish reading the README.

Once created and deployed, the average full I/O sample problem clogs the pack more than it helps. When I'm combing the hack pack during a competition, I'm only interested in the basics: a description of each algorithm or structure and a short, non-complex sample implementation with, if needed, an annotation about what kind of data it operates on or other noteworthy details. If needed. I don't want to see the standard includes unless I need them, I don't need to see int main(...) or sscanf(...) unless they fit the context, I don't want to have to think about how Bessie's troubles relate to mine, and I definitely don't want to see half a page taken up by garbage like "Sample Input: 4"!

The ideal algorithm or data structure sample doesn't need any of this extra stuff because the ideal snippet is short, sweet, and parsable; inevitable exceptions notwithstanding. We should be encouraging high-quality content like that, not average-quality content that simply ticks all the boxes. Heavy-handed checklist-style submission approval tactics will distract us (and future contributors/organizers) from what's important, like making sure that people actually find the hack pack useful.

The hack pack should be useful. It really isn't. I'm appalled at how useless the hack pack was for me during the ICPC last year. It's an overly formal mess of nigh-useless content with a few flecks of gold hidden inside. Something is very wrong if anyone ever gets close to thinking that.

The more I consider the idea, the less I care for even having the Hack Pack++ in addition to the standard Hack Pack. We're not doing one thing well; we're doing two or three things poorly. Perhaps it would be more prudent to focus on creating a streamlined, damn useful, practical document and expand it later only if interest is raised?

I think that our current helpless state demonstrates that we bit off more than we could chew. We could really benefit by reducing the scope of this project and re-evaluating what the team really needs. We don't need a formal process for anything until then.

[robertu94]

Even if we do not include the full implementations of the solutions in the Hack Pack itself, I am not convinced that we can ensure functional code without them. These "ah! the reviewers will save us" methods fail us all the time because people are failing creatures.

If you can prove exhaustively that code works without test cases and without actually compiling and testing it, then I would be happy to drop the requirement. However, time and time again we see not that careful review is what ultimately generates working code, but through testing. The last thing that we want to do in a contest is not reading a few extra lines of context and usage but to have to debug code from our cheatsheet that flat out doesn't work.

As for your python snippets, if they are sufficiently short, they probably don't belong in the algorithms sections or the data structures sections where this kind of testing is essential. Rather, they should exist in the examples section like where Makefiles are stored.

I also don't mean to discount your experience that you didn't find the document extremely useful, but if you are using the HackPack++ during a contest, you are going to be miserable. Especially, if you are a experienced veteran like you are. There is a ton of stuff that you don't need. Beyond using needing HackPack instead of HackPack++, when you had your problems: a majority of the document had not be marked to be minimized, and almost none of the sections are/were indexed. That is the tragedy of a work in progress, not a flawed design.

I am happy to put a greater focus on writing the HackPack than the HackPack++, but not at the expense of through testing.

[ProtractorNinja]

I was using the regular hack pack. It's bad. A solid design would not have enabled its creation.

I disagree with, well, just about everything you've said. I don't think you've effectively discounted any of the points I've already raised: again, submission approval is a process that only needs to be done once. Submitted code should, generally, be happily generic and widely applicable. It shouldn't be the sort of thing that needs unit tests to prove correctness.

Eliminating Dr. Dean's credit boost means that we're only going to be getting submissions from people who are interested in making the hack pack better. We don't need unit testing to tone down any kind of content influx. We need good code that works. Unit testing is one way to get it, but requiring it now is overkill for the reasons I've already stated. Critical code should be elegant enough to innately demonstrate its correctness.

People are failing creatures, yes, which is why it's nice that multiple people can review something more than once. They might mess up, but we don't need to plan for that quite yet: we haven't yet seen that reviewers are going to have trouble if they spend the time to really get involved with the code. Submissions that were already bad aren't going to get much better if they get smushed into unit tests; ironing out little bits of incorrectness won't help if the thing just sucks overall.

I think that this sweet short testing-not-needed code ideal is the biggest difference in our thought processes. Algorithm and data structure base definitions and samples should't need to be unit tested, but we could say that full, input-driven samples that exist for certain complex processes do.

[mdclyburn]

Well. I didn't have any strong opinion on the policy of unit testing, but @ProtractorNinja brings up a good point. Do we even need unit testing? Unit testing is cool, I'll admit. I use it on all of the code that I care about. But its primary use is to ensure that a growing/shrinking/morphing code base still works in the way the author(s) intend it to. Can part of the review process for submission be the reviewer testing the code? If we can do this, we can cut down on a lot of bloat. And if one person isn't enough to review a submission, add another reviewer. I'm sure we can easily follow the rule of not merging in content if it is erroneous.

Make a case for unit testing. Once a submission makes it into the Hack Pack, it should be correct. Unless there is a good reason for unit testing, I want it thrown out.