loading...

Daily Challenge #259 - Duplicate Encoder

thepracticaldev profile image dev.to staff ・1 min read

The goal of this exercise is to convert a string to a new string where each character in the new string is "(" if that character appears only once in the original string, or ")" if that character appears more than once in the original string. Ignore capitalization when determining if a character is a duplicate.

Examples
"Success" => ")())())"
"(( @" => "))(("

Tests
"din"
"recede"

Good luck!


This challenge comes from obnounce on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Discussion

pic
Editor guide
Collapse
nam288 profile image
Nam H. Le

Javascript solution:

const uniq = (str, chr) => str.indexOf(chr) === str.lastIndexOf(chr);

const encodeDuplicate = str => [...str].map(chr => uniq(str.toLowerCase(), chr)? "(" :")").join``; 
Collapse
thomasledoux1 profile image
Thomas Ledoux

Neat!
What is this syntax at the end?

join``

I always use

.join('').

Collapse
nam288 profile image
Nam H. Le

That is Tagged template literals, to save 2 character :D

Thread Thread
jsn1nj4 profile image
JSn1nj4‍‍👨‍💻

I forgot all about that syntax. I've probably only used it a few times.

Collapse
aminnairi profile image
Amin

Go

$ mkdir -p $GOPATH/src/encoder
$ cd $GOPATH/src/encoder
$ touch encoder.go
// Set of utilities to encode a string into different formats.
package encoder

import (
    "unicode"
    "strings"
)

// Encode a given string into a format comprised of left and right parens. If one character is present multiple times in the string, the left parens will be used to encode this character, otherwise, the right parens will be used.
func EncodeDuplicateParens(input string) string {
    encoded := strings.Builder{}
    occurrences := make(map[rune]int)

    for _, character := range input {
        occurrences[unicode.ToLower(character)]++
    }

    for _, character := range input {
        if occurrences[unicode.ToLower(character)] > 1 {
            encoded.WriteRune(')')
        } else {
            encoded.WriteRune('(')
        }
    }

    return encoded.String()
}
$ touch encoder_test.go
package encoder_test

import (
    "encoder"
    "fmt"
    "testing"
)

func TestWithMultipleStrings(t *testing.T) {
    valuesExpectations := map[string]string{
        "(( @": "))((",
        "Success": ")())())",
        "din": "(((",
        "recede": "()()()",
    }

    for value, expectation := range valuesExpectations {
        result := encoder.EncodeDuplicateParens(value)

        if expectation != result {
            t.Errorf("Expected encode.EncodeDuplicateParens(%q) to equal %q but got %q.", value, expectation, result)
        }
    }
}

func BenchmarkEncodeDuplicateParens(b *testing.B) {
    for index := 0; index < b.N; index++ {
        encoder.EncodeDuplicateParens("Success")
    }
}

func ExampleEncodeDuplicateParens() {
    values := []string{
        "(( @",
        "Success",
        "din",
        "recede",
    }

    for _, value := range values {
        fmt.Println(encoder.EncodeDuplicateParens(value));
    }

    // Output: ))((
    // )())())
    // (((
    // ()()()
}

$ go test -cover -bench .
goos: linux
goarch: amd64
pkg: encoder
BenchmarkEncodeDuplicateParens-4         4961448               256 ns/op
PASS
coverage: 100.0% of statements
ok      encoder 1.516s
Collapse
jvanbruegge profile image
Jan van Brügge

My Haskell solution:

import Data.Char (toLower)

encode str = (\n -> if n > 1 then ')' else '(' )
        <$> fmap (\c -> length $ filter ((==) c) str') str'
    where str' = fmap toLower str
Collapse
rafaacioly profile image
Rafael Acioly

Python solution 🐍

from collections import Counter

ONCE, MANY = '(', ')'


def parse(text: str) -> str:
  normalized_text = text.lower()
  letter_counter = Counter(normalized_text)

  result: str = normalized_text
  for letter in normalized_text:
    result = result.replace(
      letter,
      MANY if letter_counter.get(letter) > 1 else ONCE
    )

  return result
Collapse
peter279k profile image
peter279k

Here is the simple approach with nested for loops with PHP:

function duplicate_encode($word){
  $index = 0;
  $word = mb_strtolower($word);
  $result = $word;
  for ($index=0; $index<mb_strlen($word); $index++) {
    $isDuplicated = false;
    for ($secondIndex=$index+1; $secondIndex<mb_strlen($word); $secondIndex++) {
      if ($word[$index] === $word[$secondIndex]) {
        $result[$index] = ")";
        $result[$secondIndex] = ")";
        $isDuplicated = true;   
      }
    }

    if ($isDuplicated === false && $result[$index] === $word[$index]) {
      $result[$index] = "(";
    }
  }

  return $result;
}
Collapse
gnunicorn profile image
Benjamin Kampmann

In Rust – playground link (with tests)

pub fn dub_enc(inp: String) -> String {
    let lowered = inp.to_lowercase();
    lowered
        .chars()
        .map(|c| {
            let mut finder = lowered.chars().filter(|r| *r == c);
            finder.next(); // exists
            if finder.next().is_some() { // found at least once more
                ")"
            } else {
                "("
            }
        })
        .collect()
} 
Collapse
lexlohr profile image
Alex Lohr

Why not use std::str::matches to iterate over the same chars?

Collapse
gnunicorn profile image
Benjamin Kampmann

I suppose that is a valid alternative. Just not the first thing that came to mind ...

Thread Thread
lexlohr profile image
Alex Lohr

I just love how Rust has a helpful method for about everything in its std/core libs.

Collapse
jpantunes profile image
JP Antunes

A simple (and somewhat slow) JS solution:

const encodeDuplicate = str => {
    //make a frequency map
    const freqMap = [...str.toLowerCase()].reduce((acc, val) => {
        acc[val] = acc[val] + 1 || 1;
        return acc;
    }, {});
    //return the mapped str 
    return [...str.toLowerCase()]
            .map(e => freqMap[e] == 1 ? '(' : ')')
            .join('');
}
Collapse
miketalbot profile image
Mike Talbot

Not that slow :) Better than anything that searched/scanned or did an indexOf for sure! You know I like that || 1 as well, I always do (acc[val] || 0) + 1 - but that is much neater. Borrowing that.

Collapse
nam288 profile image
Nam H. Le

Same to me || 0

Collapse
jurerotar profile image
Jure Rotar

Fast and simple PHP solution :)

function replace(string $string): string {
    $string = strtolower($string);
    $values = array_count_values(str_split($string));
    foreach($values as $index => &$key) {
        $values[$index] = $key > 1 ? ')' : '(';
    }
    return strtr($string, $values);
}
Collapse
lexlohr profile image
Alex Lohr

Rust 🦀🦀🦀🦀solution:🦀🦀🦀🦀🦀 🦀

fn encode_duplicate_characters(text: &str) -> String {
    let text = text.to_lowercase();
    text.chars().map(|c| if text.matches(c).count() == 1 { '(' } else { ')' }).collect()
}
Collapse
vidit1999 profile image
Vidit Sarkar

Here is a C++ solution,

string encodeDuplicate(string s){
    // stores the count of corresponding character (lower cased) in s
    unordered_map<char, int> charCount;

    for(char c : s) charCount[tolower(c)]++;

    string ans = "";

    for(char c : s) ans += (charCount[tolower(c)] > 1)? ')' : '(';

    return ans;
}
Collapse
elcio profile image
Elcio Ferreira

A magical Python solution:

def encode(text):
    return ''.join((')' if text.lower().count(c.lower()) > 1 else '(' for c in text))

A boring Python solution:

def encode(text):
    encoded = ''
    for char in text:
        encoded += replace_char(char, text)
    return encoded

def replace_char(char, text):
    if text.lower().count(char.lower()) > 1:
        return ')' 
    return '('

Boring is good. I usually avoid oneliners and magical solutions.

A more "production ready" version of the above:

'''A "duplicate encoder"s.

Based on https://dev.to/thepracticaldev/daily-challenge-259-duplicate-encoder-2e8l

When running on command line, encodes standard input.

You can also use the following args:

-t : Executes automated testing
-h : Shows this help'''

def encode(text):
    '''Convert a string to a new string where each character in the new string
    is "(" if that character appears only once in the original string, or ")"
    if that character appears more than once in the original string.
    Examples:
    >>> encode('Success')
    ')())())'
    >>> encode('(( @')
    '))(('
    >>> encode('din')
    '((('
    >>> encode('recede')
    '()()()'
    '''
    encoded = ''
    for char in text:
        encoded += replace_char(char, text)
    return encoded

def replace_char(char, text):
    '''Returns ')' if char appears more than once in text. Otherwise, 
    returns '('. Case insensitive. Examples:
    >>> replace_char('a', 'banana')
    ')'
    >>> replace_char('B', 'banana')
    '('
    '''
    if text.lower().count(char.lower()) > 1:
        return ')'
    return '('

if __name__ == '__main__':
    import sys
    if sys.argv[-1] == '-t':
        import doctest
        doctest.testmod()
    elif sys.argv[-1] == '-h':
        import pydoc
        print(pydoc.getdoc(sys.modules[__name__]))
    else:
        print(encode(sys.stdin.read()))
Collapse
arthelon profile image
Daniel Hsing

TypeScript:

function isUnique(char: string, fullString: string): boolean {
  return fullString.indexOf(char) === fullString.lastIndexOf(char);
}

function duplicateEncoder(input: string): string {
  const lowercase = input.toLowerCase();
  return lowercase
    .split("")
    .map((char) => (isUnique(char, input) ? "(" : ")"))
    .join("");
}

Collapse
jingxue profile image
Jing Xue

Python:



from collections import Counter


def duplicate_encoder(s: str) -> str:
    all_lower = s.lower()
    counter = Counter(all_lower)
    return ''.join([')' if counter.get(c) > 1 else '(' for c in all_lower])
Collapse
patricktingen profile image
Patrick Tingen
/* Progress 4GL Daily Challenge #259
*/
FUNCTION dupDecode RETURNS CHARACTER (pcString AS CHARACTER):
  DEFINE VARIABLE i AS INTEGER NO-UNDO.
  DO i = 1 TO LENGTH(pcString):
    pcString = REPLACE( pcString
                      , SUBSTRING(pcString,i,1)
                      , STRING(NUM-ENTRIES(pcString,SUBSTRING(pcString,i,1)) = 2,'(/)')
                      ).
  END.
  RETURN pcString.
END FUNCTION.

MESSAGE dupDecode('Success')
  VIEW-AS ALERT-BOX INFORMATION BUTTONS OK.
Collapse
citizen428 profile image
Michael Kohl

Since I'm watching NimConf 2020 in the background, a Nim solution:

import strutils, tables

func encode*(s: string): string =
  let lower = s.toLowerAscii
  let counts = lower.toCountTable

  for c in lower:
    result.add(if counts[c] == 1: '(' else: ')')
Collapse
ilhotiger profile image
Ilho Song

Erlang solution, though not sure this would be the most efficient. I am still learning the language :)

process(Input) ->
    ResultMap = lists:foldl(
        fun(Char, Map) -> 
            case maps:is_key(Char, Map) of
                true -> maps:put(Char, ")", Map);
                false -> maps:put(Char, "(", Map)
            end
        end, 
        maps:new(), 
        string:lowercase(Input)),
    lists:foldl(
        fun(Char, Acc) -> lists:append(Acc, maps:get(Char, ResultMap)) end,
        "",
        string:lowercase(Input)
    ).
Collapse
jessekphillips profile image
Jesse Phillips

I'm a little late, but rather than solving the problem I instead took the different approaches people posted, wrote them in D (dlang.org) and did some basic performance ploting.

GitHub logo JesseKPhillips / devto-challenge259-dupencoder

An attempt to capture performance with different implementation approaches for a Challenge

Dev.to has a daily challenge and I happened upon the Duplicate Encoder #259 for 2020

I didn't really want to solve the challenge per se, so instead I took the top comments for implementation and wrote them in D Lang.

For clarity these are all implemented in D and do not reflect the language performance that the implementation is based on.

Image of Yaktocat

The "Haskel" implementation utilizes a range based map/filter approach to detecting duplicates.

The "PHP" implementation utilizes a nested loop apporach to intentify that the character occurs again.

The "Pointer" implementation was just something I wanted to try. It duplicates the array so it is mutable after which point it does not loop over the arry twice and instead stores pointers to the location of the same character. It takes quite a bit for this approach to see any performance gain.




I might do more work on this and write up my own post about what I did. Keep in mind that I use the terms 'php' and 'haskel' not to indicate the performance of those languages... it was just the language utilized for the approach taken. All timings are from D.

Collapse
boris profile image
Boris Quiroz

🐍

def duplicate(string):
    result = ""
    for s in string.lower():
        if string.count(s) > 1:
            result += ")"
        else:
            result += "("

    print(result)
Collapse
quoll profile image
Paula Gearon

Clojure

(defn duplicate-encode
  [s]
  (let [s (clojure.string/lower-case s)
        f (frequencies s)]
    (apply str (map #(if (= 1 (f %)) \( \)) s))))
Collapse
moufeed_m profile image
Mofid Jobakji
const encoder = str =>
  str
    .toLowerCase()
    .replace(/\W|\w/g, (chr) =>
      str.indexOf(chr) === str.lastIndexOf(chr) ? '(' : ')'
    );
Collapse
saswat01 profile image
saswat

Here is a simple python code:
alt text