Eric H Frazer
BAN USERI'm a fantastic audio/video/3d/Unity programmer. It's the small things that trick me up though.
static void Main( string [] args )
{
string s = "ababab";
int Period = 0;
string szRepeatString = "";
int l = s.Length;
for ( int subLen = 1 ; subLen <= l / 2 ; subLen++ )
{
if ( l % subLen != 0 ) continue;
string szStub = s.Substring( 0, subLen );
int nCopies = l / subLen;
int n;
for ( n = 1 ; n < nCopies ; n++ )
{
if( s.Substring( n * subLen, subLen ) != szStub )
{
break;
}
}
if ( n == nCopies )
{
szRepeatString = szStub;
Period = subLen;
break;
}
}
Console.WriteLine( "string = " + s + ", period = " + Period + ", sub string = " + szRepeatString );
}
here's my VS 2019 C# entry
static List<string> l = new List<string>( );
static Dictionary<string,int> dict = new Dictionary<string, int>( );
static void FindString( string szFind, int szFindLen, List<string> szRemainingWords, ref bool bFound, ref string szOut )
{
if( szFind == "" )
{
bFound = true;
return;
}
string szOutOriginal = szOut;
for( int i = 0 ; i < szRemainingWords.Count ; i++ )
{
string s = szRemainingWords[i];
if ( szFind.StartsWith( s ) )
{
szOut += s + " ";
int len = s.Length;
szRemainingWords [i] = "*" + szRemainingWords [i];
FindString( szFind.Substring( len ), szFindLen - len, szRemainingWords, ref bFound, ref szOut );
szRemainingWords [i] = szRemainingWords [i].Substring( 1 );
if ( bFound )
{
break;
}
}
}
if( !bFound )
{
szOut = szOutOriginal;
}
}
static bool DoesWordAppearNTimes( string szWholeString, string szFindWord, int n )
{
int offset = 0;
while ( n > 0 )
{
int i = szWholeString.Substring( offset ).IndexOf( szFindWord );
if ( i == -1 )
{
return false;
}
offset = i;
n--;
}
return true;
}
static void Main( string [] args )
{
l.Add( "abc" );
l.Add( "abc" );
l.Add( "abc" );
l.Add( "ab" );
l.Add( "ab" );
l.Add( "abca" );
dict.Add( "abc", 3 );
dict.Add( "ab", 2 );
dict.Add( "abca", 1 );
bool bFound = false;
string szOut = "";
string szFind = "abcabab";
FindString( szFind, szFind.Length, l, ref bFound, ref szOut);
if ( bFound )
{
foreach ( KeyValuePair<string, int> kvp in dict )
{
if( !DoesWordAppearNTimes( szFind, kvp.Key, kvp.Value ) )
{
bFound = false;
break;
}
}
}
Console.WriteLine( "Find = " + szFind + ", found = " + bFound.ToString( ) + ", string = " + szOut );
}
This (the above java code) fails for the case "abcabab". the code is really simple, and I like it, but it doesn't catch this case. although I admit the question is poorly worded.
- Eric H Frazer October 09, 2019here's the solution showing each string as well
static int big_o = 0;
static List<string> szOutStrings = new List<string>( );
static int helper( int n, int b, int [] LimitPerDigit, string szHeader )
{
// n == 0 === nothing. never gets here
// if we're the last digit (lenth 1), result is simply "are there still allowable #'s or not"
//
if ( n == 1 )
{
int resultZero = 0;
for ( int digit = 0 ; digit < b ; digit++ )
{
big_o++;
if ( LimitPerDigit [digit] > 0 )
{
resultZero++;
string szThis = ((char) ('a' + digit )).ToString( );
szOutStrings.Add( szHeader + szThis );
}
}
return resultZero;
}
// for each digit, if the digit is allowed, count up how many SUB-combinations are
// under that digit and add to total
int result = 0;
for ( int digit2 = 0 ; digit2 < b ; digit2++ )
{
if ( LimitPerDigit [digit2] > 0 )
{
// dock 1 for the limits per digit for this sub-inspection
LimitPerDigit [digit2]--;
string szThis = ((char) ('a' + digit2 )).ToString( );
result += helper( n - 1, b, LimitPerDigit, szHeader + szThis );
// then afterwards, bump it back up again
LimitPerDigit [digit2]++;
}
}
return result;
}
static void Main( string [] args )
{
int n = 10; // how many numbers
int b = 3; // what is the base
int [] LimitPerDigit = new int[b];
LimitPerDigit [1] = 1; // how many of each # can there be
LimitPerDigit [2] = 2;
LimitPerDigit [0] = n;
int result = helper( n, b, LimitPerDigit, "" );
Console.WriteLine( "total = " + result + ", big_o = " + big_o );
}
here is the "generic solution". or at least, one version of it
static int big_o = 0;
static List<string> szOutStrings = new List<string>( );
static int helper( int n, int b, int [] LimitPerDigit, string szHeader )
{
// n == 0 === nothing. never gets here
// if we're the last digit (lenth 1), result is simply "are there still allowable #'s or not"
//
if ( n == 1 )
{
int resultZero = 0;
for ( int digit = 0 ; digit < b ; digit++ )
{
big_o++;
if ( LimitPerDigit [digit] > 0 )
{
resultZero++;
string szThis = ((char) ('a' + digit )).ToString( );
szOutStrings.Add( szHeader + szThis );
}
}
return resultZero;
}
// for each digit, if the digit is allowed, count up how many SUB-combinations are
// under that digit and add to total
int result = 0;
for ( int digit2 = 0 ; digit2 < b ; digit2++ )
{
if ( LimitPerDigit [digit2] > 0 )
{
// dock 1 for the limits per digit for this sub-inspection
LimitPerDigit [digit2]--;
string szThis = ((char) ('a' + digit2 )).ToString( );
result += helper( n - 1, b, LimitPerDigit, szHeader + szThis );
// then afterwards, bump it back up again
LimitPerDigit [digit2]++;
}
}
return result;
}
static void Main( string [] args )
{
int n = 10; // how many numbers
int b = 3; // what is the base
int [] LimitPerDigit = new int[b];
LimitPerDigit [1] = 1; // how many of each # can there be
LimitPerDigit [2] = 2;
LimitPerDigit [0] = n;
int result = helper( n, b, LimitPerDigit, "" );
Console.WriteLine( "total = " + result + ", big_o = " + big_o );
}
here's my hacky attempt. I used something "like" an interval tree, but not really...
}
- Eric H Frazer October 10, 2019