48
\$\begingroup\$

Given a string consisting of printable ASCII chars, produce an output consisting of its unique chars in the original order. In other words, the output is the same as the input except that a char is removed if it has appeared previously.

No built-ins for finding unique elements in an array can be used (for example, MATLAB has a unique function that does that). The idea is to do it manually.

Further details:

  • Either functions or programs are allowed.
  • Input and output can be in the form of function arguments, stdin/stdout (even for functions), or a mix of those.
  • If stdin or stdout are used, a string is understood as just the sequence of chars. If function arguments are used, the sequence of chars may need to be enclosed in quotation marks or equivalent symbols that the programming language of choice uses for defining strings.
  • The output should be a string containing only the unique characters of the input. So no extra linebreaks, spaces etc. The only exception is: if the output is displayed in stdout, most displaying functions add a trailing \n (to separate the string from what will come next). So one trailing \n is acceptable in stdout.
  • If possible, post a link to an online interpreter/compiler so that others can try your code.

This is code golf, so shortest code in bytes wins.

Some examples, assuming stdin and stdout:

  1. Input string:

    Type unique chars!
    

    Output string:

    Type uniqchars!
    
  2. Input string

    "I think it's dark and it looks like rain", you said
    

    Output string

    "I think'sdarloe,yu
    
  3. Input string

    3.1415926535897932384626433832795
    

    Output string

    3.14592687
    
\$\endgroup\$
16
  • 8
    \$\begingroup\$ Just to double check: Does the no builtins rule mean that set objects are disallowed? \$\endgroup\$
    – Sp3000
    Oct 4, 2015 at 14:51
  • \$\begingroup\$ @Sp3000 Set objects are allowed. Just don't use a function or method (if it exists) that gives you its unique elements. And input/output should be strings, not set tobjects \$\endgroup\$
    – Luis Mendo
    Oct 4, 2015 at 14:54
  • 7
    \$\begingroup\$ I think only my answer uses sets currently, and I wouldn't mind if you changed it. However, I'm not really sure a bonus like that would change much, e.g. I doubt CJam would be doable in < 6 bytes without sets. Also, I'm not sure where the line is between a builtin which finds unique elements, and constructing a set from a number of elements... \$\endgroup\$
    – Sp3000
    Oct 4, 2015 at 15:13
  • 2
    \$\begingroup\$ @Sp3000 Yes, it's a blurred border. I hadn't anticipated set functions. I think I'll leave the challenge as it is now \$\endgroup\$
    – Luis Mendo
    Oct 4, 2015 at 15:16
  • 1
    \$\begingroup\$ -1 Disallowing built-ins serves no purpose other than making interesting answers. This is code-golf, not popularity contests. \$\endgroup\$
    – MilkyWay90
    Apr 6, 2019 at 2:26

83 Answers 83

3
\$\begingroup\$

C, 47 bytes

a[];main(c){for(;read(0,&c,1);write(!a[c]++));} 
\$\endgroup\$
3
\$\begingroup\$

Simplex v.0.7, 22 10 bytes

s^oR^l^Ryg
s          ~~ string input
 ^o        ~~ convert to tuple
   R       ~~ go right
    ^l     ~~ unicode tuple
      ^R   ~~ take intersection
        yg ~~ convert to string and output

sigh Minkolang is kicking Simplex's butt.

s^[oZ%_Q]n?[^_s^~M^=]]
s                      ~~ string input
 ^[     ]              ~~ postfixes each of the inner with a ^
   o                   ~~ convert to tuple
    Z                ] ~~ fold
     %                 ~~ tuple w/out current character + increment
      _                ~~ current character
       Q               ~~ membership
         n?[        ]  ~~ if current character not in tuple
            ^_s^~M^=   ~~ print that character 

\$\endgroup\$
1
  • 2
    \$\begingroup\$ What a coup for Simplex! \$\endgroup\$ Oct 28, 2015 at 2:51
3
\$\begingroup\$

Vim, 23 keystrokes

qq:s/\v(.).*\zs\1<cr>@qq@q

Explanation:

qq                           " Start recording into register 'q'
  :s/                        " Search and replace:
      \v                     " Enable 'magic', which just makes regexes a littl shorter
        (.)                  " Any symbol, captured in group one
           .*                " Anything
             \zs\1           " Start selection, group one
                             " Replace with nothing
                  <cr>       " Globally
                      @q     " Call macro q. Since we are still recording, this will not do anything the first time, and create a loop the next time
                        q    " Stop recording. 
                         @q  " Start the loop. This will run until there is no match.

Since V is backwards compatible, you can Try it online!

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 5 4 bytes

ʒkNQ

Try it online or verify all test cases.

Slightly more interesting previous 5 bytes version:

SkāαÏ

Try it online or verify all test cases.

Explanation:

ʒ     # Filter the characters in the (implicit) input-string by:
 k    #  Get the first index of the current character in the (implicit) input-string
  NQ  #  Check if it's equal to the filter-index
      # (after which the result is output implicitly)

S     # Convert the (implicit) input-string to a list of characters
 k    # Get the first 0-based index of each character in the (implicit) input-string
  ā   # Push a list in the range [1, list-length] (without popping)
   α  # Get the absolute difference between the values at the same positions in the lists
    Ï # Keep the characters of the (implicit) input-string at the truthy (==1) indices
      # (after which the result is output implicitly)

With builtins allowed, this would of course be a single byte: Ù
Try it online or verify all test cases.

\$\endgroup\$
3
\$\begingroup\$

Scala, 118114 bytes

def f(a:String):String=a.zipWithIndex.groupBy(_._1.toLower).map(_._2.head).toList.sortBy(_._2).map(_._1).mkString
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 87 bytes if you remove the unnecessary def part and use a lambda, with infix+postfix notation. \$\endgroup\$
    – user
    Sep 7, 2020 at 13:12
  • 1
    \$\begingroup\$ Or 61 bytes \$\endgroup\$
    – user
    Sep 7, 2020 at 13:18
3
\$\begingroup\$

K (ngn/k), 14 bytes

{x@&(!#x)=x?x}

Try it online!

A ngn/k implementation of the classic APL idiom for unique-ifying a list.

  • x?x find the indices of the first time each character appears in the input
  • (!#x) generate 0..n, where n is the length of the input
  • (...)=... build boolean list storing whether or not the first index of each character in the input is the same as the index of each character
  • x@& filter input to the indices where the above is true
\$\endgroup\$
3
\$\begingroup\$

i386 machine code, 22 21 bytes

Machine code:

00000034  6a 20 59 6a ff e2 fc 91  ac d0 2c 04 71 01 aa e2  |j Yj......,.q...|
00000044  f7 83 ec 80 c3                                    |.....|
00000049

Commented assembly:

        .intel_syntax noprefix
        .globl .type_uniqchars
        // dst: EDI: output buffer (must be big enough)
        // src: ESI: input string
        // len: EAX: length of string
.type_uniqchars:
        // Set ECX to 32
        push    32
        pop     ecx
        // Create a 128 byte buffer on the stack of all 1 bits
        // by pushing -1 32 times.
        // We only need 128 bytes because we know that
        // we are only dealing with ASCII.
.Lpush_loop:
        push    -1
        loop    .Lpush_loop
.Lpush_loop.end:
        // ECX = len
        // EAX = 0 (because of the loop)
        xchg    ecx, eax
.Lloop:
        // AL = *src++;
        lodsb   al, byte ptr [esi]
        // This is taking advantage of this quirk with SHR:
        //
        //   The OF flag is affected only on 1-bit shifts [...]
        //   For the SHR instruction, the OF flag is set to the
        //   most-significant bit of the original operand.
        //
        // So basically, we do this:
        //
        //     unique     duplicate
        //   0b11111111  0b01111111
        //     |\\\\\\\    |\\\\\\\
        //  OF:1||||||| OF:0|||||||
        //   0b01111111  0b00111111
        //
        // I chose this over INC+JNZ because this will never
        // overflow: it will just stay at zero.
        shr     byte ptr [esp + eax]
        // No overflow means duplicate
        jno     .Lloop.duplicate
.Lloop.unique:
        // *dst++ = AL
        stosb   byte ptr [edi], al
.Lloop.duplicate:
        // Loop while there is still data
        loop    .Lloop
.Lloop.end:
        // Clean up the stack and return.
        // Note that sub esp, -128 is smaller than add esp, 128.
        sub     esp, -128
        ret

Try it online!

char *.type_uniqchars(char *dst {edi}, const char *src {esi}, size_t len {eax})
  • src is a pointer to the input string
  • dst is a pointer to an output buffer, it must be large enough
  • len is the length of src in bytes.

A pointer one byte past the end of the output string will be returned in edi. However, in the test code, I just null terminate because it is easier to print that way.

Doesn't follow standard calling convention, hence the leading dot.

Explanation (see comments for more)

This uses a lookup table on the stack, which is set to -1. It is 128 bytes because we are only dealing with ASCII.

Then, this magic is used:

        shr     byte ptr [esp + eax]
        jno     .Lloop.duplicate

This uses the fact that a one bit shr will put the most significant bit in the overflow flag. The first time, the overflow flag will be set since all bits are set, but then that most significant bit will be shifted out.

Unlike something like this:

        inc     byte ptr [esp + eax]
        jnz     .Lloop.duplicate

You could run this 1, 10, 100000 times, and it will never fail. That inc solution will fail after 256 duplicates as it wraps around to zero. Shifting right will just end up at zero and stay there indefinitely.

Other than that, it is a pretty straightforward string copy routine.

\$\endgroup\$
3
\$\begingroup\$

GNU AWK, 35 34 bytes

BEGIN{RS=".|";ORS=e}!a[RT]++,$0=RT

Try it online!

This is a major edit of my first version. In fact, it changed entirely. Only works in GNU AWK, due to the RT variable.

BEGIN{RS=".|";ORS=e}

RS=".|" works like the /./ regex, so every character of the input is considered a record separator. The practical use is that RT returns each character at a time. ORS=e prevents newlines from appearing.

!a[RT]++,$0=RT

A simple AND gate. This is a range pattern. The left part: current RT element of the a array is incremented by 1, but it is evaluated by the NOT gate before the increment. Returns TRUE only the first time a character appears. The right part: assigns the current character (RT) to the input/output $0; only happens when beginning pattern is true, i.e., the first time a character appears.

AWK, 48 bytes (former answer)

split($0,a,e){for(i in a)printf a[j=a[i]]++?e:j}

Try it online!

{
split($0,a,e); # Splits the input into the _a_ array, one char for each element.
               # _e_ variable is not assigned, and returns "".

for(i in a)            # For each element _i_ of the array _a_,
  printf
         a[j=a[i]]++?  # if the element a[i] (AKA j) is positive (i.e, true),
                  ^--- (This also increments this element by 1 after evaluating it)
                   e:  # prints _e_ (AKA "")
                   j   # if it's zero (AKA not assigned, AKA false), prints a[i].
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can shave off one ; by moving the split($0,a,e) to the left of the {. \$\endgroup\$
    – cnamejj
    Jan 16, 2021 at 9:16
  • \$\begingroup\$ @cnamejj - you're right! Thanks for the tip. \$\endgroup\$ Jan 16, 2021 at 11:14
3
\$\begingroup\$

ngn/k (2 bytes)

!=

= produces a dict that shows where each element is located, ! takes the keys.

\$\endgroup\$
3
\$\begingroup\$

Vyxal, 2 bytes

ƒ∪

Try it Online!

Reduce by set union. Port of caird's answer.

Vyxal, 3 bytes

ÞU*

Try it Online!

Multiply by uniquify mask.

\$\endgroup\$
3
\$\begingroup\$

C - 88 Bytes

r[99];b;a;main(i){for(;read(i=0,&b,1);99-i?b=0:putchar(r[a++]=b))for(;i<99&&b-r[i++];);}

Thanks to @ceilingcat because I saved 20 bytes with his modification.

Ungolfed

r[99]; b; a;

main(i) {
    for(; read(0, &b, 1); 99 - i?b = 0: putchar(r[a++] = b))
       for(i = 0; i < 99 && b - r[i++]; ); }

Explanation

Characters are read from the console, which are searched for within a list containing all the repeated characters found so far, as the characters are read, the list is updated, with new characters being added at the end of the list. If a character is repeated it is not printed.

This code was tested on GCC and it generates some warnings but it compiles and works fine (although it is not the most optimized code).

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

AutoIt, 107

Func _($0)
$1=''
For $2 In StringSplit($0,'',3)
$1&=StringInStr($1,$2,1)?'':$2
Next
Return $1
EndFunc

Call it like any function:

ConsoleWrite(_("Type unique chars!"))
\$\endgroup\$
0
2
\$\begingroup\$

CJam, 9

Lq{1$-+}/

This doesn't convert a string to a set, but it performs a kind of set difference to determine whether a character is found in a string. Try it online

Explanation:

L       push an empty array/string
q       read the input
{…}/    for each character in the input
  1$    copy the previous string
  -     subtract from the character (set difference),
         resulting in the character or empty string
  +     append the result to the string

Another version, 13 bytes:

Lq{_2$#)!*+}/

This doesn't do anything related to sets. Try it online

Explanation:

L       push an empty array/string
q       read the input
{…}/    for each character in the input
  _     duplicate the character
  2$    copy the previous string
  #)    find the index of the character in the string and increment it
  !     negate, resulting in 0 if the character was in the string and 1 if not
  *     repeat the character that many times
  +     append the result to the string
\$\endgroup\$
2
\$\begingroup\$

Haskell, 50

f=concat.(tail>>=zipWith(\x y->[last x]\\y)).inits
\$\endgroup\$
1
  • 3
    \$\begingroup\$ inits is in Data.List, so you need an import, which is usually added to the byte count. \$\endgroup\$
    – nimi
    Oct 4, 2015 at 20:46
2
\$\begingroup\$

Matlab, 46 bytes

It uses an anonymous function, with function arguments as input and output:

@(s)eval('s(~any(triu(bsxfun(@eq,s,s''),1)))')

(I couldn't get this to work in an Octave online interpreter.)

Example use:

>> @(s)eval('s(~any(triu(bsxfun(@eq,s,s''),1)))')
ans = 
    @(s)eval('s(~any(triu(bsxfun(@eq,s,s''),1)))')

>> ans('Type unique chars!')
ans =
Type uniqchars!
\$\endgroup\$
2
  • \$\begingroup\$ that would have been my idea as well :) - you don't need the ,1 with any, btw. \$\endgroup\$
    – Jonas
    Oct 4, 2015 at 20:57
  • \$\begingroup\$ @Jonas Thanks! Alrhough it's hard to see through that mess of parentheses, the 1 is for triu (I need to remove the diagonal), not for any \$\endgroup\$
    – Luis Mendo
    Oct 4, 2015 at 22:36
2
\$\begingroup\$

Delphi, 111 bytes

procedure u(var s:string);var i:word;begin for i:=length(s) downto 1 do if pos(s[i],s)<i then delete(s,i,1)end;

Using the procedure to alter the passed in string - saves a few bytes in comparison to declaring the function. Moving backwards through the string, delete the current character if it is not the first location of that character

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6) 46

f=s=>[...s].map(c=>s[c]?'':s[c]=c,s=[]).join``

Unexpectedly, this time the flag array is one byte shorter than the indexOf approach.

\$\endgroup\$
1
  • \$\begingroup\$ .map(c=>s[c]?'':s[c]=c,s=[]) => .map(s=c=>s[c]?'':s[c]=c) \$\endgroup\$
    – l4m2
    Mar 23, 2022 at 2:41
2
\$\begingroup\$

Haskell, 33 bytes

foldl(\r c->r++[c|notElem c r])[]

Uses foldl to iterate through the string appending characters that are not in the current result, starting with the empty string (list).

\$\endgroup\$
2
\$\begingroup\$

Powershell, 30

$args-replace'(.)(?<=\1.+)',''

I feel there's likely to be a better regex than this, and I can't work out what it is

\$\endgroup\$
1
  • \$\begingroup\$ -creplace of course. Try it online! \$\endgroup\$
    – mazzy
    Jan 18, 2021 at 9:07
2
\$\begingroup\$

SED, 61 bytes

s/^/\a/
:
s/\a\(\(.\).*\)\2/\a\1/
t
s/\a\(.\)/\1\a/
t
s/\a//
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 2 characters shorter: s/\a\(.\)\(.*\)\1/\a\1\2/s/\a\(\(.\).*\)\2/\a\1/. If you have GNU sed you can remove the parenthesis escaping at the price of +1 for the -r switch. \$\endgroup\$
    – manatwork
    Oct 6, 2015 at 13:43
  • \$\begingroup\$ @manatwork: Nice, changed. (I could also shrink all \a sequences into a single unprintable BEL character, though I'm not sure it's really worth it) \$\endgroup\$
    – Hasturkun
    Oct 6, 2015 at 14:08
2
\$\begingroup\$

Perl 5.10+, 21 bytes

perl -pe '1while s/(.).*\K\1//'

20 bytes + 1 byte for -p. Note that Perl 5.10 or above is required for \K.

Takes input from stdin:

$ echo 'Type unique chars!' | perl -pe '1while s/(.).*\K\1//'
Type uniqchars!

$ echo \"I think it\'s dark and it looks like rain\", you said | perl -pe '1while s/(.).*\K\1//'
"I think'sdarloe,yu

$ echo 3.1415926535897932384626433832795 | perl -pe '1while s/(.).*\K\1//'
3.14592687

Online demo


Inspired by NinjaBearMonkey's Retina answer. Perl may not have a compact way to re-run a substitution until nothing changes, but it does have \K, which causes the regex engine to "keep" everything to its left. This allows you to drop a set of parentheses on the LHS and a capture variable on the RHS:

s/(.).*\K\1//   # 13 bytes

vs.

s/((.).*)\2/$1/ # 15 bytes
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Save 1 byte using s/(.).*\K\1//&&redo \$\endgroup\$
    – Ton Hospel
    Sep 28, 2016 at 11:50
2
\$\begingroup\$

Minkolang 0.10, 13 bytes

This language was made after this challenge but not for this challenge.

Much thanks to Sp3000 for pointing me the way to this much shorter solution.

od?.dd0q?Od0p

Try it here.

Explanation

od               Read character from input and duplicate it (for the conditional)
  ?.             Stop if 0 (i.e., input is empty)
    dd           Duplicate twice (for q and for possible output)
      0q         Gets value stored in (character,0) in the codebox (0 if empty)
        ?O       Outputs character if it's unique (i.e. the previous value was 0)
          d0p    Puts the value of the character at (value,0) in the codebox
\$\endgroup\$
2
\$\begingroup\$

AppleScript, 143 142 Bytes

set x to(display dialog""default answer"")'s text returned's characters
set o to""
repeat with i in x
if not i is in o then set o to o&i
end
o

Not a language for golfing, but it's very readable.

\$\endgroup\$
2
\$\begingroup\$

Octave, 25 bytes

@(s)s(sum(triu(s'==s))<2)
\$\endgroup\$
2
\$\begingroup\$

Javascript (ES6), 47 bytes

a=>[...a].filter((b,c)=>a.indexOf(b)==c).join``

Test it here

Some code is added to have a better input and to write to the console the result.

d=document,g=d.getElementById.bind(d);g("s").onclick=e=>console.log((a=>[...a].filter((b,c)=>a.indexOf(b)==c).join``)(g("t").value))
<input id="t"><button id="s">Convert</button>

\$\endgroup\$
2
\$\begingroup\$

Ruby, 19 + 1 = 20 bytes

Uses the -p flag. Uses set operations like the GolfScript answer, which is totally not a built-in like uniq. (Performing set or on a list and an empty list purges the list of duplicates, just like calling and against a copy of itself.)

$_=($_.chars|[])*""
\$\endgroup\$
2
\$\begingroup\$

Jelly, 3 bytes

œ|/

Try it online!

Simply reduces by set union

Slightly more creative, but relies on "unique sieve" functions not being banned:

xŒQ

Try it online!

How it works

xŒQ - Main link. Takes a string S on the left
 ŒQ - Unique sieve; For each character in S, replace it with 1 if it hasn't occurred yet, else 0
x   - Repeat each character in S according to the corresponding value in the sieve
    - Implicitly print, mashing empty strings into the output
\$\endgroup\$
2
\$\begingroup\$

Pyth, 8 bytes

s.gxQk.|

Try it online!

  1. Bitwise Or the input
  2. Group the input by:
  3. It's index in the original input
  4. Join list and print.
\$\endgroup\$
1
\$\begingroup\$

Python 2, 79

def S(s):
 s=s[::-1]
 for c in s:s=s.replace(c,'',s.count(c)-1)
 return s[::-1]

It reverses the input string, cycles through it, replaces any extra characters with null ones and returns the reverse of that. The reverse is so the last characters are removed, not the first.

>>> S('''"I think it's dark and it looks like rain", you said''')
'"I think\'sdarloe,yu'
>>> S("3.1415926535897932384626433832795")
'3.14592687'
>>> S("Type unique chars!")
'Type uniqchars!'
\$\endgroup\$
1
  • \$\begingroup\$ 68 bytes \$\endgroup\$
    – nope
    Jun 10, 2020 at 11:48
1
\$\begingroup\$

MUMPS, 54 bytes

f(s) f i=1:1:$L(s) s c=$E(s,i) s:t'[c o=o_c,t=t_c
    q o

Not terribly exciting - it just keeps a running list of already-viewed characters and only appends to the output string if the current character isn't in that list.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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