Most frequent k chars distance: Difference between revisions

{{trans|Python}}

 

DefaultDict[Char, Int] occuDict

L(c) inputString

print(dict2, end' ":\n")

print(dict2.map((c, cnt) -> c‘’String(cnt)).join(‘’))

 

{{out}}

 

=={{header|C++}}==

#include <vector>

#include <map>

return 0 ;

}

{{out}}

<pre>MostFreqKHashing( s1 , 2 ) = L9T8

=={{header|Go}}==

{{trans|Kotlin}}

 

import (

s2 = reverseStr(s1)

mostFreqKSDF(s1, s2, 2, 100)

 

{{out}}

 

=={{header|Haskell}}==

where

import Data.List ( nub , sortBy )

mostFreqKSDF :: String -> String -> Int ->Int

mostFreqKSDF s t n = mostFreqKSimilarity ( mostFreqKHashing s n ) (mostFreqKHashing t n )

{{out}}

<pre>mostFrequentKHashing "LCLYTHIGRNIYYGSYLYSETWNTGIMLLLITMATAFMGYVLPWGQMSFWGATVITNLFSAIPYIGTNLV" 2

 

=={{header|J}}==

mfksDF =: {:@:[ - (mfks@:(mfkh&.>)~ {.)~

 

NB. No need to fix mfksDF

mfkh =: mfkh f.

 

fkh =. ;@:,@:(":&.>) NB. format k hash

 

'pass'

)

'''Notes''': As of press time, there are significant discrepancies between the task description, its pseudocode, the test cases provided, and the two other existing implementations. See the [[Talk:Most frequent k chars distance#Prank_Page.3F|talk page]] for the assumptions made in this implementation to reconcile these discrepancies (in particular, in the scoring function).

 

Translation of the pseudo-code of the Wikipedia article [[wp:Most frequent k characters]] to [[wp:java]] implementation of three functions given in the definition section are given below with [[wp:JavaDoc]] comments:

 

import java.util.Comparator;

import java.util.HashMap;

}

 

 

 

Defines the functions for counting and frequency outside of the hashing function, as it is easier to calculate the comparison from a structured result rather than parsing a hash.

 

const kCounts = str => {

const counts = {};

const mostFreqKSDF = (str1, str2, k, maxDistance) => {

return maxDistance - mostFreqKSimilarity(str1, str2, k);

 

'''Testing with Jest'''

expect(mostFreqKHashing(str1, 2)).toBe("L9T8");

});

test("SDF of strings 1 and 2 with k=2 and max=100 is 83", () => {

expect(mostFreqKSDF(str1, str2, 2, 100)).toBe(83);

 

'''Testing in Console'''

const str2 = "EWIWGGFSVDKATLNRFFAFHFILPFTMVALAGVHLTFLHETGSNNPLGLTSDSDKIPFHPYYTIKDFLG";

const K = 2;

console.log(mostFreqKHashing(str1, K));

console.log(mostFreqKHashing(str2, K));

 

{{out}}

 

'''Preliminaries'''

def bow(stream):

reduce stream as $word ({}; .[($word|tostring)] += 1);

| sort_by((.[1]|f), .[0])

| reverse

'''The Tasks'''

def MostFreqKHashing($K):

def chars: explode | range(0;length) as $i | [.[$i]] | implode;

| MostFreqKSDF(2; 100);

 

{{out}}

<pre>

 

I have no idea what NULL0 is supposed to mean so I've ignored that.

 

fun mostFreqKHashing(input: String, k: Int): String =

s2 = s1.reversed()

mostFreqKSDF(s1, s2, 2, 100)

 

{{out}}

In order to avoid the limitation to 10 occurrences, we chose to use an ordered table (equivalent to Python OrderedDict). We could have used Kotlin solution or used a sequence of tuples (char, count) but the ordered table gives better performance.

 

 

type CharCounts = OrderedTable[char, int]

echo "mostFreqKHashing(str1, 2) = ", mostFreqKHashing(S1, 2)

echo "mostFreqKHashing(str2, 2) = ", mostFreqKHashing(S2, 2)

 

{{out}}

 

=={{header|Perl}}==

use strict ;

use warnings ;

print "MostFreqKHashing ( " . '$firststring , 2)' . " is " . mostFreqHashing( $firststring , 2 ) . "\n" ;

print "MostFreqKHashing ( " . '$secondstring , 2)' . " is " . mostFreqHashing( $secondstring , 2 ) . "\n" ;

{{out}}

<pre>MostFreqKHashing ( $firststring , 2) is L9T8

=={{header|Phix}}==

{{trans|Go}}

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<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>

<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>

Output matches Go and Kotlin.

 

{{works with|Python|2.7+}}

'''unoptimized and limited'''

def MostFreqKHashing(inputString, K):

occuDict = collections.defaultdict(int)

 

def MostFreqKSDF(inputStr1, inputStr2, K, maxDistance):

 

'''optimized'''

 

A version that replaces the intermediate string with OrderedDict to reduce the time complexity of lookup operation:

def MostFreqKHashing(inputString, K):

occuDict = collections.defaultdict(int)

 

def MostFreqKSDF(inputStr1, inputStr2, K, maxDistance):

Test:

str2 = "EWIWGGFSVDKATLNRFFAFHFILPFTMVALAGVHLTFLHETGSNNPLGLTSDSDKIPFHPYYTIKDFLG"

K = 2

print("%s:"%dict2)

print(''.join(c + str(cnt) for c, cnt in dict2.items()))

{{out}}

<pre>

=={{header|Racket}}==

 

 

(define (MostFreqKHashing inputString K)

;; (Should add more tests, but it looks like there's a bunch of mistakes

;; in the given tests...)

 

=={{header|Raku}}==

Maybe I am too hasty though. Lets give it a try. Implement a MFKC routine and run an assortment of words through it to get a feel for how it hashes different words.

 

# which can be joined to make a string or manipulated further.

 

>;

 

{{out}}

<pre>Bag(i2n2(151))</pre>

 

=={{header|Ring}}==

# Project : Most frequent k chars distance

 

next

return aList

Output:

<pre>

 

=={{header|Sidef}}==

 

var seen = Hash()

MostFreqKSDF(s, t, k, limit),

)

{{out}}

<pre>

=={{header|Tcl}}==

{{works with|Tcl|8.6}}

 

proc MostFreqKHashing {inputString k} {

set h2 [MostFreqKHashing $inputStr2 $k]

expr {$limit - [MostFreqKSimilarity $h1 $h2]}

Demonstrating:

set str2 "EWIWGGFSVDKATLNRFFAFHFILPFTMVALAGVHLTFLHETGSNNPLGLTSDSDKIPFHPYYTIKDFLG"

puts [MostFreqKHashing $str1 2]

puts [MostFreqKHashing $str2 2]

{{out}}

<pre>

;A more efficient metric calculator

This version is appreciably more efficient because it does not compute the intermediate string representation “hash”, instead working directly on the intermediate dictionaries and lists:

set c1 [set c2 {}]

foreach ch [split $inputStr1 ""] {dict incr c1 $ch}

}

return [expr {$limit - $s}]

It computes the identical value on the identical inputs.

 

=={{header|Typescript}}==

{{trans|Javascript}} with added type annotations

const kCounts = (str: string): Record<string, number> => {

const counts: Record<string, number> = {};

const mostFreqKSDF = ( str1: string, str2: string, k: number, maxDistance: number ): number => {

return maxDistance - mostFreqKSimilarity(str1, str2, k);

 

=={{header|Wren}}==

{{libheader|Wren-sort}}

{{libheader|Wren-trait}}

import "/sort" for Sort

import "/trait" for Stepped

s1 = "abracadabra12121212121abracadabra12121212121"

s2 = s1[-1..0]

 

{{out}}