//
//  chrisAb01.cpp
//  MiscMetatools
//
//  Created by David Van Brink on 4/24/16.
//  Copyright (c) 2016 omino.com. All rights reserved.
//

// https://www.facebook.com/christopher.hull.75/posts/10208754906725829?pnref=story
/*
 
 Christopher Hull
 7 hrs · Sunnyvale ·
 Interesting coding challenge from Google:
 You are given two sets of strings. The first set is any sequence of 0 or 1. The second set is any sequence of A or B. In the language of your choice, construct an algorithm that will determine if the first string codes for the second according to the following rules.
 1: A "0" codes for any sequence of "A"s. Thus, 0 can be A, AA, AAA, etc.
 2: A "1" codes for any sequence of "A"s or "B"s. Thus 1 can be A, AA, AAA or B, BB, BBB. A single 1 can not code to AB. A pair of 1s can code to AB, AAB, BBB, etc.
 Examples:
 00 AA yes
 00 AB no
 011 AAAB yes
 011 AAABA yes
 0110 AAABA yes
 010 AAA yes
 0001 AAB no
 How do you approach the problem? What's in your head right now?
 */
#include "OmAsserts.h"
#include <stdio.h>



bool testAb01(const char *s01, const char *sAb)
{
    char c01 = *s01++;

    if(c01 == 0)
    {
        if(*sAb == 0)
            return true; // they both ended
        else
            return false; // c01 ended first.
    }
    if(c01 == '0')
    {
        // check for any number of A's.
        while(*sAb++ == 'A')
        {
            bool result = testAb01(s01, sAb);
            if(result == true)
                return true;
        }
        return false;
    }
    else
    {
        // match 1 against runs of A or runs of B.
        if(*sAb == 'A')
        {
            while(*sAb++ == 'A')
            {
                bool result = testAb01(s01, sAb);
                if(result == true)
                    return true;
            }
            return false;
        }
        else
        {
            while(*sAb++ == 'B')
            {
                bool result = testAb01(s01, sAb);
                if(result == true)
                    return true;
            }
            return false;
        }
    }
}

void show(const char *s01, const char *sAb, bool expected)
{
    if(expected)
    {
        ASSERT_TRUE("yes", testAb01(s01, sAb));
    }
}

#define ASSERT_AB01_YES(_s01, _sAb) ASSERT_TRUE(" want true ", testAb01(#_s01, #_sAb))
#define ASSERT_AB01_NO(_s01, _sAb) ASSERT_FALSE(" want false", testAb01(#_s01, #_sAb))

int main(int argc, char *argv[])
{
    ASSERT_AB01_YES(00, AA);
    ASSERT_AB01_NO (00,AB);
    ASSERT_AB01_YES(011,AAAB);
    ASSERT_AB01_YES(011,AAABA);
    ASSERT_AB01_YES(0110,AAABA);
    ASSERT_AB01_YES(010,AAA);
    ASSERT_AB01_NO (0001,AAB);
}