TutorialEdge

Challenge 22 - Largest Pandigital Prime

Welcome, everyone to the discussion thread for the 22nd Go challenge posted to the site :tada:

Feel free to show us how you solved the challenge by posting your solutions below!

I dont know why my solution is wrong yet. The number is correct according to my research.
I know it is not the best solution using go. Iโ€™m new on this language.
I also tried not to apply big maths algorithm. Used only simple logic and solutions applied in previous challenges.
According to my research of Problem 41 of Project Euler, the The largest Pandigital prime is 7652413.
My code returns this number, but it does not pass in the test

package main

import (
	"fmt"
	"math"
	"strconv"
)

func LargestPandigitalPrime() int {
  	// finds the greater possible sequence eliminating divisibles by 3
  // I mean, 1..(greater n), where 1+2+3+..+n is not divisble by 3
	sequence := findGreaterSequence()

	if len(sequence) == 0 {
		fmt.Println("It is not possible")
      	return 0
	}

  	// using the sequence get the upper and lower boundaries
  // 1..(greater n) and (greater n) to 1
  // like 123456789 and 987654321
	lowerBound, upperBound := getLowerAndUpperBoundaries(sequence)

  	// decreasing from upper to lower, finding primes and pandigital ones
   	// the bigger found is returned
	greater := findGreaterNumber(lowerBound, upperBound)
	return greater
}

func runeToInt(r rune) int {
	return int(r) - '0'
}

func intToRune(n int) rune {
	return rune(n) + '0'
}

func isPrime(n int) bool {
	return len(CheckFactors(n)) == 2
}

// used int exercide Even and Odds factors
// could be optimized just returning false when found a factor
func CheckFactors(num int) []int {
	factors := []int{1, num}
	limit := int(math.Ceil(float64(num) / 2))
	for i := 2; i <= limit; i++ {
		if num%i == 0 {
			factors = append(factors, i)
		}
	}
	return factors
}

func isEven(n int) bool {
	return n%2 == 0
}

// Pandigital must have only one digit from 1..(size(n))
func isPandigital(n int) bool {
	str := fmt.Sprint(n)
	size := len(str)
	charMap := make(map[rune]int)

	for _, char := range str {
      // does have digit out of range from 1..(size(n))
		if runeToInt(char) > size {
			return false
		}

      // does have repeated digit
		if _, ok := charMap[char]; ok {
			return false
		}
		charMap[char] = 1

    }
	return true
}

func findGreaterNumber(lower int, upper int) int {
	for i := upper; i > lower; i-- {
		if !isEven(i) && isPandigital(i) && isPrime(i) {
			return i
		}

	}
	return 0
}

// eliminates number divisible by 3
func findGreaterSequence() []int {
	bigger := "123456789"

	for len(bigger) > 0 {
		sum, sequence := sumNumbers(bigger)
		if sum%3 != 0 {
			return sequence
		}
      	// removes the bigger digit from sequence
		bigger = bigger[0 : len(bigger)-1]
	}
	return []int{}

}

// sum the digits of a string returning the sum and all digits
func sumNumbers(s string) (int, []int) {
	sum := 0
	var sequence []int
	for _, r := range s {
		number := runeToInt(r)
		sum += number
		sequence = append(sequence, number)
	}
	return sum, sequence
}

func getLowerAndUpperBoundaries(seq []int) (int, int) {
	size := len(seq)
	min := make([]rune, size, size)
	max := make([]rune, size, size)
	for i := 0; i < size; i++ {
		r := intToRune(seq[i])
		min[i] = r
		max[size-i-1] = r
	}

	minValue, _ := strconv.ParseInt(string(min), 10, 0)
	maxValue, _ := strconv.ParseInt(string(max), 10, 0)

	return int(minValue), int(maxValue)
}

func main() {
    fmt.Println("Pandigital Primes")

    pandigitalPrime := LargestPandigitalPrime()
    fmt.Println(pandigitalPrime)
  
  	//7652413
}

Iโ€™ve just taken a look, there was a typo in the challenge tests which Iโ€™ve just pushed a fix for to the main branch for the site!

I seriously appreciate you highlighting this as it helps the site and the community! :muscle:

One slight improvement I would make is handling the ParseInt error value as itโ€™s good practice to keep checking these errors. Other than that it is a solid implementation!

1 Like

this is No.41 problem in Project Euler: https://projecteuler.net , I reference one solution from jmoiron

package main

import (
	"fmt"
	"math"
	"strconv"
)

func notPrime(n int) bool {
	if n&2 == 2 {
		return false
	}
	if (n-1)%6 == 0 {
		return false
	}
	if (n+1)%6 == 0 {
		return false
	}
	return true
}

func isPrime(n int) bool {
	if notPrime(n) {
		return false
	}
	max := int(math.Ceil(math.Sqrt(float64(n))))
	for i := int(3); i < max; i += 2 {
		if n%i == 0 {
			return false
		}
	}
	return true
}

func atoi(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}

func permute(s string) []string {
	if len(s) == 1 {
		return []string{s}
	}

	perms := []string{}
	head := string(s[0])
	tail := s[1:]

	for _, perm := range permute(tail) {
		for i := 0; i < len(s); i++ {
			newperm := perm[:i] + head + perm[i:]
			perms = append(perms, newperm)
		}
	}
	return perms
}

func LargestPandigitalPrime() int {
	max := 0
	digits := "7654321"
	for i := 0; i < len(digits); i++ {
		for _, perm := range permute(digits[i:]) {
			i := atoi(perm)
			if isPrime(i) {
				if i > max {
					max = i
				}
			}
		}
		if max > 0 {
			break
		}
	}
	return max
}

func main() {
    fmt.Println("Pandigital Primes")

    pandigitalPrime := LargestPandigitalPrime()
    fmt.Println(pandigitalPrime)
}