How to resolve the algorithm Determine if a string has all unique characters step by step in the JavaScript programming language
How to resolve the algorithm Determine if a string has all unique characters step by step in the JavaScript programming language
Table of Contents
Problem Statement
Given a character string (which may be empty, or have a length of zero characters):
Use (at least) these five test values (strings):
Show all output here on this page.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Determine if a string has all unique characters step by step in the JavaScript programming language
Implementation 1
This implementation uses a more functional approach, employing higher-order functions and data structures from the Elm Architecture (Elmish) library. It defines a dedicated duplicatedCharIndices function to find the first instance of a duplicate character in a string.
Here's an explanation of the code:
-
duplicatedCharIndices: This function takes a stringsand returns aMaybeof a tuple containing the duplicate character and a list of its indices. It first usesgroupByto group characters based on their value, then filters out groups with a length less than 2 to focus on duplicates. The function then usessortOnto sort the list of groups by the index of the first occurrence of each character and returns the first group as the result. -
JustandNothing: These are constructors for theMaybedata type, representing the presence or absence of a value, respectively. -
Tuple: This function creates a tuple (pair) from two arguments. -
chars: This function splits a string into a list of characters. -
compose: This function composes a series of functions into a single function. It's used for chaining operations succinctly. -
enumFrom: This generates an infinite list of sequential integers starting from a given number. It's used for indexing the characters in the string. -
eq: This function performs equality comparison between two values. -
fanArrow: This function creates a function that takes two functionsfandgand returns a function that appliesfandgto an input value and returns a tuple of their results. -
filter: This function filters a list based on a predicate function. -
fst: This function gets the first element of a tuple. -
fTable: This function creates a table-like string representation of a list of values. It takes a heading, two display functions, a function to apply to each value, and a list of values. -
groupBy: This function groups elements of a list based on a key function. In this case, it's used to group characters in a string by their value. -
length: This function computes the length of a list or string. -
map: This function applies a function to each element of a list. -
maybe: This function takes a default value and a function that operates on aMaybevalue. It returns the default value if theMaybevalue isNothingor applies the function to theJustvalue. -
on: This function creates a new function that applies the second function to the results of applying the first function to its arguments. -
ord: This function converts a character to its Unicode code point. -
showHex: This function converts a number to its hexadecimal representation. -
snd: This function gets the second element of a tuple. -
sortOn: This function sorts a list by a key function, but it uses an optimization to only evaluate the key function once for each element. -
take: This function returns the firstnelements of a list or string. -
uncurry: This function converts a function that takes multiple arguments into a function that takes a single tuple argument. -
zip: This function creates a list of tuples from two lists. -
zipWith: This function applies a function to each pair of elements from two lists.
Implementation 2
This implementation takes a different approach, using more imperative and object-oriented programming principles. It defines a duplicatedCharIndices function that returns the duplicate character and a list of its indices within a string.
-
duplicatedCharIndices: This function takes a stringsand returns aMaybeof a tuple containing the duplicate character and a list of its indices. It uses an object to count character occurrences and then finds the first character that appears more than once. -
Just,Nothing: Same as in the first implementation. -
Tuple: Same as in the first implementation. -
chars: Same as in the first implementation. -
comparing: This function creates a comparison function based on another function. It's used for sorting in theminimumByMayfunction. -
compose: Same as in the first implementation. -
enumFrom: Same as in the first implementation. -
filter: Same as in the first implementation. -
fst: Same as in the first implementation. -
fTable: Same as in the first implementation. -
length: Same as in the first implementation. -
maybe: Same as in the first implementation. -
minimumByMay: This function finds the smallest element of a list based on a comparison function, but returnsNothingif the list is empty. -
ord: Same as in the first implementation. -
showHex: Same as in the first implementation. -
snd: Same as in the first implementation. -
take: Same as in the first implementation. -
zipWith: Same as in the first implementation.
Main Function
The main function is responsible for testing both implementations of the duplicatedCharIndices function. It applies the function to a list of sample strings and prints the results in a tabular format using the fTable function.
Overall Comparison
Both implementations achieve the same goal of finding the first instance of a duplicate character in a string, but they use different approaches. The first implementation is more functional and emphasizes immutability and referential transparency. The second implementation is more imperative and object-oriented, focusing on object manipulation.
The choice of which implementation to use depends on the preferences and requirements of the developer. The functional implementation may be preferred in situations where immutability and purity are important, while the imperative implementation may be more straightforward and convenient for some use cases.
Source code in the javascript programming language
(() => {
'use strict';
// duplicatedCharIndices :: String -> Maybe (Char, [Int])
const duplicatedCharIndices = s => {
const
duplicates = filter(g => 1 < g.length)(
groupBy(on(eq)(snd))(
sortOn(snd)(
zip(enumFrom(0))(chars(s))
)
)
);
return 0 < duplicates.length ? Just(
fanArrow(compose(snd, fst))(map(fst))(
sortOn(compose(fst, fst))(
duplicates
)[0]
)
) : Nothing();
};
// ------------------------TEST------------------------
const main = () =>
console.log(
fTable('First duplicated character, if any:')(
s => `'${s}' (${s.length})`
)(maybe('None')(tpl => {
const [c, ixs] = Array.from(tpl);
return `'${c}' (0x${showHex(ord(c))}) at ${ixs.join(', ')}`
}))(duplicatedCharIndices)([
"", ".", "abcABC", "XYZ ZYX",
"1234567890ABCDEFGHIJKLMN0PQRSTUVWXYZ"
])
);
// -----------------GENERIC FUNCTIONS------------------
// Just :: a -> Maybe a
const Just = x => ({
type: 'Maybe',
Nothing: false,
Just: x
});
// Nothing :: Maybe a
const Nothing = () => ({
type: 'Maybe',
Nothing: true,
});
// Tuple (,) :: a -> b -> (a, b)
const Tuple = a => b => ({
type: 'Tuple',
'0': a,
'1': b,
length: 2
});
// chars :: String -> [Char]
const chars = s => s.split('');
// compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
const compose = (...fs) =>
x => fs.reduceRight((a, f) => f(a), x);
// enumFrom :: Enum a => a -> [a]
function* enumFrom(x) {
let v = x;
while (true) {
yield v;
v = 1 + v;
}
}
// eq (==) :: Eq a => a -> a -> Bool
const eq = a => b => a === b;
// fanArrow (&&&) :: (a -> b) -> (a -> c) -> (a -> (b, c))
const fanArrow = f =>
// Compose a function from a simple value to a tuple of
// the separate outputs of two different functions.
g => x => Tuple(f(x))(g(x));
// filter :: (a -> Bool) -> [a] -> [a]
const filter = f => xs => xs.filter(f);
// fst :: (a, b) -> a
const fst = tpl => tpl[0];
// fTable :: String -> (a -> String) -> (b -> String)
// -> (a -> b) -> [a] -> String
const fTable = s => xShow => fxShow => f => xs => {
// Heading -> x display function ->
// fx display function ->
// f -> values -> tabular string
const
ys = xs.map(xShow),
w = Math.max(...ys.map(length));
return s + '\n' + zipWith(
a => b => a.padStart(w, ' ') + ' -> ' + b
)(ys)(
xs.map(x => fxShow(f(x)))
).join('\n');
};
// groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
const groupBy = fEq =>
// Typical usage: groupBy(on(eq)(f), xs)
xs => 0 < xs.length ? (() => {
const
tpl = xs.slice(1).reduce(
(gw, x) => {
const
gps = gw[0],
wkg = gw[1];
return fEq(wkg[0])(x) ? (
Tuple(gps)(wkg.concat([x]))
) : Tuple(gps.concat([wkg]))([x]);
},
Tuple([])([xs[0]])
);
return tpl[0].concat([tpl[1]])
})() : [];
// length :: [a] -> Int
const length = xs =>
// Returns Infinity over objects without finite length.
// This enables zip and zipWith to choose the shorter
// argument when one is non-finite, like cycle, repeat etc
(Array.isArray(xs) || 'string' === typeof xs) ? (
xs.length
) : Infinity;
// map :: (a -> b) -> [a] -> [b]
const map = f => xs =>
(Array.isArray(xs) ? (
xs
) : xs.split('')).map(f);
// maybe :: b -> (a -> b) -> Maybe a -> b
const maybe = v =>
// Default value (v) if m is Nothing, or f(m.Just)
f => m => m.Nothing ? v : f(m.Just);
// on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
const on = f =>
g => a => b => f(g(a))(g(b));
// ord :: Char -> Int
const ord = c => c.codePointAt(0);
// showHex :: Int -> String
const showHex = n =>
n.toString(16);
// snd :: (a, b) -> b
const snd = tpl => tpl[1];
// sortOn :: Ord b => (a -> b) -> [a] -> [a]
const sortOn = f =>
// Equivalent to sortBy(comparing(f)), but with f(x)
// evaluated only once for each x in xs.
// ('Schwartzian' decorate-sort-undecorate).
xs => xs.map(
x => [f(x), x]
).sort(
(a, b) => a[0] < b[0] ? -1 : (a[0] > b[0] ? 1 : 0)
).map(x => x[1]);
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = n => xs =>
'GeneratorFunction' !== xs.constructor.constructor.name ? (
xs.slice(0, n)
) : [].concat.apply([], Array.from({
length: n
}, () => {
const x = xs.next();
return x.done ? [] : [x.value];
}));
// uncurry :: (a -> b -> c) -> ((a, b) -> c)
const uncurry = f =>
(x, y) => f(x)(y)
// zip :: [a] -> [b] -> [(a, b)]
const zip = xs => ys => {
const
lng = Math.min(length(xs), length(ys)),
vs = take(lng)(ys);
return take(lng)(xs)
.map((x, i) => Tuple(x)(vs[i]));
};
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = f =>
xs => ys => {
const
lng = Math.min(length(xs), length(ys)),
vs = take(lng)(ys);
return take(lng)(xs)
.map((x, i) => f(x)(vs[i]));
};
// MAIN ---
return main();
})();
(() => {
'use strict';
// duplicatedCharIndices :: String -> Maybe (Char, [Int])
const duplicatedCharIndices = s =>
minimumByMay(
comparing(compose(fst, snd))
)(filter(x => 1 < x[1].length)(
Object.entries(
s.split('').reduce(
(a, c, i) => Object.assign(a, {
[c]: (a[c] || []).concat(i)
}), {}
)
)
));
// ------------------------TEST------------------------
const main = () =>
console.log(
fTable('First duplicated character, if any:')(
s => `'${s}' (${s.length })`
)(maybe('None')(tpl => {
const [c, ixs] = Array.from(tpl);
return `'${c}' (0x${showHex(ord(c))}) at ${ixs.join(', ')}`
}))(duplicatedCharIndices)([
"", ".", "abcABC", "XYZ ZYX",
"1234567890ABCDEFGHIJKLMN0PQRSTUVWXYZ"
])
);
// -----------------GENERIC FUNCTIONS------------------
// Just :: a -> Maybe a
const Just = x => ({
type: 'Maybe',
Nothing: false,
Just: x
});
// Nothing :: Maybe a
const Nothing = () => ({
type: 'Maybe',
Nothing: true,
});
// Tuple (,) :: a -> b -> (a, b)
const Tuple = a => b => ({
type: 'Tuple',
'0': a,
'1': b,
length: 2
});
// chars :: String -> [Char]
const chars = s => s.split('');
// comparing :: (a -> b) -> (a -> a -> Ordering)
const comparing = f =>
x => y => {
const
a = f(x),
b = f(y);
return a < b ? -1 : (a > b ? 1 : 0);
};
// compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
const compose = (...fs) =>
x => fs.reduceRight((a, f) => f(a), x);
// enumFrom :: Enum a => a -> [a]
function* enumFrom(x) {
let v = x;
while (true) {
yield v;
v = 1 + v;
}
}
// filter :: (a -> Bool) -> [a] -> [a]
const filter = f => xs => xs.filter(f);
// fst :: (a, b) -> a
const fst = tpl => tpl[0];
// fTable :: String -> (a -> String) -> (b -> String)
// -> (a -> b) -> [a] -> String
const fTable = s => xShow => fxShow => f => xs => {
// Heading -> x display function ->
// fx display function ->
// f -> values -> tabular string
const
ys = xs.map(xShow),
w = Math.max(...ys.map(length));
return s + '\n' + zipWith(
a => b => a.padStart(w, ' ') + ' -> ' + b
)(ys)(
xs.map(x => fxShow(f(x)))
).join('\n');
};
// length :: [a] -> Int
const length = xs =>
// Returns Infinity over objects without finite length.
// This enables zip and zipWith to choose the shorter
// argument when one is non-finite, like cycle, repeat etc
(Array.isArray(xs) || 'string' === typeof xs) ? (
xs.length
) : Infinity;
// maybe :: b -> (a -> b) -> Maybe a -> b
const maybe = v =>
// Default value (v) if m is Nothing, or f(m.Just)
f => m => m.Nothing ? v : f(m.Just);
// minimumByMay :: (a -> a -> Ordering) -> [a] -> Maybe a
const minimumByMay = f =>
xs => xs.reduce((a, x) =>
a.Nothing ? Just(x) : (
f(x)(a.Just) < 0 ? Just(x) : a
), Nothing());
// ord :: Char -> Int
const ord = c => c.codePointAt(0);
// showHex :: Int -> String
const showHex = n =>
n.toString(16);
// snd :: (a, b) -> b
const snd = tpl =>
tpl[1];
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = n =>
xs => 'GeneratorFunction' !== xs.constructor.constructor.name ? (
xs.slice(0, n)
) : [].concat.apply([], Array.from({
length: n
}, () => {
const x = xs.next();
return x.done ? [] : [x.value];
}));
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = f =>
xs => ys => {
const
lng = Math.min(length(xs), length(ys)),
vs = take(lng)(ys);
return take(lng)(xs)
.map((x, i) => f(x)(vs[i]));
};
// MAIN ---
return main();
})();
You may also check:How to resolve the algorithm Singleton step by step in the Go programming language
You may also check:How to resolve the algorithm Plot coordinate pairs step by step in the jq programming language
You may also check:How to resolve the algorithm Hailstone sequence step by step in the Euphoria programming language
You may also check:How to resolve the algorithm Tarjan step by step in the Go programming language
You may also check:How to resolve the algorithm Number names step by step in the Python programming language