Distinct palindromes within decimal numbers: Difference between revisions
m (→{{header|REXX}}: added the extra strings used by another programming language entry.) |
m (→{{header|REXX}}: changed the program title comment.) |
||
| Line 334: | Line 334: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
This REXX version can handle strings or numbers. |
This REXX version can handle strings or numbers. |
||
<lang>/*REXX |
<lang>/*REXX pgm finds distinct palindromes contained in substrings (decimal #s or strings). */ |
||
parse arg LO HI mL $$ /*obtain optional arguments from the CL*/ |
parse arg LO HI mL $$ /*obtain optional arguments from the CL*/ |
||
if LO='' | LO="," then LO= 100 /*Not specified? Then use the default.*/ |
if LO='' | LO="," then LO= 100 /*Not specified? Then use the default.*/ |
||
Revision as of 00:36, 7 April 2021
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.
- 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).
Palindrome_detection
Longest_palindromic_substrings
N_1's_followed_by_a_3
Factor
<lang 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</lang>
- 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
Julia
<lang 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
</lang>
- 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
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. <lang perl6>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?></lang>
- 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. <lang>/*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?'
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 #</lang>
- 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
Wren
<lang ecmascript>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)
}</lang>
- 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