Unscramble words Challenge - improve my bash solution

Question

There is a Capture the Flag challenge

I have two files; one with scrambled text like this with about 550 entries

dnaoyt
cinuertdso
bda
haey
tolpap
...

The second file is a dictionary with about 9,000 entries

radar
ccd
gcc
fcc
historical
...

The goal is to find the right, unscrambled version of the word, which is contained in the dictionary file.

My approach is to sort the characters from the first word from the first file and then look up if the first word from the second file has the same length. If so then sort that too and compare them.

This is my fully functional bash script, but it is very slow.

#!/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

I have also tried converting all characters to ASCII integers and sum each word, but while comparing I realized that the sum of a different char pattern may have the same sum.

[edit] For the records: - no anagrams contained in dictionary - to get the flag, you need to export the unscrambled words as one blob and ans make a SHA-Hash out of it (thats the flag) - link to ctf for guy who wanted the files https://challenges.reply.com/tamtamy/user/login.action

Answer 1

You're better off creating a lookup dictionary (keyed by the sorted word) from the dictionary file.

Your loop body is executed 550 * 9,000 = 4,950,000 times (O(N*M)).

The solution I propose executes two loops of at most 9,000 passes each (O(N+M)).

Bonus: It finds all possible solutions at no cost.

#!/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;
   }
}

I wouldn't be surprised if this only takes one millionths of the time of your solution for the sizes you provided (and it scales so much better than yours if you were to increase the sizes).