Маленькая задачка
 

Предлагаю ради фана попробовать реализовать лучшим способом.

Задача: Вывести на экран числа, которые встречаются минимум два раза в разных строках файла.

Пример содержимого файла:
1 2 3 2
4 5 6 4
7 6 5 0

Предполагаемый результат: 5, 6

Мой вариант на Scala:

import scala.annotation.tailrec
import scala.io.Source

object Test extends App **
@tailrec def getListSet(iterator: Iterator[String], res:List[String]): List[String] =
if (!iterator.hasNext) res
else getListSet(iterator, iterator.next().split("\\s+").toSet.toList ::: res)

val filename = "c:\\digits.txt"
val result = getListSet(Source.fromFile(filename).getLines(), Nil)
.groupBy(k => k).filter(_._2.length > 1).keys
print(result.mkString(","))
**

Мой вариант на ObjectPascal с личными библиотеками.

program Fun ;

**$ifdef fpc****$mode objfpc****$h+****$endif**

uses TAVIntList, TAVStringFile ;

var IL:TIntList ;
ILK:TIntKeyList ;
i:Integer ;
begin

ILK:=TIntKeyList.Create() ;

with TStringFile.Create('C:\File.txt') do begin
while not EOF() do begin
IL:=TIntList.CreateFromSepList(ReadLine(),#32,[ilcRemoveRepeat]) ;
for i:=0 to IL.Count-1 do ILK.Inc(IL[i]) ;
IL.Free ;
end ;
Free ;
end ;

for i:=0 to ILK.Count-1 do
if ILK.Values[i]>=2 then Writeln(ILK.Key[i]) ;

ILK.Free ;
end.


Без библиотек, конечно, будет раза в 4 длиннее.

Полагаю Python с его срезами и tuples будет самым немногословным, а если еще и с применением его стандартной библиотеки re - тем паче.

Алгоритм вижу такой (писать лень):

1) построчно считать файл и записать в двумерный XY-массив

2) каждую "строку" массива отсортировать по знакоместу/возрастанию (индексу), получится типа:
[plain]
1 2 3
4 5 6
5 6 7 0
[/plain]

3) просуммировать столбцы. >=2 - вывести.

[code]
1 2 3
4 5 6
5 6 7 0
[/code]

C#, .NetFramework 4.0, WinFormsApplication

using System;
using System.IO;
using System.Windows.Forms;

namespace WindowsFormsApplication1
**
public partial class Form1 : Form
**
public Form1()
**
InitializeComponent();
**

private void button1_Click(object sender, EventArgs e)
**
string[] arraySTRING = File.ReadAllLines("test.txt");

for (int i = 0; i < arraySTRING.Length; i++)
**
string[] separators = **" "**;
string[] temp = arraySTRING[i].Split(separators, StringSplitOptions.RemoveEmptyEntries);

for (int j = 0; j < temp.Length; j++)
**
for (int k = 0; k < arraySTRING.Length; k++)
**
if (k != i)
**
if (arraySTRING[k].Contains(temp[j]))
**
if (listBox1.Items.Contains(temp[j]) == false)
listBox1.Items.Add(temp[j]);
break;
**
**
**
**
**
**
**
**

Комментарии обработчика кнопки:

// считываем в массив текстовый файл
string[] arraySTRING = File.ReadAllLines("test.txt");
// получаем массив из трёх элементов вида
// ** 1 2 3 2 , 4 5 6 4 , 7 6 5 0 **

// начинаем цикл по каждому элементу массива arraySTRING
for (int i = 0; i < arraySTRING.Length; i++)
**
// знак разделитель, функция Split воспринимает только массивы разделителей
string[] separators = **" "**;
// получаем массив temp элементов из одного элемента массива arraySTRING
string[] temp = arraySTRING[i].Split(separators, StringSplitOptions.RemoveEmptyEntries);

// начинаем вложенный цикл по каждому элементу массива temp
for (int j = 0; j < temp.Length; j++)
**
// начинаем ещё один вложенный цикл по начальному массиву arraySTRING
for (int k = 0; k < arraySTRING.Length; k++)
// если это не исходный элемент массива arraySTRING
if (k != i)
// если элемент массива arraySTRING содержит элемент массива temp
if (arraySTRING[k].Contains(temp[j]))
**
// проверка на повторный результат
if (listBox1.Items.Contains(temp[j]) == false)
// добавляем результат в список
listBox1.Items.Add(temp[j]);
// обрываем цикл
break;
**
**
**

2-economist > Идея интересная, но есть несколько вопросов:
1. Что делать с повторами?
2. Чтобы выбрать место надо составить список всех чисел в файле?

С остальными все более менее понятно. Еще бы оценки алгоритмам высчитать.

По каким параметрам алгоритм "самый лучший"? Самый короткий? Быстрый? Жрет памяти меньше всего? Ну и набор тестов надо бы нормальный - матрица 3х3 это не серьезно.

Предлагаю матрицу 10000x10000 с значениями от 0 до 100000.
Замерить время выполнения алгоритмов.

7-JustPass > O-нотация?
Если я не забыл как оно считается, то для решения в 0 получается для входного NxM: O(N^4*M^6).
Что есть до хрена =)

O() было бы конечно хорошо, но боюсь упремся в детали реализации языков. Несколько матриц (думаю хватит 1000х1000) и замерим время на примерно одинаковых машинах. Есть тесты? Можно конечно написать генератор, только кто его проверять будет? =)

40KHYTbIU - повторы надо убирать, конечно. А знакоместо выбирать не нужно, это же индекс (0-9), Прямо по нему и писать в массив.

Все эти алгоритмические задачи "для удовольствия" несут немного пользы. Вот пример маленькой программы, которая шлет SMS сообщения через модем или моб. телефон, взяв данные из таблицы 1С - на Python.

[code]
# -*- coding: utf-8 -*-
import os # все 8 тысяч библиотек
import re # языка Python -
import SMSSender # бесплатные!

a = SMSSender(3) #в () - номер COM-порта

# Код задействует кортежи, цикл и срезы строк.
# прочтем текстовый файл с разделителями табуляция:
# 79181234567 Оплатите задолженность 30000 руб.
# Это файл может быть получен из MS Excel или OpenOffice/LibreOffice Calc (через 1С итп)

reportFile=open('C:/sms_texts.txt', 'r')

for line in reportFile:
sms=re.split("\t", line)
tel=sms[0],
smsuni=sms[1].decode('cp1251') # Декодировали 1С/MSO итп) в utf-8
a.sendMessage(tel, smsuni)
time.sleep(20)

[/code]

[quote=JustPass;36660028]Несколько матриц (думаю хватит 1000х1000)[/quote]
От 0 и до скольки? Я думаю для чистоты эксперимента должен быть максимум 10 000 хотя бы. Чтобы в выборки строк не попадались часто одни и те же значения.

[quote=JustPass;36660028]Можно конечно написать генератор, только кто его проверять будет[/quote]
Я написал для себя генератор. Рандомом (в зависимости от текущей даты) генерит матрицу заданных размеров. Только файл txt не хилый получился, для матрицы 10 000х10 000 весил около 200 МБ.

Вот шота мне думается, что это на Lisp'e нада налобать.

13-Zobkor >welcome!
11-economist >к чему это все, еще и с рекламой?
10-JustPass >о каких деталях речь? Алгоритм можно оценить вполне конкретно, реализация дело поправимое.

40KHYTbIU - просто пример полезной программы. А "реклама" бесплатного языка - это вовсе не реклама, а популяризация. Тасазать свет знаний.

на бейсике, ля:)) if 1.1=1 then a+1, if a=> 2 print" Две единицы" бггг

С#, .NET 4.0, LINQ

string buffer = File.ReadAllText("c:\\1\\1.txt");
List<char> chars = buffer.ToList<char>();
chars=chars.FindAll(c1 => chars.FindAll(c2 => c2 == c1).Count >= 2).Distinct().ToList();
foreach (char c in chars) Console.WriteLine(c);

17-LostDaemon > а можно подробнее на словах?
А то мне кажется что если на входе:
2 2
1 1
У вас вернет 2 и 1.

Так и есть, я пропустил "мимо ушей" ключевое слово "В разных".
Вот корректировочка:

string buffer = File.ReadAllText("c:\\1\\1.txt");
List<char> chars = buffer.ToList<char>();
chars = chars.FindAll(c1 => chars.FindAll(c2 => c2 == c1).Count >= 2).Distinct().ToList(); //выбираем все повторяющиеся символы, в независимости от строки в которой они находятся
//Проверяем если ли символ конца строки между первым и последним вхождением символа.
foreach (char c in chars)
if(buffer.IndexOf(Environment.NewLine, buffer.IndexOf(c), buffer.LastIndexOf(c) - buffer.IndexOf(c))>=0&&c!='\n'&&c!='\r') Console.WriteLine(c);

19-LostDaemon > что ваша программа выведет при таком входном файле:
12 13 4
31 21 34
Есть так же подозрение на отображение пробела =)

выводит 1234, но пробелы тоже пишет.

Можно просто добавить &&c!=' ' к условию в последней строке:

if(buffer.IndexOf(Environment.NewLine, buffer.IndexOf(c), buffer.LastIndexOf(c) - buffer.IndexOf(c))>=0&&c!='\n'&&c!='\r') Console.WriteLine(c);

А еще лучше с самого начала сделать buffer=buffer.Replace(" ","");

[url]http://pastebin.com/ZcQBrJQE[/url]

22-LostDaemon > в условии было про числа, а не символы И какой то уж слишком большой оверхед у вас ИМХО.=)

22-Поскольку в задании было упоминание "в разных строках файла" я решил, что пример с числами- это всего лишь частный случай и работал с символами.

Мой код не претендует на "лучший способ". В реальной практике я бы скорее всего делал через словарь или перебор, но оба этих варианта в той или иной мере уже были предложены выше.

25-LostDaemon > Ок, зачет =)
можно подробнее о подходе перебором и словарем? а то я чет не понимаю.

Перебором со словарем:
1)Читаем в строку
2)Проходим последовательно все символы, помещая их в словарь Dictionary<char,int>, где Key-символ, Value-номер строки в которой он встретился.
3)Если находим символы конца строки, наращиваем счетчик номера строки.
4)Если символ уже есть в словаре и его Value не совпадает с текущим номером строки, то выводим этот символ в результат, а соответствующее этому символу Value в словаре меняем на -1. При значении Value=-1 обработку символа пропустить.


string input = File.ReadAllText("c:\\1\\1.txt");
Dictionary<char, int> Dict = new Dictionary<char, int>();//Словарь Key-символ Value-№строки где впервые встретился
int LineCounter = 0; //счетчик строк
foreach (char c in input) //перебираем символы
**
switch(c)
**
case '\r': break;
case '\n': LineCounter++; break; //конец строки - наращиваем счетчик строк
default:
int i=-1;
if (Dict.TryGetValue(c, out i)) //получаем номер строки первого вхождения символа, если таковое имело место
**
//если номер строки текущего символа не совпадает с номером в словаре и не равен флагу -1(см. далее) - значит нашли символ, повторяющийся в разных строках - выводим его в консоль , а значение value в словаре устанавливаем в -1, чтобы пропустить обработку этого символа в дальнейшем.
if (i != LineCounter && i != -1) ** Dict[c] = -1; Console.WriteLine(c); **
**
else
**
Dict.Add(c, LineCounter); //добавляем символ в словарь если еще не встречался
**
break;
**
**
Console.ReadLine();

Мои 5 копеек
1. Считываем все в массив размером А х Б
2. Построчно проходим по массиву, оставляя только уникальные значения
3. Рассматриваем двухмерный массив А х Б как одномерный А*Б
4. Снова задействуем алгоритм, оставляющий только уникальные значения, с поправкой, что значения дублей еще и на экран вывести

Поправка, "2. Построчно проходим по массиву, оставляя в каждой строке только уникальные значения"

AlienX - от оно... 2 вариантты