PROGRAMMING CHALLENGE
INCAPABLE CONTESTENTS BUMP

counting /g out: 1

FIZZBUMP

counting /g out: 2

File: 1349237553623.jpg (56 KB, 620x593) Image search: [Google]

56 KB, 620x593

>hey /g/ pls do my homework for me

[s | s <- subsequences "richardstallman", length s == 3]

Took me three seconds

>>53347066
Slightly improved version

[s | s@[_,_,_] <- subsequences "richardstallman" ]

>>53347081
Faster version

[[a,b,c] | (a:as) <- tails $ "richardstallman", (b:bs) <- tails as, (c:cs) <- tails bs]

>>53347124
And here I was, preparing ko.jpg.
Well done.

>>53347124
Faster version that omits duplicates

let f (x:_) (y:_) = x==y; f x y = x==y; tails' = nubBy f . tails in [[a,b,c] | (a:as) <- tails' "richardstallman", (b:bs) <- tails' as, (c:cs) <- tails' bs]

How much do you want me to continue improving my solution?

C solution

#include <stdio.h>
#include <string.h>

#define AP(n, p)   fact(n) / fact(n - p)

double fact(int in)
{
    int n;
    double p;

    for (p = n = 1; n <= in; n++)
        p *= (double)n;

    return p;
}

int main(void)
{
    char str[] = "richardstallman";

    printf("%.0lf\n", AP(strlen(str), 3));
    return 0;
}

>>53347306

λ let fact n = fromIntegral $ product [1..n]; ap n p = fact n / fact (n - p) in ap (length "richardstallman") 3
2730.0

Actual answer is 278.

>>53347306
>>53347341
Also, assuming you were trying to implement the binomial coefficients (which is not the right solution, btw), you'd still be wrong:

λ binom (length "richardstallman") 3
455

Note: Order matters

>>53347372
This is correct.

How would you go about actually solving this? I'm really struggling.

So I started trying the most naive solution I could think of which would be to select 3 letters at random where each term has to have a higher array index.

Then I thought that I just needed a fast way to get all x combinations of y elements from an array so I found this:

http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n

The first answer that made sense to me from that would be to loop over the array varying 3 array indices.

[r][i][c][h][a][r][d][s][t][a][l][l][m][a][n]
^^^
ijk

// vary k
[r][i][c][h][a][r][d][s][t][a][l][l][m][a][n]
^^     ^
ij     k

and so on with each combination. But this gets pretty intensive with higher numbers.

This was meant as a justificition exercise for being on /g, btw. Everybody here should be able to do this on their own in <15 minutes.

>>53347430
>and so on with each combination. But this gets pretty intensive with higher numbers.
There are O(n^3) solutions so there's no way to get around enumerating them all without spending that much work.

(But you can count them more quickly, of course)

>>53347430
You're on the right track, but starting on the same index is forbidden.

The solution is simpler than you think.

>>53347341
>>53347372
I used combinatorics, in specific, permutations of n elements, distributed by p spots. Sorry, kinda foggy on these maths concepts. Care to explain what I did wrong?

>>53347710
>Care to explain what I did wrong?
Print the wrong answer.

I'm not familiar with the methods you chose to arrive at your result, but your program prints 2730. A brute force enumeration of all solutions gives a much smaller number.

To make the difference more obvious, let's compare your program and mine on a small input size, say "abcd":

Your program outputs the number 24.

On paper we can easily enumerate all the possible solutions, though:

abc, abd, acd

There are no others. So the correct number in this case is 3.

>>53347778
>abc, abd, acd
Oopts, forgot ‘bcd’.

Either way,

λ let f (x:_) (y:_) = x==y; f x y = x==y; tails' = nubBy f . tails in [[a,b,c] | (a:as) <- tails' "abcd", (b:bs) <- tails' as, (c:cs) <- tails' bs]
["abc","abd","acd","bcd"]

>>53347341
I'm getting 290.

>>53347710
>>53347928
This is "combinations without repetition". The correct answer is 455.

https://www.mathsisfun.com/combinatorics/combinations-permutations.html

too lazy to test but here's pseudocode

list<string> result;
string tmp;
for (int a = 0, a < input.length - 2; a++) {
    for (int b = a + 1; b < input.length - 1; b++) {
        for (int c = b + 1; c < input.length; c++) {
            tmp = input.at(a) + input.at(b) + input.at(c); 
            result.add(tmp);
        }
    }
}
return result;

_easy_as_fuck_

>>53347464
>>53347479

Took my time but this produces the same output as the recursive one on StackOverflow.

public class ArrayCombinations {

    static final String[] arr = {"R","I","C","H","A","R","D","S","T","A","L","L","M","A","N"};
    
    public static void main(String[] args){
        findAllCombo(arr);
    }
    
    public static void findAllCombo(String[] arr){

        int i = 0;
        int j = 1;
        int k = 2;

        for (int a = i; a < arr.length-2; a++) {    
            for (int b = j; b < arr.length-1; b++) {
                for (int c = k; c < arr.length-0; c++) {
                    System.out.println("[" + arr[a] + ", " + arr[b] + ", " + arr[c] + "]");
                }
                k=b+2;
            }
            j=a+1;
        }
    }       
}

>>53348621
look at >>53348268
you don't need i j k

>>53348694
He's basically doing the same though, if you just substitute j and k by their def's below the respective loop.

>>53348732
k=b+2
Disregard what I said.

>>53348694

Now with real Code®. I got rid of tmp because I'm just printing the string.

public static void findAllCombo2(String[] input){

        for (int a = 0; a < input.length - 2; a++) {
            for (int b = a + 1; b < input.length - 1; b++) {
                for (int c = b + 1; c < input.length; c++) {
                    System.out.println("[" + input[a] + ", " + input[b] + ", " + input[c] + "]");
                }
            }
        }
        
    }

>>53348774
>String[] filled with one char at each index
k

now with actual Real™ Code® you would just use a simple String and use .chatAt(int index) on that String instead of your whatever that is

>>53348966
>.charAt(int index)
fixed

>>53348966

> micro-optimisations

>>53348988
>> micro-optimisations
https://www.youtube.com/watch?v=pzYGWF6qrts

module String_set = Set.Make (String);;

let append c set =
  String_set.fold
    (fun s set ->
     let str = Printf.sprintf "%c%s" c s in
     String_set.add str set)
    set
    String_set.empty
;;

let rec find string length offset target =
  if target = 0 then
    String_set.singleton ""
  else
    if offset < length then
      let set = find string length (succ offset) (pred target) in
      let set = append string.[offset] set in
      let other_set = find string length (succ offset) target in
      String_set.union set other_set
    else
      String_set.empty
;;

let test string target =
  let length = String.length string in
  String_set.iter
    (fun s ->
     Printf.printf "%s" s;
     print_newline ())
    (find string length 0 target)
;;

let main () = test "richardstallman" 3;;

let () = main ();;

>>53348042
Nope. It needs to be in the same order it was in the source. This is subsequences.

>>53350080
Was post was referring to the formula you have to use to get the proper number for the bottom question in the OP.

How's this algorithm? (a little better this time)
>input string S
>output (initially empty) set A

for i := 1 to length(S) do
  for j := i+1 to length(S) do
    for k := j+1 to length(S) do
      add S[i]..S[j]..S[k] to A
    od
  od
od

Should be O(length(S)^3) since the initializing and inserting into a set is constant time.

>>53350365
And I'm saying it's wrong.

>Find all 3-letter-strings that can be constructed by combining letter from the input string in sequence.
>in sequence

He even shows an example to show why ‘rll’ and ‘llr’ are not the same thing.

>>53350565
What is the correct formula then, in your opinion?

>>53350548
>>53348774
>>53348621
>>53348268
>>53347430
The problem with this approach is that you print duplicate answers.

For example, your results will contain ‘aan’ twice.

To see how you avoid duplicates, look at the difference between >>53347124 >>53347183

>>53350615
How can a set contain duplicate entries?

>>53350699
nigga if you iterate "richardstallman" it finds "aan" multiple times because of the 3 a's the string contains

>>53350609
It's not a matter of opinion. I already posted the correct result. >>53347183

Also, you can statically count the number more efficiently:

>>53347306 was on the right track, or rather >>53347372 was. If the input string contains no duplicates then this is just the binomial (length(S), 3) - but in this case you have to make sure you're not double-counting.

If IDs X and Y are the same, then aXb and aYb generate the same words but are double-counted by the binomial.

I'm not quite sure how to get around this. Ideally you can start by generating permutations with ‘Y’ omitted, and then adding words that use both X and Y at the same time. Not sure how this scales up to 3+

>>53350699
Sorry, remove >>53350548 from my list. I missed that you were using a set and not a list.

>>53346630

subseqs :: Int -> [Char] -> [[Char]]
subseqs n "" = if n == 0 then [""] else []
subseqs n (x:xs) = unionWhen (subseqs n xs) $ map (x:) $ subseqs (n - 1) xs

unionWhen :: [a] -> [a] -> [a]
unionWhen _ [] = []
unionWhen [] _ = []
unionWhen xs ys = xs ++ ys

>>53352548
Then call

subseqs 3 "richardstallman"