40
\$\begingroup\$

A lot of languages have built-in ways to get rid of duplicates, or "deduplicate" or "uniquify" a list or string. A less common task is to "detriplicate" a string. That is, for every character that appears, the first two occurrences are kept.

Here is an example where the characters that should be deleted are labelled with ^:

aaabcbccdbabdcd
  ^    ^ ^^^ ^^
aabcbcdd

Your task is to implement exactly this operation.

Rules

Input is a single, possibly empty, string. You may assume that it only contains lowercase letters in the ASCII range.

Output should be a single string with all characters removed which have already appeared at least twice in the string (so the left-most two occurrences are kept).

Instead of strings you may work with lists of characters (or singleton strings), but the format has to be consistent between input and output.

You may write a program or a function and use any of the our standard methods of receiving input and providing output.

You may use any programming language, but note that these loopholes are forbidden by default.

This is , so the shortest valid answer – measured in bytes – wins.

Test Cases

Every pair of lines is one test case, input followed by output.



xxxxx
xx
abcabc
abcabc
abcdabcaba
abcdabc
abacbadcba
abacbdc
aaabcbccdbabdcd
aabcbcdd

Leaderboard

The Stack Snippet at the bottom of this post generates a leaderboard from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

## Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

## Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

## Perl, 43 + 3 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the snippet:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 86503; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 8478; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>

\$\endgroup\$
1
  • 5
    \$\begingroup\$ Singleton strings... stringletons? \$\endgroup\$
    – anna328p
    Jul 28 '16 at 19:00

40 Answers 40

1
2
1
\$\begingroup\$

Pure Zsh, 35 bytes

eval ';1=${(I:3:)1//'{a..z}\}
<<<$1

Attempt This Online!

Explanation:

  • eval {a..z}: for each letter:
    • $1: in the input:
    • {//}: replace all matches of that letter
    • (I:3:): but only replace starting with the third match
    • ;1=: and update the input to that new string
  • <<<$1: print the variable $1
\$\endgroup\$
0
\$\begingroup\$

Javascript (using external library) (80 bytes)

This was a good one! Didn't win but it was fun

n=>{a={};return _.From(n).Where(x=>{b=a[x]?a[x]++:a[x]=1;return b<2}).Write("")}

Link to lib: https://github.com/mvegh1/Enumerable/

Code explanation: Method accepts a string, library parses it as a char array, and the Where clause is a complex filtering predicate that checks the 'a' hashmap for presence of the current char. If exists, increment counter, else set to 1. If < 2, the predicate (and current char) passes, else fail

enter image description here

\$\endgroup\$
3
  • \$\begingroup\$ You can avoid using a return but making your function a comma-separated list of a expressions in parentheses: n=>(a={},_From(n)....). The last expression is the return value. In your Where function, you can eliminate the intermediate b entirely by comparing against the result of the assignment or increment: x=>(a[x]?a[x]++:a[x]=1)<2. \$\endgroup\$
    – apsillers
    Jul 25 '16 at 16:33
  • \$\begingroup\$ Finally, you can avoid using an external library at all (and save bytes) using the string-split ellipsis and filter with join: [...n].filter(...).join(""). Flip the true/false logic when changing Where to filter. \$\endgroup\$
    – apsillers
    Jul 25 '16 at 16:40
  • \$\begingroup\$ Ahh good observations! Ill take a closer look later at your suggestion \$\endgroup\$ Jul 25 '16 at 17:53
0
\$\begingroup\$

Clojure, 72 bytes

#(apply str(reduce(fn[r c](if(<(count(filter #{c}r))2)(conj r c)r))[]%))

So many bytes...

\$\endgroup\$
0
\$\begingroup\$

Pascal (FPC), 103 bytes

var a:array['a'..'z']of word;c:char;begin repeat read(c);inc(a[c]);if a[c]<3then write(c)until eof end.

Try it online!

Explanation:

var a:array['a'..'z']of word; //used for counting occurences of characters in the input
                              //array indices are accessed by chars
    c:char;
begin
  repeat
    read(c);                  //read a character from input
    inc(a[c]);                //increment the count of that character (its number in array)
    if a[c]<3 then write(c)   //if this is character's 1st or 2nd occurence, output it
  until eof                   //go back to reading if input is not read completely
end.
\$\endgroup\$
0
\$\begingroup\$

sed (with -r), 25 bytes

:x;s/((.).*\2.*)\2/\1/;tx

Try it online!

Takes input from STDIN, outputs to STDOUT. Very straightforward implementation: does a regexp match for triple characters, deletes the last one, and loops until it didn't find anything else.

\$\endgroup\$
0
\$\begingroup\$

Bash + GNU sed, 18 bytes

sed -es/{a..z}//3g

Try it online!

Way better than my pure sed answer. I marked it as GNU sed because POSIX sed doesn't define the result of supplying both a number and g as flags to the s command. GNU sed, as an extension, takes this to mean "replace all matches starting with the third", which is just what we want.

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 7 bytes

ʒIN£y¢!

Try it online!

\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog Unicode), 19 bytes

{⍵/⍨i∨≠0@(⍸i←≠⍵)⊢⍵}

Try it on TryAPL (because this doesn't work in TIO)

is the unique mask function when used monadically. It returns an array of ones and zeroes (ones where the first occurrence of an element is found, zeroes where there are duplicates). i ← ≠⍵ assigns the unique mask of (the argument to this function) to i.

i gives us ones where the first occurrence of each element is found, but we also need ones where the second occurrence of each element is found. To do that, we use again, but first we clear all the unique elements from . tells us the indices of the ones in its argument, so ⍸i gives the indices of unique elements in ⍵. (0 @ (⍸i)) ⍵ replaces the elements in at these indices to 0 (so now they're all duplicates, and they don't conflict with the other lowercase letters in ). Running on that gives ones where the second occurrence of each element is, along with a one as the first element.

(or) combines these two masks so there are zeroes only at the indices where triplicates are. / is can take a mask on its left and keep only the elements in its right argument that correspond to a 1 in the mask. just swaps its order so we don't need parentheses.

\$\endgroup\$
0
\$\begingroup\$

Jelly, 7 bytes

Ġḣ€2FṢị

Try it online!

A byte longer than Dennis' but a unique approach as far as I can tell

How it works

Ġḣ€2FṢị - Main link. Takes a string s on the left
Ġ       - Group the indices of s by their values
  €     - Over each group:
 ḣ 2    -   Take the first 2
    F   - Flatten
     Ṣ  - Sort
      ị - Index back into s
\$\endgroup\$
-5
\$\begingroup\$

TCC, 5 4 bytes

$~;2

Try it online!

     | Print (implicit)
$~   | Limit char occurence
     | of input (assumed if not given)
  ;  | seperator
   2 | to 2
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Do you have a link to the language specification as well? \$\endgroup\$ Jul 25 '16 at 11:21
  • \$\begingroup\$ Nope. I just know Lua, so I learned the language myself, but I can't find a specification anywhere. You can find the Lua source at ccode.gq/projects/tcc.lua \$\endgroup\$
    – brianush1
    Jul 25 '16 at 11:29
  • 4
    \$\begingroup\$ Did this work with a version of tcc.lua before the challenge was posted? Since the $~ command was modified at 16-07-25 12:57 UTC and you've recently added commands to solve three other challenges, I assume it didn't. If your answer requires a version of the language that postdates the challenge, you must label it as non-competing in the header. I'll remove my downvote when you add the label or provide proof that your code worked in an earlier version. \$\endgroup\$
    – Dennis
    Jul 26 '16 at 17:07
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.