tag:blogger.com,1999:blog-8288194986820249216.post5974909782060211896..comments2024-03-22T05:09:17.789-07:00Comments on Abstract Heresies: 20 minute puzzleJoe Marshallhttp://www.blogger.com/profile/03233353484280456977noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-8288194986820249216.post-1210067033754449912012-04-09T13:58:38.581-07:002012-04-09T13:58:38.581-07:00I didn't bother loading up SRFI-1 so I wrote a...I didn't bother loading up SRFI-1 so I wrote an implementation in R5RS Scheme:<br /><br />https://gist.github.com/2346450Duncanhttps://www.blogger.com/profile/13843763027842460609noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-5456679772654914002012-04-09T13:44:46.774-07:002012-04-09T13:44:46.774-07:00You don't say how big the lists are expected t...You don't say how big the lists are expected to be, which of course controls the sort of algorithms I'd use.<br /><br />If they are big enough to be in external storage, I'd sort them (mapping the objects to their names with "cut") and then use "comm -13". If they are in memory and I get to use Scheme, I'd use MAP to map the objects to their names, and then use LSET-DIFFERENCE from SRFI 1, on the assumption that Olin Shivers is more likely to get that operation right than I am.<br /><br />If I knew the length of the list of names was at most four, I'd make sure the other list's length was at most four too, and if not, return false without further work.John Cowanhttps://www.blogger.com/profile/11452247999156925669noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-80490833658137954812012-04-09T13:42:18.804-07:002012-04-09T13:42:18.804-07:00Oh, and I guess the answer is that I wouldn't ...Oh, and I guess the answer is that I wouldn't change my program unless I really cared about squeezing out performance for small collections of names and objects. If so, my first thought would be whether I could arrange to get the objects and names ordered in advance, so that I could zip down the lists and check like that.mquanderhttps://www.blogger.com/profile/04628649386002008189noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-4531026665299480622012-04-09T13:39:25.204-07:002012-04-09T13:39:25.204-07:00A simple C# implementation the most obvious way:
...A simple C# implementation the most obvious way:<br /><br />public static bool IsComplete(IEnumerable<string> keys, IEnumerable<NamedThing> objects) {<br /> var objNames = new HashSet<string>(objects.Select(o => o.Name));<br /> return keys.All(objNames.Contains);<br />}<br /><br />The "same thing" in Clojure:<br /><br />(defn is-complete? [names objs]<br /> (let [obj-names (set (map :name objs))]<br /> (every? #(contains? obj-names %) names)))mquanderhttps://www.blogger.com/profile/04628649386002008189noreply@blogger.com