Most frequent k chars distance: Difference between revisions

Content added Content deleted
m (→‎{{header|Phix}}: added syntax colouring, marked p2js compatible)
Line 1,067: Line 1,067:
=={{header|Phix}}==
=={{header|Phix}}==
{{trans|Go}}
{{trans|Go}}
<!--<lang Phix>(phixonline)-->
<lang Phix>function mostFreqKHashing(string input, integer k)
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
string cfs = ""
<span style="color: #008080;">function</span> <span style="color: #000000;">mostFreqKHashing</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">input</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
sequence cfsnx = {}
<span style="color: #004080;">string</span> <span style="color: #000000;">cfs</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
for i=1 to length(input) do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cfsnx</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
integer r = input[i],
<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;">input</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
ix = find(r,cfs)
<span style="color: #004080;">integer</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">input</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span>
if ix>0 then
<span style="color: #000000;">ix</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cfs</span><span style="color: #0000FF;">)</span>
cfsnx[ix][1] -= 1
<span style="color: #008080;">if</span> <span style="color: #000000;">ix</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
else
<span style="color: #000000;">cfsnx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ix</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
cfs &= r
<span style="color: #008080;">else</span>
cfsnx = append(cfsnx,{-1,length(cfs)})
<span style="color: #000000;">cfs</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">r</span>
end if
<span style="color: #000000;">cfsnx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cfsnx</span><span style="color: #0000FF;">,{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cfs</span><span style="color: #0000FF;">)})</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
cfsnx = sort(cfsnx) -- (aside: the idx forces stable sort)
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
sequence acc := {}
<span style="color: #000000;">cfsnx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cfsnx</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (aside: the idx forces stable sort)</span>
for i=1 to min(length(cfs),k) do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">acc</span> <span style="color: #0000FF;">:=</span> <span style="color: #0000FF;">{}</span>
integer {n,ix} = cfsnx[i]
<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;">min</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cfs</span><span style="color: #0000FF;">),</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
acc &= {cfs[ix], -n}
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ix</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cfsnx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
end for
<span style="color: #000000;">acc</span> <span style="color: #0000FF;">&=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">cfs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ix</span><span style="color: #0000FF;">],</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">n</span><span style="color: #0000FF;">}</span>
return acc
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">acc</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
function mostFreqKSimilarity(sequence input1, input2)
integer similarity := 0
<span style="color: #008080;">function</span> <span style="color: #000000;">mostFreqKSimilarity</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">input1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">input2</span><span style="color: #0000FF;">)</span>
for i=1 to length(input1) by 2 do
<span style="color: #004080;">integer</span> <span style="color: #000000;">similarity</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">0</span>
for j=1 to length(input2) by 2 do
<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;">input1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
if input1[i] == input2[j] then
<span style="color: #008080;">for</span> <span style="color: #000000;">j</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;">input2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
integer freq1 = input1[i+1],
<span style="color: #008080;">if</span> <span style="color: #000000;">input1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">input2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
freq2 = input2[j+1]
<span style="color: #004080;">integer</span> <span style="color: #000000;">freq1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">input1</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>
if freq1=freq2 then
<span style="color: #000000;">freq2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">input2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
similarity += freq1
<span style="color: #008080;">if</span> <span style="color: #000000;">freq1</span><span style="color: #0000FF;">=</span><span style="color: #000000;">freq2</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">similarity</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">freq1</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
return similarity
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">similarity</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
function flat(sequence s)
string res = ""
<span style="color: #008080;">function</span> <span style="color: #000000;">flat</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
for i=1 to length(s) by 2 do
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
res &= sprintf("%c%d",s[i..i+1])
<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;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
end for
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%c%d"</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: #000000;">1</span><span style="color: #0000FF;">])</span>
return res
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
procedure mostFreqKSDF(string input1, input2, integer k, maxDistance)
printf(1,"input1 : %s\n", {input1})
<span style="color: #008080;">procedure</span> <span style="color: #000000;">mostFreqKSDF</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">input1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">input2</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">maxDistance</span><span style="color: #0000FF;">)</span>
printf(1,"input2 : %s\n", {input2})
<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;">"input1 : %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">input1</span><span style="color: #0000FF;">})</span>
sequence s1 := mostFreqKHashing(input1, k),
<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;">"input2 : %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">input2</span><span style="color: #0000FF;">})</span>
s2 := mostFreqKHashing(input2, k)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s1</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">mostFreqKHashing</span><span style="color: #0000FF;">(</span><span style="color: #000000;">input1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">),</span>
printf(1,"mfkh(input1, %d) = %s\n", {k,flat(s1)})
<span style="color: #000000;">s2</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">mostFreqKHashing</span><span style="color: #0000FF;">(</span><span style="color: #000000;">input2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
printf(1,"mfkh(input2, %d) = %s\n", {k,flat(s2)})
<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;">"mfkh(input1, %d) = %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">flat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">)})</span>
integer result := maxDistance - mostFreqKSimilarity(s1, s2)
<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;">"mfkh(input2, %d) = %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">flat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s2</span><span style="color: #0000FF;">)})</span>
printf(1,"SDF(input1, input2, %d, %d) = %d\n\n", {k, maxDistance, result})
<span style="color: #004080;">integer</span> <span style="color: #000000;">result</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">maxDistance</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">mostFreqKSimilarity</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s2</span><span style="color: #0000FF;">)</span>
end procedure
<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;">"SDF(input1, input2, %d, %d) = %d\n\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">maxDistance</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">result</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
constant tests = {{"research", "seeking"},
{"night", "nacht"},
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #008000;">"research"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"seeking"</span><span style="color: #0000FF;">},</span>
{"my", "a"},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"night"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"nacht"</span><span style="color: #0000FF;">},</span>
{"research", "research"},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"my"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"a"</span><span style="color: #0000FF;">},</span>
{"aaaaabbbb", "ababababa"},
<span style="color: #0000FF;">{</span><span style="color: #008000;">"research"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"research"</span><span style="color: #0000FF;">},</span>
{"significant", "capabilities"}}
<span style="color: #0000FF;">{</span><span style="color: #008000;">"aaaaabbbb"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"ababababa"</span><span style="color: #0000FF;">},</span>
for i=1 to length(tests) do
<span style="color: #0000FF;">{</span><span style="color: #008000;">"significant"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"capabilities"</span><span style="color: #0000FF;">}}</span>
string {t1,t2} = tests[i]
<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;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
mostFreqKSDF(t1, t2, 2, 10)
<span style="color: #004080;">string</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
end for
<span style="color: #000000;">mostFreqKSDF</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
string s1 := "LCLYTHIGRNIYYGSYLYSETWNTGIMLLLITMATAFMGYVLPWGQMSFWGATVITNLFSAIPYIGTNLV",
s2 := "EWIWGGFSVDKATLNRFFAFHFILPFTMVALAGVHLTFLHETGSNNPLGLTSDSDKIPFHPYYTIKDFLG"
<span style="color: #004080;">string</span> <span style="color: #000000;">s1</span> <span style="color: #0000FF;">:=</span> <span style="color: #008000;">"LCLYTHIGRNIYYGSYLYSETWNTGIMLLLITMATAFMGYVLPWGQMSFWGATVITNLFSAIPYIGTNLV"</span><span style="color: #0000FF;">,</span>
mostFreqKSDF(s1, s2, 2, 100)
<span style="color: #000000;">s2</span> <span style="color: #0000FF;">:=</span> <span style="color: #008000;">"EWIWGGFSVDKATLNRFFAFHFILPFTMVALAGVHLTFLHETGSNNPLGLTSDSDKIPFHPYYTIKDFLG"</span>
s1 = "abracadabra12121212121abracadabra12121212121"
<span style="color: #000000;">mostFreqKSDF</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">100</span><span style="color: #0000FF;">)</span>
s2 = reverse(s1)
<span style="color: #000000;">s1</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"abracadabra12121212121abracadabra12121212121"</span>
mostFreqKSDF(s1, s2, 2, 100)</lang>
<span style="color: #000000;">s2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">mostFreqKSDF</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">100</span><span style="color: #0000FF;">)</span>
<!--</lang>-->
Output matches Go and Kotlin.
Output matches Go and Kotlin.


Retrieved from "https://rosettacode.org/wiki/Most_frequent_k_chars_distance"