Distinct palindromes within decimal numbers: Difference between revisions
(Add Factor) |
|||
Line 158: | Line 158: | ||
83071934127905179083 true |
83071934127905179083 true |
||
1320267947849490361205695 false |
1320267947849490361205695 false |
||
</pre> |
|||
=={{header|Phix}}== |
|||
<!--<lang Phix>(phixonline)--> |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">show_all_palindromes</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">longest</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">longest</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]?</span><span style="color: #000000;">2</span><span style="color: #0000FF;">:</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">rev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">,</span> |
|||
<span style="color: #000000;">fwd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">rev</span><span style="color: #0000FF;"><</span><span style="color: #000000;">i</span> <span style="color: #008080;">and</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">fwd</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">rev</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">fwd</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">longest</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">rev</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">fwd</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">rev</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #000000;">fwd</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">longest</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">longest</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">longest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rev</span><span style="color: #0000FF;">+</span><span style="color: #000000;">fwd</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">longest</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%-26s %t\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">longest</span><span style="color: #0000FF;"><</span><span style="color: #000000;">3</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" %s %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">unique</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">))})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Number Palindromes\n"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">,{{</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">},</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">125</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">)}),</span><span style="color: #000000;">show_all_palindromes</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split_any</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"""9, 169, 12769, 1238769, 123498769, 12346098769, |
|||
1234572098769, 123456832098769, 12345679432098769, 1234567905432098769, |
|||
123456790165432098769, 83071934127905179083, 1320267947849490361205695"""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" ,\n"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nNumber Has no >2 digit palindromes\n"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #000000;">show_all_palindromes</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span> |
|||
<!--</lang>--> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
</pre> |
Revision as of 13:24, 6 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,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,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(unique(res))}) 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 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