Distinct palindromes within decimal numbers
(Redirected from Distinct Palindromes within decimal numbers)
Find all distinct palindromes contained as substrings in decimal representation of n. Note that for the purpose of the initial function, a single digit will be considered a palindrome.
Distinct palindromes within decimal numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- Task
- Find all the palindromes including single digits in the integers from 100 to 125, inclusive.
- Determine which if any of the following decimal integers contain palindromes of 2 digits or more:
9, 169, 12769, 1238769, 123498769, 12346098769, 1234572098769, 123456832098769, 12345679432098769, 1234567905432098769, 123456790165432098769, 83071934127905179083, 1320267947849490361205695
- Also see
-
- OEIS entry: A262188 (Task 1).
- OEIS entry: A151997 (Task 2).
Related tasks
Palindrome_detection
Longest_palindromic_substrings
N_1's_followed_by_a_3
C++
#include <algorithm>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <set>
#include <string>
#include <vector>
bool has_significant_strings(const std::set<std::string>& strings) {
for ( const std::string& string : strings ) {
if ( string.length() > 1 ) {
return true;
}
}
return false;
}
std::set<std::string> all_palindromes(const std::string& number) {
std::vector<std::string> substrings{ };
for ( uint32_t i = 0; i < number.length(); ++i ) {
for ( uint32_t j = 1; j <= number.length() - i; ++j ) {
substrings.emplace_back(number.substr(i, j));
}
}
std::set<std::string> palindromes{ };
for ( std::string substring : substrings ) {
const std::string substring_copy = substring;
std::reverse(substring.begin(), substring.end());
if ( substring == substring_copy ) {
palindromes.insert(substring);
}
}
return palindromes;
}
int main() {
std::cout << "Number Palindromes" << std::endl;
for ( uint32_t i = 100; i <= 125; ++i ) {
std::set<std::string> palindromes = all_palindromes(std::to_string(i));
std::cout << i << " ";
for ( const std::string& palindrome : palindromes ) {
std::cout << std::setw(5) << palindrome;
}
std::cout << std::endl;
}
const std::vector<std::string> numbers = { "9", "169", "12769", "1238769", "123498769", "12346098769",
"1234572098769", "123456832098769", "12345679432098769", "1234567905432098769",
"123456790165432098769", "83071934127905179083", "1320267947849490361205695" };
std::cout << "\nNumber Has no >= 2 digit palindromes" << std::endl;
for ( const std::string& number : numbers ) {
const bool none = ! has_significant_strings(all_palindromes(number));
std::cout << std::left << std::setw(26) << number
<< std::setw(1) << std::boolalpha << none << std::endl;
}
}
- Output:
Number Palindromes 100 0 00 1 101 0 1 101 102 0 1 2 103 0 1 3 104 0 1 4 105 0 1 5 106 0 1 6 107 0 1 7 108 0 1 8 109 0 1 9 110 0 1 11 111 1 11 111 112 1 11 2 113 1 11 3 114 1 11 4 115 1 11 5 116 1 11 6 117 1 11 7 118 1 11 8 119 1 11 9 120 0 1 2 121 1 121 2 122 1 2 22 123 1 2 3 124 1 2 4 125 1 2 5 Number Has no >= 2 digit palindromes 9 true 169 true 12769 true 1238769 true 123498769 true 12346098769 true 1234572098769 true 123456832098769 true 12345679432098769 true 1234567905432098769 true 123456790165432098769 true 83071934127905179083 true 1320267947849490361205695 false
Factor
USING: formatting io kernel math math.ranges present prettyprint
sequences sequences.extras sets ;
: dpal ( n -- seq )
present all-subseqs members [ dup reverse = ] filter ;
! task 1
"Number Palindromes" print
100 125 [a..b] [ dup pprint bl bl bl bl bl dpal . ] each nl
! task 2
"Number Has no >= 2 digit-palindromes?" print
{ 9 169 12769 1238769 123498769 12346098769 1234572098769
123456832098769 12345679432098769 1234567905432098769
123456790165432098769 83071934127905179083
1320267947849490361205695 }
[ dup dpal [ length 2 < ] reject empty? "%-25d %u\n" printf ]
each
- Output:
Number Palindromes
100 { "1" "0" "00" }
101 { "1" "0" "101" }
102 { "1" "0" "2" }
103 { "1" "0" "3" }
104 { "1" "0" "4" }
105 { "1" "0" "5" }
106 { "1" "0" "6" }
107 { "1" "0" "7" }
108 { "1" "0" "8" }
109 { "1" "0" "9" }
110 { "1" "0" "11" }
111 { "1" "11" "111" }
112 { "1" "2" "11" }
113 { "1" "3" "11" }
114 { "1" "4" "11" }
115 { "1" "5" "11" }
116 { "1" "6" "11" }
117 { "1" "7" "11" }
118 { "1" "8" "11" }
119 { "1" "9" "11" }
120 { "1" "2" "0" }
121 { "1" "2" "121" }
122 { "1" "2" "22" }
123 { "1" "2" "3" }
124 { "1" "2" "4" }
125 { "1" "2" "5" }
Number Has no >= 2 digit-palindromes?
9 t
169 t
12769 t
1238769 t
123498769 t
12346098769 t
1234572098769 t
123456832098769 t
12345679432098769 t
1234567905432098769 t
123456790165432098769 t
83071934127905179083 t
1320267947849490361205695 f
FreeBASIC
Type StringArray
items(Any) As String
count As Integer
End Type
Function ReverseString(s As String) As String
Dim As String result = ""
For i As Integer = Len(s) To 1 Step -1
result &= Mid(s, i, 1)
Next
Return result
End Function
Sub GetSubstrings(s As String, result As StringArray)
Dim As Integer i, j
Redim result.items(0)
result.count = 0
For i = 1 To Len(s)
For j = 1 To Len(s) - i + 1
result.count += 1
Redim Preserve result.items(result.count - 1)
result.items(result.count - 1) = Mid(s, i, j)
Next
Next
End Sub
Sub SortUnique(arr As StringArray)
Dim As Integer i, j
' Remove duplicates
Dim As StringArray temp
Redim temp.items(arr.count - 1)
For i = 0 To arr.count - 1
Dim As Boolean found = False
For j = 0 To temp.count - 1
If temp.items(j) = arr.items(i) Then
found = True
Exit For
End If
Next
If Not found Then
temp.items(temp.count) = arr.items(i)
temp.count += 1
End If
Next
' Sort by length and then alphabetically
For i = 0 To temp.count - 2
For j = i + 1 To temp.count - 1
If Len(temp.items(i)) > Len(temp.items(j)) Orelse _
(Len(temp.items(i)) = Len(temp.items(j)) Andalso temp.items(i) > temp.items(j)) Then
Swap temp.items(i), temp.items(j)
End If
Next
Next
arr = temp
End Sub
' Main program
Dim As Integer i, j
Dim As StringArray subs, pals
Print "Number Palindromes"
For i = 100 To 125
pals.count = 0
Redim pals.items(0)
GetSubstrings(Str(i), subs)
For j = 0 To subs.count - 1
If subs.items(j) = ReverseString(subs.items(j)) Then
pals.count += 1
Redim Preserve pals.items(pals.count - 1)
pals.items(pals.count - 1) = subs.items(j)
End If
Next
SortUnique(pals)
Print Using " ### ["; i;
For j = 0 To pals.count - 1
Print Using "\ \"; pals.items(j);
Next
Print "]"
Next
Print !"\nNumber Has no >2 digit palindromes"
Dim As String nums(12) = { _
"9", "169", "12769", "1238769", "123498769", "12346098769", "1234572098769", _
"123456832098769", "12345679432098769", "1234567905432098769", "123456790165432098769", _
"83071934127905179083", "1320267947849490361205695" }
For i = 0 To 12
GetSubstrings(nums(i), subs)
Dim As Boolean none = True
For j = 0 To subs.count - 1
If Len(subs.items(j)) > 1 Then
If subs.items(j) = ReverseString(subs.items(j)) Then
none = False
Exit For
End If
End If
Next
Print Using "\ \ &"; nums(i); none
Next
Sleep
- Output:
Number Palindromes 100 [0 1 00 ] 101 [0 1 101] 102 [0 1 2 ] 103 [0 1 3 ] 104 [0 1 4 ] 105 [0 1 5 ] 106 [0 1 6 ] 107 [0 1 7 ] 108 [0 1 8 ] 109 [0 1 9 ] 110 [0 1 11 ] 111 [1 11 111] 112 [1 2 11 ] 113 [1 3 11 ] 114 [1 4 11 ] 115 [1 5 11 ] 116 [1 6 11 ] 117 [1 7 11 ] 118 [1 8 11 ] 119 [1 9 11 ] 120 [0 1 2 ] 121 [1 2 121] 122 [1 2 22 ] 123 [1 2 3 ] 124 [1 2 4 ] 125 [1 2 5 ] Number Has no >2 digit palindromes 9 true 169 true 12769 true 1238769 true 123498769 true 12346098769 true 1234572098769 true 123456832098769 true 12345679432098769 true 1234567905432098769 true 123456790165432098769 true 83071934127905179083 true 1320267947849490361205695 false
Go
package main
import (
"fmt"
"sort"
"strings"
)
func substrings(s string) []string {
var ss []string
n := len(s)
for i := 0; i < n; i++ {
for j := 1; j <= n-i; j++ {
ss = append(ss, s[i:i+j])
}
}
return ss
}
func reversed(s string) string {
var sb strings.Builder
for i := len(s) - 1; i >= 0; i-- {
sb.WriteByte(s[i])
}
return sb.String()
}
func main() {
fmt.Println("Number Palindromes")
for i := 100; i <= 125; i++ {
var pals []string
ss := substrings(fmt.Sprintf("%d", i))
for _, s := range ss {
if s == reversed(s) {
pals = append(pals, s)
}
}
m := make(map[string]bool)
for _, pal := range pals {
m[pal] = true
}
pals = pals[:0]
for k := range m {
pals = append(pals, k)
}
sort.Slice(pals, func(i, j int) bool {
if len(pals[i]) == len(pals[j]) {
return pals[i] < pals[j]
}
return len(pals[i]) < len(pals[j])
})
fmt.Printf("%d %3s\n", i, pals)
}
nums := []string{
"9", "169", "12769", "1238769", "123498769", "12346098769", "1234572098769",
"123456832098769", "12345679432098769", "1234567905432098769", "123456790165432098769",
"83071934127905179083", "1320267947849490361205695",
}
fmt.Println("\nNumber Has no >= 2 digit palindromes")
for _, num := range nums {
tmp := substrings(num)
var ss []string
for _, t := range tmp {
if len(t) > 1 {
ss = append(ss, t)
}
}
none := true
for _, s := range ss {
if s == reversed(s) {
none = false
break
}
}
fmt.Printf("%-25s %t\n", num, none)
}
}
- Output:
Number Palindromes 100 [ 0 1 00] 101 [ 0 1 101] 102 [ 0 1 2] 103 [ 0 1 3] 104 [ 0 1 4] 105 [ 0 1 5] 106 [ 0 1 6] 107 [ 0 1 7] 108 [ 0 1 8] 109 [ 0 1 9] 110 [ 0 1 11] 111 [ 1 11 111] 112 [ 1 2 11] 113 [ 1 3 11] 114 [ 1 4 11] 115 [ 1 5 11] 116 [ 1 6 11] 117 [ 1 7 11] 118 [ 1 8 11] 119 [ 1 9 11] 120 [ 0 1 2] 121 [ 1 2 121] 122 [ 1 2 22] 123 [ 1 2 3] 124 [ 1 2 4] 125 [ 1 2 5] Number Has no >= 2 digit palindromes 9 true 169 true 12769 true 1238769 true 123498769 true 12346098769 true 1234572098769 true 123456832098769 true 12345679432098769 true 1234567905432098769 true 123456790165432098769 true 83071934127905179083 true 1320267947849490361205695 false
Java
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
import java.util.stream.Collectors;
public final class DistinctPalindromesWithinDecimalNumbers {
public static void main(String[] args) {
System.out.println("Number Palindromes");
for ( int i = 100; i <= 125; i++ ) {
System.out.print(i + " ");
allPalindromes(String.valueOf(i)).forEach( palindrome ->
System.out.print(String.format("%5s", palindrome)) );
System.out.println();
}
List<String> numbers = List.of( "9", "169", "12769", "1238769", "123498769", "12346098769",
"1234572098769", "123456832098769", "12345679432098769", "1234567905432098769",
"123456790165432098769", "83071934127905179083", "1320267947849490361205695" );
System.out.println("\nNumber Has no >= 2 digit palindromes");
numbers.forEach( number -> {
boolean none = allPalindromes(String.valueOf(number)).stream().noneMatch( s -> s.length() > 1 );
System.out.println(String.format("%-26s%1s", number, none));
} );
}
private static Set<String> allPalindromes(String number) {
List<String> substrings = new ArrayList<String>();
for ( int i = 0; i < number.length(); i++ ) {
for ( int j = 1; j <= number.length() - i; j++ ) {
substrings.addLast(number.substring(i, i + j));
}
}
return substrings.stream()
.filter( s -> s.equals( new StringBuilder(s).reverse().toString() ) )
.collect(Collectors.toCollection(TreeSet::new));
}
}
- Output:
Number Palindromes 100 0 00 1 101 0 1 101 102 0 1 2 103 0 1 3 104 0 1 4 105 0 1 5 106 0 1 6 107 0 1 7 108 0 1 8 109 0 1 9 110 0 1 11 111 1 11 111 112 1 11 2 113 1 11 3 114 1 11 4 115 1 11 5 116 1 11 6 117 1 11 7 118 1 11 8 119 1 11 9 120 0 1 2 121 1 121 2 122 1 2 22 123 1 2 3 124 1 2 4 125 1 2 5 Number Has no >= 2 digit palindromes 9 true 169 true 12769 true 1238769 true 123498769 true 12346098769 true 1234572098769 true 123456832098769 true 12345679432098769 true 1234567905432098769 true 123456790165432098769 true 83071934127905179083 true 1320267947849490361205695 false
jq
Works with jq (but the second task requires a version with support for "big integer" literals)
Works with gojq, the Go implementation of jq (provided `keys_unsorted` is replaced by `keys`)
In this entry, except for 0 itself, palindromes involving leading 0s are ignored.
One feature of the implementation given here is that uniqueness is achieved without any sorting; however, if gojq is used, then `keys` would have to be used, thus entailing a sort after distinctness has been achieved.
Note that for the second task, and for very large integers (greater than 2^53) in general, accurate results require gojq, or a version of jq supporting "big integer" literals.
# input: an integer
# output a stream of distinct integers, each representing an admissible palindrome
def palindromes:
# input: an array
def is_palindrome: . == reverse;
def all_palindromes:
(tostring|explode)
| range(0; length) as $i
| range($i+1; length+1) as $j
| .[$i:$j] # candidate
| select(is_palindrome)
| implode
# trim leading 0s:
| if length > 1 then sub("^00*"; "") else . end
| select(length>0) ;
INDEX(all_palindromes; .) | keys_unsorted[] | tonumber;
def task1:
" i palindromes",
(range(100; 126)
| "\(.) \([palindromes]|join(" "))" );
def task2:
(9, 169, 12769, 1238769, 123498769, 12346098769, 1234572098769,
123456832098769, 12345679432098769, 1234567905432098769, 123456790165432098769,
83071934127905179083, 1320267947849490361205695)
| select( any(palindromes; . > 99) );
task1,
"\nThe integers amongst those in the problem statement that have 2 or more digits:",
task2- Output:
i palindromes 100 1 0 101 1 101 0 102 1 0 2 103 1 0 3 104 1 0 4 105 1 0 5 106 1 0 6 107 1 0 7 108 1 0 8 109 1 0 9 110 1 11 0 111 1 11 111 112 1 11 2 113 1 11 3 114 1 11 4 115 1 11 5 116 1 11 6 117 1 11 7 118 1 11 8 119 1 11 9 120 1 2 0 121 1 121 2 122 1 2 22 123 1 2 3 124 1 2 4 125 1 2 5 The integers amongst those in the problem statement that have 2 or more digits: 1320267947849490361205695
Julia
function allpalindromes(a::Vector{T}) where T
pals = Vector{Vector{T}}([[x] for x in a])
len = length(a)
len < 2 && return pals
a == reverse(a) && push!(pals, a)
len == 2 && return pals
for i in 2:len
left = a[1:i]
left == reverse(left) && push!(pals, left)
end
return unique(vcat(pals, allpalindromes(a[2:end])))
end
println("Number Palindromes")
for n in 100:125
println(" ", rpad(n, 7), sort(allpalindromes(digits(n))))
end
palindrome2plusfree(n) = (a = allpalindromes(digits(n)); all(x -> length(x) == 1, a))
println("\nNumber Has no >= 2 digit palindromes")
for n in [9, 169, 12769, 1238769, 123498769, 12346098769, 1234572098769, 123456832098769,
12345679432098769, 1234567905432098769, 123456790165432098769, 83071934127905179083, 1320267947849490361205695]
println(rpad(n, 26), palindrome2plusfree(n))
end
- Output:
Number Palindromes 100 [[0], [0, 0], [1]] 101 [[0], [1], [1, 0, 1]] 102 [[0], [1], [2]] 103 [[0], [1], [3]] 104 [[0], [1], [4]] 105 [[0], [1], [5]] 106 [[0], [1], [6]] 107 [[0], [1], [7]] 108 [[0], [1], [8]] 109 [[0], [1], [9]] 110 [[0], [1], [1, 1]] 111 [[1], [1, 1], [1, 1, 1]] 112 [[1], [1, 1], [2]] 113 [[1], [1, 1], [3]] 114 [[1], [1, 1], [4]] 115 [[1], [1, 1], [5]] 116 [[1], [1, 1], [6]] 117 [[1], [1, 1], [7]] 118 [[1], [1, 1], [8]] 119 [[1], [1, 1], [9]] 120 [[0], [1], [2]] 121 [[1], [1, 2, 1], [2]] 122 [[1], [2], [2, 2]] 123 [[1], [2], [3]] 124 [[1], [2], [4]] 125 [[1], [2], [5]] Number Has no >= 2 digit palindromes 9 true 169 true 12769 true 1238769 true 123498769 true 12346098769 true 1234572098769 true 123456832098769 true 12345679432098769 true 1234567905432098769 true 123456790165432098769 true 83071934127905179083 true 1320267947849490361205695 false
Mathematica /Wolfram Language
ClearAll[ContainsPalindromeQ]
ContainsPalindromeQ[n_Integer, minlength_ : 1, b_ : 10] := Select[DeleteDuplicates@Subsequences[IntegerDigits[n, b], {minlength, \[Infinity]}], PalindromeQ]
ContainsPalindromeQ /@ Range[100, 125] // Column
Length[ContainsPalindromeQ[#, 2]] > 0 & /@ {9, 169, 12769, 1238769,
123498769, 12346098769, 1234572098769, 123456832098769,
12345679432098769, 1234567905432098769, 123456790165432098769,
83071934127905179083, 1320267947849490361205695}
- Output:
{{1},{0},{0,0}}
{{1},{0},{1,0,1}}
{{1},{0},{2}}
{{1},{0},{3}}
{{1},{0},{4}}
{{1},{0},{5}}
{{1},{0},{6}}
{{1},{0},{7}}
{{1},{0},{8}}
{{1},{0},{9}}
{{1},{0},{1,1}}
{{1},{1,1},{1,1,1}}
{{1},{2},{1,1}}
{{1},{3},{1,1}}
{{1},{4},{1,1}}
{{1},{5},{1,1}}
{{1},{6},{1,1}}
{{1},{7},{1,1}}
{{1},{8},{1,1}}
{{1},{9},{1,1}}
{{1},{2},{0}}
{{1},{2},{1,2,1}}
{{1},{2},{2,2}}
{{1},{2},{3}}
{{1},{2},{4}}
{{1},{2},{5}}
{False, False, False, False, False, False, False, False, False, False, False, False, True}
Nim
import algorithm, sequtils, sets, strutils
iterator substrings(s: string): string =
## Yield the substrings of the given string.
for istart in 0..s.high:
for istop in istart..s.high:
yield s[istart..istop]
func isPalindrome(s: string): bool =
## Return true if "s" is a palindrome.
result = true
for i in 0..(s.high div 2):
if s[i] != s[s.high - i]: return false
func cmpPal(s1, s2: string): int =
## Compare two palindromes (used for sort).
result = cmp(s1.len, s2.len)
if result == 0:
result = cmp(s1[0], s2[0])
func palindromes(str: string): seq[string] =
## Return the sorted list of palindromes contained in "str".
var palSet: HashSet[string]
for s in substrings(str):
if s.isPalindrome: palSet.incl s
result = sorted(toSeq(palSet), cmpPal)
when isMainModule:
for n in 100..125:
echo n, ": ", palindromes($n).mapIt(it.align(3)).join(" ")
echo()
for s in ["9", "169", "12769", "1238769", "123498769", "12346098769",
"1234572098769", "123456832098769", "12345679432098769",
"1234567905432098769", "123456790165432098769",
"83071934127905179083", "1320267947849490361205695"]:
let pals2 = palindromes(s).filterIt(it.len >= 2)
let verb = if pals2.len == 0: " doesn't contain palindromes "
else: " contains at least one palindrome "
echo s, verb, "of two digits or more"
- Output:
100: 0 1 00 101: 0 1 101 102: 0 1 2 103: 0 1 3 104: 0 1 4 105: 0 1 5 106: 0 1 6 107: 0 1 7 108: 0 1 8 109: 0 1 9 110: 0 1 11 111: 1 11 111 112: 1 2 11 113: 1 3 11 114: 1 4 11 115: 1 5 11 116: 1 6 11 117: 1 7 11 118: 1 8 11 119: 1 9 11 120: 0 1 2 121: 1 2 121 122: 1 2 22 123: 1 2 3 124: 1 2 4 125: 1 2 5 9 doesn't contain palindromes of two digits or more 169 doesn't contain palindromes of two digits or more 12769 doesn't contain palindromes of two digits or more 1238769 doesn't contain palindromes of two digits or more 123498769 doesn't contain palindromes of two digits or more 12346098769 doesn't contain palindromes of two digits or more 1234572098769 doesn't contain palindromes of two digits or more 123456832098769 doesn't contain palindromes of two digits or more 12345679432098769 doesn't contain palindromes of two digits or more 1234567905432098769 doesn't contain palindromes of two digits or more 123456790165432098769 doesn't contain palindromes of two digits or more 83071934127905179083 doesn't contain palindromes of two digits or more 1320267947849490361205695 contains at least one palindrome of two digits or more
Perl
#!/usr/bin/perl
# https://rosettacode.org/wiki/Distinct_Palindromes_Within_Decimal_Numbers
use strict;
use warnings;
for ( 100 .. 125 )
{
my %found;
/.+(?{$& eq reverse $& and $found{$&}++})(*FAIL)/;
print "$_ => @{[ sort { $a <=> $b } keys %found ]}\n"
}
/..+(??{$& == (reverse $&) ? '' : '(*FAIL)' })/ and
print "$_ has a palindrome of 2 or more\n"
for ' 9, 169, 12769, 1238769, 123498769, 12346098769, 1234572098769,
123456832098769, 12345679432098769, 1234567905432098769,
123456790165432098769, 83071934127905179083, 1320267947849490361205695'
=~ /\d+/g;
- Output:
100 => 00 0 1 101 => 0 1 101 102 => 0 1 2 103 => 0 1 3 104 => 0 1 4 105 => 0 1 5 106 => 0 1 6 107 => 0 1 7 108 => 0 1 8 109 => 0 1 9 110 => 0 1 11 111 => 1 11 111 112 => 1 2 11 113 => 1 3 11 114 => 1 4 11 115 => 1 5 11 116 => 1 6 11 117 => 1 7 11 118 => 1 8 11 119 => 1 9 11 120 => 0 1 2 121 => 1 2 121 122 => 1 2 22 123 => 1 2 3 124 => 1 2 4 125 => 1 2 5 1320267947849490361205695 has a palindrome of 2 or more
Phix
procedure show_all_palindromes(string s, integer longest=0) sequence res = {} for i=1 to length(s) do if longest=0 then res = append(res,{1,s[i..i]}) end if for j=0 to iff(i>1 and s[i-1]=s[i]?2:1) do integer rev = j, fwd = 1 while rev<i and i+fwd<=length(s) and s[i-rev]=s[i+fwd] do if longest=0 then res = append(res,{rev+fwd+1,s[i-rev..i+fwd]}) end if rev += 1 fwd += 1 end while if longest>0 then longest = max(longest,rev+fwd-1) end if end for end for if longest then printf(1,"%-26s %t\n",{s,longest<3}) else printf(1," %s %s\n",{s,join(vslice(unique(res),2))}) end if end procedure printf(1,"Number Palindromes\n") papply(apply(true,sprintf,{{"%d"},tagset(125,100)}),show_all_palindromes) constant tests = split_any("""9, 169, 12769, 1238769, 123498769, 12346098769, 1234572098769, 123456832098769, 12345679432098769, 1234567905432098769, 123456790165432098769, 83071934127905179083, 1320267947849490361205695"""," ,\n") printf(1,"\nNumber Has no >2 digit palindromes\n") papply(true,show_all_palindromes,{tests,1})
- Output:
Number Palindromes 100 0 1 00 101 0 1 101 102 0 1 2 103 0 1 3 104 0 1 4 105 0 1 5 106 0 1 6 107 0 1 7 108 0 1 8 109 0 1 9 110 0 1 11 111 1 11 111 112 1 2 11 113 1 3 11 114 1 4 11 115 1 5 11 116 1 6 11 117 1 7 11 118 1 8 11 119 1 9 11 120 0 1 2 121 1 2 121 122 1 2 22 123 1 2 3 124 1 2 4 125 1 2 5 Number Has no >2 digit palindromes 9 true 169 true 12769 true 1238769 true 123498769 true 12346098769 true 1234572098769 true 123456832098769 true 12345679432098769 true 1234567905432098769 true 123456790165432098769 true 83071934127905179083 true 1320267947849490361205695 false
Raku
A minor modification of the Longest palindromic substrings task. As such, works for any string, not just integers.
use Sort::Naturally;
sub getpal ($str) {
my @chars = $str.comb;
my @pal = flat @chars,
(1 ..^ @chars).map: -> \idx {
my @s;
for 1, 2 {
my int ($rev, $fwd) = $_, 1;
loop {
quietly last if ($rev > idx) || (@chars[idx - $rev] ne @chars[idx + $fwd]);
$rev = $rev + 1;
$fwd = $fwd + 1;
}
@s.push: @chars[idx - $rev ^..^ idx + $fwd].join if $rev + $fwd > 2;
last if @chars[idx - 1] ne @chars[idx];
}
next unless +@s;
@s
}
@pal.unique.sort({.chars, .&naturally});
}
say 'All palindromic substrings including (bizarrely enough) single characters:';
put "$_ => ", getpal $_ for 100..125;
put "\nDo these strings contain a minimum two character palindrome?";
printf "%25s => %s\n", $_, getpal($_).tail.chars > 1 for flat
9, 169, 12769, 1238769, 123498769, 12346098769, 1234572098769,
123456832098769, 12345679432098769, 1234567905432098769,
123456790165432098769, 83071934127905179083, 1320267947849490361205695,
<Do these strings contain a minimum two character palindrome?>
- Output:
All palindromic substrings including (bizarrely enough) single characters:
100 => 0 1 00
101 => 0 1 101
102 => 0 1 2
103 => 0 1 3
104 => 0 1 4
105 => 0 1 5
106 => 0 1 6
107 => 0 1 7
108 => 0 1 8
109 => 0 1 9
110 => 0 1 11
111 => 1 11 111
112 => 1 2 11
113 => 1 3 11
114 => 1 4 11
115 => 1 5 11
116 => 1 6 11
117 => 1 7 11
118 => 1 8 11
119 => 1 9 11
120 => 0 1 2
121 => 1 2 121
122 => 1 2 22
123 => 1 2 3
124 => 1 2 4
125 => 1 2 5
Do these strings contain a minimum two character palindrome?
9 => False
169 => False
12769 => False
1238769 => False
123498769 => False
12346098769 => False
1234572098769 => False
123456832098769 => False
12345679432098769 => False
1234567905432098769 => False
123456790165432098769 => False
83071934127905179083 => False
1320267947849490361205695 => True
Do => False
these => True
strings => False
contain => False
a => False
minimum => True
two => False
character => True
palindrome? => False
REXX
This REXX version can handle strings or numbers.
/*REXX pgm finds distinct palindromes contained in substrings (decimal #s or strings). */
parse arg LO HI mL $$ /*obtain optional arguments from the CL*/
if LO='' | LO="," then LO= 100 /*Not specified? Then use the default.*/
if HI='' | HI="," then HI= 125 /* " " " " " " */
if mL='' | mL="," then mL= 2 /* " " " " " " */
if $$='' | $$="," then $$= 9 169 12769 1238769 12346098769 1234572098769 123456832098769,
12345679432098769 1234567905432098769 123456790165432098769 ,
83071934127905179083 1320267947849490361205695,
'Do these strings contain a minimum two character palindrome?',
'amanaplanacanalpanama' /*a man a plan a canal panama*/
w= length(HI) /*max width of LO ──► HI for alignment.*/
do j=LO to HI; #= Dpal(j, 1) /*get # distinct palindromes, minLen=1 */
say right(j, w) ' has ' # " palindrome"s(#)': ' $
end /*j*/
#= words($$); if #==0 then exit 0 /*No special words/numbers? Then exit.*/
do m=1 for #; w= max(w, length(word($$, m))) /*find max width string in $$*/
end /*m*/
say
do j=1 for #; z= word($$, j) /*obtain a string in the $$ list. */
#= Dpal(z, mL) /*get # distinct palindromes, minLen=mL*/
_= left(':', #>0); @has= ' has '; @of='of length'
say right(z, w) @has # " palindrome"s(#,,' ') @of mL "or more"_ space($)
end /*j*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
s: if arg(1)==1 then return arg(3); return word( arg(2) 's', 1)
/*──────────────────────────────────────────────────────────────────────────────────────*/
Dpal: procedure expose @. !. $ w; parse arg x, mL; $=; !.= 0; #= 0; L= length(x)
do j=1 for L /*test for primality for all substrings*/
do k=1 to L-j+1 /*search for substrings (including X).*/
y= strip( substr(x, j, k) ) /*extract a substring from the X string*/
if length(y)<mL | y\==reverse(y) then iterate /*too short or ¬palindromic?*/
if \!.y then do; $= $ right(y, w); !.y= 1; #= # + 1; end
end /*k*/
end /*j*/
return #
- output when using the default inputs:
100 has 3 palindromes: 1 0 00
101 has 3 palindromes: 1 101 0
102 has 3 palindromes: 1 0 2
103 has 3 palindromes: 1 0 3
104 has 3 palindromes: 1 0 4
105 has 3 palindromes: 1 0 5
106 has 3 palindromes: 1 0 6
107 has 3 palindromes: 1 0 7
108 has 3 palindromes: 1 0 8
109 has 3 palindromes: 1 0 9
110 has 3 palindromes: 1 11 0
111 has 3 palindromes: 1 11 111
112 has 3 palindromes: 1 11 2
113 has 3 palindromes: 1 11 3
114 has 3 palindromes: 1 11 4
115 has 3 palindromes: 1 11 5
116 has 3 palindromes: 1 11 6
117 has 3 palindromes: 1 11 7
118 has 3 palindromes: 1 11 8
119 has 3 palindromes: 1 11 9
120 has 3 palindromes: 1 2 0
121 has 3 palindromes: 1 121 2
122 has 3 palindromes: 1 2 22
123 has 3 palindromes: 1 2 3
124 has 3 palindromes: 1 2 4
125 has 3 palindromes: 1 2 5
9 has 0 palindromes of length 2 or more
169 has 0 palindromes of length 2 or more
12769 has 0 palindromes of length 2 or more
1238769 has 0 palindromes of length 2 or more
12346098769 has 0 palindromes of length 2 or more
1234572098769 has 0 palindromes of length 2 or more
123456832098769 has 0 palindromes of length 2 or more
12345679432098769 has 0 palindromes of length 2 or more
1234567905432098769 has 0 palindromes of length 2 or more
123456790165432098769 has 0 palindromes of length 2 or more
83071934127905179083 has 0 palindromes of length 2 or more
1320267947849490361205695 has 3 palindromes of length 2 or more: 202 494 949
Do has 0 palindromes of length 2 or more
these has 1 palindrome of length 2 or more: ese
strings has 0 palindromes of length 2 or more
contain has 0 palindromes of length 2 or more
a has 0 palindromes of length 2 or more
minimum has 3 palindromes of length 2 or more: minim ini mum
two has 0 palindromes of length 2 or more
character has 1 palindrome of length 2 or more: ara
palindrome? has 0 palindromes of length 2 or more
amanaplanacanalpanama has 12 palindromes of length 2 or more: ama amanaplanacanalpanama manaplanacanalpanam ana anaplanacanalpana naplanacanalpan aplanacanalpa planacanalp lanacanal anacana nacan aca
Ruby
def sub_palins(num, min_size = 1)
digits = num.digits.reverse
res = []
(min_size..digits.size).each do |sub_num_size|
digits.each_cons(sub_num_size){|sub|res << sub if sub == sub.reverse }
end
res.uniq
end
(100..125).each {|num| puts "#{num}: #{sub_palins(num)}" }
tests = [9, 169, 12769, 1238769, 123498769, 12346098769, 1234572098769,
123456832098769, 12345679432098769, 1234567905432098769, 123456790165432098769,
83071934127905179083, 1320267947849490361205695]
max_size = tests.max.digits.size
puts "\n#{"Number".ljust(max_size)} Has no >= 2 digit palindromes"
tests.each do |num|
puts "#{num.to_s.ljust(max_size)} #{! sub_palins(num,2).empty?}"
end
- Output:
100: [[1], [0], [0, 0]] 101: [[1], [0], [1, 0, 1]] 102: [[1], [0], [2]] 103: [[1], [0], [3]] 104: [[1], [0], [4]] 105: [[1], [0], [5]] 106: [[1], [0], [6]] 107: [[1], [0], [7]] 108: [[1], [0], [8]] 109: [[1], [0], [9]] 110: [[1], [0], [1, 1]] 111: [[1], [1, 1], [1, 1, 1]] 112: [[1], [2], [1, 1]] 113: [[1], [3], [1, 1]] 114: [[1], [4], [1, 1]] 115: [[1], [5], [1, 1]] 116: [[1], [6], [1, 1]] 117: [[1], [7], [1, 1]] 118: [[1], [8], [1, 1]] 119: [[1], [9], [1, 1]] 120: [[1], [2], [0]] 121: [[1], [2], [1, 2, 1]] 122: [[1], [2], [2, 2]] 123: [[1], [2], [3]] 124: [[1], [2], [4]] 125: [[1], [2], [5]] Number Has no >= 2 digit palindromes 9 false 169 false 12769 false 1238769 false 123498769 false 12346098769 false 1234572098769 false 123456832098769 false 12345679432098769 false 1234567905432098769 false 123456790165432098769 false 83071934127905179083 false 1320267947849490361205695 true
Sidef
func palindromes(arr) {
gather {
for a in (0..arr.end), b in (a .. arr.end) {
var sublist = arr.items(a..b -> ...)
take(sublist) if (sublist == sublist.flip)
}
}.uniq
}
for n in (100..125) {
say "#{n} -> #{palindromes(n.digits).sort.map{.join}.sort_by{.len}.join(' ')}"
}
[9, 169, 12769, 1238769, 123498769, 12346098769, 1234572098769,
123456832098769, 12345679432098769, 1234567905432098769, 123456790165432098769,
83071934127905179083, 1320267947849490361205695, "amanaplanacanalpanama"].each {|n|
var p = palindromes(n.kind_of(Number) ? n.digits : n.chars).grep { .len >= 2}
say ("#{'%25s' % n} has #{'%2d' % p.len} palindromes of length 2 or more: ",
p.sort.map{.join}.sort_by{.len}.join(' '))
}
- Output:
100 -> 0 1 00
101 -> 0 1 101
102 -> 0 1 2
103 -> 0 1 3
104 -> 0 1 4
105 -> 0 1 5
106 -> 0 1 6
107 -> 0 1 7
108 -> 0 1 8
109 -> 0 1 9
110 -> 0 1 11
111 -> 1 11 111
112 -> 1 2 11
113 -> 1 3 11
114 -> 1 4 11
115 -> 1 5 11
116 -> 1 6 11
117 -> 1 7 11
118 -> 1 8 11
119 -> 1 9 11
120 -> 0 1 2
121 -> 1 2 121
122 -> 1 2 22
123 -> 1 2 3
124 -> 1 2 4
125 -> 1 2 5
9 has 0 palindromes of length 2 or more:
169 has 0 palindromes of length 2 or more:
12769 has 0 palindromes of length 2 or more:
1238769 has 0 palindromes of length 2 or more:
123498769 has 0 palindromes of length 2 or more:
12346098769 has 0 palindromes of length 2 or more:
1234572098769 has 0 palindromes of length 2 or more:
123456832098769 has 0 palindromes of length 2 or more:
12345679432098769 has 0 palindromes of length 2 or more:
1234567905432098769 has 0 palindromes of length 2 or more:
123456790165432098769 has 0 palindromes of length 2 or more:
83071934127905179083 has 0 palindromes of length 2 or more:
1320267947849490361205695 has 3 palindromes of length 2 or more: 202 494 949
amanaplanacanalpanama has 12 palindromes of length 2 or more: aca ama ana nacan anacana lanacanal planacanalp aplanacanalpa naplanacanalpan anaplanacanalpana manaplanacanalpanam amanaplanacanalpanama
Wren
import "./seq" for Lst
import "./fmt" for Fmt
import "./sort" for Sort
var substrings = Fn.new { |s|
var ss = []
var n = s.count
for (i in 0...n) {
for (j in 1..n-i) ss.add(s[i...i + j])
}
return ss
}
System.print("Number Palindromes")
for (i in 100..125) {
var pals = []
var ss = substrings.call(i.toString)
for (s in ss) {
if (s == s[-1..0]) pals.add(s)
}
pals = Lst.distinct(pals)
var cmp = Fn.new { |i, j| (i.count - j.count).sign }
Sort.insertion(pals, cmp) // sort by length
Fmt.print("$d $3s", i, pals)
}
var nums = [
"9", "169", "12769", "1238769", "123498769", "12346098769", "1234572098769",
"123456832098769", "12345679432098769", "1234567905432098769", "123456790165432098769",
"83071934127905179083", "1320267947849490361205695"
]
System.print("\nNumber Has no >= 2 digit palindromes")
for (num in nums) {
var ss = substrings.call(num).where { |s| s.count > 1 }
var none = !ss.any { |s| s == s[-1..0] }
Fmt.print("$-25s $s", num, none)
}
- Output:
Number Palindromes 100 1 0 00 101 1 0 101 102 1 0 2 103 1 0 3 104 1 0 4 105 1 0 5 106 1 0 6 107 1 0 7 108 1 0 8 109 1 0 9 110 1 0 11 111 1 11 111 112 1 2 11 113 1 3 11 114 1 4 11 115 1 5 11 116 1 6 11 117 1 7 11 118 1 8 11 119 1 9 11 120 1 2 0 121 1 2 121 122 1 2 22 123 1 2 3 124 1 2 4 125 1 2 5 Number Has no >= 2 digit palindromes 9 true 169 true 12769 true 1238769 true 123498769 true 12346098769 true 1234572098769 true 123456832098769 true 12345679432098769 true 1234567905432098769 true 123456790165432098769 true 83071934127905179083 true 1320267947849490361205695 false
Zig
const std = @import("std");
pub fn main() !void {
// ArenaAllocator with its facility to reset obviates the
// requirement to individually free()/deinit() any allocated
// memory.
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer _ = arena.deinit();
const allocator = arena.allocator();
const writer = std.io.getStdOut().writer();
// --------------------------------------------------- task 1
try writer.writeAll("Number Palindromes\n");
var i: u32 = 100;
while (i <= 125) : (i += 1) {
var buf: [3]u8 = undefined;
const s = try std.fmt.bufPrint(&buf, "{d}", .{i});
const palindromes: [][]const u8 = try allPalindromes(allocator, s);
defer _ = arena.reset(.retain_capacity);
try writer.print("{} ", .{i});
std.mem.sort([]const u8, palindromes, {}, lessThan);
for (palindromes) |palindrome|
try writer.print("{s:5}", .{palindrome});
try writer.writeByte('\n');
}
// --------------------------------------------------- task 2
const numbers = [_][]const u8{
"9", "169", "12769",
"1238769", "123498769", "12346098769",
"1234572098769", "123456832098769", "12345679432098769",
"1234567905432098769", "123456790165432098769", "83071934127905179083",
"1320267947849490361205695",
};
try writer.writeAll("\nNumber Has no >= 2 digit palindromes\n");
for (numbers) |number| {
const palindromes = try allPalindromes(allocator, number);
defer _ = arena.reset(.retain_capacity);
const none = !hasSignificantStrings(palindromes);
try writer.print("{s: <26} {}\n", .{ number, none });
}
}
/// This function does not free any of its allocated memory.
/// Freeing relies upon the allocator's parent being reset
/// i.e. ArenaAllocator in this solution.
fn allPalindromes(allocator: std.mem.Allocator, number: []const u8) ![][]const u8 {
var substrings = std.ArrayList([]const u8).init(allocator);
for (0..number.len) |i|
for (1..number.len - i + 1) |j|
try substrings.append(number[i .. i + j]);
var palindrome_set = std.StringArrayHashMap(void).init(allocator);
for (substrings.items) |string|
if (isPalindrome(string))
try palindrome_set.put(string, {});
return palindrome_set.keys();
}
fn isPalindrome(s: []const u8) bool {
for (0..s.len / 2) |i|
if (s[i] != s[s.len - i - 1])
return false;
return true;
}
fn hasSignificantStrings(strings: []const []const u8) bool {
for (strings) |s|
if (s.len > 1)
return true;
return false;
}
/// Lexicographically compare two strings. Returns true if a < b
fn lessThan(_: void, a: []const u8, b: []const u8) bool {
const len = @min(a.len, b.len);
for (a[0..len], b[0..len]) |c1, c2|
return switch (std.math.order(c1, c2)) {
.lt => true,
.eq => continue,
.gt => false,
};
return a.len < b.len;
}
// Some minimal tests...
const testing = std.testing;
test isPalindrome {
try testing.expect(isPalindrome("0"));
try testing.expect(isPalindrome("11"));
try testing.expect(isPalindrome("121"));
try testing.expect(!isPalindrome("12"));
try testing.expect(!isPalindrome("122"));
}
test hasSignificantStrings {
try testing.expect(hasSignificantStrings(&[_][]const u8{ "9", "10", "11" }));
try testing.expect(!hasSignificantStrings(&[_][]const u8{}));
try testing.expect(!hasSignificantStrings(&[_][]const u8{""}));
try testing.expect(!hasSignificantStrings(&[_][]const u8{ "1", "2" }));
}