A Repeat of Pi

[aurora]

i used php, which is pretty inefficient in such things. however i started three instances of my script and it did the job without taking too much time:

Code: Select all

#!/usr/bin/env php
<?php

if ($argc < 3 || $argv[1] > $argv[2]) {
    die("usage: $0 start stop [start-len]\nexample: $0 1 4\n");
}

$start = $argv[1];
$end   = $argv[2];

$txt = file_get_contents('pi1000000.txt');
$seq = '';
$len = (isset($argv[3]) ? $argv[3] : 7);

while (true) {
    $rpt = 0;

    for ($i = $start; $i <= $end; ++$i) {
        $offset = 0;

        while (($pos = strpos($txt, (string)$i, $offset)) !== false) {
            $seq = substr($txt, $pos, $len);

            if (substr_count($txt, $seq, $pos) > 1) {
                ++$rpt;
                print "$seq\n";

                if ($rpt > 1) {
                    break(2);
                }
            }

            $offset = $pos + 1;
        }
    }

    if ($rpt <= 1) break;

    ++$len;
}

[speedfire]

Haha no program is necessary, Just 5 minutes on the internet. I was too lazy to write the code

[egj]

Splitted pi into substrings and sorted them with a mergesort algorithm I had lying around from school. Then just checked the following value.
Changed the lenght of the substrings manually as I was just trying and got it right immediatly
Takes under 1 Sec (Without Mergesort it takes way longer)

Code: Select all

import java.io.File;
import java.util.Scanner;

public class ARepeatOfPi {
    public static void main(String[] args) throws Exception{
        String Pi = new Scanner( new File("PATH TO PI.TXT") ).useDelimiter("\\A").next();
        int n=12;
        long[] Piss = new long[Pi.length()-n];
        for (int i=0;i<Piss.length;i++){
            Piss[i]= Long.parseLong(Pi.substring(i,i+n));
        }
        mergesort(Piss,0,Piss.length-1);
        System.out.println(check(Piss,n));
    }
    public static long check(long[] Piss, long n){
        for (int i=0;i<Piss.length-1;i++){
            if (Piss[i]==Piss[i+1]){
                return Piss[i];
            }
        }
        return 0;
    }
    public static void merge(long A[] ,int p, int q, int r) {
        int n1, n2;
        n1=q-p+1;
        n2=r-q;
        long L[]=new long[n1+1];
        long R[]=new long[n2+1];

        for (int i=0; i<n1; i++) L[i] = A[p + i];
        for (int j=0; j<n2; j++) R[j] = A[q + j + 1];

        L[n1]=Long.MAX_VALUE;
        R[n2]=Long.MAX_VALUE;
        int i=0;
        int j=0;
        for (int k=p;k<=r;k++) {
            if (L[i]<=R[j]) {
                A[k]=L[i];
                i=i+1;
            }
            else {
                A[k]=R[j];
                j=j+1;
            }
        }
    }

    public static void mergesort(long A [], int p, int r) {
        if (p<r) {
            int q= (p+r)/2;
            mergesort(A,p,q);
            mergesort(A,q+1,r);
            merge(A,p,q,r);
        }
    }
}

[/code]

[Nudin]

I used a recursive DFS algorithm:

Code: Select all

#!/usr/bin/env python3
import os

file=open("pi_1mio1.txt", "r")
pi=file.read()

# random small startvalue
lengrecord=3
longest="123"

def search(start,leng):
 global lengrecord, longest
 if leng > lengrecord:
   lengrecord=leng
   longest=start
 for i in range(0,10):
   i = str(i)
   erste = pi.find(start+i)
   if erste != -1:
      if pi.find(start+i,erste+1) != -1:
         search(start+i,leng+1)

start="9"
search(start,3)
print("Longest:"+longest)

I started this 10 times with different start values (0-9) to have it running on multiple CPUs parallel. On my PC it took about 10 minutes.

[Hippo]

I did this: (I originally used maxdepth above 100, reducing speeded things up )

Code: Select all

public class pi {

	int[] succ = new int[10];
	int back;
	static short maxdepth = 13;

	/**
	 * finds longest repeated substring
	 */
	public static void repeated() {
		pi aho [] = new pi[piDigits.length()*maxdepth];
		//write("pi_rep.txt",words[maxind]);
		aho[0] = new pi(0);
		int root = 0, currdepth = 0, nextAlloc=1;
		int updpath[] = new int[maxdepth];
		int bestmatch=0, besti=0;
		for(int i=0;i<piDigits.length();i++) {
			int dig="0123456789".indexOf(piDigits.charAt(i));
			if (currdepth==maxdepth) {
				root=aho[root].back;
				currdepth--;
			}
			int upd=root, upddepth=currdepth;
			while ((upddepth>0)&&(aho[upd].succ[dig]==0)) {
				updpath[upddepth]=upd;
				upd=aho[upd].back;
				upddepth--;
			}
			if (upddepth>bestmatch) {
				bestmatch=upddepth;
				System.out.printf("New best depth "+bestmatch+" at "+i+"\n");
				besti=i;
			}
			int back=aho[upd].succ[dig];
			if (back==0) {// we are at root
				aho[nextAlloc] = new pi(0);
				aho[upd].succ[dig]=back=nextAlloc++;
			}
			upddepth++;
			while (upddepth<=currdepth) {
				aho[nextAlloc] = new pi(back);
				aho[updpath[upddepth++]].succ[dig]=back=nextAlloc++;
			}
			root=back;currdepth++;
		}
		write("pi_Rep.txt",piDigits.substring(besti-bestmatch,besti+1));		
	}
}

[Napoleon]

Maybe a tad late. But here's my solver. I just used regex. Took about 10 mins I think

Code: Select all

import re
import time
import multiprocessing
import json
import os
with open('pi1000000.txt') as f:
	pi = f.read();

def log(text):
	with open('log_speed.txt', 'a', encoding='utf-8') as file:
		file.write(text);
	print(text);

def writeStatus(number,status):
	with open('log_speed_'+str(number)+'.txt', 'a', encoding='utf-8') as file:
		if(os.stat('log_speed_'+str(number)+'.txt').st_size == 0):
			file.write(json.dumps(status));

def check(number):
	try:
		with open('log_speed_'+str(number)+'.txt', 'r') as f:
			return json.loads(f.read());
	except FileNotFoundError:
		return {'found':False};
	
def search(longd,indexs,last):
	count = 0;
	index = 0;
	while(1):
		if(check(longd)['found']):
			longd +=1;
		if(longd > 12):
			break;
		search	= 	pi[(index+indexs):(longd+index+indexs)];
		p 			= 	re.compile('('+search+')', re.MULTILINE);
		results	= 	re.findall(p, pi);

		if(len(search) <= 0):
			print("Search: '"+(search)+"', index:"+str(index)+", stop:"+str(last)+", longd: "+str(longd));
		
		if(len(results)>=2):
			log("Searched for:\n\t"+search+"\nFound "+str(len(results))+" matches.. Continuing.. \n-------------------------\n");
			writeStatus(longd,{'found':True,'number':search});
			longd +=1;
			index = 0;
			count = 0;
		else:
			if((index+indexs) >= last):
				log("\nFinished searching everything, for length: "+str(longd)+"\n");
				index =0;
				longd +=1;
				count =0;
			count+=1;
			index+=1;
			if(count%100==0):
				print(str(longd)+" -- Nothing found, shifting index to "+str(index+indexs)+"...\n");
if __name__ == '__main__':
	jobs = []
	for i in range(8):
		longd = 1;
		p = multiprocessing.Process(target=search, args=(longd,int((len(pi)/9)*i),int((len(pi)/9)*(i+1)),));
		jobs.append(p)
		p.start()

[/code]

[Grusewolf]

This is my solution in groovy. It calculated 13 min

Code: Select all

String pi = new File("Pi_1Mio.txt").text
int max = pi.size()
int len = 1
int index = 0
while(index+len < max) {
    while(true) {
        int s = pi[index..<max].findAll(pi[index..<index+len]).size()
        if(s > 1) {
            println "${pi[index..<index+len]} - $s  -  $len  -  $index"
            len++
        }
        else {
            break
        }
    }
    index++
}