Daily Programming Challenge

static String common( String str1, String str2) {
        String largest = null;
        
        for( int i=0; i < str1.length(); ++i) {
            for( int j=i+1; j < str1.length(); ++j) {
                if( !str2.contains(str1.substring(i, j)))
                    break;
                
                if( largest == null || largest.length() < j - i)
                    largest = str1.substring(i, j);
            }
        }
        return largest;
    }
    static String common( List<String> strings) {
        String largest = null;
        
        if( strings == null || strings.isEmpty()) return null;
        if( strings.size() == 1) return strings.get(0);
        
        String str1 = strings.get(0);
        
        for( int i=0; i < str1.length(); ++i) {
            for( int j=i+1; j < str1.length(); ++j) {
                boolean bad = false;
                for( String str2 : strings) {
                    if( str2 == str1) continue;
                    
                    if( !str2.contains(str1.substring(i, j))) {
                        bad = true;
                        break;
                    }
                }
                if( bad) break;
                
                if( largest == null || largest.length() < j - i)
                    largest = str1.substring(i, j);
            }
        }
        return largest;
    }

>>58982880
>actually doing OP's homework
top cuck

>>58982880
woops, forgot how substring indexes. Should be <= in the for loops.

File: tumblr_nzq9seNb0J1s21xzoo1_500.gif (1MB, 500x278px) Image search: [Google]

1MB, 500x278px

*meant to say "two or more"

>>58982880

       01 MAX-LEN       PIC 9999 COMP.
       01 WS-IX1        PIC 9999 COMP.
       01 WS-IX2        PIC 9999 COMP.
       01 WK-LEN        PIC 9999 COMP.
       01 WS-LOC1       PIC 9999 COMP.
       01 WS-LOC2       PIC 9999 COMP.
       01 WS-FLAG       PIC X.
          88 NO-DIFFERENCE-FOUND VALUE 'N'.
          88 DIFFERENCE-FOUND    VALUE 'Y'.
       
       MOVE ZERO TO MAX-LEN.                                     
       PERFORM VARYING WS-IX1 FROM 1 BY 1 UNTIL WS-IX1 > WS-LEN1
         PERFORM VARYING WS-IX2 FROM 1 BY 1 UNTIL WS-IX2 > WS-LEN2
           SET NO-DIFFERENCE-FOUND TO TRUE
           PERFORM VARYING WK-LEN FROM MAX-LEN BY 1 UNTIL           
                           WS-IX1 + WK-LEN > WS-LEN1 OR             
                           WS-IX2 + WK-LEN > WS-LEN2 OR
                           DIFFERENCE-FOUND                
             IF WS-TEXT1(WS-IX1 : WK-LEN + 1) = WS-TEXT2(WS-IX2 : WK-LEN + 1)                       
                COMPUTE MAX-LEN = WK-LEN + 1                        
                MOVE WS-IX1 TO WS-LOC1                              
                MOVE WS-IX2 TO WS-LOC2                              
             ELSE                                                   
                SET DIFFERENCE-FOUND TO TRUE
             END-IF                                                 
           END-PERFORM                                              
         END-PERFORM                                              
       END-PERFORM.

>>58982885
It's actually your daily homework :)

>>58982815

use List::Util qw/reduce/;
print reduce{length($a)<length($b)?$b:$a} "$ARGV[0]\0$ARGV[1]"=~/(.+)(?=.*?\0.*?\1)/g;

Here. Unhappy about having to include reduce but I don't see a shorter solution.

>>58982997

($_)=sort{length $b<=>length $a}"$ARGV[0]\0$ARGV[1]"=~/(.+)(?=.*\0.*\1)/g;print

All right. Here's the version without reduce.

C:\>perl cs.pl aweaseeeeesdf op9-0aewsdf
sdf
C:\>perl cs.pl aweaseeeeesdf op9-0aeeeeeeeeeeeeeeeeeewsdf
eeeee
C:\>

>>58982815
Whose fang is this?

>>58982902
Which dialect of COBOL is that? Very nice!

>>58983095
the anime girls fang

>>58983095
Sakurano probably

This is probably a really stupid way to do it, but I didn't feel like tracking the largest substring "found so far" logic because I'm not very good at it.

char *largest_common(char *str1, char *str2)
{
    unsigned len = strlen(str1);
    unsigned i, j;
    for (i = len; i > 0; --i) /* query len */
    {
        for (j = 0; i + j <= len; j++)
        {
            char *test = (char *) malloc(sizeof(char) * i + 1);
            memcpy(test, &str1[j], i); test[i] = '\0';
            printf("string: '%s'\n", test);
            if (strstr(str2, test))
                return test;
            else
                free(test);
        }
    }
    return NULL;
}

>>58983095
Chinese cartoon girl number four.

I'll solve this tomorrow and keep you guys posted

>>58983912
it's not even that hard

Perl wins again with shortest code to complete the task. The best!

>>58983995
i cant even fucking read it

>>58984106
Too bad for you.

>>58983048
christ
this looks like what an autistic child would imagine regex to be

>>58984160
It works.

Plus the actual regular expression I use is extremely simple.

No need to fear the unknown, anon.

>>58982815
kirino an shit

File: Kirino_322.jpg (119KB, 600x600px) Image search: [Google]

119KB, 600x600px

>>58985332
It's not Kirino, it's that stupid new vampire girl from that one anime drawn by the same artist.

It would be infinitely better if it was Kirino, amirite?

don't slip off on me now thread.

Page 10 save rave!

>>58983912
>>58983915
I know, but it was late and I was tired. Now that it's the morning -- here you go.

<?php

function comp($str, $str2) {
    $strlen = strlen($str);
    $index = 0;

    for ($i = $strlen; $i > 0; $i--) {
        for ($j = 0; $j <= $index; $j++) {
            $substr = substr($str, $j, $i);
            if (strpos($str2, $substr) !== false) {
                return $substr;
            }
        }
        $index++;
    }
}

print comp('aweasdf', 'op9-0awsdf');

sdf

File: 13988520[1].jpg (66KB, 575x323px) Image search: [Google]

66KB, 575x323px

>>58982815
>two arguments
>$./main qxbn322r pv22rqx reqxetc

>>58983265
what language is this? I thought that char meant it was a one character string, and other strings had to be declared str

>>58987852
this is C

and you're correct, char can only hold a single character byte, but an array of chars lets you hold strings of arbitrary length

File: 2017-02-17-113002_1039x861_scrot.png (280KB, 1039x861px) Image search: [Google]

280KB, 1039x861px

>>58983048
Very nice. Here's your up(You).

>>58982899
i don't wanna rewrite my solution to use va_args because that's dumb

I rewrote my solution to be 90% more efficient!
There's no point in searching for larger substrings within smaller ones.

char *largest_common(const char *str1, const char *str2)
{
    unsigned l1 = strlen(str1), l2 = strlen(str2);
    const char *sm = (l1 < l2) ? str1 : str2;
    const char *lg = (l2 > l1) ? str2 : str1;
    unsigned len = strlen(sm);
    unsigned i, j;
    for (i = len; i > 0; --i) /* query length */
    {
        for (j = 0; i + j <= len; j++) /* scan */
        {
            char *str = (char *) malloc(sizeof(char) * i + 1);
            memcpy(str, &sm[j], i); str[i] = '\0';
            if (!strstr(lg, str))
                free(str);
            else
                return str;
        }
    }
    return NULL;
}

>>58982815
So if I get this right,
>./strcmp abcdef abcdxef ef1234 123efxx
should output "ef"?
This seems like a difficult problem and everyone is ignoring it so far by making their solution only take two arguments.

Given texts T1, T2, ..., Tn on the alphabet A, we want the maximal word W such that W is a subword of each Ti.

1. Build a suffix tree of the text "T1#1T2#2...Tn" (where #i are symbols not in A).
2. Mark all the inner nodes that, for each Ti, have at least one leaf that started in Ti.
3. Pick one of the marked nodes that's at a maximal distance from the root.

File: money wayward.jpg (120KB, 392x445px) Image search: [Google]

120KB, 392x445px

>>58991641
Conceptually, you only need to check the first and shortest string given, and then part it out by checking all possible substrings within it.
Then sequentially check if that substring exists in all the other strings.
If it does, you have a match.

>>58992215
>>58991641
You got me fired up so I went ahead and rewrote it to take an arbitrary number of arguments.

char *largest_common_n(const char **str, unsigned args)
{
    unsigned i, j, k, len;
    char **arr = (char **) malloc(sizeof(char *) * args);
    for (i = 0; i < args; i++) /* mutable array copy */
        arr[i] = (char *) str[i];
    char *sm = *arr, *ret = NULL;
    for (i = 0; i < args; i++) /* find smallest */
    {
        if (strlen(arr[i]) > strlen(sm))
        {
            char *tmp = sm;
            sm = arr[i];
            arr[i] = tmp;
        }
    }
    len = strlen(sm);
    for (i = len; i > 0; --i) /* query length */
    {
        for (j = 0; i + j <= len; j++) /* scan */
        {
            char *str = (char *) malloc(sizeof(char) * i + 1);
            memcpy(str, &sm[j], i); str[i] = '\0';
            for (k = 1; k < args; k++)
                if (!strstr(arr[k], str))
                    break;
            if (k != args) /* no match */
                free(str);
            else
            {
                ret = str;
                goto exit;
            }
        }
    }
    exit: free(arr);
    return ret;
}

File: strcmp.png (54KB, 1448x846px) Image search: [Google]

54KB, 1448x846px

>>58982815
>>58992215

; --- Finds longest common substring in n strings --- 
; requires 8086 cpu and about 1kB free memory
; assemble with fasm

org 0x100
use16
    cld
    xor bx, bx
    xor ch, ch
    mov cl, [0x80]      
    mov di, 0x82
@@: mov al, ' '
    mov dx, cx
    repne scasb
    sub dx, cx
    mov ax, di          
    sub ax, dx          
    dec dx
    test dx, dx
    jz @b               
    push ax
    push dx
    inc bl
    jcxz @f             
    jmp @b
@@: cmp bl, 1
    jbe error_input     
    mov bp, sp
    mov cx, [bp]
.ret_too_long: 
    mov si, [bp+2]
.ret_next_substr:
    mov di, bx
    shl di, 2
.next_str:
    sub di, 4
    test di, di
    jz .found
    cmp [bp+di], cx
    jb .too_long
    push di
    push cx
    mov cx, [bp+di]
    mov di, [bp+di+2]
.search_again:
    mov al, [si]
    repne scasb
    jne .next_substr
    dec di
    inc cx
    pop ax
    push ax
    cmp cx, ax
    jb .next_substr
    xchg cx, ax
    push di
    push si
    repe cmpsb
    pop si
    pop di
    je @f 
    mov cx, ax
    dec cx
    inc di
    jmp .search_again
@@: pop cx
    pop di
    jmp .next_str
.next_substr:
    pop cx
    pop di
    inc si
    mov di, si
    add di, cx
    mov ax, [bp+2]
    add ax, [bp]
    cmp di, ax
    jbe .ret_next_substr
.too_long: 
    dec cx
    test cx, cx
    jnz .ret_too_long
.found:
    mov dx, si
    add si, cx
    mov byte [si], '$'
    mov ah, 0x09
    int 0x21
    mov ax, 0x4c00
    int 0x21
    
error_input:
    mov dx, err_input
    mov ah, 0x09
    int 0x21
    mov ax, 0x4cff
    int 0x21
err_input db "Usage: STRCMP str0 str1 [str2 ... strn]$"

That turned out to be easier than I expected.

>>58982815

 
string challenge(const string& first, const string& second)
{
    vector<string> possible;
    for (int i = 0; i < first.size(); ++i) {
        for (int j = 0; j < second.size(); ++j) {
            string newitem = "";
            int iter = 0;
            if (first[i] == second[j]) {
                while (first[i + iter] == second[j + iter]) {
                    newitem += first[i + iter];
                    if (i + iter == first.size()) break;
                    iter++;
                }
                possible.push_back(newitem);
            }
        }
    }
    std::sort(possible.begin(), possible.end(), [](string a, string b) {
        return a.size() > b.size();
    });
    cout << possible << endl;
    return possible[0];
}

>>58991641

System.out.println(common( Arrays.asList(new String[]{"abcdef", "abcdxef", "ef1234", "123efxx"})));

Result
ef
Works for me.

File: 1478580210251.jpg (23KB, 240x207px) Image search: [Google]

23KB, 240x207px

>>58983265
>>58987928
>casting malloc in C

>>58994526
>implying it's not done everywhere

File: 1423263360501.jpg (56KB, 926x960px) Image search: [Google]

56KB, 926x960px

>>58983265
>>58990617
>sizeof(char)

fucking hell

>>58994670
Is there a problem?

>>58995060

sizeof(char)

is absolutely and everywhere always exactly 1

File: strcmp2.png (17KB, 1106x829px) Image search: [Google]

17KB, 1106x829px

>>58982815

#include <string>
#include <vector>
#include <iostream>

auto find_common(auto strings)
{
    auto a = strings.back();
    strings.pop_back();
    auto begin = 0;
    auto length = a.length();
    
next_substr:
    auto b = a.substr(begin, length);
    for (auto s : strings)
        if (s.find(b) == std::string::npos)
        {
            if (++begin + length > a.length())
            {
                begin = 0;
                --length;
            }
            goto next_substr;
        }    
    return b;
}

int main(int argc, char** argv)
{
    std::vector<std::string> input { };
    for(int i = 1; i < argc; ++i) input.emplace_back(argv[i]);
    std::cout << find_common(input) << std::endl;
}

Same algorithm as >>58994211
except it's copying strings and the exe takes 440k instead of 200 bytes

>>58995291
ditch string
ditch vector
ditch iostream

>>58995150
It's good practice regardless. It's not like it compiles any different.

>>58995291
C++ is such a disgusting language.

>>58995462
>malloc(sizeof(char) * i + 1);
is the same as
>malloc(i + 1);
the compiler may or may not optimize it, depends
but if the compiler doesn't it compiles different
in the first one you get the size of a char first and then calculate it

it's not good practice
I don't know who told you that
but it's not good practice to sizeof(char)

>>58995551
see >>58995450
also he used labels and goto in c++
no one fucking does that

his post is the incarnation of everything why everybody thinks c++ is a bad language

>>58995575
The compiler "may or may not" optimize a sizeof into a literal and then optimize 1 * (int)x into just x? Man, why are all C++ "enthusiasts" such paranoid ignoramuses?

Yes, it's always good practice to do sizeof(type) into malloc. Because you might change the type at some point in the future. I know you enthusiasts have a hard-on for brevity and in consciously putting pitfalls into your code and jacking off to the fact that you never step on them, but it's bad design.

File: de6e150d779a12b87991b8af2fd9655f.png (74KB, 224x351px) Image search: [Google]

74KB, 224x351px

listening to childhood anime OP and ED

I just can't program with all this nostalgia bottled up inside ;_;

>cant even think of how to start this problem
oh well i planned on being a C# monkey anyways

>>58995150
>sizeof(char) is absolutely and everywhere always exactly 1
No it's not, its some times 1L some times 1UL and some times 1ULL.

You're forgetting the type, it's a size_t.

>>58995708
you will never be able to be a smart programmer unless you take off your clothes and put knee socks on, anon

>>58995600
>goto
what else would you use? I'd like to see you try rewriting the same function without it.

btw same thing with iterators

auto find_common(auto strings)
{
    auto a = strings.back();
    strings.pop_back();
    auto begin = a.cbegin();
    auto end = a.cend();
    
next_substr:
    for (const auto& s : strings)
        if (*std::search(s.cbegin(), s.cend(), begin, end) != *begin)
        {
            if (++begin == a.cend()) break;
            if (end >= a.cend())
            {
                end -= (begin - a.cbegin());
                begin = a.cbegin();
            }
            else ++end;
            goto next_substr;
        }    
    return std::string { begin, end };
}

>>58995648
It was this
https://www.youtube.com/watch?v=GLg_wp0IXoI&

or

https://www.youtube.com/watch?v=vZa0Yh6e7dw

Wasn't it anon?

File: that.jpg (43KB, 380x401px) Image search: [Google]

43KB, 380x401px

>>58995805

>>58982815
Scala:

object Substr extends App {
    println(args(0).zip(args(1)).takeWhile(s => s._1 == s._2).unzip._1.mkString)
}

>>58982815
I'm sure there's a shorter solution

import Data.List
common a b = maximumBy (\x y -> length x `compare` length y)
             $ intersect (strings a) (strings b)
   where strings = takeWhile (/="") . iterate (drop 1)

>>58995735
why would you use goto in lieu of a loop structure?
goto should only be used to escape from multi-level loops.

>>58982815
Excuse my autism

 private string SearchStrings(string str1, string str2)
        {
            string str3 = string.Empty;
            int length = 0;            
            for (int i = 0; i < str1.Length; i++)
            {
                for (int j = 0; j < str2.Length; j++)
                {
                    if (str1[i] == str2[j])
                    {
                        int localLength = 1;
                        int k = i + 1;
                        for (int l = j + 1; k < str1.Length && l < str2.Length; k++, l++)
                        {
                            if (str1[k] == str2[l])
                            {
                                localLength++;
                            }
                        }
                        string localString = str1.Substring(i, localLength);
                        if (localLength > length)
                        {
                            length = localLength;
                            str3 = localString;
                        }
                    }
                }
            }
            return str3;
        } 

I only see like 3 solutions that actually do what the OP asked for, which is finding the common substring in all the strings provided, not just 2.

>>58982880

function stringCommon(str1,str2){
    var largest=undefined;
    for(i=0;i<str1.length;i++){
        for(j=i+1;j<str1.length;j++) {
            if(str2.indexOf(str1.substring(i,j))==-1){
                break;
            }
            if(largest==undefined||largest.length<j-i){
                largest=str1.substring(i,j);
            }
        }
    }
    return largest;
}

>>58998951
>which is finding the common substring in all the strings provided, not just 2.

>Write a program that returns the largest common string between two arguments.
>returns the largest common string between two arguments.
>between two arguments.
>two

>>58987353
this.

challenge dropped

>>58995913

> compare "heyy" "youu"
> *** Exception: Prelude.foldr1: empty list

>>58998951
l2r idiot

>>58997706
Without goto, it would be:

auto find_common(auto strings)
{
    auto a = strings.back();
    strings.pop_back();
    auto begin = a.cbegin();
    auto end = a.cend();
    
    bool found;
    do
    {
        found = true;
        for (const auto& s : strings)
            if (std::search(s.cbegin(), s.cend(), begin, end) != s.cend())
            {
                if (++begin == a.cend()) break;
                if (end == a.cend())
                {
                    end -= (begin - a.cbegin());
                    begin = a.cbegin();
                }
                else ++end;
                found = false;
                break;
            }
    }
    while (!found);

    return std::string { begin, end };
}

So there's a multi-level loop. Using flags as control flow just for the sake of avoiding goto is way worse than a single goto, imo.

>>59000675
>>59000991
>>59001177
see
>>58982899

File: 1482158236503.jpg (28KB, 411x411px) Image search: [Google]

28KB, 411x411px

>>58994211
stop making me want to learn x86 assembly

import Data.List

f :: String -> String -> [String]
f xs ys
  | xs == [] = []
  | ys == [] = []
  | xs `isInfixOf` ys = [xs]
  | otherwise = g $ (f (tail xs) ys) ++ (f (init xs) ys)
  where
    g zs = [z | z <- zs, (length z) == maximum (fmap length zs)]

>>59002110
I dropped in some comments for you. so now you have no reason not to.
>>>http://pastebin.com/a14bgM5E