10
\$\begingroup\$

I had fun solving this, so I offer this golf challenge.

The objective of this golf is to find the largest prime number that can be constructed using the given instructions.

You should accept 3x3 grid of single digits as input. (It's up to you how you want to do that, but specify that in your program.)

You can move along the grid orthogonally (left, right, up or down), and as you move, you keep appending the digits you walk across.

E.g.

1 2 3
3 5 6 
1 8 9

Say we start at 1, we can form the number 1236589 but cannot form 15.

You have to evaluate every starting position.

If a prime cannot be found, print -1, else print the prime itself.

Shortest code wins, make sure it runs within 10 secs.

Have Fun!

Edit: Use one position exactly once, in the entire number.

Here's a test case

Input:

1 2 3
4 5 6
7 8 9

Output: 69854123

\$\endgroup\$
  • \$\begingroup\$ I presume we can't repeat positions? \$\endgroup\$ – Keith Randall May 6 '11 at 5:58
  • \$\begingroup\$ No, You cannot. Otherwise it'll be an infinite search :) Sorry, forgot to mention that. Editing. \$\endgroup\$ – st0le May 6 '11 at 6:05
  • \$\begingroup\$ I can haz test cases? \$\endgroup\$ – MtnViewMark May 12 '11 at 3:45
  • \$\begingroup\$ @MtnViewMark, i haz postd testcase, and confirmed your answer aswell. Cheers! :) \$\endgroup\$ – st0le May 12 '11 at 4:00
4
\$\begingroup\$

Haskell, 239 characters

p=2:q[3..]
q=filter(#p)
n#(x:y)=n==x||n`mod`x/=0&&(n`div`x<x||n#y)
(n§m)q=n:maybe[](\i->[q-4,q-1,q+1,q+4]>>=(n*10+i)§filter(/=(q,i))m)(lookup q m)
i=[0,1,2,4,5,6,8,9,10]
main=getLine>>=print.maximum.(-1:).q.(i>>=).(0§).zip i.map read.words

Input is given as a single line of nine numbers:

$> echo 1 2 3  3 5 6  1 8 9 | runhaskell 2485-PrimeGrid.hs
81356321
$> echo 1 2 3  4 5 6  7 8 9 | runhaskell 2485-PrimeGrid.hs
69854123
$> echo 1 1 1  1 1 1  1 1 1 | runhaskell 2485-PrimeGrid.hs
11
$> echo 2 2 2  2 2 2  2 2 2 | runhaskell 2485-PrimeGrid.hs
2
$> echo 4 4 4  4 4 4  4 4 4 | runhaskell 2485-PrimeGrid.hs
-1
\$\endgroup\$
  • \$\begingroup\$ I can confirm your answer :) \$\endgroup\$ – st0le May 12 '11 at 3:59
3
\$\begingroup\$

Python, 286 274 chars

I=lambda:raw_input().split()
m=['']
G=m*4+I()+m+I()+m+I()+m*4
def B(s,p):
 d=G[p]
 if''==d:return-1
 G[p]='';s+=d;n=int(s)
 r=max(n if n>1and all(n%i for i in range(2,n**.5+1))else-1,B(s,p-4),B(s,p+4),B(s,p-1),B(s,p+1))
 G[p]=d;return r
print max(B('',i)for i in range(15))

This does give a deprecation warning for the float argument to range. Ignore it, or spend 5 more chars to wrap int() around it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.