Page 2 of 2
Posted: Tue Jan 31, 2012 10:17 am
by 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;
}
Posted: Fri Aug 03, 2012 7:50 pm
by speedfire
Haha no program is necessary, Just 5 minutes on the internet. I was too lazy to write the code
Posted: Thu May 16, 2013 8:31 pm
by 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]
Recursive
Posted: Thu Sep 12, 2013 1:33 pm
by 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.
Posted: Tue Apr 01, 2014 10:25 pm
by 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));
}
}
Posted: Tue Mar 08, 2016 2:16 am
by 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]
Posted: Thu Mar 29, 2018 8:32 pm
by 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++
}