YAPC: Double Acrostics

Weedpacket

http://dictionary.reference.com/search?q=acrostic
Acrostic: A poem or series of lines in which certain letters, usually the first in each line, form a name, motto, or message when read in sequence.

A double acrostic is the same thing - except that the last letters in the lines also form a name, motto, etc.

The double acrostics here are slightly simpler. Each line consists of a single word, the first letters of which (when read in sequence) also form a word, and ditto for the last letters. The length of an acrostic is the number of lines, the width is the number of letters in each line (which is constant).

An example double acrostic of length 5, width 4:
[font=monospace]LAOS
ITLL
GAPE
HERE
TRIP[/font]
The words in the first and last letters being light and sleep. (Yes, I'll accept "itll" - it's "it'll" with the apostrophe removed.)

You should be able to dig up or construct a decent wordlist yourself. "Decent" in this case being on the order of 25,000 distinct entries, and stored as a text file with one word per line.

With your wordlist in hand, write a program that will either generate a double acrostic of given length and width (preferably using different words whenever possible), or declare that there is no such acrostic possible with the given list.

Quickly, please 🙂

onion2k

If you were using MySQL 5, and had the opportunity to use stored SQL procedures..

SET @width = 4;
SET @lword = 'dad';
SET @rword = 'ant';
SET @length = char_length(@lword);
SET @counter = 0;
LOOP
IF @counter > @length THEN
  LEAVE;
ELSE
  #do nothing
END IF
SELECT * FROM `acrostic` WHERE left(word,1) = left(@lword,1) and right(word,1) = left(@rword,1) and char_length(word) = @width order by rand limit 1;
@counter = @counter + 1;
END LOOP;

I've not got MySQL 5 installed so I can't actually test it. Obviously width, lword, and rword would be parametres passed in. The database structure is a single table called "acrostic" with a single column called "word".

Still.. I might have done it in pure SQL.. that has to be both something..

Weedpacket

Originally posted by onion2k
If you were using MySQL 5, and had the opportunity to use stored SQL procedures...

Don't forget the bit where you read in the wordlist. But let's see about doing this in a base PHP install (like all the other programming challenges).

Weedpacket

It's not that difficult a task, is it? 🙂
Given integers length and width and a word list (stored as a text file with one word per line), generate an acrostic of the above form with those parameters, or indicate that nonesuch acrostic can be generated.

Shrike

This sort-of works. It takes GET inputs width and length, then selects all of the words in the input file which are of $width width, randomises the list (just to get different results), then loops through sets of $length words to try and find an double acrostic. It should probably make permutations of the whole list, but that gets hard programatically and causes too much overhead on big lists.

<?php

// This script could get CPU intensive
ini_set("max_execution_time", 300);
ini_set("memory_limit", "20M");

// Check inputs
!isset($_GET['width'])
	and $_GET['width'] = 4;
!isset($_GET['length'])
	and $_GET['length'] = 4;

// Read word file
$wordfile = file('dict.txt');
foreach($wordfile as $w)
{
	$w = chop($w);
	if(strlen($w) == $_GET['width'])
	{
		$words[] = $w;
	}
	// Duplication :?
	if(strlen($w) == $_GET['length'])
	{
		$checklist[] = $w;
	}
}

// Randomise
shuffle($words);

// Make an acrostic word
for($i = 0, $a = sizeof($words); $i < $a; $i++)
{
	if(strlen($words[$i]) != $_GET['width'])
	{
		continue;
	}
	$acrostic1 = $words[$i][0];
	$acrostic2 = $words[$i][strlen($words[$i])-1];
	for($x = 0; $x < $_GET['length']-1; $x++)
	{
		if(strlen($words[$i+1+$x]) != $_GET['width'])
		{
			continue;
		}
		$acrostic1 .= $words[$i+1+$x][0];
		$acrostic2 .= $words[$i+1+$x][strlen($words[$i+1+$x])-1];
	}
	// Check if it's in the dictionary
	if(in_array($acrostic2, $checklist))
	{
		if(in_array($acrostic1, $checklist))
		{
			echo "<p>Found a double acrostic: <b>$acrostic1 $acrostic2</b></p><pre>";
			for($y = $i, $z = $i + $_GET['length']; $y < $z; $y++)
			{
				echo "<p><font size=\"+2\">" , $words[$y] . "<br>&nbsp;<br>&nbsp;</font>";
			}
			echo "</pre>";
			exit;
		}
	}
}

// Failed
echo "<p>Nothing found.</p>";

?>

I used a 17,000 word list of variable length words. Anything up to 4*4 worked quickly, over that the script started to chug but that might be to do with the word list as much as processing time.

Let me know if it breaks horribly 🙂

Weedpacket

Well, here is the program I wrote to judge the feasibility of the problem. The principal feature is the search trie which categorises each word successively by length, first letter and last letter. E.g., "vagabond" would be an element of the array $words[8]['v']['d'], along with "vineyard" and "vanguard". So if I needed an eight-letter word that started with 'v' and ended with 'd', I knew exactly where to look.

The wordlist used contains 24867 entries, where the longest is "electroencephalography".

function letters_only($a)
{
	return preg_replace('![^a-z]!','',$a);
}

$program_start = microtime(true);
$wordlist = preg_grep('!^$!', //killing blank lines
	array_map('letters_only',
		array_map('strtolower',
			file('wordlist.txt'))), PREG_GREP_INVERT);

// Build the table ($words_flat) and search trie ($words)
// Each element of $words_flat is an array of words that are all the same length:
// it is indexed by that length, and used to find candidate left and right words.
// $words breaks that array down further into arrays that are indexed by the
// first letter of the words they contain, then further still into arrays that are
// indexed by the last letter.
$words = array();
$words_flat = array();
foreach($wordlist as $word)
{
	$length = strlen($word);
	$words_flat[$length][] =
	$words[$length][$word{0}][$word{$length-1}][] = $word;
}

// Should probably check these exist, eh?
$length = $argv[1];
$width = $argv[2];

// Obvious impossibilities
if(!isset($words_flat[$length]))
{
	echo "No acrostics of the given length.";
	exit;
}
if(!isset($words_flat[$width]))
{
	echo "No acrostics of the given width.";
	exit;
}

$found = false;
$acrostic = array();
shuffle($words_flat[$length]); // For variety in left and right words
$search_start = microtime(true);
foreach($words_flat[$length] as $left_word)
{
	foreach($words_flat[$length] as $right_word)
	{
		if($right_word==$left_word) continue; //???Do we care about this?
		for($i=0; $i<$length; ++$i)
		{
			if(!isset( $words[$width][$left_word{$i}][$right_word{$i}] )) break;
			$suitable_words = $words[$width][$left_word{$i}][$right_word{$i}];
			$acrostic[$i] = $suitable_words[array_rand($suitable_words)]; // Pick any one
		}
		if($i==$length)
		{
			$found = true;
			break 2;
		}
	}
}
$program_end = microtime(true);
if($found)
{
	echo join("\n",$acrostic),"\n";
}
else
{
	echo "Nonesuch.\n";
}
echo "\nThis program took ",($program_end-$program_start)," seconds\n",
"to produce the above result, of which ",($program_end-$search_start),"\n",
"were spent searching.";

php -f acrostic.php 12 12
southernmost
uniprocessor
pennsylvania
episcopalian
radiophysics
stroboscopic
thoroughfare
indoeuropean
transshipped
indisputable
ombudsperson
northernmost

This program took 1.5061788558959961 seconds
to produce the above result, of which 0.20378994941711426
were spent searching.

Incidentally, it often returned results for a 12x12 double acrostic in less than 1/20 of a second of searching, and occasionally less than 1/50.