10
\$\begingroup\$

In fairness, this is based on a StackExchange question - but its a good question.

The challenge is fairly simple:

  1. Take a string of numerals
  2. Find and print the largest contiguous prime number in the string

Scoring:

  • Lowest number of characters wins.
  • Victor will likely be a golfscript entry but we won't hold that against them, cause we all have fun and learn things, right.
  • Winner we be awarded when I notice that I haven't actually ticked the green button.

Assumptions:

  • The string is only numbers
    • If the string contains letters, you may have undefined behaviour
  • The string contains at least 1 prime
    • If the string does not contains 1 valid prime number, you may have undefined behaviour
  • Speed is not a constraint
    • Use a shorter prime algorithm over a faster one.
    • If your entry eventually finishes, thats ok, just make sure it will provable happen before the heat death of the universe.
  • The length of the string can be assumed less than 15 characters long

For example:

>> Input:  3571
<< Output: 3571

>> Input:  123
<< Output: 23

>> Input:  1236503
<< Output: 236503

>> Input:  46462
<< Output:  2

>> Input:  4684
<< Output: ValueError: max() arg is an empty sequence

>> Input:  460
<< Output: 0   # Note, zero is not a prime, but the above string has no valid prime

>> Input:  4601
<< Output: 601

>> Input:  "12 monkeys is a pretty good movie, but not as good as se7en"
<< Output: ValueError: Fight Club was also good, I find Brad Pitt to be a consistantly good actor.

Possible implementations:

  1. Find all substrings of the input, check if they are prime. - Legostormtroopr (original)
  2. Find all integers less than input, check if they are in the input then check if it is prime - Ben Reich
  3. Take a list of all primes less than the input, check if it is in the input - daniero
\$\endgroup\$
11
  • 1
    \$\begingroup\$ This seems basically like: find a way of iterating over each substring of the string, and check the primality of the substring. Sounds like a fun problem. \$\endgroup\$
    – Justin
    Jan 16, 2014 at 4:43
  • 1
    \$\begingroup\$ @Quincunx Correct. But I wanted to make it as unambiguous as possible. And also drop pop-culture references. \$\endgroup\$
    – user8777
    Jan 16, 2014 at 4:46
  • 1
    \$\begingroup\$ @Quincunx That's not the only possible algorithm, though! Check out my answer, which can be described as: Iterate over all integers less than the input, and determine the largest one that is both a substring of the input and is prime. \$\endgroup\$
    – Ben Reich
    Jan 16, 2014 at 5:32
  • \$\begingroup\$ @BenReich Or as I did, iterate over all primes less than or equal to the input in and see of they are in the string. \$\endgroup\$
    – daniero
    Jan 16, 2014 at 14:30
  • 1
    \$\begingroup\$ Why do I care about an even playing field? We know which scripts win, but winning isn't everything? Make the shortest, cleverest code possible you can in your favourite language. \$\endgroup\$
    – user8777
    Jan 16, 2014 at 22:42

17 Answers 17

6
\$\begingroup\$

GolfScript 40 37

.{`\`?)}+\~),\,{.,(;\{\%!}+,,1=},)\;

This looks at all numbers less than or equal to the the input, filters down to the ones that are substrings of the input, and then filters further down to the primes. Then, it takes the largest such element (which is obviously guaranteed to have the most digits).

Let's break it down into two main sections:

.{`\`?)}+\~,\,

This part of the code filters down to all integers string contained in the input. It uses grave accent to turn numbers into strings, and then ? to determine the index of the substring. Since ? returns -1 in the case of no containment, increment using ) so that the output is 0 for non-substrings, which will behave nicely with the , filtering.

{.,(;\{\%!}+,,1=},

This part of the code filters down to the primes by counting the number of factors less than the given number (an integer is a factor only if number factor %! is 1. A prime number will have exactly 1 factor strictly less than itself, so do 1=.

Since the numbers are in order, take the last one and clear the stack using )\;

This obviously isn't as efficient as possible (since it somewhat unnecessarily iterates over all integers less than the input), but it still terminates with big input like 1236503 relatively quickly on my computer (1 minute).

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Thanks to you I shaved almost as many answer as you used :P \$\endgroup\$
    – user8777
    Jan 16, 2014 at 5:25
  • 1
    \$\begingroup\$ If the input is a prime then this won't find it, because the first filter is applied to numbers up to but not including it. The fix costs one character, but there are two characters to be saved by storing the input in a variable rather than concatenating with the block (because that way you eliminate some flips). \$\endgroup\$ Jan 16, 2014 at 14:29
4
\$\begingroup\$

Python 2.7 - 84

Here is a reference implementation to beat, I used it for the example output in the question, so its gauranteed to work * Not an actual guarantee

Shameless improvement based on Ben Reich's much better solution than my original one. With major assistance from Volatility

N=input()
print max(x for x in range(N+1)if(`x`in`N`)&all(x%i for i in range(2,x)))

Prior incantations of the second line include:

print max(x for x in range(N+1)if`x`in`N`and 0 not in(x%i for i in range(2,x)))
print max(x for x in range(N+1)if`x`in`N`and sum(x%i<1 for i in range(2,x))<1)

The original version - 143

N=`input()`
p=lambda n:[n%i for i in range(2,n)if n%i==0]
print max(int(N[j:i])for i in range(len(N)+1)for j in range(i)if not p(int(N[j:i])))
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Get rid of p and replace not p(x) with sum(x%i for i in range(2,x))<1 - it should work and gets you down to 86 chars. \$\endgroup\$
    – Volatility
    Jan 16, 2014 at 5:32
  • \$\begingroup\$ @Volatility Not quite, sum(x%i for i in range(2,x)) will be quite high for most numbers. But the generator is a great idea and I got it to 91. \$\endgroup\$
    – user8777
    Jan 16, 2014 at 5:55
  • \$\begingroup\$ Actually, you know what, I think you can use all(x%i for i in range(2,x)) instead. \$\endgroup\$
    – Volatility
    Jan 16, 2014 at 6:04
  • \$\begingroup\$ Switching to all and bracketing the (`x`in`N`) Saves a few more too! \$\endgroup\$
    – user8777
    Jan 16, 2014 at 6:08
2
\$\begingroup\$

Vyxal G, 4 bytes

ǎ⌊~æ

Try it Online! Link includes test cases.

Input as a string. Add the flag if you want input as a number.

Explanation

ǎ⌊~æ  # Implicit input
ǎ     # Substrings
 ⌊    # Cast to integer
  ~   # Filtered by
   æ  # Is prime
      # G flag gets maximum
      # Implicit output
\$\endgroup\$
1
\$\begingroup\$

Ruby 61

Take all primes up to N and see if they are in the string

require'prime'
p Prime.each(gets.to_i).select{|i|~/#{i}/}.max

I think this only works on Ruby 1.9 and newer, but I'm not sure.

\$\endgroup\$
3
  • \$\begingroup\$ What does your program return for the last test example? The prime, 2, is in it, but should not be recognized (if I understand the requirements correctly). \$\endgroup\$
    – DavidC
    Jan 17, 2014 at 2:27
  • 1
    \$\begingroup\$ @DavidCarraher: Assumptions: The string is only numbers; If the string contains letters, you may have undefined behaviour I think that "undefined behaviour" means that it could spit out 2 or it could spit out mush \$\endgroup\$
    – Kyle Kanos
    Jan 17, 2014 at 3:11
  • \$\begingroup\$ Kyle, Very good observation! \$\endgroup\$
    – DavidC
    Jan 17, 2014 at 3:29
1
\$\begingroup\$

Scala (83 chars)

I wasn't sure how to provide inputs to the program so I considered n is the input. Here's the actual solution (based on which the solution length is evaluated). Below that is an executable form of the solution (which isn't golfed yet) for execution along with the output (for the samples give OP has).

Solution:

n.inits.flatMap(_.tails.toList.init.map(BigInt(_))).filter(_ isProbablePrime 1).max

Executable solution:

object A {
  def main(x:Array[String])=List("3571","123","23","1236503","46462","4684","460","4601","12 monkeys..").foreach(e=>println(e+" => "+q(e)))

  private def p(n: String)=n.inits.flatMap(_.tails.toList.init.map(BigInt(_))).filter(_ isProbablePrime 1).max
  private def q(n: String)=try p(n)catch{case e=>e.toString}
}

Sample output:

3571 => 3571
123 => 23
23 => 23
1236503 => 236503
46462 => 2
4684 => java.lang.UnsupportedOperationException: empty.max
460 => java.lang.UnsupportedOperationException: empty.max
4601 => 601
12 monkeys.. => java.lang.NumberFormatException: For input string: "12 "

Explanation:

Steps are pretty straight forward.

input -> Find all substrings -> filter non primes -> find longest value

  • main(Array[String]): Method provides sample input and executes method q(String) for each input
  • q(String): Wraps actual program logic from p(String) so any exceptions are appropriately reported. Helps in formatting the output better because invalid inputs are going to get NumberFormatExceptions where as the lack of a prime will throw an UnsupportedOperationException
  • p(String): Actual logic of the program. Let's split the explanation for this into parts
    • n.inits: Creates an Iterator to iterate over the String input (n)
    • flatMap(f): Applies an operation on the Iterator and pushes the result into a List
      • _.tails.toList.init.map(BigInt(_)): Splits the String and removes empty Strings from the resultant List. Finally converts the String to a BigInt which is an equivalent of java.math.BigInteger. For golfing reasons, BigInt is selected (shorter name).
    • filter(f): if f returns false, the value is removed from the resultant List
      • _ isProbablePrime 1: This line could have been written as _.isProbablePrime(1) but the representation used saves 1 byte. This line actually checks if the value is a prime (probabilistically; since certainty is set to 1, execution time goes up but the system makes certain (more or less) that the number is a prime.
    • max: Finds the maximum value (not String based length. Actual max value)
\$\endgroup\$
1
\$\begingroup\$

J (24 22)

Reading from the keyboard is actually shorter than defining a function.

>./(*1&p:);".\.\1!:1[1

Test:

   >./(*1&p:);".\.\1!:1[1
3571
3571
   >./(*1&p:);".\.\1!:1[1
46462
2
   >./(*1&p:);".\.\1!:1[1
1236503
236503
   >./(*1&p:);".\.\1!:1[1
4684
0
   >./(*1&p:);".\.\1!:1[1
4680
0
   >./(*1&p:);".\.\1!:1[1
twelve monkeys is a pretty good movie
__

Explanation:

  • 1!:1[1: read a line of text from the keyboard
  • ".\.\: the evaluation (".) of each suffix (\.) of each prefix (\) of the string.
  • ;: flatten the matrix
  • *1&p:: multiply each value by whether it is a prime or not (so all nonprimes will be zero)
  • >./: get the largest value in the list
\$\endgroup\$
1
\$\begingroup\$

Haskell, 94

main=getLine>>=print.maximum.filter(\x->and$map((0/=).mod x)[2..x-1]).map read.init.scanr(:)[]

\$\endgroup\$
4
  • 3
    \$\begingroup\$ Care to explain the process behind this for those who don't do Haskell? \$\endgroup\$
    – user8777
    Jan 17, 2014 at 2:07
  • \$\begingroup\$ @LegoStormtroopr Sure, i try it. main = getLine >>= print . maximum . filter isPrime . map read . allNums is the original form. it gets a line and gives it (>>=) to the big combined function - combined with the . infix operator, who simply puts the result of the right function to the left function. things like (\x -> ...) are lambda expressions. function parameters are applied without parenthesis and functions can be partially applied ((0/=) for example is a function, that checks if a number is not 0). \$\endgroup\$
    – vek
    Jan 18, 2014 at 1:42
  • \$\begingroup\$ allNums = init . scanr (:) []. scanr scans and init removes the last value of the result of scanr, which is an empty string, that cant be read to a Integer. map read reads a list of strings to its destinated values. in this case Integer or something else from the Integral typeclass, because isPrime need a Integral. filter isPrime does exactly, what it says. isPrime x = and $ map ((0/=). mod x) [2..(x-1)] means, given a list from 2 to (x-1), make the division check and then apply and to the Bool list. \$\endgroup\$
    – vek
    Jan 18, 2014 at 1:43
  • \$\begingroup\$ there are some more clear and powerful functions in other standard modules, but i tried to work with the Prelude module only. ;) \$\endgroup\$
    – vek
    Jan 18, 2014 at 1:47
1
\$\begingroup\$

Perl 6 (40 characters, 41 bytes)

$_=get;say max grep &is-prime,+«m:ex/.+/

First get input into $_, this makes the regex match call shorter. :ex gives exhaustive matching for regex, it will give all possibilities. The hyper op (or +<< works too) will make numbers out of the Match objects, those are passed to grep with &is-prime sub as selector. Finally take the maximum of the remaining list and output it.

\$\endgroup\$
1
\$\begingroup\$

Jelly, 6 bytes

DẆḌẒƇṀ

Try it online!

Takes input as an integer. If input must be a string, then 7 bytes. Returns 0 for numbers with no primes in them.

How it works

DẆḌẒƇṀ - Main link. Takes n on the left
    Ƈ  - Find...
     Ṁ - ...the largest...
 Ẇ     - ...contiguous...
  ḌẒ   - ...prime...
D      - ...in a string

or, alternatively,

DẆḌẒƇṀ - Main link. Takes n on the left
D      - Convert n to digits
 Ẇ     - Get all contiguous sublists
  Ḍ    - Convert each back from digits
    Ƈ  - Filter keep:
   Ẓ   -   Primes
     Ṁ - Yield the maximum
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 5 bytes

Œʒp}Z

Try it online!

Explanation

Œʒp}Z  # Implicit input
Π     # Substrings
 ʒ }   # Filtered by
  p    # Is prime
    Z  # Maximum
       # Implicit output
\$\endgroup\$
1
\$\begingroup\$

PowerShell, 170 bytes

I'm sure there is a better way of doing this...

$v.count..1|%{
	$d=$_
	0..(-$d+$v.count)|%{
		$n=$v[$_..($_+$d-1)]-join""
		$a=@()
		1..[math]::sqrt($n)|%{$a+=$_,($n/$_)*!($n%$_)}
		if($a.count-eq2){$b+=$n}
	}
}

$b[0]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Mathematica 67 47

StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&

Explanation

The code is a pure function. It has no name. In it, # represents the full input string.

StringCases takes the input, #, and checks for substrings, a, of one character or more (that's why __ was used instead of _) that are primes; PrimeQ must return True for the substring.

All the favorable cases, i.e. the substrings that are primes, are by default returned in a list. 〚1〛, or [[1]] takes the first part, that is, the first element of that list of primes. element[[1]] is shorthand for Part[element, 1]. If there is more than one prime, the first one will be the longest prime (StringCases checks the longest substrings first).

Examples

StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&["1236503"]

"236503"

StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&/@ 
{"1236503", "123", "46462", "4684", "460", "4601", 
"12 monkeys is a pretty good movie, but not as good as se7en"}

{"236503", "23", "2", {}[[1]], {}[[1]], "601", "2"}

\$\endgroup\$
5
  • \$\begingroup\$ Care to explain the process behind this for those who don't do Mathematica? \$\endgroup\$
    – user8777
    Jan 17, 2014 at 2:07
  • 1
    \$\begingroup\$ I must say that usage of 〚1〛 characters was sadistic on us, non-mathematica, programmers. (cue me frantically worried that I'm going blind, then looking at other brackets with confusion that they look sharp, while this one isn't!) \$\endgroup\$
    – eithed
    Jan 17, 2014 at 17:01
  • \$\begingroup\$ 〚1〛has double brackets and is equivalent to [[1]]. I used them because a double bracket counts as a single character. \$\endgroup\$
    – DavidC
    Jan 17, 2014 at 17:06
  • \$\begingroup\$ @David Carraher Yeah, but I think you have to count it as two bytes so it doesn't really save you anything. \$\endgroup\$ Jan 17, 2014 at 22:19
  • \$\begingroup\$ But I'm counting characters, not bytes. Please explain. \$\endgroup\$
    – DavidC
    Jan 17, 2014 at 23:01
0
\$\begingroup\$

Perl 6 (50 characters, 51 bytes)

say max +«get.match(/(.+)<?{(+$0).is-prime}>/,:ex)

maps strings to numbers, max gets the biggest number, get receives a line. /(.+)<?{(+$0).is-prime}>/ is a regular expression that gets all primes <?{}> is a code assertion. is-prime is Int class method which checks if number is a prime. I need to cast value to number by using +, because it's Str by default. :ex means that it tries to find ALL matches (including those where overlap others). Because of Rakudo Perl bug, it's currently impossible to use m// here.

This works for any number, and if you remove max (or replace it with sort) you will get list of all primes in the number, for extra bonus (not that this gives points, or anything). For example (with sort in this case):

1234567890
2 3 5 7 23 67 89 4567 23456789
\$\endgroup\$
0
\$\begingroup\$

Japt -h, 6 bytes

ã f_°j

Try it

\$\endgroup\$
0
\$\begingroup\$

Husk, 6 bytes

→fṗmrQ

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Arturo, 50 bytes

$[s][last select..1do s'x->∧prime? x in?~"|x|"s]

Try it

\$\endgroup\$
0
\$\begingroup\$

PARI/GP, 212 bytes

Try it online!

ss(s,n,m)=concat(Vec(s)[n..n+m-1])
ivn(s)={my(v=Vecsmall(s));for(i=1,#s,if(v[i]<48||v[i]>57,return(0)));1}
ips(s)={my(l=#s);for(i=1,l,for(j=1,i,my(st=ss(s,j,l+1-i));if(ivn(st)&&isprime(eval(st)),return(st))));""}

         

Ungolfed version

substring(s,n,m)=concat(Vec(s)[n..n+m-1])
is_valid_number(s) = {
  my(vec_s = Vecsmall(s));
  for (i = 1, #s, if (vec_s[i] < 48 || vec_s[i] > 57, return(0)));
  return(1);
}
is_prime_string(s) = {
  my(len = #s);
  for (i = 1, len,
    for (j = 1, i,
      my(substr = substring(s, j, len+1-i));
      if (is_valid_number(substr) && isprime(eval(substr)), return(substr));
    )
  );
  return("");
}
strings = ["1236503", "123", "46462", "4684", "460", "4601","12 monkeys is a pretty good movie, but not as good as se7en"];
ans = vector(#strings, i, is_prime_string(strings[i]))
print(ans)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.