Generate String

11/18/2019 - 2:20 PM

An exercise to generate a string.

Given 3 numbers (a,b,c), which describe the number of times to repeat 'a', 'b', and 'c', create a string that contains all necessary repeated characters without ever having more than 2 duplicate characters in a row.

Valid Examples: aabbcc abbaccb

Invalid Examples: aaabbccc cccaab

Lengths

Language        |   Char #  | Line #

Haskell         |     228   |     8

Ruby            |     271   |    11

Python          |     295   |    10

Scala           |     408   |    11

Java11Vavr      |     831   |    24

Java14          |    2242   |    56

Java13          |    2403   |    66

Java5           |    3437   |   127

Haskell.hs

import Data.List

noTriple (a,b,c) = a /= b && b /= c

noTriples xs = all noTriple $ zip3 xs (drop 1 xs) (drop 2 xs)

generateString a b c = find noTriples . permutations $ 
  replicate a 'a' ++ replicate b 'b' ++ replicate c 'c'

Ruby2.7.rb

def noTriple(t)
  t[0] != t[1] and t[1] != t[2]
end

def noTriples(xs)
  xs.zip(xs.drop(1), xs.drop(2)).filter { @1.none? { @1.nil? } }.all? { noTriple @1 }
end

def generateString(a, b, c)
  ('a' * a + 'b' * b + 'c' * c).chars.permutation.find { noTriples @1 }&.join
end

Python.py

from itertools import permutations

def noTriple(t):
    return not t[0] == t[1] == t[2]

def noTriples(xs):
    return all(noTriple(ys) for ys in zip(xs, xs[1:], xs[2:]))

def generateString(a, b, c):
    return [''.join(p) for p in permutations("a" * a + "b" * b + "c" * c) if noTriples(p)][0]

Scala.scala

def noTriple[T](t: Tuple3[T, T, T]) = 
  t._1 != t._2 && t._2 != t._3

def noTriples[T](xs: List[T]) = 
  zip3(xs, xs.drop(1), xs.drop(2)).toList.forall(noTriple(_))

def generateString(a: Int, b: Int, c: Int) = 
  ("a" * a + "b" * b + "c" * c).toList.permutations.find(noTriples(_)).map(_.mkString)

def zip3[T](xs: List[T], ys: List[T], zs: List[T]) = 
  xs zip ys zip zs map { case ((a,b), c) => (a,b,c) }

Java11Vavr.java

import io.vavr.Tuple3;
import io.vavr.collection.List;

public class Main {
    public static <T> boolean noTriple(Tuple3<T, T, T> t) {
        return !(t._1.equals(t._2) && t._2.equals(t._3));
    }

    public static <T> boolean noTriples(List<T> xs) {
        return zip3(xs, xs.drop(1), xs.drop(2)).forAll(Main::noTriple);
    }

    public static String generateString(int a, int b, int c) {
        return List.ofAll(("a".repeat(a) + "b".repeat(b) + "c".repeat(c)).toCharArray())
                .permutations()
                .filter(Main::noTriples)
                .map(xs -> xs.map(Object::toString))
                .get(0).mkString();
    }

    public static <T> List<Tuple3<T, T, T>> zip3(List<T> xs, List<T> ys, List<T> zs) {
        return xs.zip(ys).zip(zs).map(t -> new Tuple3<>(t._1._1, t._1._2, t._2));
    }
}

Java13.java

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Main {
    public static <T> boolean noTriple(Tuple3<T, T, T> t) {
        return !(t._1.equals(t._2) && t._2.equals(t._3));
    }

    public static <T> boolean noTriples(List<T> xs) {
        var ys = xs.subList(1, xs.size());
        var zs = xs.subList(1, ys.size());
        return zip3(xs, ys, zs).stream().allMatch(Main::noTriple);
    }

    public static Optional<String> generateString(int a, int b, int c) {
        var initialString = "a".repeat(a) + "b".repeat(b) + "c".repeat(c);
        var stringAsList = initialString.chars()
                .mapToObj(cc -> (char) cc)
                .collect(Collectors.toList());

        var resultAsList = permutations(stringAsList).stream()
                .filter(Main::noTriples)
                .findFirst();

        return resultAsList.map(list ->
                list.stream().map(Object::toString).collect(Collectors.joining()));
    }
    
    public static <T> List<List<T>> permutations(List<T> initial) {
        return switch(initial.size()) {
            case 0 -> List.of();
            case 1 -> List.of(initial);
            default -> permutations(initial.subList(1, initial.size())).stream()
                    .flatMap(perm ->
                        IntStream.rangeClosed(0, perm.size()).mapToObj(i -> {
                            var newPerm = new ArrayList<T>();
                            newPerm.addAll(perm.subList(0, i));
                            newPerm.addAll(initial.subList(0, 1));
                            newPerm.addAll(perm.subList(i, perm.size()));
                            return newPerm;
                        }))
                    .collect(Collectors.toList());
        };
    }

    public static <T> List<Tuple3<T, T, T>> zip3(List<T> xs, List<T> ys, List<T> zs) {
        var min = IntStream.of(xs.size(), ys.size(), zs.size()).min().getAsInt();
        return Stream.iterate(0, x -> x < min, x -> x + 1)
                .map(i -> new Tuple3<>(xs.get(i), ys.get(i), zs.get(i)))
                .collect(Collectors.toList());
    }

    public static class Tuple3<A, B, C> {
        public A _1;
        public B _2;
        public C _3;

        public Tuple3(A a, B b, C c) {
            _1 = a;
            _2 = b;
            _3 = c;
        }
    }
}

Java5.java

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static <T> boolean hasTriple(Tuple3<T, T, T> t) {
        return t._1.equals(t._2) && t._2.equals(t._3);
    }

    public static <T> boolean noTriples(List<T> xs) {
        List<T> ys = xs.subList(1, xs.size());
        List<T> zs = xs.subList(1, ys.size());

        List<Tuple3<T, T, T>> items = zip3(xs, ys, zs);

        for (Tuple3<T, T, T> item : items) {
            if (hasTriple(item)) {
                return false;
            }
        }
        return true;
    }

    public static String generateString(int a, int b, int c) {
        StringBuilder initialStringBuilder = new StringBuilder();

        for (int i = 0; i < a; i++) {
            initialStringBuilder.append('a');
        }

        for (int i = 0; i < b; i++) {
            initialStringBuilder.append('b');
        }

        for (int i = 0; i < c; i++) {
            initialStringBuilder.append('c');
        }

        String initialString = initialStringBuilder.toString();
        List<Character> initialCharacters = new ArrayList<Character>();

        for (int i = 0; i < initialString.length(); i++) {
            initialCharacters.add(initialString.charAt(i));
        }

        List<List<Character>> permutations = permutations(initialCharacters);
        List<Character> resultPermutation = null;

        for (List<Character> permutation : permutations) {
            if (noTriples(permutation)) {
                resultPermutation = permutation;
                break;
            }
        }

        if (resultPermutation == null) {
            return null;
        }

        StringBuilder resultStringBuilder = new StringBuilder();

        for (Character character : resultPermutation) {
            resultStringBuilder.append(character);
        }

        return resultStringBuilder.toString();
    }

    public static <T> List<List<T>> permutations(List<T> initial) {
        List<List<T>> result = new ArrayList<List<T>>();

        if (initial.size() == 1) {
            result.add(initial);
        }
        else if (initial.size() > 1) {
            List<T> x = initial.subList(0, 1);
            List<T> xs = initial.subList(1, initial.size());
            List<List<T>> perms = permutations(xs);

            for (List<T> perm : perms) {
                for (int i = 0; i <= perm.size(); i++) {
                    List<T> newPerm = new ArrayList<T>();
                    newPerm.addAll(perm.subList(0, i));
                    newPerm.addAll(x);
                    newPerm.addAll(perm.subList(i, perm.size()));
                    result.add(newPerm);
                }
            }
        }

        return result;
    }

    public static <T> List<Tuple3<T, T, T>> zip3(List<T> xs, List<T> ys, List<T> zs) {
        int min = xs.size();

        if (ys.size() < min) {
            min = ys.size();
        }

        if (zs.size() < min) {
            min = zs.size();
        }

        List<Tuple3<T, T, T>> result = new ArrayList<Tuple3<T, T, T>>();

        for (int i = 0; i < min; i++) {
            result.add(new Tuple3<T, T, T>(xs.get(i), ys.get(i), zs.get(i)));
        }

        return result;
    }

    public static class Tuple3<A, B, C> {
        public A _1;
        public B _2;
        public C _3;

        public Tuple3(A a, B b, C c) {
            _1 = a;
            _2 = b;
            _3 = c;
        }
    }
}

Java14.java

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Main {
    public static <T> boolean noTriple(Tuple3<T, T, T> t) {
        return !(t._1.equals(t._2) && t._2.equals(t._3));
    }

    public static <T> boolean noTriples(List<T> xs) {
        var ys = xs.subList(1, xs.size());
        var zs = xs.subList(1, ys.size());
        return zip3(xs, ys, zs).stream().allMatch(Main::noTriple);
    }

    public static Optional<String> generateString(int a, int b, int c) {
        var initialString = "a".repeat(a) + "b".repeat(b) + "c".repeat(c);
        var stringAsList = initialString.chars()
                .mapToObj(cc -> (char) cc)
                .collect(Collectors.toList());

        var resultAsList = permutations(stringAsList).stream()
                .filter(Main::noTriples)
                .findFirst();

        return resultAsList.map(list ->
                list.stream().map(Object::toString).collect(Collectors.joining()));
    }
    
    public static <T> List<List<T>> permutations(List<T> initial) {
        return switch(initial.size()) {
            case 0 -> List.of();
            case 1 -> List.of(initial);
            default -> permutations(initial.subList(1, initial.size())).stream()
                    .flatMap(perm ->
                        IntStream.rangeClosed(0, perm.size()).mapToObj(i -> {
                            var newPerm = new ArrayList<T>();
                            newPerm.addAll(perm.subList(0, i));
                            newPerm.addAll(initial.subList(0, 1));
                            newPerm.addAll(perm.subList(i, perm.size()));
                            return newPerm;
                        }))
                    .collect(Collectors.toList());
        };
    }

    public static <T> List<Tuple3<T, T, T>> zip3(List<T> xs, List<T> ys, List<T> zs) {
        var min = IntStream.of(xs.size(), ys.size(), zs.size()).min().getAsInt();
        return Stream.iterate(0, x -> x < min, x -> x + 1)
                .map(i -> new Tuple3<>(xs.get(i), ys.get(i), zs.get(i)))
                .collect(Collectors.toList());
    }

    public static record Tuple3<A, B, C>(A _1, B _2, C _ 3)
}

Cacher is the code snippet organizer for pro developers

We empower you and your team to get more done, faster

Generate String

Lengths