Jeg beklager det noget sene svar på det seneste spørgsmål - kodetravlheden har været meget overvældende de seneste dage...
Der kom kun tre svar på palindromspørgsmålet (så I andre havde haft ret gode chancer for at vinde præmier i denne uge). Til gengæld var alle tre svar særdeles gode svar.
Rasmus Faber-Espensen og Allan Agerholm Dahl havde lavet nogle løsninger, der lå ret tæt på hinanden - løsninger der iøvrigt begge to performede rigtigt, rigtigt godt. De sammenlignede begge enkeltkarakterer, hvilket nok var en ret god ide, idet deres løsninger performede langt, langt bedre end min egen løsning, hvor jeg havde været mere doven og sammenlignet strenge på traditionel manér. Det samme havde Leif Thomsen - og han havde fået en lige så ringe performance ud af det som jeg ;^) Til gengæld havde han også lavet en alternativ og ganske interessant løsning, hvor han konstruerede mulige palindromer for så derefter at tjekke, om de var en del af strengen. Hans egen konklusion var dog desværre, at "det kører herrelangsomt, så jeg droppede helt at teste og optimere yderligere på den fremgangsmåde!". Naturligvis ærgerligt hvis man skal se rent performancemæssigt på det, men han får mange point for den eksperimenterende tilgang. Alle tre kom iøvrigt frem til det rigtige antal unikke palindromer (144) ved søgning i strengen genereret af CreateRandomNumberString(42, 2442).
Som inspiration kommer her Rasmus og Allans løsninger...
Rasmus løsning:
public static ICollection<string> FindPalindromes(string s)
{
var res = new HashSet<string>();
// Odd length:
for (int i = 1; i < s.Length - 1; i++)
{
for (int j = 1; i - j >= 0 && j + i < s.Length; j++)
{
if (s[i - j] != s[i + j])
break;
res.Add(s.Substring(i - j, 2 * j + 1));
}
}
// Even length:
for (int i = 1; i < s.Length; i++)
{
for (int j = 1; i - j >= 0 && j + i - 1 < s.Length; j++)
{
if (s[i - j] != s[i + j - 1])
break;
res.Add(s.Substring(i - j, 2 * j));
}
}
return res;
}
Allans løsning:
public static class Palindromes
{
public static List<string> FindAllPalindromes(this string input)
{
List<string> found = new List<string>();
if (input.Length >= 3) //this one counts palindromes of uneven length
{
for (int i = 1; i < input.Length - 1; i++)
{
if (input[i - 1] == input[i + 1])
{
found.Add(input.Substring(i - 1, 3));
int counter = 2;
while (i - counter >= 0 && i + counter < input.Length && input[i - counter] == input[i + counter])
{
found.Add(input.Substring(i - counter, counter * 2 + 1));
counter++;
}
}
}
}
if (input.Length >= 2) //this one counts palindromes of even length
{
for (int i = 0; i < input.Length - 1; i++)
{
if (input[i] == input[i + 1])
{
found.Add(input.Substring(i, 2));
int counter = 2;
while (i + 1 - counter >= 0 && i + counter < input.Length && input[i + 1 - counter] == input[i + counter])
{
found.Add(input.Substring(i + 1 - counter, counter * 2));
counter++;
}
}
}
}
return found;
}
public static int FindPalindromeCount(this string input)
{
return input.FindAllPalindromes().Count;
}
public static int FindUniquePalindromeCount(this string input)
{
return input.FindAllPalindromes().Distinct().Count();
}
}
Rasmus har allerede vundet to gange og mener ikke at han kan bruge præmierne i flere eksemplarer (men cool nok at han alligevel deltager for udfordringens skyld ;^) så præmierne sponsoreret af http://www.microsoft.com/web/webmatrix/ går til:
ASP.NET bogen går til: Allan Agerholm Dahl, Ringsted
Pluralsight abonnementet går til: Leif Romme Thomsen, Aarhus