tag:blogger.com,1999:blog-6373963829340632529.post3659203143617959184..comments2024-01-30T05:40:30.415-03:00Comments on Algorithmically challenged: Expressive Code and the Alternative VoteDanielhttp://www.blogger.com/profile/07505997833685327219noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-6373963829340632529.post-29144278276781332011-05-03T21:39:14.500-03:002011-05-03T21:39:14.500-03:00Oh, shoot, now I see what you're saying. The m...Oh, shoot, now I see what you're saying. The mutual recursion was definitely unintended. The tail call in elect was supposed to be another call to electHelper - that's a typo that arose because I moved the validCandidates check out of the elect function at the last minute and then posted it without trying it. Sorry. Moving it out was wrong on my part anyway.<br /><br />I don't have a problem with using collections as functions:<br /><br /> if( friends(jimmy) ) { .... } // awesome<br /> a(10) = 444 // great<br /> if( a(0) > 10 ) { ... } // rad<br /> vote filter candidates // pushing it, but fine<br /><br />but<br /><br /> candidates maxBy votesByCandidate // contortionistic<br /><br />Guess we just disagree.<br /><br />I said the voters are a Traversable. Each voter is represented by a Seq of votes. Agree? We both know that the votes themselves have an order, but the outer collection ('votes' in your code) has no order.<br /><br />But yes, I think "val (winner,winnerVotes) = votesByCandidate.maxBy(_._2)" is preferable to your code. Not least because I get the winnerVotes variable along with it, which you have to retrieve later and because it's completely straightforward about what it's doing.<br /><br />I didn't want to get into a big arguing match, I guess we just disagree about how best to present Scala to newcomers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6373963829340632529.post-6300983513431443982011-05-03T21:05:23.633-03:002011-05-03T21:05:23.633-03:00In your original code you had elect call electHelp...In your original code you had elect call electHelper and vice versa. That's mutual recursion and it is not optimized by Scala.<br /><br />You pick on "vote" -- though vote is explicitly defined as a list of candidates ranked by preference -- but go on to say that "allVoters" is a list of "choices". How can allVoters be a list of choices, and not voters?<br /><br />I call "votes" a list of "vote", and it is a sequence -- not a traversable or iterable -- because it *cannot* be a set. It must be able to admit multiple identical votes, and the only collection that *ensures* that is sequence. To ensure that is typechecked I made it a sequence.<br /><br />You say underscore is idiomatic Scala, which is true enough (though you could have replaced (candidates.contains(_)) with (candidate contains). However, you complain about using collections as functions. Well, I have news for you: *that* is idiomatic Scala, and you should get used to it. Collections are functions for a reason, not by coincidence.<br /><br />However, I did not write this code for people who are used to reading Scala code -- it adds nothing for them. I wrote it for people who are curious about Scala, or learning it.<br /><br />And you think that<br /><br />val (winner, winnerVotes) = votesByCandidate.maxBy{case (_,voteCount) => voteCount}<br /><br />is preferable to<br /><br />val mostVotesCandidate = candidates maxBy votesByCandidate<br /><br />???<br /><br />You can keep it, thanks. I wish I could use a case class vote(choices: Choices), type Choices = Seq[String], but there's no place to put that -- it adds things that are not related to the problem.<br /><br />I did find your use of "find" perfect, though. I'll change my own version to use it as well.Danielhttps://www.blogger.com/profile/07505997833685327219noreply@blogger.comtag:blogger.com,1999:blog-6373963829340632529.post-30656731015319119602011-05-03T19:36:34.949-03:002011-05-03T19:36:34.949-03:00First of all, I'm not using mutual recursion -...First of all, I'm not using mutual recursion - you might want to read my code again. And my code is definitely tail-call optimizable...<br /><br />Second, you're talking about trivial syntactic differences - underscore versus named variable, _2 versus an explicit pattern match. These aren't my concern and I wouldn't have commented if they were. If underscores really damage your calm, be explicit:<br /><br /> allVoters flatMap (choices => choices.headOption)<br /> ...<br /> votesByCandidate.maxBy{case (candidate,allVotes) => allVotes.size}<br /><br />But these are minor nitpicky differences. I'm talking about the overall flow of the program and I stand by my claim that mine is easier to follow than yours is. Using collections as the function argument to filter or maxBy is just poor form, IMO, and needlessly obscure. I don't have a preference between infix and dot-syntax - I used dots because that's my habit, not to make a point. But I would recommend getting accustomed to underscores, since they're idiomatic Scala and they're there for a reason - sometimes repeating the name of the object you're working on is noisier than just the fill-in-the-blank the underscore suggests. You got lucky that you could use container apply methods here but in the general case you're going to need the underscore.<br /><br />orderedChoices may not be the perfect name but in the expression "vote filter candidates" vote is a singular noun, which should be a giveaway that your naming might not be mapping well to the real world. Another minor point is that the list of voters doesn't have any sequence - it should be a Traversable, not a Seq; what if one day you want to pass in a Set of votes?<br /><br />groupBy(identity) is the only hairy part of my code, but it's not too bad and the benefit is that nice "val (winner,winnerCount)" destructuring later on. If you're worried about tracking the type of votesByCandidate, give it an explicit type (that's a good idea and I replaced my comment with a type assertion).<br /><br />I'm not going to sit here and compare underscore counts but here's my updated version, fixing my mistake about valid candidates and removing every single underscore:<br /><br />http://hpaste.org/46346/alternative_votingAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6373963829340632529.post-78682819678976961792011-05-03T18:26:41.571-03:002011-05-03T18:26:41.571-03:00You picked on the single line that I said didn'...You picked on the single line that I said didn't read right, though I blame the word "filter" on that. And while "contains" makes what happens more explicit, I much prefer to explain how maps, sets and seqs work than be redundant.<br /><br />As for the vote/orderedChoices, vote is clearly defined as "Each vote is a list of candidates ranked by preference." In fact, I think "orderedChoices" obscures the fact that it corresponds to someone's actual vote. I'd probably make vote a case class Vote(choices: Seq[String]) instead, but I don't think it adds readability here, and does add complexity.<br /><br />But, aside from these issues which are arguable, I wouldn't go with your code. I feel that mutual recursion is more confusing than simple recursion, and you loose tail recursion optimization to boot. <br /><br />My original code used groupBy/mapValue (though then did toMap to it), but I wasn't happy with that. First, "groupBy(identity)" sounds confusing. Second, it produces the list of candidates from the list of votes, which is the main source of my discontent.<br /><br />While not as efficient, declaring that the votes of a candidate is the number of votes for that candidate feels much more natural to me. As for efficiency, the number of candidates is bound to be low with AV system (or, otherwise, ranking them would be a nightmare for the voter), and I believe in not prematurely optimizing, and the magnitude of the numbers involved all point to this being a pretty fast calculation.<br /><br />Likewise, I avoided tuples, because I hate "_._2". I think it looks ugly and it is completely obscure to its meaning.<br /><br />And while I did like how you got the winner votes, that requires one to keep track of the fact that votesByCandidate is a list of tuples. I don't think the tradeoff is worth it.<br /><br />Finally, note that there isn't a single instance of "_" in my code. I don't know about you, but those underscores where my main source of unease while learning Scala.<br /><br />Oh, and I much prefer infix notation. I believe that punctuation should be used to draw attention to something, instead of being lost in the trees.Danielhttps://www.blogger.com/profile/07505997833685327219noreply@blogger.comtag:blogger.com,1999:blog-6373963829340632529.post-56398137261053087832011-05-03T17:33:55.807-03:002011-05-03T17:33:55.807-03:00Also, I'm mistaken. I see now that you're ...Also, I'm mistaken. I see now that you're not validating the candidates - you're removing ones who've been eliminated in previous rounds. So the elect/electHelper distinction can go away and the logic in my elect needs to be at the top of the current electHelper.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6373963829340632529.post-75065372107844134312011-05-03T17:07:25.703-03:002011-05-03T17:07:25.703-03:00Formatting got nuked. Here it is (with a little cl...Formatting got nuked. Here it is (with a little cleanup, like only calculating the loser when we don't find a winner):<br /><br />http://hpaste.org/46335/runoffsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6373963829340632529.post-28132692618676468782011-05-03T16:50:44.849-03:002011-05-03T16:50:44.849-03:00Why is it so obfuscated? Yes, sets and maps implem...Why is it so obfuscated? Yes, sets and maps implement apply, but to be honest, I think you're abusing that a little in this example - they make the code a puzzle to decode rather than something to scan and grasp.<br /><br />"vote filter candidates" took me a while to figure out. The identifier "vote" would be clearer as "orderedChoices", e.g. "orderedChoices.filter(candidates.contains(_)" makes perfect sense to me. Even the original "orderedChoices filter candidates" makes more sense.<br /><br />Additionally, you should mention that Set only implements maxBy and minBy in the (unreleased) 2.9. I would move the validation out to an external wrapper - it takes extra time and code complexity to do it at every match-up.<br /><br />Sorry to be so critical but we all need to fight the stereotype of Scala as a confusing or "complex" language.<br /><br />Here's my entry (I also assume 2.9's maxBy and minBy; in this case on Map):<br /><br />---<br /><br /> type OrderedChoices = Seq[String]<br /><br /> def elect(candidates : Set[String], orderedChoicesList : Traversable[OrderedChoices]) = {<br /> val validVotes = orderedChoicesList.map(_.filter(candidates.contains(_)))<br /> electHelper(candidates, validVotes)<br /> }<br /><br /> def electHelper(candidates: Set[String], orderedChoicesList: Traversable[OrderedChoices]): String = {<br /> val firstChoices = orderedChoicesList.flatMap(_.headOption)<br /> val votesByCandidate = firstChoices.groupBy(identity).mapValues(_.size) // map from candidate to vote count<br /><br /> val (winner,winnerVotes) = votesByCandidate.maxBy(_._2)<br /> val (loser,_) = votesByCandidate.minBy(_._2)<br /><br /> if( winnerVotes >= orderedChoicesList.size / 2 || candidates.size <= 2 )<br /> winner<br /> else<br /> elect(candidates - loser, orderedChoicesList)<br /> }Anonymousnoreply@blogger.com