8
\$\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\$
  • 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 '14 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 '14 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 '14 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 '14 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 '14 at 22:42
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\$
  • 1
    \$\begingroup\$ Thanks to you I shaved almost as many answer as you used :P \$\endgroup\$ – user8777 Jan 16 '14 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\$ – Peter Taylor Jan 16 '14 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\$
  • 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 '14 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 '14 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 '14 at 6:04
  • \$\begingroup\$ Saves one more, thanks :) \$\endgroup\$ – user8777 Jan 16 '14 at 6:05
  • \$\begingroup\$ Switching to all and bracketing the (`x`in`N`) Saves a few more too! \$\endgroup\$ – user8777 Jan 16 '14 at 6:08
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\$
  • \$\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 '14 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 '14 at 3:11
  • \$\begingroup\$ Kyle, Very good observation! \$\endgroup\$ – DavidC Jan 17 '14 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\$
  • 3
    \$\begingroup\$ Care to explain the process behind this for those who don't do Haskell? \$\endgroup\$ – user8777 Jan 17 '14 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\$ – Vektorweg Jan 18 '14 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\$ – Vektorweg Jan 18 '14 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\$ – Vektorweg Jan 18 '14 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\$
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\$
  • \$\begingroup\$ Care to explain the process behind this for those who don't do Mathematica? \$\endgroup\$ – user8777 Jan 17 '14 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 '14 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 '14 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\$ – Michael Stern Jan 17 '14 at 22:19
  • \$\begingroup\$ But I'm counting characters, not bytes. Please explain. \$\endgroup\$ – DavidC Jan 17 '14 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\$

Your Answer

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