FANDOM


Задача про T9Edit

Постановка (gromozeka, 15.10.2007)

Думаю, все здесь присутствующие знакомы с системой Т9 ( http://ru.wikipedia.org/wiki/T9 ), соответствие цифр и букв кириллицы в этой системе следующее:
2 - а,б,в,г
3 - д,е,ж,з
4 - и,й,к,л
5 - м,н,о,п
6 - р,с,т,у
7 - ф,х,ц,ч
8 - ш,щ,ъ,ы
9 - ь,э,ю,я
Таким образом, каждой последовательности букв соответствует одна последовательность цифр, например, слову "последовательность" соответствует последовательность "556433522634955669".
Скачиваем словарь словоформ русского языка отсюда: http://www.artint.ru/projects/frqlist/words.num.zip
1) Какой процент слов в словаре "уникален" (последовательность цифр, соответствующая слову из словаря, соответствует только этому слову)?
2) Выведите последовательность цифр, которой соответствует наибольшее кол-во слов из словаря, выведите соответствующие слова.
3) Выведите самую длинную последовательность, которой соответствует более одного слова из словаря, выведите соответствующие слова.
4) Создайте словарь последовательностей:
В каждой строке файла последовательность цифр, за ней все соответствующие ей слова отсортированные лексикографически. Сами строки, разумеется, тоже отсортированы.
"словарная статья" может выглядеть например так:
6329 - сдаю, себя, тебя

Python, Vladimir the Red Sunny, 17.10.2007, link Используется вспомогательный файл "t9_dict.txt", состоящий из 8 строк вида "2 а б в г" и т. д.

Забыл сказать - тот файл я предварительно передраконил, чтобы остались только сами слова, по 1 на строку.

from collections import defaultdict

def word_to_t9(w, d):
    return ''.join([d[l] for l in w])

def unique_percent(dict):
    total = len(dict)
    unique = 0
    for el in dict.values():
        if len(el) == 1: unique+=1    
    return 100*unique/total

def max_words(dict):
    max_len = 0
    max_elem = -1
    for el in dict.keys():
        if len(dict[el]) > max_len:
            max_len = len(dict[el])
            max_elem = el
    return (max_elem, max_len)

def max_non_unique(dict):
    max_len = 0
    max_elem = -1
    for el in dict.keys():
        if len(dict[el]) < 2: continue
        if len(el) > max_len:
            max_len = len(el)
            max_elem = el
    return (max_elem, max_len)

fi = open("t9_dict.txt", "rb")
dict = {}
for line in fi:
    lst = line.strip().split(' ')
    n, s = lst[0], lst[1:]
    for i in s:
        dict[i] = n
fi.close()

f_dict = defaultdict(list)
fi = open("words.txt", "rb")
for word in fi:
    f_dict[word_to_t9(word.strip(), dict)] += [word.strip()]
fi.close()

str_list = [i[0]+' - '+', '.join(i[1]) for i in f_dict.items()]
str_list.sort()

fo = open("result.txt", "wb")
for s in str_list:
    fo.write(s + '\r\n')
fo.close()

up = unique_percent(f_dict)
mw = max_words(f_dict)
mnu = max_non_unique(f_dict)

report = open("report.txt", "wb")
report.write("Unique words: " + `up` + " %\r\n")
report.write("Max. words: " + mw[0] + ", " + `mw[1]` + " words\r\n")
report.write("The words are: " + ", ".join(f_dict[mw[0]]) + "\r\n")
report.write("The longest non-unique: " + mnu[0] + ", " + `mnu[1]` + " symbols\r\n")
report.write("The words are: " + ", ".join(f_dict[mnu[0]]) + "\r\n")
report.close()


Python, gromozeka, 18.10.2007, link Начал подвергать программу Владимира жесткой обфускации на случай, если кому-нибудь вздумается меряться длиной кода (программа классно написанна, даже жалко с ней так поступать icon_smile.gif ):

# -*- coding: cp1251 -*-
from collections import defaultdict
dct,rus={},"абвгдежзийклмнопрстуфхцчшщъыьэюя"
for i in xrange(len(rus)): dct[rus[i]]=`i/4+2`
fd = defaultdict(list)
for w in open("words.txt", "r"): fd[''.join([dct[l] for l in w.strip()])] += [w.strip()]
open("result.txt", "w").writelines([s+"\r\n" for s in sorted([i[0]+' - '+', '.join(i[1]) for i in fd.items()])])
up = 100*len([el for el in fd.values() if len(el)==1])/len(fd)
mw = max([(len(fd[el]),el) for el in fd.keys()])
mnu = max([(len(el),el) for el in fd.keys() if len(fd[el])>=2])
report = open("report.txt", "w")
report.write("Unique words: " + `up` + " %\r\n")
report.write("Max. words: " + mw[1] + ", " + `mw[0]` + " words\r\n")
report.write("The words are: " + ", ".join(fd[mw[1]]) + "\r\n")
report.write("The longest non-unique: " + mnu[1] + ", " + `mnu[0]` + " symbols\r\n")
report.write("The words are: " + ", ".join(fd[mnu[1]]) + "\r\n")
report.close()


J, danio, 19.10.2007, link

load 'files'
lz =: ' abc  def  ghi  jkl  mno  pqrs tuv  wxyz '
fw=: #~ [:>([:*/e.&lz)&.>
in=: fw 'b' fread '/usr/share/dict/british-english'    
dgt=: ([:<.5%~lz&i.){'23456789'"1
dgtK=: dgt&.>in    
ch=: <@:/:~;~[:dgt(0&{::)
dict=: /:~dgtK ch/. in    
unPerc=: (100*#%~[:#~.) dgtK
lwChap=: {.(\:[:(#&.>)}."1) dict
mChap=: (#~[:>[:(1<#)&.>{:"1) dict
lkChp=: {.(\: [:(#&.>){."1) mChap

fmt=: [:([,', ',])/[:>[:>{:
't9dict.txt' fwrites~ (([:>{.),' - ',fmt)"1 dict


K, zevun, 20.10.2007, link

t9: {:[(x<"а") | (x>"я"); "\0"; *$2+(x>/:("г";"з";"л";"п";"у";"ч";"ы";"я"))?0]}'

trim: {(-+/&\|" "=x)_ x}
split: {1_'(&x=y)_ x:y,x}
nfltr: {y@&~|/'x=y . z}
join: {(#x)_ ,/x,/:y}

d: ,/(nfltr["\0";;(;0)]@{+(t9'x;x)}@split[;" "]@trim@)'0:"words.num"
g: =d[;0]
g: g[<d[g[;0]]]
n: #:'g
r: ,"Unique: ",($_(100*#&1=n)%#g),"%"
m: g[*>n]
r,: ,"Max words: ",d[*m;0],", ",($#m)," word(s)"
r,: ,"The words are: ",join[", "]d[m;1]
m: &1<n
m: g@m@*>#:'d[g[m;0];0]
r,: ,"The longest non-unique: ",d[*m;0],", ",($#d[*m;0])," symbol(s)"
r,: ,"The words are: ",join[", "]d[m;1]
"report.txt" 0:r
"t9dict.txt" 0:{d[*x;0],"\t-\t",join[", "]{x@<x}d[x;1]}'g


C++, Narwal, 21.10.2007, link

#include <TCHAR.h>
#include "fstream"
#include <map>
#include <vector>
#include <string>

#include <utility>
#include <iostream>
#include <algorithm>

typedef std::multimap< std::string, std::string > MultiMap;

struct DictTrait
{
    int total;
    int unique;
    std::pair< size_t, std::vector< MultiMap::const_iterator > > maxLength;
    std::pair< size_t, std::vector< MultiMap::const_iterator > > maxRange;

    DictTrait()
        : total( 0 )
        , unique( 0 )
        , maxLength( std::make_pair( 0, std::vector< MultiMap::const_iterator >() ) )
        , maxRange( std::make_pair( 0, std::vector< MultiMap::const_iterator >() ) )
    {
    }
    
    void ProcessUnique( MultiMap::const_iterator b, MultiMap::const_iterator e, size_t rangeLen )
    {
        ++total;

        if ( rangeLen == 1 )
        {
            ++unique;
        }
    }
    
    void ProcessMaxRange( MultiMap::const_iterator b, MultiMap::const_iterator e, size_t rangeLen )
    {
        if ( rangeLen > maxRange.first )
        {
            maxRange.first = rangeLen;
            maxRange.second.clear();
            maxRange.second.push_back( b );
        }
        else if ( rangeLen == maxRange.first )
            maxRange.second.push_back( b );
    }
    
    void ProcessMaxLength( MultiMap::const_iterator b, MultiMap::const_iterator e, size_t rangeLen, size_t wordLength )
    {
        if ( wordLength > maxLength.first && rangeLen > 1 )
        {
            maxLength.first = wordLength;
            maxLength.second.clear();
            maxLength.second.push_back( b );
        }
        else if ( wordLength == maxLength.first && rangeLen > 1 )
        {
            maxLength.second.push_back( b );
        }
    }

};

struct ConverterToT9
{
private:
    typedef std::map< char, std::string > Map;
    Map map_;

public:
    ConverterToT9()
    {
        std::ifstream file( "D:\\programming\\tasks\\t9\\t9_dict.txt" );
        char num;
        std::string tmp, str;
        while( !file.eof() )
        {
            file >> num >> tmp >> str;
            map_.insert( std::make_pair( num, str ) );
        }

        file.close();
    }
    
    std::string Execute( const std::string& str ) const
    {
        std::string res;
        for ( std::string::const_iterator i = str.begin(); i != str.end(); ++i )
        {
            res.push_back( CharToT9( *i ) );
        }

        return res;
    }

private:
    struct CmpChar
    {
        char s_;

        CmpChar( char s )
        {
            s_ = s;
        }

        bool operator()( const std::pair< const char, std::string >& i ) const
        {
            return i.second.find( s_ ) != std::string::npos;
        }
    };

    char CharToT9( char s ) const
    {
        Map::const_iterator i = std::find_if( map_.begin(), map_.end(), CmpChar( s ) );
        if ( i == map_.end() )
            throw std::out_of_range( "Char wasn't found" );

        return i->first;
    }
};

void LoadDict( MultiMap& res, const ConverterToT9& conv )
{
    int num;
    float freq;
    std::string str;

    std::ifstream in( "D:\\programming\\tasks\\t9\\words.num" );
    if ( !in.is_open() )
        throw std::invalid_argument( "Can't open file" );

    while( !in.eof() )
    {
        in >> num >> freq >> str;

        res.insert( std::make_pair( conv.Execute( str ), str ) );
    }

    in.close();
}


int _tmain( int argc, TCHAR* argv[] )
{
    //*
    ConverterToT9 conv;
    MultiMap res;
    DictTrait trait;
    size_t rangeLen;
    size_t wordLength;

    LoadDict( res, conv );
    
    std::pair< MultiMap::iterator, MultiMap::iterator > range = std::make_pair( res.begin(), res.begin() );
    range = res.equal_range( range.first->first );

    std::ofstream out( "D:\\programming\\tasks\\t9\\result.txt" );
    while ( ( range.first != res.end() ) && ( range.second != res.end() ) )
    {
        rangeLen = std::distance( range.first, range.second );
        wordLength = range.first->first.size();
        
        trait.ProcessUnique( range.first, range.second, rangeLen );
        trait.ProcessMaxRange( range.first, range.second, rangeLen );
        trait.ProcessMaxLength( range.first, range.second, rangeLen, wordLength );
        
        out << range.first->first << " - ";
        while ( range.first != range.second )
        {
            out << range.first->second << ", ";
            ++range.first;
        }

        out << "\n";

        range = res.equal_range( range.first->first );    
    }

    out << "Unique percent: " << 100 * trait.unique / trait.total << "%" << "\n";
    out << "Max range: " << trait.maxRange.first << " words\n";
    out << "Words are: \n";
    for ( size_t i = 0; i < trait.maxRange.second.size(); ++i )
    {
        out << "    " << ( *( ( trait.maxRange.second )[ i ] ) ).second << "\n";
    }
    out << "Max length: " << trait.maxLength.first << " symbols\n";
    out << "Words are: \n";
    for ( size_t i = 0; i < trait.maxLength.second.size(); ++i )
    {
        out << "    " << ( *trait.maxLength.second[ i ] ).second << "\n";
    }

    out.close();

    getchar();

    return 0;
}

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.