I do not claim to be a "code fu" kind of guy. I don't do Code Golf for fun in my spare time.

This problem showed up last week at work and I was surprised at the difficulty of wrapping my head around the code implementation of it.

You have a data table of:

- 3 columns of data.
- CompanyID, AddressID, and AddressType
- The first two are linking different files of lists of data, not important. What is important is that any time a row matches the first two columns (Company+Address), and there exists one or more of those with AddressType="" (blank), the blank duplicate should be merged (removed).

with sample data (in my case it was some 20,000 rows):

100, 232, "Shipping"
101, 232, "Billing"
101, 232, ""
101, 232, ""
101, 232, "Shipping"
162, 343, "Shipping"
(etc)

It's seemingly simple. "Deduplicate any rows where the first two columns match, where data takes precedence over blanks."

But the second you start writing code, now you have to deal with how you're looping through it and whether you're modifying the data structure en-loop or creating a new one.

It was a fun puzzle in the few hours I had to get it working at the end of one work shift.

Knowing you guys, there's probably some jerk that can do it in two lines of Haskell.

Might be it was not actually CSV, and there were other constraints?

Problem sounds and probably IS simple but implementation of the de-duplicating algorithm may be a bit tricky (haven't thought really about it, honestly).

What was exactly the culprit of your "struggle"?

Well, perhaps I was too worn out by the end of the day.

Python is great, I've really started to learn and love it the last few weeks. But I'm still new to it.

You can use "set" to unique-ify lists. But it's only going to work over the entire tuple. Can you unique based on only a subset of data, and yet have it effect the whole?

My "struggle" was, each time I tried to implement my idea, I would run into boundries. Use dictionaries? Ok, but you can't index a dictionary. Use lists? Enjoy n^2 iteration and you still can't modify the container inside a traditional for each. So now, you have to be able to decide whether or not each entry should go into the new list (it's unique), or not (it's a duplicate), but not send the same unique value twice. Or, modify the list as you index it manually, compare each against all the other entries, and when a duplicate is found run the comparison to see who "wins" and remove the loser.

See what I'm getting at? The issue is deceptively simple, the implementation is not--at least to my inexperienced brain.

Exactly what I thought , implementation may be tricky.

One thing that I was worried about in my (very) sparse thoughts was not find the duplicates (even caching the results in an ad-hoc index, and then modifying the whole structure at once), but doing the thing INTELLIGENTLY with a non-exponential O loop, for example.

My perplexity was due to the fact that you worded the problem as there was some sort of n"hidden gotcha".

Anyway I am thinking language agnostic, and Matthew example (which I get is SQL? ) shows that "implementation" is ALSO a matter of tools.

BTW, was it implied that you were using Python? I do not have any knowledge of it

Perl example:

That's no golf example, but it gets the job done. That took me about 3 minutes to stub out, and another 30 minutes to debug. That is with a little (rusty) experience parsing and processing CSV with Perl. I used a module somewhat new to me (Text::CSV) which resulted in most of the debugging time, but I'm also rusty with the module that I'm more familiar with (Text::CSV::Simple) so there's no guarantee that it wouldn't have taken me as long using that.

The key to solving a problem like this "fast" is having done it before and having tools available to you that do most of the work for you. You should prefer a tool that lets you solve the problem quickly first. For this a dynamic programming language is ideal. Attempting to solve this well in C would add to the headache. As far as performance is concerned, 20000 rows is negligible. If you were dealing with gigabytes of data my solution would probably fall on its face (in particularly, it is needlessly copying data into new array structures, which could be eliminated with relatively little effort). Whether you go for something lazy and slow or something intricate and blazing depends on how much time you and the computer have to solve the problem, and also how much time it will take to develop and debug that blazing fast solution versus just letting the computer brute force with something sloppy.

These kinds of problems can be deceptively time consuming. The more experience you have solving them the more quickly you'll wire the pieces up to solve them. Matthew might not have been entirely in left field. You might be able to get that data into a DBMS, run the query, and output it again more efficiently (human and machine) than rolling your own. For example, on our ancient QNX systems at work we are running an old version of Sybase ... Like 5.5 or something. I'm barely familiar with it, and documentation is hard to come by, but you can import CSV data with `INPUT INTO tbl FROM /path/to/csv;` and export data to CSV with `SELECT ...; OUTPUT TO /path/to/csv;`. That might well be an efficient way to solve the problem, but of course it depends on what kind of environments are available to you already (e.g., do you have a DBMS that supports importing/exporting CSV data, does one exist in a development or testing environment where an accidental query won't damage production data and cause downtime or loss, etc?).

Another thing to note is that "CSV" is a poorly standardized format. Different software solutions understand different variations of it. You'll note that my Perl program doesn't output in the exact same "format" e.g., same rules as the input came from. You can almost certainly tweak the output somewhat, but there will be limitations. Generally when it comes to general parsing solutions they try to be strict with their inputs (one of the things that took time to debug was figuring out which configuration options were needed to parse your sample input; more may be needed for the real thing). General CSV parsers maybe struggle to support arbitrarily structured formats (e.g., quotes only for 'string typed' fields, etc.). A "well-formed" CSV format may be defined as no arbitrary white-space, always or never quoted fields, etc. All of these little details add to the complexity of the solution.

Having your data in CSV is probably an indication of a problem to begin with. It's an acceptable solution for QnD one-off solutions, but it's not a very robust solution (e.g., see lack of standardization).

Personally I wouldn't use Microsoft Office for anything programming related unless forced to. Though in general I won't use Microsoft Office for anything unless forced to. That more or less extends to Microsoft anything too. It's just not robust software. You end up attempting to link proprietary software with proprietary software. Sorry, only the most simple or standard configurations are supported or documented. Your real world case is either not supported or not documented and you don't know which. In my experience it's usually a waste of time trying. That isn't limited to Microsoft. I find all proprietary software is like that.

Software is meant to be malleable. That's where the "soft" comes from. Proprietary software is not malleable. It might as well be hardware. It doesn't do exactly what you want, and you practically have to reverse engineer it to figure out what it can do. That's not to say that open source software solves all of life's problems, but it causes fewer of them and once you solve the ones you have you have the freedom to save the next guy the trouble.

I think that as software developers the whole "capitalism" thing really doesn't work so well for most of us (for those few Bill Gates' it works out pretty fantastic, but those are a needle in a hay stack). Well I feel your pain. Maybe not the same pains, but similar ones. I think that Microsoft causes pain right across the board. Even our "in house" software feels proprietary. It often comes from Argentina, Mexico, or <elsewhere>. Often it is half Spanish/half English. When there even is source code there are no comments, and the code is not self documenting. Often there is no code. Only binaries from unknown sources. When there is code there are 100 copies of it and no record of its origins (i.e., production versions, incomplete updates, untracked "backups" in the event that updates cause irreversible damage; arbitrarily located and named). The majority of my job is debugging others' broken, undocumented, untracked code; or attempting to extend or change it with as few pokes as necessary and absolutely no development/test environments and usually a dearth of required development tools' software licenses.

Example in Python:

N.B. it doesn't work with the dialect of CSV you've posted, I believe that all is required is to fiddle with the options on the csv.reader constructor.

Sorry if I miss something obvious, but I'd sort first on all three columns (the last one in descending order), and then I'd perform a single pass on all records, comparing record N with record N+1 :
- if they have same IDs
- and record N has a type
- and record N+1 has no type,
then record N+1 can be omitted.

The specific process would be slightly complicated by the need sometimes to omit multiple records, but I guess it would stay O(N)

Is your 25 lines supposed to scare me?!

And Text::CSV has an XS (native-code implementation) module so if you install that you can get C-like performance automatically (but see its caveats).

Yes, input is the easy thing to handle. CSV parsers can relax the rules quite a bit to do a best effort at parsing pretty horrible formats. However, the more relaxed the rules get the less reliable the parsing will get. I'm not at all surprised that Perl modules will parse almost anything you throw at them. Configuring for sloppy output is the harder job to do. It's all well and good if Perl can read the input, but if the programmers' own tools can't read the output then it doesn't do you any good to have generated the output. Therein lies the conundrum with using CSV at all. In particular, often propretary software will tell you it can generate or consume CSV without specifying exactly what that means. You are left to guess and the robustness of your solution depends on the accuracy of your assumptions.

Protip: Tobias Dammers loves Haskell and could probably put forth a challenge, though if he can beat Perl at being terse I want to see it. Albeit, something of this nature is less of a language competition and more of a library competition. I started learning Haskell, and it was actually quite enlightening, but I got distracted and haven't returned. Wrapping your head around coding with monads takes some effort...

They did, 0x1c - 0x1f are set aside as separators for exactly this purpose.
http://en.wikipedia.org/wiki/ASCII#ASCII_control_code_chart
The morons are whoever chose to ignore these and use printable , and " instead.

I believe this family of 'delimited ASCII' formats were only ever intended to represent tabular text - typed and/or structured data is really outside the remit.

Anyway, you're right, we are where we are, just like CRLF vs LF and just like '\' vs '/' - decisions made a long time ago still cause us pain today.

Anyone running CSV as a developer should at the bare minimum be running a text editor that can show non-printable characters, such as Notepad2/Notepad++.

Even if you don't use them as delimiters, some moron, writing some terrible e-mail program (Outlook?), is going to send non-printable ASCII characters in some malformed XML/HTML e-mail and it's going to infuriate you when it crashes. I ended up having to run a regular expression in Notepad++ to match and remove all non-printable characters because Microsoft Dynamics would fail out the second it tried to read it.