时间戳

首页 > 解决方案 > 解读单词挑战 - 改进我的 bash 解决方案

bash - 解读单词挑战 - 改进我的 bash 解决方案

问题描述

有一个夺旗挑战

我有两个文件；一个带有这样的乱码，大约有 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（这就是标志） - 链接到 ctf for guy谁想要这些文件https://challenges.reply.com/tamtamy/user/login.action

标签： bashperlstring-comparisonscramble

解决方案

您最好从字典文件中创建一个查找字典（由排序的单词键入）。

你的循环体被执行了 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;
   }
}

如果对于您提供的尺寸，这只需要您解决方案的百万分之一的时间，我不会感到惊讶（如果您要增加尺寸，它的扩展性比您的要好得多）。

推荐阅读