[ /tv/ /rf/ /vg/ /a/ /b/ /u/ /bo/ /fur/ /to/ /dt/ /cp/ /oe/ /bg/ /ve/ /r/ /mad/ /d/ /mu/ /cr/ /di/ /sw/ /hr/ /wh/ /lor/ /s/ /hau/ /slow/ /gf/ /vn/ /w/ /ma/ /azu/ /wn/ ] [ Main | Settings | Bookmarks | Music Player ]

No.34703 Reply
File: e3278e63y.jpg
Jpg, 532.47 KB, 1600×892 - Click the image to expand
edit Find source with google Find source with iqdb
e3278e63y.jpg
Няши, как называется эта задача? Решить не получилось, гугление условия не помогает. Условие звучит как-то так:

Дан большой текст, где может встречаться любой символ. В тексте нужно сделать замену x на y, y на x. Замену можно делать только сразу по всему тексту. Заменить x на z, y на x, z на y нельзя, z может быть в исходном тексте (z - любой символ или последовательность символов). Как реализовать замену?
>> No.34712 Reply
>>34703
$ echo 'qxxxwwwyrrytxyyyxiiixyydddydyhyjylllyyxyxyy' | tr xy yx
qyyywwwxrrxtyxxxyiiiyxxdddxdxhxjxlllxxyxyxx
Самое короткое придуманное решение.
Хотя задача элементарная, на любом языке программирования это один цикл и два условия.
>> No.34714 Reply
>>34712
tr нет. Какие два условия? Не понимат.
>> No.34715 Reply
>>34714
Ах, эти. Так это посимвольная замена, а в условии только глобальная. В оригинале человек и условный текстовый редактор, замена работает как обычно.
>> No.34722 Reply
>>34714
А регэкспы есть? Потому что других способов глобальной замены не придумывается.
>> No.34723 Reply
>>34722
Регэкспов нет, только find/replace, только хардкор.
>> No.34724 Reply
>>34723
А можно делать больше одной замены по тексту?
>> No.34726 Reply
>>34724
Можно. Число замен вообще не ограничено (по условию).
>> No.34728 Reply
>>34726
Тогда чисто теоретически:
1) первым реплейсом заменяем x на что-то вроде x-x;
2) вторым реплейсом заменяем все y на y-y;
3) третьим реплейсом заменяем x-x на y;
4) четвёртым реплейсом заменяем y-y на x.
Хотя, кажется, без посимвольных чеков тут не обойтись. Надо быть хитрее. ПОтом ещё подумать попробую.
>> No.34729 Reply
>>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 Reply
Вы когда гуглить научитесь, двоечники?

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

(какая шикарная капча: «прибывших трудолюбие»)
>> No.34731 Reply
>>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 Reply
>>34730
xor - не replace же. Мне кажется, тут по другому поиздеваться хотели.
>> No.34735 Reply
>>34732
Совсем упорот, что ли? Я принцип демонстрирую.
replaceall(a, a xor b);
replaceall(b, b xor a);
replaceall(a, a xor b);
> Мне кажется, тут по другому поиздеваться хотели.
Чтобы делать обоснованные предположения на эту тему, необходимо знать контекст задачи. Название предмета, на каком языке принимаются задачи, какие темы недавно рассмотрены…
>> No.34736 Reply
>>34735
Няша, xor нет, и xor swap нет. Задача вообще не для погромистов. Модель - длинный текст в notepad и терпеливая блондинка, которая знает про Ctrl-H. Что ей делать?
Контекста нет. Абстрактный паззл.
Ответы принимаются в виде описания алгоритма.
>> No.34737 Reply
>>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 Reply
>>34736
Блеать.
notepad - правка - заменить
Или не катит?
>> No.34739 Reply
>>34737
Выше по треду:
> Так это посимвольная замена, а в условии только глобальная.
Не решение.
>> No.34740 Reply
>>34738
Дочитай условие до конца. Ну, заменишь ты один раз x на y, как ты будешь "первоначальные" y искать и заменять их на х?
>> No.34742 Reply
>>34737
В цикле нельзя.

>>34738
См. >>34740

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

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

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

>>34759
В тексте может быть всё. Не о том задача. Посмотри переформулировку в >>34756 (нельзя использовать символы, которых нет в тексте) - мб так яснее.
>> No.34764 Reply
>>34763
> но есть такие замены, для которых не требуется отличать "замененные" от "уже бывших", т.к. "бывшие" перестали существовать.
что-то мне подсказывает, что это только те типы замен, в которых заменяемая строка является началом замещающей, а ими одними не обойдешься
>> No.34765 Reply
>>34762
Как \ любой другой символ в строке.
>> No.34766 Reply
>>34765
Не сработает, после s y x появятся \x, которые потом восстановятся в у, т.е. по этим позициям замена не произойдет.
>> No.34767 Reply
>>34766
Хорошо, тогда s y \y и так далее.
>> No.34768 Reply
>>34767
Похоже, там нужно
s x \x\
s y /y/
и т.д.
Не успеваю проверить.
>> No.34769 Reply
>>34768
на строке \x\y\/x/y/ не сработает
>> No.34773 Reply
>>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 Reply
>>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 Reply
>>34774
\ → \\
x → \x
y → \y
\x → y
\y → x
\\ → \
>> No.34784 Reply
>>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 Reply
>>34784
Вижу, в чём проблема. Забавная задача.
>> No.34856 Reply
>>34703
Тред не читай @ сразу отвечай.

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

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

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

>>34862
>>34909
> В два прохода.
Неважно. Проходов замены может быть много. Но:
> Проверяем
> проверить
В редакторе нет find, только replace.
>> No.34912 Reply
просмотрел

>>34856
> узнать количество символов в тексте и затем заменить, скажем, все x на последовательность, длина которой должна быть больше исходного текста
1) способа узнать длину текста нет 2) использовать последовательности длины сравнимой с длиной текста "опять нельзя".
>> No.34916 Reply
>>34784
А так?
d → dd
x → xdx
y → ydy
ydy → x
xdx → y
dd → d
>> No.34917 Reply
>>34911
> В редакторе нет find, только replace.
Условия больно жесткие. А что еще есть в редакторе? Какие значения может возвращать replace?
>> No.34924 Reply
>>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 Reply
>>34924
Проверь >>34774? (/ и \ - буквы)

>>34917
Никаких. Текст изменяется, но ты не можешь проверить, где и как (inb4: очень длинный текст, вручную проверить невозможно).
>> No.34952 Reply
>>34950
$ perl ./replace.pl \\x\\y\/x/y/
\x\y/x/y/
\y\x/y/x/
Скрипт тот же, что и в >>34924
>> No.34953 Reply
>>34952
А, прошу прощения, не заметил один незаэкранированный \:
$ perl ./replace.pl \\x\\y\\/x/y/
\x\y\/x/y/
\y\x\/y/x/
>> No.34954 Reply
>>34950
> Проверь >>34774? (/ и \ - буквы)
А в тексте есть метасимволы?
>> No.34956 Reply
>>34954
Есть.
>> No.34963 Reply
Ох, анончики.
Решение >>34774 принято оффициально. Но модератор, который модератор и может указывать мне, указал мне:
> можно улучшить двумя способами:
> 1) Не использовать дополнительные символы.
> 2) Использовать меньшее число замен.
Под "дополнительным" символом понимается "не х и не у".
>> No.34965 Reply
И есть ощущение, что модератор - мудак прав

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


Password:

[ /tv/ /rf/ /vg/ /a/ /b/ /u/ /bo/ /fur/ /to/ /dt/ /cp/ /oe/ /bg/ /ve/ /r/ /mad/ /d/ /mu/ /cr/ /di/ /sw/ /hr/ /wh/ /lor/ /s/ /hau/ /slow/ /gf/ /vn/ /w/ /ma/ /azu/ /wn/ ] [ Main | Settings | Bookmarks | Music Player ]