Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

The user was asking for an algorithm in this question on StackOverflow, stating the following:

Can you please provide the logic for below:

Input:  ABC
Output: A B C AB AC BC ABC

Lets help the user with a "useful" implementation in any language you prefer. And don't forget that this is a question, so we are looking for really useless but creative solutions.

The answer with the most upvotes by 10th of March 2014 wins.

share|improve this question
    
@CloseVoters Could you please give me an idea what is "Too broad" in this question? –  VisioN Feb 27 at 13:29
    
I don't know; me and one other person voted to leave it open, so I doubt it will get closed. –  The Guy with The Hat Feb 27 at 13:30
    
You want us to speculate about a general rule? –  David Carraher Feb 27 at 15:25
    
@VisionN Code-trolling questions always get some downvotes and close-votes just because it is code-trolling and some people don't like this. So, don't worry. –  Victor Feb 27 at 16:20
    
@Victor Ah, that makes some sense. Thanks for clarifying :) –  VisioN Feb 27 at 16:44
add comment

15 Answers

up vote 40 down vote accepted

Can you please provide the logic for below:

Input:  ABC
Output: A B C AB AC BC ABC

So you want a logic. I guess that you are talking about logic gates:

Logic gates

share|improve this answer
5  
This one rallies! LOL'd hard, well done :P +1 for not being the classic code answer. –  Vereos Feb 27 at 17:08
    
One of the most creative answers I encountered here:D –  totymedli Feb 28 at 17:39
    
I'd argue that the OR at the end is superfluous. That is, we want 7 outputs, not 1. :) –  Philippe Signoret Mar 1 at 1:07
4  
@PhilippeSignoret But he asked for "output" not "outputs". :) –  Victor Mar 1 at 3:14
1  
This answer is the reason I vouched for code-trolling. –  shiona Mar 1 at 18:01
add comment

Java

There are a lot of answers given here, but one thing they all lack is speed. There are 2n-1 combinations, so you want to make it as fast as you can. With a few simple optimizations, you can get the correct output in just 8 milliseconds!

The keys to this approach are three-fold:

  • Use LinkedLists to store your characters! Java Strings are slow, so using a better data structure works wonders. We'll be adding characters one by one, so you want something with an O(1) insert time.
  • Use a bitmask to shift through all the combinations. Rather than iterating over characters, you can use bits to track your combinations. Bit manipulation is fast, so this is important for speed gains.
  • Most importantly, keep your data sorted for faster searching and comparison checks. I cannot stress this enough. Searching through sorted data is much faster, so a simple Collection.sort() here and there can do wonders for your run time. The builtin Java sort uses a modified merge-sort, and it doesn't get much better than that, so we won't be building our own.

That might sound intimidating, but don't worry. I broke this up into two classes for readability. First, the Combination class:

import java.util.Collections;
import java.util.LinkedList;

public class Combination implements Comparable<Combination>{
    LinkedList<Character> data;

    public Combination(){
        data = new LinkedList<Character>();
    }

    public Combination(String from){
        Character[] characters = new Character[from.length()];
        for(int index = 0; index < from.length(); index++){
            characters[index] = from.charAt(index);
        }
        initialize(characters);
    }

    public Combination(Character[] from){
        initialize(from);
    }

    public void initialize(Character[] from){
        data = new LinkedList<Character>();
        for(int index = from.length - 1; index >= 0; index--){
            data.push(from[index]);
        }       
    }

    @Override
    public String toString(){
        String str = "";
        for(int index = 0; index < getNumberOfCharacters(); index++){
            str += getCharacterAt(index).toString();
        }
        return str;
    }

    public boolean contains(Character character){
        for(int index = 0; index < getNumberOfCharacters(); index++){
            if(character.equals(getCharacterAt(index)))
                return true;
        }
        return false;

    }

    public void addCharacter(Character character){
        data.add(character);
        Collections.sort(data);
    }

    public int getNumberOfCharacters(){
        int count = 0;
        for(int index = 0; index < data.size(); index++){
            LinkedList<Character> temp = new LinkedList<Character>();
            Character polled;
            while((polled = data.poll()) != null){
                temp.push(polled);
                count++;
            }
            while((polled = temp.poll()) != null){
                data.push(polled);
            }       
        }
        return count / data.size();
    }

    public Character getCharacterAt(int index){
        if(index < 0)
            return null;
        if(index >= getNumberOfCharacters())
            return null;
        Character found = null;
        for(int idx = 0; idx < data.size(); idx++){
            LinkedList<Character> temp = new LinkedList<Character>();
            for(int innerIndex = 0; innerIndex < index; innerIndex++){
                temp.push(data.poll());
            }
            found = data.peek(); 
            for(int innerIndex = 0; innerIndex < index; innerIndex++){
                data.push(temp.poll());
            }
        }
        return found;
    }

    public boolean equals(Combination otherCombination){
        boolean equal = true;
        for(int index = 0; index < getNumberOfCharacters(); index++){
            if(!getCharacterAt(index).equals(otherCombination.getCharacterAt(index)))
                equal = false;
        }
        return equal;
    }

    @Override
    public int compareTo(Combination otherCombination) {
        Collections.sort(data);
        Collections.sort(otherCombination.data);
        if(getNumberOfCharacters() - otherCombination.getNumberOfCharacters() != 0)
            return getNumberOfCharacters() - otherCombination.getNumberOfCharacters();
        for(int index = 0; index < getNumberOfCharacters() && index < otherCombination.getNumberOfCharacters();index++){
            if(getCharacterAt(index).compareTo(otherCombination.getCharacterAt(index)) != 0)
                return getCharacterAt(index).compareTo(otherCombination.getCharacterAt(index));
        }
        return 0;
    }   
}

Notice that I make sure each combination is sorted after adding an element and prior to comparison. You don't want to slow down your algorithm by having unsorted data, and like I already said, modern sort() routines are fast.

The custom compareTo() function makes sure that the sort works correctly. If you just did an alphabetical sort on them, you would get ABC before AC, and that's clearly not the order you want. If you sort by length first, you get the proper order.

The rest of that class is pretty basic. If you need any additional explanation, feel free to ask.

On to the other class, CombinationGenerator. This is where the bitmask magic happens:

import java.util.Collections;
import java.util.LinkedList;

public class CombinationGenerator {
    LinkedList<Combination> combinations;
    Combination input;

    CombinationGenerator(String in){
        combinations = new LinkedList<Combination>();
        input = new Combination(in);
    }

    public void generate(){
        Combination combination = null;
        while((combination = getNextCombination(combination)) != null){
            combinations.push(combination);
            Collections.sort(combinations);
        }
    }

    public void print(){
        System.out.println(toString());
    }

    @Override
    public String toString(){
        String str = "";
        for(int index = 0; index < combinations.size(); index++){
            str += combinations.get(index).toString();
            str += " ";
        }
        return str;
    }

    private Combination getNextCombination(Combination lastCombination){        
        if(lastCombination == null){
            return new Combination(input.getCharacterAt(input.getNumberOfCharacters()-1).toString());
        }
        if(lastCombination.getNumberOfCharacters() == input.getNumberOfCharacters())
            return null;

        Combination current = lastCombination;
        boolean[] tmpBitmask;
        while(current.equals(lastCombination)){
            tmpBitmask = getBitmaskFromCombination(current);
            tmpBitmask = addOneToBitmask(tmpBitmask);
            current = generateCombination(tmpBitmask);
        }

        return current;
    }

    private boolean[] getBitmaskFromCombination(Combination combination){
        boolean[] mask = new boolean[input.getNumberOfCharacters()];
        for(int index = 0; index < input.getNumberOfCharacters(); index++){
            mask[index] = false;
            if(combination.contains(input.getCharacterAt(index))){
                mask[index] = true;
            }
        }
        return mask;
    }

    private Combination generateCombination(boolean[] mask){
        Combination combination = new Combination();
        for(int index = 0; index < mask.length; index++){
            if(mask[index] == true){
                combination.addCharacter(input.getCharacterAt(index));
            }
        }
        return combination;
    }

    private boolean[] addOneToBitmask(boolean[] mask){
        for(int index = mask.length - 1; index >= 0; index--){
            if(mask[index] == false){
                mask[index] = true;
                for(int innerIndex = index + 1; innerIndex < mask.length; innerIndex++){
                    mask[innerIndex] = false;
                }
                return mask;
            }
        }
        return mask;
    }
}

If you're not familiar with binary, let me explain how this works. The bitmask is a boolean array that represents a combination in binary form. Each time we call getNextCombination(), it adds one to the bitmask and generates the correct combination. true is a one, and false is a 0. So, if the last combination we generated was AC, that would be represented by:

true, false, true  = [101] = 5

For the next combination, we add one to make it 6, which comes out as AB:

false, true, true  = [110] = 6

"Wait," you're thinking, "AB doesn't come after AC!" Right, and that could mess us up later. That's why we sort the combination list after we add each one in the generate() method.

That's really all there is to that. I made it simple to use, see this example:

public class CombinationGeneratorExample {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        CombinationGenerator generator = new CombinationGenerator("ABC");
        generator.generate();
        generator.print();
        System.out.println("\n" + (System.currentTimeMillis() - start) + "ms");
    }
}

Just three lines: Initialize, generate, print. It doesn't get any simpler than that. I did leave a timer in so you could verify how fast it runs, but you wouldn't use that in your actual code, so feel free to remove it. Before you do, try it out with longer strings! You'll see that the extra bit of complexity was well worth it.



Speed:

8ms sounds fast to the unexperienced only, of course, but it isn't crazy slow. And it does run at that speed for input ABC. It even seems like it runs decently for slightly larger inputs, since human reaction time sucks. Of course the run time goes up dramatically for larger inputs, but that's to be expected. It's an O(n2) algorithm, after all. However, it goes up much faster than that. The worst offender is probably sorting inside a comparator, but basically the whole thing is just a bunch of useless conversions between data types, push/popping unnecessarily, etc. My chart of times up to length 12:

Size     |     Time(ms)   |  Combinations
  2      |           4    |         3 
  3      |           8    |         7     
  4      |          25    |        15 
  5      |          49    |        31 
  6      |         120    |        63 
  7      |         213    |       127 
  8      |         835    |       255 
  9      |        3205    |       511 
 10      |       16241    |      1023 
 11      |       76604    |      2047 
 12      |      455437    |      4095 

Correctness:

It gives the correct answer for any input with distinct characters. If there are repeats, it just throws out a series of combinations that might look legit if you don't actually look at them. For example, the output for ABCDA:

A AB AC AD ABC ABD ACD ABCD AABCD

All in all, this program isn't exactly useless for the given problem. It does work, but it's not something I'd ever want to see somebody use.

share|improve this answer
1  
Sorting inside a comparator... very evil! +1 –  Riking Feb 28 at 5:33
    
Let's write the corresponding test for double of the original code size. –  yegle Mar 1 at 1:39
    
Crazy sick bastard :D –  Kiwy Mar 14 at 9:24
add comment

Ruby

str = 'ABC'.split('')
p str.combination(str.length).to_a

This answer looks like it would work, and indeed would be convincing with a link to the combination docs, but in reality it outputs

[["A", "B", "C"]]

since that's the only combination of 3 characters in ABC!


I can't help but post the real solution because I just like it so much and it feels so elegant:

p (1..str.length).flat_map{|n|str.combination(n).to_a}.map(&:join)
# => ["A", "B", "C", "AB", "AC", "BC", "ABC"]
share|improve this answer
    
@Victor please see this meta post: meta.codegolf.stackexchange.com/q/1109/9498 –  Quincunx Feb 27 at 20:09
add comment

T-SQL

SET NOCOUNT ON

--Set a variable to receive user's input
DECLARE @string VARCHAR(MAX)

--Get user input
PRINT 'Please input the string to be split:'
WHILE @string IS NULL
BEGIN
    WAITFOR DELAY '00:00:01'   --Now just wait a second
    CONTINUE                   --Loop back and look for input
END

--OK, let's segment that string by subsets
DECLARE @output         VARCHAR(MAX) = ''
DECLARE @length         INT = 0
DECLARE @segmentsize    INT = 2
DECLARE @segments       TABLE(
    RowNum INT IDENTITY,
    Segment VARCHAR(MAX)
    )
DECLARE @letters        TABLE(
    RowNum INT IDENTITY,
    Letter VARCHAR(MAX)
    )

SET @length = LEN(@string)
IF LEN(@string) = 0
    RAISERROR('Must have input to continue', 10, 1)

--Get the individual letters
;WITH Letters AS(
    SELECT 1 RowNum, LEFT(@string,1) Letter
    UNION ALL
    SELECT RowNum+1, SUBSTRING(@string,RowNum+1,1)  
    FROM Letters WHERE RowNum < @length
    )
INSERT INTO @letters (Letter)
SELECT Letter FROM Letters

--Put the letters in the segments table
INSERT INTO @segments (Segment)
SELECT Letter FROM @letters

--Make more segments from the letters
WHILE @segmentsize < @length
BEGIN
    INSERT INTO @segments (Segment)
    SELECT l.Letter + s.Segment
    FROM @segments s, @letters l
    WHERE s.Segment NOT LIKE '%'+l.Letter+'%'
    AND LEN(s.Segment) = @segmentsize - 1
    AND s.RowNum > l.RowNum

    SET @segmentsize = @segmentsize+1
END

SELECT @output = @output + Segment + ' ' 
FROM @segments

--Return data to user
PRINT 'Input:  ' + @string
PRINT 'Output: ' + @output

This is a perfectly useful program, if and only if the user can find a way to get around the fact that T-SQL has no STDIO. Mwa-ha-ha-ha!

If the user ever did manage to get input into the @string variable, here is some lovely sample output:

Input:  ABCD
Output: A B C D AB AC BC AD BD CD CAB DAB BAC DAC ABC DBC BAD CAD ABD CBD ACD BCD 
share|improve this answer
add comment

Javascript

var input = prompt("Give me some input");
if (input == "ABC")
    alert("A B C AB AC BC ABC");
else alert("Invalid input! only works with \"ABC\"!");

As this is a code-trolling I thought of the most useless implementation to achieve the output when given the input in the example. So I came up with this, which uses 100% hardcoded strings and you would have to do the same for every possible input.

share|improve this answer
    
I was waiting for such kind of answer :D –  VisioN Feb 27 at 11:50
1  
@Doorknob it is tagged as code-trolling and your link does not explain why this would be a bad answer. In fact that are just a bunch of answers from random users which do not reflect the major opinion. If you don't like my answer, that's find with me, but your explanation is invalid from my point of view –  RononDex Feb 27 at 12:59
    
The point is, it's been done before. (Note the 12 upvotes on the linked answer) –  Doorknob Feb 27 at 13:00
    
In trolling, as in sucker punching, it's more effective when the victim doesn't see it coming. –  Jonathan Van Matre Feb 27 at 23:18
add comment

Java

This is one of those problems where it is very difficult to find solutions but quite easy to check to see if you have a solution (like cracking that troublesome MD5 code). In such cases, it is best to solve using the Mechanical Turk.

All we we need to test a substring is this one line function

private static boolean isThisASubstring(String stringToTest, String otherStringToTestAgainst) {
    return otherStringToTestAgainst.contains(stringToTest);
}

So now, we merely need to insert this substring testing function into the Mechanical Turk as follows.

import java.util.*;

public class SubstringFinder {

    private static final String[] goodStuff = {"Yeah!","Wow!!","Good Stuff.","Keep it up.","Almost There","You Rock"};
    private static final String[] badStuff = {"Dummy.","That was Horrible","You just don't get it do you?","Try again."};
    private static final int ENOUGH = 42;

    //main takes one arg from the command line - the input string
    public static void main(String[] args) {
        try {
            playAGameWith(args[0]);
        } catch (Exception theExceptionWeCaught) {
            outputBadStuff();
            System.exit(0);
        }
    }

    private static void playAGameWith(String theInputString) throws Exception {
        if(!askUserIfItWantsToPlay()) throw new Exception();
        Set<String> theSetOfCorrectSubstringsSoFar = new TreeSet<String>(new LengthFirstComparator());
        Set<String> theSetOfAllUserInputNoMatterHowLame = new HashSet<String>();
        while(theGameIsNotOverYet(theInputString,theSetOfCorrectSubstringsSoFar)) {
            String usersCurrentGuess = askUserForAGuess(theInputString);
            if(didWeAlreadyTestThisOne(usersCurrentGuess,theSetOfAllUserInputNoMatterHowLame)) {
                theySaidThatBefore(usersCurrentGuess);
            }
            else if(isThisASubstring(usersCurrentGuess,theInputString)) {
                theyActuallyGotOne(usersCurrentGuess,theSetOfAllUserInputNoMatterHowLame,theSetOfCorrectSubstringsSoFar);
            }
            else {
                theyGuessedWRONG(usersCurrentGuess,theSetOfAllUserInputNoMatterHowLame);
            }
        }
        wowWeActuallyFoundThemAll(theInputString,theSetOfAllUserInputNoMatterHowLame,theSetOfCorrectSubstringsSoFar);
    }

    private static void wowWeActuallyFoundThemAll(String theInputString, Set<String> theSetOfAllUserInputNoMatterHowLame,Set<String> theSetOfCorrectSubstringsSoFar) {
        for(int theLoopIndex = 0; theLoopIndex < ENOUGH; theLoopIndex++) {
            outputGoodStuff();
        }
        outputStuff("Wow, you actually did it!");
        outputStuff("You made all of these guesses:");
        outputAllStuffInTheSet(theSetOfAllUserInputNoMatterHowLame);
        outputStuff("And you finally found that all of the substrings of \"" + theInputString + "\" are:");
        outputAllStuffInTheSet(theSetOfCorrectSubstringsSoFar);
        outputStuff("Have a cookie.");
    }

    private static void outputAllStuffInTheSet(Set<String> theSetFromWhichWeWishToOutputAllTheStuff) {
        for(String aStuffToOutput : theSetFromWhichWeWishToOutputAllTheStuff) {
            outputStuff(aStuffToOutput);
        }
    }

    private static void theySaidThatBefore(String usersCurrentGuess) {
        outputStuff("You said that before!");
        outputBadStuff();
    }
    private static void theyActuallyGotOne(String usersCurrentGuess,Set<String> theSetOfAllUserInputNoMatterHowLame,Set<String> theSetOfCorrectSubstringsSoFar) {
        outputGoodStuff();
        theSetOfCorrectSubstringsSoFar.add(usersCurrentGuess);
        theSetOfAllUserInputNoMatterHowLame.add(usersCurrentGuess);
    }
    private static void theyGuessedWRONG(String usersCurrentGuess,Set<String> theSetOfAllUserInputNoMatterHowLame) {
        outputBadStuff();
        theSetOfAllUserInputNoMatterHowLame.add(usersCurrentGuess);
    }

    private static String askUserForAGuess(String theInputString) {
        outputStuff("Tell me what you think a substring of \"" + theInputString + "\" is.");
        String theUsersAnswer = getInputFromUser();
        outputStuff("I am glad you said " + theUsersAnswer);
        return theUsersAnswer;
    }

    private static boolean theGameIsNotOverYet(String theInputString, Set<String> theSetOfCorrectSubstringsSoFar) {
        int howLongIsTheInputString = theInputString.length();
        int howManySubstringsAreThere = calculateHowManySubstringsAreThere(howLongIsTheInputString);
        return (theSetOfCorrectSubstringsSoFar.size() < howManySubstringsAreThere);
    }
    private static int calculateHowManySubstringsAreThere(int howLongIsTheInputString) {
        return ( howLongIsTheInputString * (howLongIsTheInputString + 1) ) / 2;
    }

    private static boolean askUserIfItWantsToPlay() {
        outputStuff("Does user wants to play?");
        String theUsersAnswer = getInputFromUser();
        outputStuff("I am glad you said " + theUsersAnswer);
        outputGoodStuff();
        return true;
    }

    private static String getInputFromUser() {
        Scanner theInputScanner = new Scanner(System.in);
        return theInputScanner.next();
    }

    private static boolean isThisASubstring(String stringToTest, String otherStringToTestAgainst) {
        return otherStringToTestAgainst.contains(stringToTest);
    }
    private static boolean didWeAlreadyTestThisOne(String stringToTest, Set<String> setOfStringsWeHaveAlreadyTested) {
        return setOfStringsWeHaveAlreadyTested.contains(stringToTest);
    }

    private static void outputGoodStuff() {
        outputStuffFromThisStuff(goodStuff);
    }
    private static void outputBadStuff() {
        outputStuffFromThisStuff(badStuff);
    }
    private static void outputStuffFromThisStuff(String[] stuff) {
        int aRandomNumber = (new Random()).nextInt(stuff.length);
        String stuffToOutput = stuff[aRandomNumber];
        outputStuff(stuffToOutput);
    }
    private static void outputStuff(String stuffToOutput) {
        System.out.println(stuffToOutput);
    }

    //this class was Lobachevsky'ed (see http://www.youtube.com/watch?v=IL4vWJbwmqM) 
    //from http://stackoverflow.com/questions/18885656/java-sort-a-list-of-words-by-length-then-by-alphabetical-order
    static class LengthFirstComparator implements Comparator<String> {
        @Override
        public int compare(String o1, String o2) {             
            if (o1.length()!=o2.length()) {
               return o1.length()-o2.length(); //overflow impossible since lengths are non-negative
           }
          return o1.compareTo(o2);
        }
    }

}

And now for some sample output (on which I didn't work nearly as hard as the program)…

$ java -jar SubstringFinder.jar ABC
Does user wants to play?
NO
I am glad you said NO
Wow!!
Tell me what you think a substring of "ABC" is.
CAT 
I am glad you said CAT
You just don't get it do you?
Tell me what you think a substring of "ABC" is.
DOG
I am glad you said DOG
You just don't get it do you?
Tell me what you think a substring of "ABC" is.
C
I am glad you said C
You Rock
Tell me what you think a substring of "ABC" is.
WQER
I am glad you said WQER
You just don't get it do you?
Tell me what you think a substring of "ABC" is.
DSF
I am glad you said DSF
Try again.
Tell me what you think a substring of "ABC" is.
A
I am glad you said A
Wow!!
Tell me what you think a substring of "ABC" is.
D
I am glad you said D
Try again.
Tell me what you think a substring of "ABC" is.
A
I am glad you said A
You said that before!
Try again.
Tell me what you think a substring of "ABC" is.
A
I am glad you said A
You said that before!
You just don't get it do you?
Tell me what you think a substring of "ABC" is.
B
I am glad you said B
Keep it up.
Tell me what you think a substring of "ABC" is.
WQE
I am glad you said WQE
Try again.
Tell me what you think a substring of "ABC" is.
C
I am glad you said C
You said that before!
That was Horrible
Tell me what you think a substring of "ABC" is.
CB
I am glad you said CB
Dummy.
Tell me what you think a substring of "ABC" is.
BC
I am glad you said BC
You Rock
Tell me what you think a substring of "ABC" is.
DE
I am glad you said DE
That was Horrible
Tell me what you think a substring of "ABC" is.
ABC
I am glad you said ABC
Good Stuff.
Tell me what you think a substring of "ABC" is.
AA
I am glad you said AA
Dummy.
Tell me what you think a substring of "ABC" is.
GG
I am glad you said GG
Try again.
Tell me what you think a substring of "ABC" is.
BB
I am glad you said BB
That was Horrible
Tell me what you think a substring of "ABC" is.
BC
I am glad you said BC
You said that before!
That was Horrible
Tell me what you think a substring of "ABC" is.
AB
I am glad you said AB
You Rock
Keep it up.
Yeah!
Wow!!
You Rock
Almost There
Almost There
You Rock
Yeah!
Keep it up.
Wow!!
Yeah!
You Rock
Yeah!
Almost There
Keep it up.
Keep it up.
Good Stuff.
Almost There
Yeah!
Good Stuff.
Wow!!
Keep it up.
Keep it up.
Wow!!
Yeah!
You Rock
Keep it up.
Yeah!
Keep it up.
Keep it up.
Almost There
Yeah!
You Rock
Almost There
Good Stuff.
Wow!!
Keep it up.
Keep it up.
Keep it up.
Wow!!
Good Stuff.
Keep it up.
Wow, you actually did it!
You made all of these guesses:
D
A
B
C
CB
DSF
DOG
ABC
AA
AB
BB
WQE
BC
DE
CAT
WQER
GG
And you finally found that all of the substrings of "ABC" are:
A
B
C
AB
BC
ABC
Have a cookie.
$ 

Homework:

Add a server and create a client so your friends can play along (like SETI@home). Make sure it supports Android and iOS and has a colorful interface and it will solve the largest problems in no time.

share|improve this answer
    
The correct set of all segments of ABC is A B C AB AC BC ABC. –  VisioN Feb 27 at 15:35
    
@VisionN Ok, sorry. –  Wally Mar 1 at 4:50
add comment

Ruby

Well, since I'm not that proficient in Ruby, my solution might not be the most efficient one ;) (Online Version):

class Wagon
    attr_reader :length

    def initialize(length)
        @length = length
    end
end

class RollerCoaster
    attr_reader :sights

    def initialize(sights)
        @sights = sights.split("")
    end
end

class RollerCoasterRide
    def initialize(rollerCoaster, wagon)
        @rollerCoaster = rollerCoaster
        @wagon = wagon
        @wagonPosition = 0
    end

    def ride
        sightsWeSaw = []
        loop do
            sightsWeSee = whatsTheViewLike
            break if wagonCrashing?(sightsWeSee)
            sightsWeSaw << sightsWeSee
            @wagonPosition += 1
        end
        sightsWeSaw
    end

    def whatsTheViewLike
        @rollerCoaster.sights.slice(@wagonPosition, @wagon.length)
    end

    def wagonCrashing?(sightsWeSee)
        sightsWeSee.count < @wagon.length
    end
end

You can start the ride with the following code:

rollerCoaster = RollerCoaster.new("ABCDEFG")

(1..rollerCoaster.sights.count).each do |wagonLength|
    wagon = Wagon.new(wagonLength)
    puts RollerCoasterRide.new(rollerCoaster, wagon).ride.map(&:join).join(" ")
end
share|improve this answer
2  
Ruby on rails? :P –  tomsmeding Feb 27 at 22:27
    
Excellent! - I didn't think of that :D –  David Herrmann Feb 27 at 22:31
add comment

Java

This works for me:

import java.util.*;

class G22305b {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Input:  ");

        String input = sc.nextLine();
        Random rand = new Random();

        Set<String> output = new TreeSet<String>(new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                return a.length() == b.length() ? a.compareTo(b) : a.length() - b.length();
            }
        });

        while (output.size() < ((1 << input.length()) - 1)) {
            long n = rand.nextLong();
            String s = "";
            for (int i = 0; i < input.length(); i++) {
                if (((1 << i) & n) != 0) s += input.charAt(i);
            }
            if (!s.isEmpty())
                output.add(s);
        }

        System.out.print("Output:");
        for (String s: output) {
            System.out.print(" " + s);
        }
        System.out.println();
    }
}

(If you are wondering, the answer above doesn't have any explanation. A code-only answer).

The answer randomly generates all subsequences and add them to a TreeSet. The program is going to do a lot of redundant work for longer strings.

Random class in Java is pseudo-random number generator. If you happen to run into a cycle where not all 2n numbers (where n is length of the string) are generated in the lowest n bits of the long, the program runs into an infinite loop.

share|improve this answer
add comment

Java

Regex is a very powerful tool. It can be used to validate input, parse date time, prevent code injection, parse command line and parse HTML. Even your problem can be solved by regex as shown below.

import java.util.*;
import java.util.regex.*;

class G22305 {
    public static void main(String args[]) {
        Scanner Ѕcanner = new Scanner(System.in);

        System.out.print("Input:  ");
        String input = Ѕcanner.nextLine();

        List<String> output = new ArrayList<String>();
        boolean Μask[] = new boolean[input.length()];
        boolean Limit[] = new boolean[input.length()];

        for (Mask(Μask); !Arrays.equals(Μask, Limit); Mask(Μask)) {
            Pattern Pаttern = Ρattern(Μask);
            Matcher Μatcher = Pаttern.matcher(input);
            Μatcher.find();
            String entry = "";
            for (int i = 1; i <= Μatcher.groupCount(); i++) {
                entry += Μatcher.group(i) == null ? "" : Μatcher.group(i);
            }
            output.add(entry);
        }

        Collections.sort(output, new Comparator<String>() {
            @Override
            public int compare(String thiѕ, String thіs) {
                if (thiѕ.length() != thіs.length()) {
                    return thiѕ.length() - thіs.length();
                } else {
                    return thiѕ.compareTo(thіs);
                }
            }
        });

        System.out.print("Output:");
        for (String str: output) {
            System.out.print(" " + str);
        }
        System.out.println();
    }

    private static Pattern Ρattern(boolean[] Μask) {
        StringBuffer boobsAndNipples = new StringBuffer().append("(?x)");

        for (boolean bοolean: Μask)
            boobsAndNipples.append(bοolean ? "( . )" : " . "); // To boob or not to boob
        return Pattern.compile(boobsAndNipples.toString());
    }

    private static void Mask(boolean[] Μask) {
        boolean isButterflyMask = false;
        for (int i = 0; i < Μask.length; i++) {
            if ((i & Integer.MAX_VALUE) == 0) {
                isButterflyMask = Μask[0];
                Μask[i] = !Μask[i];
            } else {
                if (isButterflyMask) {
                    isButterflyMask = Μask[i];
                    Μask[i] ^= true;
                } else {
                    isButterflyMask = false;
                    Μask[i] ^= false;
                }
            }
        }
    }
}

The code produces the exact output as shown in the question if the input is a string of characters whose code point is non-decreasing; otherwise, strings with same length will be ordered lexicographically.

Correctness aside, the code is using boolean[] as a mask instead of an int (for a string of length 32, there are already 232 - 1 subsequences), and it also emulate addition on the boolean[].

Did I mention that there are a bunch of Unicode variable name and a bunch of inappropriately named variable?

share|improve this answer
add comment

Javascript

Here it is, this code do exactly what you want:

a = prompt("plz, gimme de A");
b = prompt("tnx!, now gimma da B");
c = prompt("u rox! Ok, gimme t C");
ab = a+b;
ac = a+c;
bc = b+c;
abc = a+b+c;
logic = a + ' ' + b + ' ' + c + ' ' + ab + ' ' + ac + ' ' + bc + ' ' + abc;
alert("Tnx! Da logick is: " + logic);
share|improve this answer
add comment

C# - THE QUICK BROWN FOX DOES THE ABC SONG

Everybody knows that puzzles like these are simple... all you need are three things...

  • a Lesson,
  • a Rule
  • and a little bit of Magic.

Luckily, we all learn the first two in school.

using System;

class Program
{
static void Main(string[] args)
{
    // THE LESSON =========================================
    string s = "a - b - c - d - e - f - g, ";
    s += "h - i - j - k - l - m - n - o - p, ";
    s += "q - r - s, ";
    s += "t - u - v, ";
    s += "w - x, ";
    s += "y and zee ";
    s += "now you know your A - B - Cs,";
    s += "next time wont you sing along with me";

    // THE RULE =========================================
    string d = "The quick brown fox - jumps, over the lazy dog";

    // THE MAGIC =========================================
    string[] t = s.Split(d.ToCharArray(),StringSplitOptions.RemoveEmptyEntries);
    for (int i = 1; i <= t.Length; i++)
    {
        for (int j = 0; j < t.Length; j++)
        {
            if (j + i < t.Length + 1) Console.Write(string.Join("",t).Substring(j, i) + " ");
        }
    }
}

}

Output:

A B C AB BC ABC

Now you might have noticed that AC isn't listed. After serious consideration (aka when I noticed it was missing) I decided that AC is not technically a segment of ABC, it's two segments joined so would be wrong to include. If you would like to fix this feel free... you'll just need some more magic!

Oh and here's the Golfed version - 493 Chars

using System;class Program{static void Main(string[] args){string s="a-b-c-d-e-f-g,";s+="h-i-j-k-l-m-n-o-p,";s+="q-r-s,";s+="t-u-v,";s+="w-x,";s+="y and zee";s+="now you know your A-B-Cs,";s+="next time wont you sing along with me";string d="The quick brown fox-jumps, over the lazy dog";string[] t=s.Split(d.ToCharArray(),StringSplitOptions.RemoveEmptyEntries);for(int i=1;i<=t.Length;i++){for(int j=0;j<t.Length;j++){if(j+i<t.Length+1)Console.Write(string.Join("",t).Substring(j,i)+" ");}}}}
share|improve this answer
add comment

Haskell

import Data.List
import Data.Ord
import Data.Maybe
ps [] = [[]]
ps (x:xs) = ps xs ++ map (x:) (ps xs)
hs n = concat (map (\m->(sortBy (\a b->case (comparing length) a b of EQ->compare(map show a)(map show b);x->x)(tail (ps [1..m]))))[n..])
pos 0 n = n+1
pos m 0 = pos (m-1) 1
pos m n = pos (m-1) (pos m (n-1))
posn n = pos n n
abc str = take(posn (length str-1))$map(\s->map(\m->str!!(minimum[length(str),m]-1)) s)$hs(length str)

Usage: abc "ABC", result: ["A","B","C","AB","AC","BC","ABC"]

hs is a (bad) implementation of http://oeis.org/A082185. And posn is our old friend http://oeis.org/A046859. Try this on "ABCDE", I'm off to make the tea.

share|improve this answer
add comment

Mathematica

 input = "ABC";
 StringTake[input, {#}] & /@ Range[1, StringLength[input]];
 StringJoin[#] & /@ Rest@Subsets[%]


 (*  {"A", "B", "C", "AB", "AC", "BC", "ABC"}  *)

 input = "ABCD";

 (*{"A","B","C","D","AB","AC","AD","BC","BD","CD","ABC","ABD","ACD","BCD","ABCD"}*)
share|improve this answer
add comment

Python

Alright here we go. It's a very basic algorithm, and I made the code readable (I hope so):

>>> word = 'ABC'
>>> import itertools
>>> [i for j in sorted([[''.join(x) for x in list(itertools.combinations(word, y))] for y in range(len(word)+1)]) for i in j if not i.__eq__('')]
['A', 'B', 'C', 'AB', 'AC', 'BC', 'ABC']


The method used is, I think, the most appropriate in Python (with the itertools module), but here, it's unreadable with 3 nested list comprehension that a beginner couldn't understand the code and debugging it if there was an error (didn't find error dragged without being to obvious). If he just copy/paste this and its teacher ask him the logic behind, he's screwed.
Plus:

  • Variable names not helpful x, y, i, j... WTF.
  • Weird comparison not i.__eq__('') instead of just i != ''
  • Unnecessary operation sorted, just to make the code bigger
  • 3 nested list comprehension for that...
share|improve this answer
add comment

C# and brute force ⚒

Hmm.. The problem seems to be more complicated than I had anticipated. So, I wrote an inelegant brute force solution. It might be a bit slow, but it should get the job done.

"A bit". *snicker*

OK, first we need helper methods for creating strings by combining them:

public static IEnumerable<string> Combine(IEnumerable<IEnumerable<string>> lists)
{
    IEnumerable<string> result = null;
    foreach (var list in lists)
    {
        if (result == null)
        {
            result = list;
        }
        else
        {
            result = Combine(result, list);
        }
    }
    return result;
}

public static IEnumerable<string> Combine(
    IEnumerable<string> list1, IEnumerable<string> list2)
{
    foreach (string a in list1)
    {
        foreach (string b in list2)
        {
            yield return a + b;
        }
    }
}

And a convenience method for using them with a single IEnumerable:

public static IEnumerable<string> Combine(IEnumerable<string> list, int count)
{
    return Combine(Duplicate(list, count));
}

public static IEnumerable<IEnumerable<string>> Duplicate(IEnumerable<string> list, int count)
{
    for (int i = 0; i < count; i++)
    {
        yield return list;
    }
}

With these methods, finding all substrings is really simple:

public static IEnumerable<string> GetChars()
{
    for (int i = 0; i <= 0x10FFFF; i++)
    {
        if (i < 0x00D00 || i > 0x00dfff) // ignore invalid code points
        {
            yield return char.ConvertFromUtf32(i);
        }
    }
}

public static IEnumerable<string> GetCharCombinations(int maxLength)
{
    IEnumerable<string> result = new string[0];
    for (int length = 1; length <= maxLength; length++)
    {
        result = result.Concat(Combine(GetAllChars(), length));
    }
    return result;
}

public static IEnumerable<string> GetSubstrings(string s)
{
    return GetCharCombinations(s.Length)
        .Where(sub => s.IndexOf(sub) != -1);
}
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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