Program this!, Programming thread Options

[mipadi]

I'm of the understand that there are a few Technology forum aficionados that are programmers, or are at least interested in programming, so I thought I'd start a thread -- a sort of game. The game was inspired by this thread. It's pretty simple: just implement the following program in whatever language you desire. If someone's already posted a program in your favorite language, see if you can do better! You get bragging rights if you implement the program in a weird/unusual/rare language.

Here are the guidelines for the program:

1. Write a method named matchesPattern1() that accepts a String as input. This method determines whether or not the input String has the following property:
   
   The string has a number of c's equal to the total number of a's and b's.
   
   In other words, every word in this language is of the form:
   
   anbmc(n + m), where n ≥ 0 and m ≥ 0.
   
   n and m may be equal, but this is not required.
   
   Thus, bc, abccac, aabbcccc and abbbbccccc are all valid words in this language.
   
   Your method should return a boolean value: true if the input string satisfies these requirements, and false if it does not.
   
   For example, given a String such as aabbcc, your method should return false.
2. Write a method named matchesPattern2() that accepts a String as input. This method determines whether or not the input String has the following properties:
   
   The string has a number of c's equal to the total number of a's and b's.
   All a's come before any b's, and all b's come before any c's. (HINT: Can you test for this using one or more boolean variable "flags"?)
   
   In other words, every word in this language is of the form:
   
   anbmc(n + m), where n ≥ 0 and m ≥ 0.
   
   n and m may be equal, but this is not required.
   
   Thus, aabbcccc and abbbbccccc are valid words in this language, but abaccc and abc are not.
   
   Your method should return a boolean value: true if the input string satisfies these requirements, and false if it does not.
   
   For example, given a String such as aabbcc, your method should return false.
   
   This pattern is identical to the one above, except it imposes a specific ordering requirement on the input string.
3. Write a method named matchesPattern3() that accepts a String as input. This method determines whether or not the input String has the following properties:
   
   The string has an equal (nonzero) number of a's and c's, and any number of (zero or more) b's.
   All a's come before any b's, and all b's come before any c's.
   
   In other words, every word in this language is of the form:
   
   anb*cn, where n > 0.
   
   Thus, aabbcc and ac are valid words in this language, but abaccc and aabc are not.
   
   Your method should return a boolean value: true if the input string satisfies these requirements, and false if it does not.
   
   For example, given a String such as aabbaa, your method should return false.

[mipadi]

Haskell

CODE

matchesPattern1 s = mp s (0, 0, 0)
    where
        mp [] (a, b, c)                = a + b == c
        mp (x:xs) (a, b, c) | x == 'a' = mp xs ((a + 1), b, c)
                            | x == 'b' = mp xs (a, (b + 1), c)
                            | x == 'c' = mp xs (a, b, (c + 1))


matchesPattern2 s = mp s (0, 0, 0) (False, False, False)
    where
        mp [] (a, b, c) _                           = a + b == c
        mp (x:xs) (a, b, c) (sa, sb, sc) | x == 'a' =
            if sb || sc
                then False
                else mp xs ((a + 1), b, c) (True, sb, sc)
                                         | x == 'b' =
            if sc
                then False
                else mp xs (a, (b + 1), c) (sa, True, sc)
                                         | x == 'c' =
            mp xs (a, b, (c + 1)) (sa, sb, True)


matchesPattern3 s = mp s (0, 0, 0) (False, False, False)
    where
        mp [] (a, b, c) _                           = (a == c) && (a > 0)
        mp (x:xs) (a, b, c) (sa, sb, sc) | x == 'a' =
            if sb || sc
                then False
                else mp xs ((a + 1), b, c) (True, sb, sc)
                                         | x == 'b' =
            if sc
                then False
                else mp xs (a, (b + 1), c) (sa, True, sc)
                                         | x == 'c' =
            mp xs (a, b, (c + 1)) (sa, sb, True)

Source: Matcher.hs

[mipadi]

Erlang

CODE

-module(matcher).
-export([matches_pattern_1/1, matches_pattern_2/1, matches_pattern_3/1]).


matches_pattern_1(S) -> mp1(S, {0,0,0}).

mp1([], {A, B, C})                  -> A + B =:= C;
mp1([H|T], {A, B, C}) when H =:= $a -> mp1(T, {A+1, B, C});
mp1([H|T], {A, B, C}) when H =:= $b -> mp1(T, {A, B+1, C});
mp1([H|T], {A, B, C}) when H =:= $c -> mp1(T, {A, B, C+1}).


matches_pattern_2(S) -> mp2(S, {0,0,0}, {false,false,false}).

mp2([], {A, B, C}, _)                                  -> A + B =:= C;
mp2([H|T], {A, B, C}, {_, Saw_b, Saw_c}) when H =:= $a ->
    if
        Saw_b -> false;
        Saw_c -> false;
        true  -> mp2(T, {A+1, B, C}, {true, Saw_b, Saw_c})
    end;
mp2([H|T], {A, B, C}, {Saw_a, _, Saw_c}) when H =:= $b ->
    if
        Saw_c -> false;
        true  -> mp2(T, {A, B+1, C}, {Saw_a, true, Saw_c})
    end;
mp2([H|T], {A, B, C}, {Saw_a, Saw_b, _}) when H =:= $c ->
    mp2(T, {A, B, C+1}, {Saw_a, Saw_b, true}).


matches_pattern_3(S) -> mp3(S, {0,0,0}, {false,false,false}).

mp3([], {A, _, C}, _)                                  -> A =:= C andalso A > 0;
mp3([H|T], {A, B, C}, {_, Saw_b, Saw_c}) when H =:= $a ->
    if
        Saw_b -> false;
        Saw_c -> false;
        true  -> mp3(T, {A+1, B, C}, {true, Saw_b, Saw_c})
    end;
mp3([H|T], {A, B, C}, {Saw_a, _, Saw_c}) when H =:= $b ->
    if
        Saw_c -> false;
        true  -> mp3(T, {A, B+1, C}, {Saw_a, true, Saw_c})
    end;
mp3([H|T], {A, B, C}, {Saw_a, Saw_b, _}) when H =:= $c ->
    mp3(T, {A, B, C+1}, {Saw_a, Saw_b, true}).

Source: matcher.erl

[Uronacid]

I'd love to do this, but "anbmc(n + m), where n ≥ 0 and m ≥ 0." I don't understand this line.

[mipadi]

I'd love to do this, but "anbmc(n + m), where n ≥ 0 and m ≥ 0." I don't understand this line.

It's a string in which the total number of a's and b's equals the total number of c's.

Valid: "aabbcccc", "acbc", "abaccc"
Invalid: "abc", "aabbc", "cabb"

[heyo-captain-jac...]

Any specific language we have to use?

I might start on this later.

[Uronacid]

It's a string in which the total number of a's and b's equals the total number of c's.

Valid: "aabbcccc", "acbc", "abaccc"
Invalid: "abc", "aabbc", "cabb"

vbscript

CODE

strTest =  "ccccc"
wscript.echo "1:" & pattern1(strTest) & " 2:" & pattern2(strTest) & " 3:" & pattern2(strTest)

Private Function pattern1(strValue)

     numAB = 0
     numC = 0
     numPos = 1
     strPos = " "
    
    
     Do Until  numPos = Len(strValue) + 1
          strPos = Mid(strValue,numPos,1)
          If StrComp(strPos, "a", vbTextCompare) = 0 OR StrComp(strPos, "b", vbTextCompare) = 0 Then
               numAB = numAB + 1
          ElseIf StrComp(strPos, "c", vbTextCompare) = 0 Then
               numC = numC + 1
          End If
          numPos = numPos + 1
     Loop

     If numC => numAB Then
          pattern1 = "true"
     Else
          pattern1 = "false"
     End If

End Function

Private Function pattern2(strValue)

    numAB = 0
    numC = 0
    numPos = 1
    strPos = Mid(strValue,numPos,1)
    blnA = true
    blnB = false
    blnC = true
    

    If StrComp(strPos, "b", vbTextCompare) = 0 OR StrComp(strPos, "c", vbTextCompare) = 0 Then
        pattern2 = "false"
        Exit Function
    End If
    
    Do Until  numPos = Len(strValue) + 1
        strPos = Mid(strValue,numPos,1)
          
        If StrComp(strPos, "a", vbTextCompare) = 0 Then
            If blnA = true Then
                blnA = true
                blnB = true
                blnC = true
            Else
                pattern2 = "false"
                Exit Function
            End If
        ElseIf StrComp(strPos, "b", vbTextCompare) = 0 Then
            If blnB = true Then
                blnA = false
                blnB = true
                blnC = true
                
            Else
                pattern2 = "false"
                Exit Function
            End If
        ElseIf StrComp(strPos, "c", vbTextCompare) = 0 Then
            If blnC = true Then
                blnA = false
                blnB = false
                blnC = true
            Else
                pattern2 = "false"
                Exit Function
            End If
        End If
            
          
          If StrComp(strPos, "a", vbTextCompare) = 0 OR StrComp(strPos, "b", vbTextCompare) = 0 Then
               numAB = numAB + 1
          ElseIf StrComp(strPos, "c", vbTextCompare) = 0 Then
               numC = numC + 1
          End If
          numPos = numPos + 1
     Loop

     If numC => numAB Then
          pattern2 = "true"
     Else
          pattern2 = "false"
     End If

End Function

Private Function pattern3(strValue)

    numAB = 0
    numC = 0
    numPos = 1
    strPos = Mid(strValue,numPos,1)
    blnA = true
    blnB = false
    blnC = false
    

    If StrComp(strPos, "b", vbTextCompare) = 0 OR StrComp(strPos, "c", vbTextCompare) = 0 Then
        pattern3 = "false"
        Exit Function
    End If
    
    Do Until  numPos = Len(strValue) + 1
        strPos = Mid(strValue,numPos,1)
          
        If StrComp(strPos, "a", vbTextCompare) = 0 Then
            If blnA = true Then
                blnA = true
                blnB = true
                blnC = true
            Else
                pattern3 = "false"
                Exit Function
            End If
        ElseIf StrComp(strPos, "b", vbTextCompare) = 0 Then
            If blnB = true Then
                blnA = false
                blnB = true
                blnC = true
                
            Else
                pattern3 = "false"
                Exit Function
            End If
        ElseIf StrComp(strPos, "c", vbTextCompare) = 0 Then
            If blnC = true Then
                blnA = false
                blnB = false
                blnC = true
            Else
                pattern3 = "false"
                Exit Function
            End If
        End If
            
          
          If StrComp(strPos, "a", vbTextCompare) = 0 OR StrComp(strPos, "b", vbTextCompare) = 0 Then
               numAB = numAB + 1
          ElseIf StrComp(strPos, "c", vbTextCompare) = 0 Then
               numC = numC + 1
          End If
          numPos = numPos + 1
    Loop
    
    If numC => numAB Then
        If numAB > 0 Then
            pattern2 = "true"
        Else
            pattern2 = "false"
        End If
    Else
        pattern2 = "false"
    End If

End Function

Like that?

[mipadi]

Any specific language we have to use?

I might start on this later.

No, use whatever you want. (But if I have a way to run the program, I might check it.)

Like that?

It looks good, but I haven't run it.

Maybe I should post a text file with some valid/invalid strings that programs can be checked against...

[heyo-captain-jac...]

Cool. I'll see if I can somehow get this done in Lua.

[mipadi]

Ruby

CODE

def matches_pattern_1?(s)
  if s =~ /[abc]*/
    sums = {:a => 0, :b => 0, :c => 0}
    s.each_char { |ch| sums[ch.intern] += 1 }
    sums[:a] + sums[:b] == sums[:c]
  else
    false
  end
end

def matches_pattern_2?(s)
  if s =~ /(a*)(b*)(c*)/
    $1.length + $2.length == $3.length
  else
    false
  end
end

def matches_pattern_3?(s)
  if s =~ /(a+)b*(c+)/
    $1.length == $2.length
  else
    false
  end
end

Source: matcher.rb

[mipadi]

C

CODE

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

static int matches_pattern_1(const char *s)
{
    struct {
        unsigned int a;
        unsigned int b;
        unsigned int c;
    } sums = {0,0,0};
    
    while (*s) {
        switch (*s) {
        case 'a': sums.a++; break;
        case 'b': sums.b++; break;
        case 'c': sums.c++; break;
        }
        s++;
    }
    
    return sums.a + sums.b == sums.c;
}

static int matches_pattern_2(const char *s)
{
    struct {
        unsigned int a;
        unsigned int b;
        unsigned int c;
    } sums = {0,0,0};
    struct {
        int a;
        int b;
        int c;
    } saw = {0,0,0};
    
    while (*s) {
        switch (*s) {
        case 'a':
            if (saw.b || saw.c) return 0;
            saw.a = 1;
            sums.a++;
            break;
        case 'b':
            if (saw.c) return 0;
            saw.b = 1;
            sums.b++;
            break;
        case 'c':
            saw.c = 1;
            sums.c++;
            break;
        }
        s++;
    }
    
    return sums.a + sums.b == sums.c;
}

static int matches_pattern_3(const char *s)
{
    struct {
        unsigned int a;
        unsigned int c;
    } sums = {0,0};
    struct {
        int a;
        int b;
        int c;
    } saw = {0,0,0};
    
    while (*s) {
        switch (*s) {
        case 'a':
            if (saw.b || saw.c) return 0;
            saw.a = 1;
            sums.a++;
            break;
        case 'b':
            if (saw.c) return 0;
            saw.b = 1;
            break;
        case 'c':
            saw.c = 1;
            sums.c++;
            break;
        }
        s++;
    }
    
    return sums.a == sums.c && sums.a > 0;
}

int main(int argc, char **argv)
{
    char buf[81];
    
    while (fscanf(stdin, "%s\n", buf) != EOF) {
        printf("%s\n", buf);
        printf("  matches pattern1? %s\n", (matches_pattern_1(buf) ? "true" : "false"));
        printf("  matches pattern2? %s\n", (matches_pattern_2(buf) ? "true" : "false"));
        printf("  matches pattern3? %s\n", (matches_pattern_3(buf) ? "true" : "false"));
    }
    
    return 0;
}

Source: matcher.c

[Uronacid]

No, use whatever you want. (But if I have a way to run the program, I might check it.)
It looks good, but I haven't run it.

Maybe I should post a text file with some valid/invalid strings that programs can be checked against...

you can just copy it to a text file and change to extension to *.vbs double click it and it will run.

[mipadi]

you can just copy it to a text file and change to extension to *.vbs double click it and it will run.

Yeah, but I don't have an interpreter for VBScript.

[mipadi]

Python

CODE

def matches_pattern_1(s):
    sums = {'a': 0, 'b': 0, 'c': 0}
    for ch in s:
        try:
            sums[ch] += 1
        except KeyError:
            pass
    return sums['a'] + sums['b'] == sums['c']


def matches_pattern_2(s):
    sums = {'a': 0, 'b': 0, 'c': 0}
    saw = {'a': False, 'b': False, 'c': False}
    for ch in s:
        after = [chr(x) for x in xrange(ord(ch)+1, ord('c')+1)]
        for a in after:
            if saw[a]:
                return False
        saw[ch] = True
        sums[ch] += 1
    return sums['a'] + sums['b'] == sums['c']


def matches_pattern_3(s):
    sums = {'a': 0, 'c': 0}
    saw = {'a': False, 'b': False, 'c': False}
    for ch in s:
        if ch == 'a':
            if saw['b'] or saw['c']:
                return False
            saw['a'] = True
            sums['a'] += 1
        elif ch == 'b':
            if saw['c']:
                return False
            saw['b'] = True
        else:
            saw['c'] = True
            sums['c'] += 1
    return 0 < sums['a'] == sums['c']

Source: matcher.py

[Uronacid]

Yeah, but I don't have an interpreter for VBScript.

You don't have windows?

[mipadi]

You don't have windows?

Negative; I use Mac OS X.

(Well, I have a Windows machine that I could run it on, except it's not on and I don't feel like turning it on right now. But I spent four years writing web apps in VBScript, so I understand the code quite well.)

[Uronacid]

Negative; I use Mac OS X.

(Well, I have a Windows machine that I could run it on, except it's not on and I don't feel like turning it on right now. But I spent four years writing web apps in VBScript, so I understand the code quite well.)

Haha, I gotcha.

[mipadi]

Hey! There are more programmers than just the two of us on CB, aren't there?

[mipadi]

Objective-C

This one isn't dramatically different from the C version...but for such a low-level task, that's to be expected, I guess.

CODE

/* Compile:
*   $ gcc -std=c99 -o matcher-objc -framework Foundation matcher.m
*   # ./matcher-objc
*/

#import <Foundation/Foundation.h>


#define foreach(s)     for (unsigned int i = 0; i < [s length]; i++)


static BOOL matchesPattern1(NSString *s)
{
    struct { unsigned int a; unsigned int b; unsigned int c; } sums = {0,0,0};
    
    foreach(s) {
        switch ([s characterAtIndex:i]) {
            case 'a': sums.a++; break;
            case 'b': sums.b++; break;
            case 'c': sums.c++; break;
        }
    }
    
    return sums.a + sums.b == sums.c;
}


static BOOL matchesPattern2(NSString *s)
{
    struct { unsigned int a; unsigned int b; unsigned int c; } sums = {0,0,0};
    struct { BOOL a; BOOL b; BOOL c; } saw = {NO,NO,NO};
    
    foreach(s) {
        switch ([s characterAtIndex:i]) {
            case 'a':
                if (saw.a || saw.b) return NO;
                saw.a = YES;
                sums.a++;
                break;
            case 'b':
                if (saw.c) return NO;
                saw.b = YES;
                sums.b++;
                break;
            case 'c':
                saw.c = YES;
                sums.c++;
                break;
        }
    }
    
    return sums.a + sums.b == sums.c;
}


static BOOL matchesPattern3(NSString *s)
{
    struct { unsigned int a; unsigned int c; } sums = {0,0};
    struct { BOOL a; BOOL b; BOOL c; } saw = {NO,NO,NO};
    
    foreach(s) {
        switch ([s characterAtIndex:i]) {
            case 'a':
                if (saw.b || saw.c) return NO;
                saw.a = YES;
                sums.a++;
                break;
            case 'b':
                if (saw.c) return NO;
                saw.b = YES;
                break;
            case 'c':
                saw.c = YES;
                sums.c++;
                break;
        }
    }
    
    return sums.a == sums.c && sums.a > 0;
}


int main(int argc, char **argv)
{
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
    char buf[81];
    
    while (fscanf(stdin, "%s\n", buf) != EOF) {
        NSString *s = [[NSString alloc] initWithCString:buf];
        printf("%s\n", [s UTF8String]);
        printf("  matches pattern 1? %s\n", (matchesPattern1(s) ? "true" : "false"));
        printf("  matches pattern 2? %s\n", (matchesPattern2(s) ? "true" : "false"));
        printf("  matches pattern 3? %s\n", (matchesPattern3(s) ? "true" : "false"));
        [s release];
    }
    
    [pool release];
    return 0;
}

Source: matcher.m

[heyo-captain-jac...]

Hey! There are more programmers than just the two of us on CB, aren't there?

At least me, but I'm too unmotivated for this shit.

[mipadi]

At least me, but I'm too unmotivated for this shit.

Real programmers don't need a good reason to program.

Maybe you want a bigger challenge? Or something more...meaningful, or useful?