解读单词挑战 - 改进我的 bash 解决方案
Unscramble words Challenge - improve my bash solution
有夺旗挑战
我有两个文件;一个像这样的乱序文本大约有 550 个条目
dnaoyt
cinuertdso
bda
haey
tolpap
...
第二个文件是一个有大约 9,000 个条目的字典
radar
ccd
gcc
fcc
historical
...
我们的目标是找到包含在词典文件中的单词的正确、未加扰版本。
我的做法是从第一个文件的第一个单词开始排序,然后查找第二个文件的第一个单词是否具有相同的长度。如果是这样,那么也对其进行排序并进行比较。
这是我的全功能 bash 脚本,但是速度很慢。
#!/bin/bash
while IFS="" read -r p || [ -n "$p" ]
do
var=0
ro=$(echo $p | perl -F -lane 'print sort @F')
len_ro=${#ro}
while IFS="" read -r o || [ -n "$o" ]
do
ro2=$(echo $o | perl -F -lane 'print sort @ F')
len_ro2=${#ro2}
let "var+=1"
if [ $len_ro == $len_ro2 ]; then
if [ $ro == $ro2 ]; then
echo $o >> new.txt
echo $var >> whichline.txt
fi
fi
done < dictionary.txt
done < scrambled-words.txt
我也尝试过将所有字符转换为 ASCII 整数并对每个单词求和,但在比较时我意识到不同字符模式的总和可能具有相同的总和。
[编辑]
对于记录:
- 字典中没有字谜
- 要获得标志,您需要将未加扰的词作为一个 blob 导出,并从中生成 SHA-Hash(这就是标志)
- link 给想要文件的人 ctf https://challenges.reply.com/tamtamy/user/login.action
我尝试了一些非常相似的东西,但又有点不同。
#!/bin/bash
exec 3<scrambled-words.txt
while read -r line <&3; do
printf "%s" ${line} | perl -F -lane 'print sort @F'
done>scrambled-words_sorted.txt
exec 3>&-
exec 3<dictionary.txt
while read -r line <&3; do
printf "%s" ${line} | perl -F -lane 'print sort @F'
done>dictionary_sorted.txt
exec 3>&-
printf "" > whichline.txt
exec 3<scrambled-words_sorted.txt
while read -r line <&3; do
counter="$((++counter))"
grep -n -e "^${line}$" dictionary_sorted.txt | cut -d ':' -f 1 | tr -d '\n' >>whichline.txt printf "\n" >>whichline.txt
done
exec 3>&-
如您所见,我没有创建 new.txt
文件;相反,我只创建 whichline.txt
并在单词不匹配的地方有一个空行。您可以轻松地将它们粘贴起来以创建 new.txt
.
脚本背后的逻辑几乎就是你的逻辑,除了我少调用了 perl
次并且我保存了两个支持文件。
我认为(但我不确定)创建它们并仅循环一个文件会比 perl
的 ~5kk 次调用更好。这样就调用了"only"~10k次。
最后,我决定使用 grep
,因为它(可能)是最快的正则表达式匹配器,并且搜索正则表达式中固有长度的整行。
请注意,@benjamin-w 所说的仍然有效,在那种情况下,grep
会回复得很糟糕,我没有做到!
希望对您有所帮助[:
我会用 gawk 做这样的事情
gawk '
NR == FNR {
dict[csort()] = [=10=]
next
}
{
print dict[csort()]
}
function csort( chars, sorted) {
split([=10=], chars, "")
asort(chars)
for (i in chars)
sorted = sorted chars[i]
return sorted
}' dictionary.txt scrambled-words.txt
这是我使用 sort
和 join
提出的无 perl 解决方案:
sort_letters() {
# Splits each letter onto a line, sorts the letters, then joins them
# e.g. "hello" becomes "ehllo"
echo "" | fold-b1 | sort | tr -d '\n'
}
# For each input file...
for input in "dict.txt" "words.txt"; do
# Convert each line to [sorted] [original]
# then sort and save the results with a .sorted extension
while read -r original; do
sorted=$(sort_letters "${original}")
echo "${sorted} ${original}"
done < "${input}" | sort > "${input}.sorted"
done
# Join the two files on the [sorted] word
# outputting the scrambled and unscrambed words
join -j 1 -o 1.2,2.2 "words.txt.sorted" "dict.txt.sorted"
您最好从字典文件中创建一个查找字典(以排序的词为关键字)。
你的循环体执行了 550 * 9,000 = 4,950,000 次 (O(N*M))。
我提出的解决方案执行两个循环,每个循环最多 9,000 次 (O(N+M))。
奖励:它可以免费找到所有可能的解决方案。
#!/usr/bin/perl
use strict;
use warnings qw( all );
use feature qw( say );
my $dict_qfn = "dictionary.txt";
my $scrambled_qfn = "scrambled-words.txt";
sub key { join "", sort split //, $_[0] }
my %dict;
{
open(my $fh, "<", $dict_qfn)
or die("Can't open \"$dict_qfn\": $!\n");
while (<$fh>) {
chomp;
push @{ $dict{key($_)} }, $_;
}
}
{
open(my $fh, "<", $scrambled_qfn)
or die("Can't open \"$scrambled_qfn\": $!\n");
while (<$fh>) {
chomp;
my $matches = $dict{key($_)};
say "$_ matches @$matches" if $matches;
}
}
对于您提供的大小,如果这只花费您解决方案时间的百万分之一,我不会感到惊讶(如果您要增加大小,它的扩展性比您的好得多)。
有夺旗挑战
我有两个文件;一个像这样的乱序文本大约有 550 个条目
dnaoyt
cinuertdso
bda
haey
tolpap
...
第二个文件是一个有大约 9,000 个条目的字典
radar
ccd
gcc
fcc
historical
...
我们的目标是找到包含在词典文件中的单词的正确、未加扰版本。
我的做法是从第一个文件的第一个单词开始排序,然后查找第二个文件的第一个单词是否具有相同的长度。如果是这样,那么也对其进行排序并进行比较。
这是我的全功能 bash 脚本,但是速度很慢。
#!/bin/bash
while IFS="" read -r p || [ -n "$p" ]
do
var=0
ro=$(echo $p | perl -F -lane 'print sort @F')
len_ro=${#ro}
while IFS="" read -r o || [ -n "$o" ]
do
ro2=$(echo $o | perl -F -lane 'print sort @ F')
len_ro2=${#ro2}
let "var+=1"
if [ $len_ro == $len_ro2 ]; then
if [ $ro == $ro2 ]; then
echo $o >> new.txt
echo $var >> whichline.txt
fi
fi
done < dictionary.txt
done < scrambled-words.txt
我也尝试过将所有字符转换为 ASCII 整数并对每个单词求和,但在比较时我意识到不同字符模式的总和可能具有相同的总和。
[编辑] 对于记录: - 字典中没有字谜 - 要获得标志,您需要将未加扰的词作为一个 blob 导出,并从中生成 SHA-Hash(这就是标志) - link 给想要文件的人 ctf https://challenges.reply.com/tamtamy/user/login.action
我尝试了一些非常相似的东西,但又有点不同。
#!/bin/bash
exec 3<scrambled-words.txt
while read -r line <&3; do
printf "%s" ${line} | perl -F -lane 'print sort @F'
done>scrambled-words_sorted.txt
exec 3>&-
exec 3<dictionary.txt
while read -r line <&3; do
printf "%s" ${line} | perl -F -lane 'print sort @F'
done>dictionary_sorted.txt
exec 3>&-
printf "" > whichline.txt
exec 3<scrambled-words_sorted.txt
while read -r line <&3; do
counter="$((++counter))"
grep -n -e "^${line}$" dictionary_sorted.txt | cut -d ':' -f 1 | tr -d '\n' >>whichline.txt printf "\n" >>whichline.txt
done
exec 3>&-
如您所见,我没有创建 new.txt
文件;相反,我只创建 whichline.txt
并在单词不匹配的地方有一个空行。您可以轻松地将它们粘贴起来以创建 new.txt
.
脚本背后的逻辑几乎就是你的逻辑,除了我少调用了 perl
次并且我保存了两个支持文件。
我认为(但我不确定)创建它们并仅循环一个文件会比 perl
的 ~5kk 次调用更好。这样就调用了"only"~10k次。
最后,我决定使用 grep
,因为它(可能)是最快的正则表达式匹配器,并且搜索正则表达式中固有长度的整行。
请注意,@benjamin-w 所说的仍然有效,在那种情况下,grep
会回复得很糟糕,我没有做到!
希望对您有所帮助[:
我会用 gawk 做这样的事情
gawk '
NR == FNR {
dict[csort()] = [=10=]
next
}
{
print dict[csort()]
}
function csort( chars, sorted) {
split([=10=], chars, "")
asort(chars)
for (i in chars)
sorted = sorted chars[i]
return sorted
}' dictionary.txt scrambled-words.txt
这是我使用 sort
和 join
提出的无 perl 解决方案:
sort_letters() {
# Splits each letter onto a line, sorts the letters, then joins them
# e.g. "hello" becomes "ehllo"
echo "" | fold-b1 | sort | tr -d '\n'
}
# For each input file...
for input in "dict.txt" "words.txt"; do
# Convert each line to [sorted] [original]
# then sort and save the results with a .sorted extension
while read -r original; do
sorted=$(sort_letters "${original}")
echo "${sorted} ${original}"
done < "${input}" | sort > "${input}.sorted"
done
# Join the two files on the [sorted] word
# outputting the scrambled and unscrambed words
join -j 1 -o 1.2,2.2 "words.txt.sorted" "dict.txt.sorted"
您最好从字典文件中创建一个查找字典(以排序的词为关键字)。
你的循环体执行了 550 * 9,000 = 4,950,000 次 (O(N*M))。
我提出的解决方案执行两个循环,每个循环最多 9,000 次 (O(N+M))。
奖励:它可以免费找到所有可能的解决方案。
#!/usr/bin/perl
use strict;
use warnings qw( all );
use feature qw( say );
my $dict_qfn = "dictionary.txt";
my $scrambled_qfn = "scrambled-words.txt";
sub key { join "", sort split //, $_[0] }
my %dict;
{
open(my $fh, "<", $dict_qfn)
or die("Can't open \"$dict_qfn\": $!\n");
while (<$fh>) {
chomp;
push @{ $dict{key($_)} }, $_;
}
}
{
open(my $fh, "<", $scrambled_qfn)
or die("Can't open \"$scrambled_qfn\": $!\n");
while (<$fh>) {
chomp;
my $matches = $dict{key($_)};
say "$_ matches @$matches" if $matches;
}
}
对于您提供的大小,如果这只花费您解决方案时间的百万分之一,我不会感到惊讶(如果您要增加大小,它的扩展性比您的好得多)。