Greplin Programming Challenge - Level 1

Question

It would be interesting to see some solutions to this challenge in a variety of languages! It's fairly simple but I think there's lots of different approaches that could be taken and I look forward to seeing what the community comes up with!

---

Embedded in the below block of text is the password for level 2. The password is the longest substring that is the same in reverse. As an example, if the input was "I like racecars that go fast" the password would be "racecar".

---

FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth

---

I'll post my PHP approach to start off with.

PHP:

<?php

/**
 * The Greplin Programming Challenge
 * http://challenge.greplin.com/
 *
 * Level 1 PHP Solution
 * Minimised at http://chiggles.net/greplin/1-min.phps
*/

ini_set('memory_limit', '512M'); // this is a shame...

$str = 'FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth';
$possibles = array();
$palindromes = array();

for ($i = 2; $i <= strlen($str); $i++)
{
    for ($j = 0; $j < $i; $j++)
    {
        preg_match_all('/.{'.$i.'}/i', $str, $matches, NULL, $j);
        foreach ($matches[0] as $match) $possibles[] = $match;
    }
}
foreach ($possibles as $possibility) if($possibility == strrev($possibility) && !in_array($possibility, $palindromes)) $palindromes[strlen($possibility)] = $possibility;

krsort($palindromes);
echo reset($palindromes); // ranynar

Answer 1

F#:

Program:

let s = "I like racecars that go fast"

let text = "FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"

let solve (s:string) =
    let mutable max = 0 // longest found so far
    // the word itself and where we found it
    let mutable word = ""
    let mutable index = 0

    for i = 0 to s.Length - 1 do
        for j = s.Length - 1 downto i do
            if s.[i] = s.[j] then
                let mutable n = 1
                while n < j-i && s.[i+n] = s.[j-n] do
                    n <- n + 1
                if n=j-i && n > max then
                    max <- n
                    word <- s.Substring(i, n+1)
                    index <- i

    printfn ">>>%s<<< at index %d" word index

solve s
solve text

Output:

>>>racecar<<< at index 7
>>>ranynar<<< at index 204