[Burichan] [Futaba] [Gurochan] [Photon] [Tomorrow] - [Главная] [Управление]

[Назад]
Ответ
Leave these fields empty (spam trap):
Имя
E-mail
Тема
Сообщение
Файл
Подтверждение
Пароль (для удаления файлов и сообщений)
  • Supported file types are: GIF, JPG, PNG
  • Maximum file size allowed is 1000 KB.
  • Images greater than 200x200 pixels will be thumbnailed.

e3278e63y.jpg (0.0 KB, -1x-1)
0 No.34703  
Няши, как называется эта задача? Решить не получилось, гугление условия не помогает. Условие звучит как-то так:

Дан большой текст, где может встречаться любой символ. В тексте нужно сделать замену x на y, y на x. Замену можно делать только сразу по всему тексту. Заменить x на z, y на x, z на y нельзя, z может быть в исходном тексте (z - любой символ или последовательность символов). Как реализовать замену?
>> No.34712  
>>34703`


$ echo 'qxxxwwwyrrytxyyyxiiixyydddydyhyjylllyyxyxyy' | tr xy yx
qyyywwwxrrxtyxxxyiiiyxxdddxdxhxjxlllxxyxyxx

` Самое короткое придуманное решение.
Хотя задача элементарная, на любом языке программирования это один цикл и два условия.
>> No.34714  
>>34712
tr нет. Какие два условия? Не понимат.
>> No.34715  
>>34714
Ах, эти. Так это посимвольная замена, а в условии только глобальная. В оригинале человек и условный текстовый редактор, замена работает как обычно.
>> No.34722  
>>34714
А регэкспы есть? Потому что других способов глобальной замены не придумывается.
>> No.34723  
>>34722
Регэкспов нет, только find/replace, только хардкор.
>> No.34724  
>>34723
А можно делать больше одной замены по тексту?
>> No.34726  
>>34724
Можно. Число замен вообще не ограничено (по условию).
>> No.34728  
>>34726
Тогда чисто теоретически:
1) первым реплейсом заменяем x на что-то вроде x-x ;
2) вторым реплейсом заменяем все y на y-y ;
3) третьим реплейсом заменяем x-x на y ;
4) четвёртым реплейсом заменяем y-y на x.
Хотя, кажется, без посимвольных чеков тут не обойтись. Надо быть хитрее. ПОтом ещё подумать попробую.
>> No.34729  
>>34728
Не пройдет, т.к. '-' может быть в исходном тексте; например, подстрока x-xx-xx-xx-xx-xx-xy-yy-yy-yy-yy-yy-yy-y преобразуется в xxxxxxx-xx-xx-xx-xx-xx-xx-x.
>> No.34730  
Вы когда гуглить научитесь, двоечники?

a = a xor b;
b = b xor a;
a = a xor b;

(какая шикарная капча: «прибывших трудолюбие»)
>> No.34731  
>>34729
Таки да, и просто удлиннять параметры не выходит, чёрт.`


$ cat ./replace.pl
#!/usr/bin/perl -w

my $line = $ARGV[0];
print( $line , "\n\r" );
$line =~ s/x/xxxx/g;
$line =~ s/y/yyyy/g;
$line =~ s/xxxx/y/g;
$line =~ s/yyyy/x/g;
print ( $line , "\n\r" );


$ perl ./replace.pl x-xx-xx-xx-xx-xx-xy-yy-yy-yy-yy-yy-yy-y
x-xx-xx-xx-xx-xx-xy-yy-yy-yy-yy-yy-yy-y
y-yy-yy-yy-yy-yy-xy-xx-xx-xx-xx-xx-xx-x

$ perl ./replace.pl qxxxwwwyrrytxyyyxiiixyydddydyhyjylllyyxyxyy
qxxxwwwyrrytxyyyxiiixyydddydyhyjylllyyxyxyy
qyyywwwxrrxtxxxyyiiixxydddxdxhxjxlllxxxxxyy

` Как-то идеи, кроме как пихать непечатаемые символы, поиссякли. Ещё подумаю.
>> No.34732  
>>34730
xor - не replace же. Мне кажется, тут по другому поиздеваться хотели.
>> No.34735  
>>34732
Совсем упорот, что ли? Я принцип демонстрирую.
replaceall(a, a xor b);
replaceall(b, b xor a);
replaceall(a, a xor b);
> Мне кажется, тут по другому поиздеваться хотели.
Чтобы делать обоснованные предположения на эту тему, необходимо знать контекст задачи. Название предмета, на каком языке принимаются задачи, какие темы недавно рассмотрены…
>> No.34736  
>>34735
Няша, xor нет, и xor swap нет. Задача вообще не для погромистов. Модель - длинный текст в notepad и терпеливая блондинка, которая знает про Ctrl-H. Что ей делать?
Контекста нет. Абстрактный паззл.
Ответы принимаются в виде описания алгоритма.
>> No.34737  
>>34703
Один цикл, 2 условия и в каждом ещё по условиюборемся с обратной заменой
В паскале примерно так:
For i:=1 to n do //n - длинна текста
If a[i]=x
a[i]:=y
k:=1;
If a[i]=y
if k<>1
a[i]:=x
k:=0; //к - переменная по борьбе с обратной заменой
End;
не бейте ногами, синтаксис забыл напроч
>> No.34738  
>>34736
Блеать.
notepad - правка - заменить
Или не катит?
>> No.34739  
>>34737
Выше по треду:
> Так это посимвольная замена, а в условии только глобальная.
Не решение.
>> No.34740  
>>34738
Дочитай условие до конца. Ну, заменишь ты один раз x на y, как ты будешь "первоначальные" y искать и заменять их на х?
>> No.34742  
>>34737
В цикле нельзя.

>>34738
См. >>34740

ОП
>> No.34746  
Эта задача нерешаема. Проблема стоит в том, чтобы отделить сущности, которые были в тексте до нас, от сущностей, которые мы внесли. Какую бы мы замену не сделали, найдется такой текст, в котором невозможно будет отличить замененные буквосочетания от уже находившихся в тексте. Единственный вариант решения этой задачи - обеспечение единственности замены (т.е. каждый символ может быть обработан только один раз), чего по условию не достигнешь.

капча весть лечить
>> No.34747  
>>34746
Утверждается, что задача решаема (за что купил...). Есть строгое доказательство нерешаемости?
>> No.34749  
Анон, есть такая задачка: есть файл A с полными именами файлов (один на строку) и файл Б, в котором каждая строка либо пустая, либо тоже имя файла. Как сделать так, чтобы из файла А были стерты все строки, которые есть в файле Б? Средствами командной строки, по возможности. Ну и sed, awk.
>> No.34750  
>>34742
Переформулируй задачу и скажи чем можно пользываться.
А если забить 2 масива, один с номерами символов Х, другой - У, а потом все елементы с такими номерами поменять? Или это опять "нельзя"?
>> No.34753  
>>34747
ну, хз, как это обосновать матанно, но простая логика говорит, что понадобится как минимум две замены. А значит, какое-то промежуточное выражение обязательно встретится в тексте и всё испортит
>> No.34755  
>>34749
> Как сделать так, чтобы из файла А были стерты все строки, которые есть в файле Б
Может, проще будет
> Как получить файл В, в котором будет то, чего нет в в Б, но есть в А
А потом `mv В А` ?
>> No.34756  
>>34750
Попробую.
Дана строка [a-z] неизвестной конечной длины. Все x нужно заменить на y, y на x. Других изменений в конечной строке по сравнению с начальной быть не должно. В заменах нельзя использовать символы, отсутствующие в строке (метки). Нельзя использовать замены с длиной, сравнимой с длиной строки (это из комментов). Замены бывают только s///g (регэкспов нет). Количество замен (шагов) не ограничено. Работать можно только со строкой (массивы "нельзя").
Задача вообще не предполагает использование определенного языка. Имитация тупой замены по тексту в блокнотике.

>>34747
> Какую бы мы замену не сделали, найдется такой текст, в котором невозможно будет отличить замененные буквосочетания от уже находившихся в тексте.
Мне кажется, что результаты замены нужно отличать не от находившихся в исходном тексте сочетаний, а от находящимся в тексте после такой замены. Например, меняем x на xy. После замены не будет ху, которые пришли из исходника. Обратная замена xy на x возвращает исходный текст.
>> No.34758  
>>34756
> Например, меняем x на xy. После замены не будет ху, которые пришли из исходника. Обратная замена xy на x возвращает исходный текст.
Не работает. Точнее, работает, но у нас первый проход заменой x заменяет всё на xy , а второй проход заменой y заменяет как оригинальные y , так и полученные в результате предыдущей замены. "Многопоточный" реплэйсмент не позволяется условием задачи.
>> No.34759  
\7 может быть в исходном тексте?
>> No.34760  
>>34759
У нас, собственно, в это и упёрлось, что при условии, что в тексте могут быть абсолютно любые символы. Если заранее известно, какой символ может отсутствовать в тексте, задача решаема, иначе - нет.
>> No.34761  
>>34756
> Например, меняем x на xy. После замены не будет ху, которые пришли из исходника. Обратная замена xy на x возвращает исходный текст.
В том то и дело, что будут (предполагаем худший вариант что в тексте есть всевозможные сочетания любых символов). Если мы их попытаемся заменить на что-нибудь ещё (xyx), в тексте обязательно встретится и такая комбинация... и так далее.
>> No.34762  
s \ \\
s x \x
s y x
s \x y
s \\ \
(вспоминая Си)
Как-то так?
>> No.34763  
>>34758
>>34761
Нет, я имею виду ровно то, что замена x на xy, потом xy на х не изменяет текст. Т.е. утверждение
> Какую бы мы замену не сделали, найдется такой текст, в котором невозможно будет отличить замененные буквосочетания от уже находившихся в тексте.
не то чтобы неверно, но есть такие замены, для которых не требуется отличать "замененные" от "уже бывших", т.к. "бывшие" перестали существовать.

>>34759
В тексте может быть всё. Не о том задача. Посмотри переформулировку в >>34756 (нельзя использовать символы, которых нет в тексте) - мб так яснее.
>> No.34764  
>>34763
> но есть такие замены, для которых не требуется отличать "замененные" от "уже бывших", т.к. "бывшие" перестали существовать.
что-то мне подсказывает, что это только те типы замен, в которых заменяемая строка является началом замещающей, а ими одними не обойдешься
>> No.34765  
>>34762
Как \ любой другой символ в строке.
>> No.34766  
>>34765
Не сработает, после s y x появятся \x, которые потом восстановятся в у, т.е. по этим позициям замена не произойдет.
>> No.34767  
>>34766
Хорошо, тогда s y \y и так далее.
>> No.34768  
>>34767
Похоже, там нужно
s x \x\
s y /y/
и т.д.
Не успеваю проверить.
>> No.34769  
>>34768
на строке \x\y\/x/y/ не сработает
>> No.34773  
>>34769
`


0 \x\z\/x/z/
s x \x\ \\x\\z\/\x\/z/
s z /z/ \\x\\/z/\/\x\//z//
s \x\ \z\ \\z\\/z/\/\z\//z//
s /z/ /x/ \\z\\/x/\/\z\//x//
s \z\ z \z\/x/\/z//x//
s /x/ x \z\x\/z/x/

`
>> No.34774  
>>34773
То есть, закрывающая не обязательна
`


0 \x\z\/x/z/
s x \x \\x\z\/\x/z/
s z /z \\x\/z\/\x//z/
s \x \z \\z\/z\/\z//z/
s /z /x \\z\/x\/\z//x/
s \z z \z\/x\/z//x/
s /x x \z\x\/z/x/

`
>> No.34782  
>>34774
\ → \\
x → \x
y → \y
\x → y
\y → x
\\ → \
>> No.34784  
>>34782
Анон, ты близок, но опять же на определённых последовательностях работает:
`


$ cat replace.pl
#!/usr/bin/perl -w

my $line = $ARGV[0];
print( $line , "\n\r" );
$line =~ s/d/dd/g;
$line =~ s/x/dx/g;
$line =~ s/y/dy/g;
$line =~ s/dx/y/g;
$line =~ s/dy/x/g;
$line =~ s/dd/d/g;
print ( $line , "\n\r" );


$ perl ./replace.pl dyyyddyxxxydydyxxxxdyydydxdddddddyyyyyxxd
dyyyddyxxxydydyxxxxdyydydxdddddddyyyyyxxd
dxxxddxyyyxdxdxyyyydxxdxdxdddddddxxxxxyyd

`
>> No.34853  
>>34784
Вижу, в чём проблема. Забавная задача.
>> No.34856  
>>34703
Тред не читай @ сразу отвечай.

Эта задача точно имеет решение? Я бы рассмотрел текст только из символов x y z для простоты. Любая замена x или y на любую последовательность символов не годится, потому что есть вероятность встретить такую же последовательность и заменить её по ошибке. Единственный выход, как мне кажется, перед началом замены узнать количество символов в тексте и затем заменить, скажем, все x на последовательность, длина которой должна быть больше исходного текста. Тогда такая последовательность заведомо не встретится. Щас некогда думать дальше о возможных проблемах, так что попробуй обмозговать эту идею сам.
>> No.34862  
Т=0
начало
цикл по
Записываем Т бинарным кодом
Переводим 0 в х, 1 в у
Проверяем, есть ли такое слово в тексте
Нет слова-выходим из цикла

перед каждым х и у в тексте добавляем такое слово
проверяем текст, сколько там таких слов, и если это не Т-убираем изменения в тексте и идём в начало

заменяем все Словох на у
заменяем все Словоу на х
всё
>> No.34909  
>>34703
В два прохода. Первый раз запомнить порядковый номер символа и тип преобразования, во второй раз преобразовывать по этому списку.

если только find/replace, тогда нужно сначала рандомом сгенерировать последовательность Z, которой в тексте заведомо нет, проверить это дело find'ом. Ну а потом x->Z, y->x, Z->y.
>> No.34911  
>>34856
Точно имеет.

>>34862
>>34909
> В два прохода.
Неважно. Проходов замены может быть много. Но:
> Проверяем
> проверить

В редакторе нет find, только replace.
>> No.34912  
просмотрел

>>34856
> узнать количество символов в тексте и затем заменить, скажем, все x на последовательность, длина которой должна быть больше исходного текста
1) способа узнать длину текста нет 2) использовать последовательности длины сравнимой с длиной текста "опять нельзя".
>> No.34916  
>>34784
А так?
d → dd
x → xdx
y → ydy
ydy → x
xdx → y
dd → d
>> No.34917  
>>34911
> В редакторе нет find, только replace.
Условия больно жесткие. А что еще есть в редакторе? Какие значения может возвращать replace?
>> No.34924  
>>34916
Кажется, ты гениален.
`


$ cat replace.pl
#!/usr/bin/perl -w

use Term::ANSIColor;

my $line = $ARGV[0];
print( $line , "\n\r" );
$line =~ s/d/dd/g;
$line =~ s/x/xdx/g;
$line =~ s/y/ydy/g;
$line =~ s/xdx/y/g;
$line =~ s/ydy/x/g;
$line =~ s/dd/d/g;
print ( $line , "\n\r" );

$ cat lol.txt | xargs perl ./replace.pl
xxxxxxxyxxxdxxyxxxyyxxydxxdxxxdyxxddxyxxxyxyxyxdxyyxxyyyxyydxydxxydyxyddxdxxxdxyxdxdxdyxxdyyxdydxddxxddyxddd
yyyyyyyxyyydyyxyyyxxyyxdyydyyydxyyddyxyyyxyxyxydyxxyyxxxyxxdyxdyyxdxyxddydyyydyxydydydxyydxxydxdyddyyddxyddd

` По крайней мере, тесткейс, об который система сломается, я пока не придумал.
>> No.34950  
>>34924
Проверь >>34774? (/ и \ - буквы)

>>34917
Никаких. Текст изменяется, но ты не можешь проверить, где и как (inb4: очень длинный текст, вручную проверить невозможно).
>> No.34952  
>>34950`


$ perl ./replace.pl \\x\\y\/x/y/
\x\y/x/y/
\y\x/y/x/

` Скрипт тот же, что и в >>34924
>> No.34953  
>>34952
А, прошу прощения, не заметил один незаэкранированный \:`


$ perl ./replace.pl \\x\\y\\/x/y/
\x\y\/x/y/
\y\x\/y/x/

`
>> No.34954  
>>34950
> Проверь >>34774? (/ и \ - буквы)
А в тексте есть метасимволы?
>> No.34956  
>>34954
Есть.
>> No.34963  
Ох, анончики.
Решение >>34774 принято оффициально. Но модератор, который модератор и может указывать мне, указал мне:

> можно улучшить двумя способами:
> 1) Не использовать дополнительные символы.
> 2) Использовать меньшее число замен.

Под "дополнительным" символом понимается "не х и не у".
>> No.34965  
И есть ощущение, что модератор - ~~мудак~~ прав

s z zz
s x zx
s zz x
s zx z


Удалить сообщение []
Пароль