解读的话挑战 - 提高我的bash解决方案

Question

有一个夺旗挑战

我有两个文件;一个像这样的密文与约550项

dnaoyt
cinuertdso
bda
haey
tolpap
...

第二个文件是用约9000个条目的字典

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和ANS做出SHA散列出来的（那旗） - 链接到CTF的家伙谁曾想文件https://challenges.reply.com/tamtamy/user/login.action

Answer 1

你是去创建从词典文件中查找字典（由分类词键控）更好。

您的循环体被执行550 * 9000 = 4,950,000次（O（N * M））。

我提出解决方案执行至多9000个通行证各（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;
   }
}

我也不会感到惊讶，如果这只是利用了您的解决方案的时间百万分之一为您提供的尺寸（以及其扩展比你好多了，如果你是要增加大小）。

Answer 2

我会做这样的事情与GAWK

gawk '
NR == FNR {
    dict[csort()] = $0
    next
}

{
    print dict[csort()]
}

function csort(    chars, sorted) {
    split($0, chars, "")
    asort(chars)
    for (i in chars)
        sorted = sorted chars[i]

    return sorted
}' dictionary.txt scrambled-words.txt

Answer 3

这是我想出了利用sort和join免费Perl的解决方案：

sort_letters() {
    # Splits each letter onto a line, sorts the letters, then joins them
    #   e.g. "hello" becomes "ehllo"
    echo "${1}" | 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"

Answer 4

我试过的东西非常相似，但有点不同。

#!/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少次，我救两个支撑文件。我认为，（但我不知道），创造他们和周期只有一个文件会比〜好5KK perl的电话。这样，“才”〜10K次被调用。

最后，我决定使用grep，因为它是（可能）最快的正则表达式匹配，并搜索整条生产线的lenght是正则表达式的内在。

请注意，什么@本杰明-W说仍然是有效的，在这种情况下，grep将回复不好，我没有管理它！

我希望这能帮助[：