/* fpi.c
Pialyzer
Copyright (C) Eric Pepke 2003
Attempts to find a string in the digits of pi. For entertainment
purposes only.
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation version 2.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details. You can find this
at [url]www.gnu.org[/url]
Compiling
fpi.c is written in simple, unassuming ANSI C and should
compile on any compiler worth its salt.
Requires a file called "pi" containing some digits of pi as
ASCII digits '0'-'9' with nothing else (no whitespace, line
breaks, etc.) I use a file with the first 50 million digits
of pi. These are freely downloadable from several sources;
do a quick Web search to find some. This file must be in
the current directory for fpi to find it.
Three constants at the beginning of the program can be
modified.
FN is the name of the file containing the digits.
NDIGITS is the number of digits in the file.
MAXDIFF is the maximum number of different characters.
Values from the size of a typical alphabet (say 32 to
handle 26 letters plus a few punctuation marks) up to
100 are permitted. Lower numbers generally increase
the odds of finding matches, but not always, and not
by much.
PROGNAME is the name of the executable; it's included
as a constant because some systems don't handle argv[0]
properly.
Using
Run the program from the command like, including a single
quoted argument containing the string to look for.
For example, ./fpi "Eric Pepke" finds my name at position
243606.
Algorithm
The algorithm tries to match characters to subsequent pairs
of digits, even- or odd-aligned against a large but not
exhaustive number of possible substitution ciphers. The
number of possible ciphers is MAXDIFF!, but there is also
a reduncancy factor of 100/MAXDIFF. Case is ignored, but
whitespace is significant.
*/
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define FN "pi" /* Name of file with pi, better be NDIGITS */
#define NDIGITS 50000000 /* Number of digits of pi */
#define MAXDIFF 100 /* Max # different characters, up to 100 */
#define PROGNAME "fpi" /* Interactive name of the program */
int main (int argc, char *argv[])
{
char *s; /* String to test */
int sLen; /* Length of s */
char *r; /* Runner for string */
char used[128]; /* Number of times each char is used */
int k;
int n; /* Number of different characters */
FILE *in; /* Input file */
char *buffer; /* Input buffer for pi */
int inputToChar[MAXDIFF]; /* Dynamic mapping of input to result */
/* Legal stuff */
printf("Pialyzer, Copyright (C) 2003 Eric Pepke. ABSOLUTELY NO WARRANTY.\n");
printf("See version 2 of the GNU Public License for detals ([url]www.gnu.org[/url]).\n\n");
/* Check to see if there's an arg */
if (argc != 2)
{
printf("Usage: " PROGNAME " inputString\n", argv[1]);
exit(0);
}
s = argv[1];
/* Reject 0- or 1-length strings, trivial case and might break the alg. */
if (strlen(s) == 1)
{
fprintf(stderr, PROGNAME ": Input string must have at least 2 characters.\n");
exit(2);
}
else
{
sLen = strlen(s);
}
if (sLen > NDIGITS)
{
fprintf(stderr, PROGNAME ": This is ludicrous.\n");
exit(1);
}
/* Make the input buffer */
buffer = malloc(sLen * 2);
if (!buffer)
{
fprintf(stderr, PROGNAME ": Out of memory\n");
exit(1);
}
/* Clear the used array */
for (k = 0; k < 128; ++k) used[k] = 0;
/* Count the characters */
for (r = s; *r; ++r)
{
char c = toupper(*r);
++used[c & 0x7F];
}
n = 0;
for (k = 0; k < 128; ++k)
{
if (used[k])
{
++n;
}
}
/* See if too many different characters */
if (n > MAXDIFF)
{
fprintf(stderr, PROGNAME ": Too many different characters\n");
exit(1);
}
/* Open the file */
in = fopen(FN, "r");
if (in)
{
/* Fill the buffer */
for (k = 0; k < sLen * 2; ++k)
{
buffer[k] = getc(in);
}
/* Now go through the file */
for (; k < NDIGITS; ++k)
{
int i;
/* Clear the input to result array */
for (i = 0; i < MAXDIFF; ++i)
{
inputToChar[i] = '\0';
}
/* Clear the used array */
for (i = 0; i < sLen; ++i)
{
used[toupper(s[i])] = 0;
}
/* Now go through the result */
for (i = 0; i < sLen; ++i)
{
int comb = (buffer[i * 2] - '0') * 10 +
(buffer[i * 2 + 1] - '0');
comb = comb % MAXDIFF;
if (inputToChar[comb] == '\0')
{
if (used[toupper(s[i])])
{
break;
}
inputToChar[comb] = toupper(s[i]);
used[toupper(s[i])] = 1;
}
if (inputToChar[comb] != toupper(s[i]))
{
break;
}
}
if (i >= sLen)
{
printf("String found at position %d\n", k - sLen * 2);
exit(1);
}
/* Shift the buffer and move over. (I know a circular list
would be faster, but I don't care.) */
for (i = 0; i < sLen * 2 - 1; ++i)
{
buffer[i] = buffer[i + 1];
}
/* Read the next digit in the file */
{
int c;
c = getc(in);
if (c < 0)
{
fprintf(stderr, PROGNAME ": Ran off end of file\n");
exit(1);
}
buffer[sLen * 2 - 1] = c;
}
}
fclose(in);
}
else
{
fprintf(stderr, PROGNAME ": Couldn't open %s\n", FN);
}
free(buffer);
}
, for n=2,3,5,6,7,8, etc. is normal.
