[ch-076/jeongoon] bug fixed in task #2

3 files changed, 67 insertions, 143 deletions

diff --git a/challenge-076/jeongoon/haskell/ch-2.hs b/challenge-076/jeongoon/haskell/ch-2.hs
index 7751a49b30..934b819f82 100644
--- a/challenge-076/jeongoon/haskell/ch-2.hs
+++ b/challenge-076/jeongoon/haskell/ch-2.hs
@@ -1,12 +1,10 @@
 {-# LANGUAGE DeriveGeneric     #-}
 {-# LANGUAGE OverloadedStrings #-}
 import Options.Generic
-import Data.List ( find, findIndex, span, insert
+import Data.List ( find, findIndex, span, insert, intersectBy, sortBy
             ,inits, tails, isPrefixOf, unfoldr )
 import Data.Char ( toLower )
 import System.IO
-import System.Exit (die)
-import Control.Exception
 
 {- tested with:
 ghc ch-2.hs
@@ -113,7 +111,6 @@ bothDirectAllIndices = flatOnce.(map obverseAndReverse).allIndices where
       | otherwise     = [ a, reverse a ]
 
 -- final result of indices
-
 allUsefulCombinationIndices = {-usefulInits.
   -- note: wordTreeGetAllWords generate all subsequence which begins from
   --       the begining so we can skip generating `inits'
@@ -152,60 +149,20 @@ wordTreeFromGridData =
   (foldr (flip wordTreeSaveWord) (Root [])).allUsefulWordsFromGridData
 
 -- comparison
-{- If we create a list from a dictionary by using `readFile'
-we can easily get the result by `intersect'
-but I tried to go little bit further in order to study Haskell
-which is not easy when it comes with unfamiliar context `Monad'...
--}
-nextDictWord :: Handle -> IO (Maybe String)
-nextDictWord dictFh = do
-  eof <- hIsEOF dictFh
-  if eof then return Nothing
-    else do
-    word <- hGetLine dictFh
-    return (Just word)
-
--- there is no standard unfoldM and mapM doesn't look efficient in this case,
--- and have to reset the reading position via (hTell, hSeek) ...
--- so I decided to make own (recursive) function
-grepMatchedWord dictFh gridWords =
-  impli Nothing gridWords [] where
-  impli :: Maybe String -> [String] -> [String]  -> IO [String]
-  impli _ [] matchedWords = return matchedWords
-  impli lastDictWord gWords@(gridWord:gridRestWords) matchedWords =
-    case lastDictWord of
-      Nothing -> do
-        res <- nextDictWord dictFh
-        case res of
-          Nothing        -> return matchedWords -- dictionary finised first
-          Just newDWord  -> impli (Just newDWord) gWords matchedWords
-      Just lastDWord     ->
-        let last_dword = map toLower lastDWord in
-          case (compare last_dword gridWord) of
-            LT -> impli Nothing gWords matchedWords
-            EQ -> impli Nothing gridRestWords (matchedWords ++ [gridWord])
-            GT -> impli lastDictWord gridRestWords matchedWords
+grepMatched dictWords gridWords = impli dictWords gridWords [] where
+  impli _ [] matchedWords = matchedWords
+  impli [] _ matchedWords = matchedWords
+  impli dw@(d:ds) gw@(g:gs) matchedWords =
+    case ((map toLower d) `compare` g) of -- grid words already in lower case
+      LT -> impli ds gw matchedWords
+      EQ -> impli ds gs (matchedWords ++ [d])
+      GT -> impli dw gs matchedWords
 
 defaultGridFile   = "../data/grid.txt"
 --defaultDictionary = "../tinyDict.txt"
 defaultDictionary = "/usr/share/dict/british-english"
 -- via `words' package in Arch Linux
 
-tryOpenDict :: FilePath -> IO (Maybe Handle)
-tryOpenDict dpath =
-  (do
-      fh <- openFile dpath ReadMode
-      return (Just fh)) `catch` openDictHandler
-
-openDictHandler :: IOError -> IO (Maybe Handle)
-openDictHandler e = do
-  putStrLn $ "[ERR] Could not open given dictionary: " ++ (show e)
-  if isPrefixOf (defaultDictionary++":") (show e) then return Nothing -- give up
-  else do
-    putStrLn $ "[INF] Trying to open default dictionary: " ++ defaultDictionary
-    (tryOpenDict defaultDictionary) `catch` openDictHandler
-
-
 -- testing ...
 data Sample = Sample { grid :: Maybe FilePath, dict :: Maybe FilePath }
   deriving (Generic, Show)
@@ -221,21 +178,22 @@ main = do
                    Nothing -> defaultDictionary
                    Just dp -> dp
     in do
-    rawData <- readFile gridPath
+    rawData  <- readFile gridPath
+    dictData <- readFile dictPath
+
     putStrLn $ "Grid Contents:\n" ++ rawData
     let gridWords = (wordTreeGetAllWords
                     .wordTreeFromGridData
                     .gridDataFromString) rawData
+        dictWords = sortBy (\a b ->
+                              compare (map toLower a) (map toLower b)
+                           ) $ lines dictData
+        matchedWords = grepMatched dictWords gridWords
       in do
-      maybeDictFh <- tryOpenDict dictPath
-      case maybeDictFh of
-        Nothing -> do
-          putStrLn "[WRN] Dictionary not available: could not match anytying."
-        Just dictFh -> do
-          matchedWords <- grepMatchedWord dictFh gridWords
-          print matchedWords
-          putStrLn $ "\nTotal "
-            ++ (show (length matchedWords)) ++ " word(s) found."
-          hClose dictFh
-
--- ok...
+      putStrLn $ "Total " ++ (show (length gridWords))
+        ++ " possible words in grid."
+      print matchedWords
+      putStrLn $ "\nTotal "
+        ++ (show (length matchedWords)) ++ " word(s) found."
+
+-- ok ok ...
diff --git a/challenge-076/jeongoon/perl/ch-2.pl b/challenge-076/jeongoon/perl/ch-2.pl
index 77387e1bf6..762a186dbf 100644
--- a/challenge-076/jeongoon/perl/ch-2.pl
+++ b/challenge-076/jeongoon/perl/ch-2.pl
@@ -11,6 +11,7 @@ perl ch-2.pl --grid <word search grid file path> --dict <dictionary file path>
 =head1 Solution
 
 #. assumption: dictionary already stored in ascending order.
+#  --> this was wrong assumption: I changed the subroutine accordingly.
 
 1. store every possible words in every direction into array (and sorted)
    this words has possibly quite a huge amount of sub sequences
@@ -85,9 +86,12 @@ sub allTopLeftToBottomRightIndices ($$) {
     map { my $b = $_;
           my $col = $b % $lineLen;
           [ $b, map {
-              my $p = $b + $_; $p > $maxPos ? () : $p
-            } (map {$_*($lineLen+1)} 1 .. ($lineLen -$col -1)) ] }
-    ( 0 .. ($lineLen -1), map { $lineLen*$_ } 1 .. $rowsIdx )
+              my $p = $b + $_;
+              ( ($p <= $maxPos) and (($p % $lineLen) > $col) )
+                ? $p : ()
+            } (map {$_*($lineLen+1)} 1 .. $lineLen -1 ) ] }
+      ( 0 .. ($lineLen -1), map { $lineLen*$_ } 1 .. $rowsIdx )
+      # for every starting poin
 }
 
 sub allTopRightToBottomLeftIndices ($$) {
@@ -97,7 +101,9 @@ sub allTopRightToBottomLeftIndices ($$) {
     map { my $b = $_;
           my $col = $b % $lineLen;
           [ $b, map {
-              my $p = $b + $_; $p > $maxPos ? () : $p
+              my $p = $b + $_;
+              ( ($p <= $maxPos) and (($p % $lineLen) < $col) )
+                ? $p: ()
             } (map {$_*($lineLen-1)} 1 .. $col) ] }
     ( 0 .. ($lineLen -1), map { $lineLen*$_ -1 } 2 .. $rowsIdx )
 }
@@ -120,7 +126,7 @@ sub subsequences {
     # against a whole possible line. but... my dictionary contains 127,466 lines
     ( @_ == 1 ) and return [ @_ ];
 
-    [ $_[0] ], map { [ @_[ $$_[0] .. $$_[1] ] ] } combinationsIndex( 2, scalar @_ )
+    [ $_[0] ], map{ [ @_[ $$_[0] .. $$_[1] ] ] } combinationsIndex(2, scalar@_)
 }
 
 sub allSubsequencesIndices { # final summary of indices
@@ -129,6 +135,8 @@ sub allSubsequencesIndices { # final summary of indices
       map { bothDirection @$_ } allIndices( $maxPos, $lineLen );
 }
 
+say scalar allSubsequencesIndices( 303, 16 );
+
 sub genWordsOrganized {
     my ( $maxPos, $lineLen, $gridString ) = @_;
     my @allPossibleIndices = allSubsequencesIndices( $maxPos, $lineLen );
@@ -141,12 +149,12 @@ sub genWordsOrganized {
                allSubsequencesIndices( $maxPos, $lineLen ) ) );
 }
 
-sub unsafe_readChaos { # unsafe means can throw exception(die)
-    my $chaosPath = shift;
-    -r $chaosPath or ::dprint( "[ERR] $chaosPath: not readable: bye!\n" );
+sub unsafe_slurpFile { # unsafe means can throw exception(die)
+    my $FilePath = shift;
+    -r $FilePath or ::dprint( "[ERR] $FilePath: not readable: bye!\n" );
 
-    open( my $fh, '<', $chaosPath ) or
-        die "could not open chaos: $chaosPath";
+    open( my $fh, '<', $FilePath ) or
+        die "could not open chaos: $FilePath";
 
     local $/ = undef;
     my $data = <$fh>;
@@ -164,54 +172,21 @@ sub prepareGridData ($) {
     $maxPos, $lineLen, (lc $gdata) # finay $gdata is in a linear form
 }
 
-sub unsafe_openDict {
-    my $dictPath = shift;
-    -r $dictPath or die "$dictPath: not readable: bye!";
-
-    open( my $fh, '<', $dictPath ) or
-        die "could not open dictionary: $dictPath";
-
-    return $fh;
-}
-
-sub getDictWord ($$) {
-    state $lastDictWord;
-    my ( $dfh, $update ) = @_;
-
-    if ( not defined $lastDictWord or $update ) {
-        $lastDictWord = <$dfh>;
-        defined $lastDictWord or return undef;
-        chomp $lastDictWord;
-    }
-    $lastDictWord
-}
-
-sub grepMatchedWords {
-    my $dfh      = shift;
-    my ( $gridWordsOrganized_ref ) = @_;
-    my @gridWords = ( ref $gridWordsOrganized_ref
-                      ? @$gridWordsOrganized_ref
-                      : $$gridWordsOrganized_ref[ 2.. $#_ ] );
+sub grepMatchedWordsWithSortedData {
+    my @dictWords = @{$_[0]};
+    my @gridWords = @{$_[1]}; # XXX: this is kinda a copying
 
+    my ( $di, $gi ) = ( 0, 0 );
     my @result;
-    my $update_dict = 1;
-  GRID_WORDS:
-    for ( my $gi = 0; $gi < @gridWords; ) {
-        # note: lc() for sure
-        my $dictWord = lc getDictWord( $dfh, $update_dict );
-        defined $dictWord or last GRID_WORDS;
-        ::dprint "$dictWord vs $gridWords[$gi]\n" if 0;
-        for ( $dictWord cmp $gridWords[$gi] ) {
-            when (-1) {
-                $update_dict = 1;
-            }
-            when ( 0) {
-                push @result, $gridWords[$gi];
-                $update_dict = 1; ++$gi;
-            }
-            when ( 1) {
-                $update_dict = 0; ++$gi;
+    while ( $di <= @dictWords && $gi <= @gridWords ) {
+        ::dprint "$dictWords[$di] vs $gridWords[$gi]\n" if 0;
+        for ( lc $dictWords[$di] cmp $gridWords[$gi] ) { # note: lc
+            when ( -1 ) { ++$di }
+            when (  0 ) {
+                push @result, $dictWords[$di];
+                ++$di, ++$gi;
             }
+            when (  1 ) { ++$gi }
         }
     }
     @result;
@@ -232,11 +207,15 @@ if ( not defined $::gridPath ) {
     ::dprint "[WRN] using default word grid search file: $::gridPath\n";
 }
 
-my $dictFh      = unsafe_openDict(  $::dictPath );
-my $rawGridData = unsafe_readChaos( $::gridPath );
+my $dictData    = unsafe_slurpFile( $::dictPath );
+my $rawGridData = unsafe_slurpFile( $::gridPath );
 
+my @dictOrganized = sort { (lc $a) cmp (lc $b) } ( split "\n", $dictData );
+defined $dictOrganized[-1] or pop @dictOrganized; # XXX
 my @gridWordsOrganized = genWordsOrganized( prepareGridData( $rawGridData ) );
 
+
+
 if ( $::debugging ) {
     my $cnt = scalar @gridWordsOrganized;
     ::dprint "[DBG] Total $cnt possible words in the word-search grid.\n";
@@ -245,10 +224,9 @@ if ( $::debugging ) {
     ::dprint(sprintf("%${wd}d  ",++$i), $_, $/) for @gridWordsOrganized;
 }
 
-my @matchedWords = grepMatchedWords( $dictFh, \@gridWordsOrganized );
+my @matchedWords =
+  grepMatchedWordsWithSortedData( \@dictOrganized, \@gridWordsOrganized );
 
 say "Word Search Grid:\n$rawGridData";
 say "Total: ".(scalar @matchedWords)." word(s) found.";
 say raku_array( @matchedWords );
-
-close $dictFh;
diff --git a/challenge-076/jeongoon/raku/ch-2.raku b/challenge-076/jeongoon/raku/ch-2.raku
index 4c3bca5246..d574c64e73 100644
--- a/challenge-076/jeongoon/raku/ch-2.raku
+++ b/challenge-076/jeongoon/raku/ch-2.raku
@@ -26,7 +26,7 @@ class GridSizeInfo {
     method all-rows-indices {
         ( 0 .. $!rows-idx ).map(              # for every row index
         -> $ri { my $r = $ri * $!line-len;
-                ( 0 ..^ $!line-len ).map( # for every colum index
+                ( 0 ..^ $!line-len ).map(     # for every colum index
                     -> $c { my $p = $r + $c;
                            $p > $!max-pos and last; $p } ) } );
     }
@@ -125,8 +125,6 @@ sub MAIN (
         where { $grid.IO.r } = '../data/grid.txt',
     Bool :verbose(:$v)             #= verbose message
                              = False,
-    Bool :$intersection            #= alternatively using `intersection'
-                             = False,
 ) {
     $debugging = $v;
 
@@ -140,25 +138,15 @@ sub MAIN (
     }
 
     my @grid-words = $gd.get-all-possible-words;
+    say "Total {@grid-words.elems} word(s) in the grid.\n" if $debugging;
     my $gi = 0;
-
     my @result;
-    if $intersection.not {
-        for  $dict.IO.open.lines -> $dword {
-            given ( $dword cmp @grid-words[$gi] ) {
-                when Same { @result.push($dword); ++$gi; }
-                when More { ++$gi; redo }
-            }
-        }
-    }
-    else {
-        # or probably we can do like below
-        # which seems little bit faster than above. :-\
-        @result = ( $dict.IO.open.lines ∩ @grid-words ).List;
-    }
 
+    @result = ( $dict.IO.open.lines.map(
+                      -> $w { $w.lc } )  ∩ @grid-words ).List;
+
+    say @result.raku if $debugging;
     say "Total {@result.elems} word(s) found.";
-    say @result.raku;
 
     if 0 { # small test for indices: change to 1 to have a look
         # 0  1  2