aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--challenge-076/jeongoon/data/grid.txt19
-rw-r--r--challenge-076/jeongoon/data/tinyDict.txt63
-rw-r--r--challenge-076/jeongoon/haskell/OthersPrimeNumber.hs24
-rw-r--r--challenge-076/jeongoon/haskell/ch-1.hs55
-rw-r--r--challenge-076/jeongoon/haskell/ch-2.hs241
-rw-r--r--challenge-076/jeongoon/perl/CombinationsIndex.pm121
-rw-r--r--challenge-076/jeongoon/perl/ch-1.pl65
-rw-r--r--challenge-076/jeongoon/perl/ch-2.pl254
-rw-r--r--challenge-076/jeongoon/raku/ch-1.raku49
-rw-r--r--challenge-076/jeongoon/raku/ch-2.raku183
10 files changed, 1074 insertions, 0 deletions
diff --git a/challenge-076/jeongoon/data/grid.txt b/challenge-076/jeongoon/data/grid.txt
new file mode 100644
index 0000000000..31cf2e0fd8
--- /dev/null
+++ b/challenge-076/jeongoon/data/grid.txt
@@ -0,0 +1,19 @@
+B I D E M I A T S U C C O R S T
+L D E G G I W Q H O D E E H D P
+U S E I R U B U T E A S L A G U
+N G N I Z I L A I C O S C N U D
+T G M I D S T S A R A R E I F G
+S R E N M D C H A S I V E E L I
+S C S H A E U E B R O A D M T E
+H W O V L P E D D L A I U L S S
+R Y O N L A S F C S T A O G O T
+I G U S S R R U G O V A R Y O C
+N R G P A T N A N G I L A M O O
+E I H A C E I V I R U S E S E D
+S E T S U D T T G A R L I C N H
+H V R M X L W I U M S N S O T B
+A E A O F I L C H T O D C A E U
+Z S C D F E C A A I I R L N R F
+A R I I A N Y U T O O O U T P F
+R S E C I S N A B O S C N E R A
+D R S M P C U U N E L T E S I L
diff --git a/challenge-076/jeongoon/data/tinyDict.txt b/challenge-076/jeongoon/data/tinyDict.txt
new file mode 100644
index 0000000000..73a976d2e2
--- /dev/null
+++ b/challenge-076/jeongoon/data/tinyDict.txt
@@ -0,0 +1,63 @@
+aimed
+align
+and
+antes
+argos
+arose
+ashed
+blunt
+blunts
+bread
+broad
+buries
+clove
+cloven
+constitution
+constitutions
+construction
+cron
+croon
+depart
+departed
+enter
+filch
+garlic
+goats
+grieve
+grieves
+hazard
+liens
+malign
+malignant
+malls
+margo
+midst
+ought
+ovary
+parted
+partition
+patna
+pudgiest
+quash
+quashed
+raped
+ruses
+shame
+shrine
+shrines
+shy
+social
+socializing
+spam
+spasm
+spasmodic
+succor
+succors
+theorem
+theorems
+traci
+tracie
+troy
+virus
+viruses
+wigged
diff --git a/challenge-076/jeongoon/haskell/OthersPrimeNumber.hs b/challenge-076/jeongoon/haskell/OthersPrimeNumber.hs
new file mode 100644
index 0000000000..b07f2ee058
--- /dev/null
+++ b/challenge-076/jeongoon/haskell/OthersPrimeNumber.hs
@@ -0,0 +1,24 @@
+-- credit: https://ideone.com/e81
+module OthersPrimeNumber
+ ( primesTME
+ ) where
+
+primesTME :: [Int]
+primesTME = 2 : ([3,5..] `minus` foldt [ [p*p,p*p+2*p..] | p <- primes_ ])
+ where
+ primes_ = 3 : ([5,7..] `minus` foldt [ [p*p,p*p+2*p..] | p <- primes_ ])
+ foldt ~((x:xs):t) = x : union xs (foldt (pairs t))
+ pairs ~((x:xs):ys:t) = (x : union xs ys) : pairs t
+
+minus :: [Int] -> [Int] -> [Int]
+minus xs@(x:xt) ys@(y:yt) = case compare x y of
+ LT -> x : minus xt ys
+ EQ -> minus xt yt
+ GT -> minus xs yt
+minus a b = a
+
+union :: [Int] -> [Int] -> [Int]
+union xs@(x:xt) ys@(y:yt) = case compare x y of
+ LT -> x : union xt ys
+ EQ -> x : union xt yt
+ GT -> y : union xs yt
diff --git a/challenge-076/jeongoon/haskell/ch-1.hs b/challenge-076/jeongoon/haskell/ch-1.hs
new file mode 100644
index 0000000000..54f319bc58
--- /dev/null
+++ b/challenge-076/jeongoon/haskell/ch-1.hs
@@ -0,0 +1,55 @@
+{-# LANGUAGE DeriveGeneric #-}
+{-# LANGUAGE OverloadedStrings #-}
+import Options.Generic
+import OthersPrimeNumber
+import Data.List (sortBy, unfoldr)
+import Data.Maybe (fromJust, isJust)
+
+-- solution: same as 075/ch-1, so I made a little bit more general solution
+minPrimeSum = (minimum.map length.allPrimeSum)
+allPrimeSum s = allPossibleSum ( s, primeNumbers ) where
+ primeNumbers = takeWhile (<=s) $ primesTME
+
+allPossibleSum ( targetSum, els ) =
+ case ( combPS targetSum els ) of
+ Nothing -> []
+ Just xs -> xs
+ where
+ combPS :: Int -> [Int] -> Maybe [[Int]]
+ combPS targetSum els
+ | null els = Nothing
+ | otherwise = Just $ (joinCombi.grepCombi) goThroughThisOne
+ where
+ this = head sortedDesc
+ others = tail sortedDesc
+ sortedDesc = sortBy(\a b -> compare b a) els
+ maxNoe = targetSum `div` this -- Noe: Number of Elements
+ joinCombi = foldr (++) []
+ grepCombi = (map fromJust).(filter isJust)
+
+ goThroughThisOne = unfoldr goThroughThisOneInner maxNoe
+ goThroughThisOneInner noe
+ | noe < 0 = Nothing
+ | True =
+ if remainder == 0 then -- generate from maxNoe to 0
+ Just ( Just [fillThisOne], (pred noe) )
+ else case (combPS remainder others) of
+ Nothing -> Just ( Nothing, (pred noe) )
+ Just p -> Just ( Just (
+ map (\r -> fillThisOne ++ r) p), (pred noe))
+ where
+ fillThisOne = (replicate noe this)
+ remainder = targetSum - ( this * noe )
+
+-- testing
+main = do
+ args <- getRecord "Challennge #076 - Task #1"
+ let tSum = args :: Int in
+ do
+ putStrLn "Input:"
+ putStrLn $ "$N = " ++ (show tSum)
+ putStrLn $ "possible ways are: "
+ mapM_ (putStrLn.show)
+ $ sortBy (\a b -> compare (length b) (length a)) (allPrimeSum tSum)
+
+ putStrLn $ "Output:" ++ (show (minPrimeSum tSum))
diff --git a/challenge-076/jeongoon/haskell/ch-2.hs b/challenge-076/jeongoon/haskell/ch-2.hs
new file mode 100644
index 0000000000..7751a49b30
--- /dev/null
+++ b/challenge-076/jeongoon/haskell/ch-2.hs
@@ -0,0 +1,241 @@
+{-# LANGUAGE DeriveGeneric #-}
+{-# LANGUAGE OverloadedStrings #-}
+import Options.Generic
+import Data.List ( find, findIndex, span, insert
+ ,inits, tails, isPrefixOf, unfoldr )
+import Data.Char ( toLower )
+import System.IO
+import System.Exit (die)
+import Control.Exception
+
+{- tested with:
+ghc ch-2.hs
+./ch-2 --grid ../data/grid.txt --dict ../data/tinyDict.txt
+ # or this will use `/usr/share/dict/british-english' by default
+-}
+
+{- comment:
+I try to learn how `data' works in Haskell
+probably I could have used `nub` for duplicated words
+and use `readFile' to get simply a list of words in a dictionary
+but try to do more investigation about this interesting language
+-}
+
+-- solution:
+-- 1. read Grid and generate all possile (and useful) indices
+-- 2. save all words accoring to the indcies found above into tree
+-- 3. read Dictionary
+-- 4. compare one by one
+--- all data is sorted so we can easily compare between two.
+
+-- not-efficient tree with multiple child nodes
+data WordTree = Root [WordTree] | Node Char [WordTree]
+ deriving (Show, Read, Eq, Ord)
+
+wordTreeNodeVal (Node a _) = a
+wordTreeNodeVal (Root _) = '\NUL'
+wordTreeChildren (Root children) = children
+wordTreeChildren (Node _ children) = children
+
+findChild a wtree = find ((a ==).(wordTreeNodeVal)) (wordTreeChildren wtree)
+spanChildren c children = span ((<c).(wordTreeNodeVal)) children
+
+newChild a = Node a [] -- with char
+newChildren str
+ | length str == 1 = newChild (head str)
+ | otherwise = foldr (\x acc -> Node x [acc]) (newChild (last str)) (init str)
+
+wordTreeSaveWord :: WordTree -> String -> WordTree
+wordTreeSaveWord (Root children) str@(c:cs) =
+ let (leChildren, riChildren) = spanChildren c children
+ foundChild = head riChildren
+ in
+ if (null riChildren) || ((wordTreeNodeVal.head) riChildren /= c)
+ then Root (insert (newChildren str) children)
+ else if null cs then Root children -- already saved: skip
+ else Root$leChildren ++ (wordTreeSaveWord foundChild cs):(tail riChildren)
+
+wordTreeSaveWord (Node a children) str@(c:cs) =
+ let (leChildren, riChildren) = spanChildren c children
+ foundChild = head riChildren
+ in
+ if (null riChildren) || ((wordTreeNodeVal.head) riChildren /= c)
+ then Node a (insert (newChildren str) children)
+ else if null cs then Node a children -- already saved: skip
+ else Node a $ leChildren
+ ++ (wordTreeSaveWord foundChild cs):(tail riChildren)
+
+wordTreeGetAllWords :: WordTree -> [String]
+wordTreeGetAllWords (Root children) =
+ ((foldr (++) []).(map wordTreeGetAllWords)) children
+
+wordTreeGetAllWords (Node nv children) =
+ [[nv]] ++ ((foldr (++) [])
+ .(map (\wtree -> [ nv:str | str <-(wordTreeGetAllWords wtree)] )))
+ children
+
+-- find out all indices
+allColumnIndices (maxPos, llen) =
+ map (\c -> takeWhile (<=maxPos) $
+ map ((c+).(llen*)) [ 0 .. (maxPos `div` llen) ] )
+ [ 0.. (llen -1) ]
+
+allRowIndices (maxPos, llen) =
+ map (\c -> takeWhile (<=maxPos) $
+ map (c+) [ 0 .. (llen -1) ] )
+ [ 0, llen .. maxPos ]
+
+allTopLeftToBottomRightIndices (maxPos, llen) =
+ map (\c -> [c] ++ ( takeWhile
+ (\x -> x <= maxPos
+ && (rem c llen) < (rem x llen) ) $
+ map (c+) [ (llen+1), (llen+llen+2) .. ] ) ) $
+ [ 0 .. (llen-1) ] ++ [ llen, llen + llen .. maxPos ]
+
+allTopRightToBottomLeftIndices (maxPos, llen) =
+ map (\c -> [c] ++ ( takeWhile
+ (\x -> x <= maxPos
+ && (rem x llen) < (rem c llen) )
+ $ map (c+) [ (llen-1), (llen+llen-2) .. ] ) )
+ $ [ 0 .. (llen-1) ] ++ [ llen+llen-1, llen+llen+llen-1 .. maxPos ]
+
+allIndices (maxPos, llen) = let idxArgs = (maxPos, llen) in
+ (allColumnIndices idxArgs)
+ ++ (allRowIndices idxArgs)
+ ++ (allTopLeftToBottomRightIndices idxArgs)
+ ++ (allTopRightToBottomLeftIndices idxArgs)
+
+flatOnce = foldr (++) []
+
+bothDirectAllIndices = flatOnce.(map obverseAndReverse).allIndices where
+ obverseAndReverse a
+ | length a == 1 = [ a ] -- rerversing is not useful
+ | 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'
+-}
+ usefulTails.bothDirectAllIndices where
+ -- another possible approach might be (not checked)
+ -- (filter ((2<).length).subsequences)
+ --usefulInits = flatOnce.map (drop 2. inits)
+ usefulTails = flatOnce.map
+ ((\ls -> let len = length ls in take (len-2) ls).tails)
+
+data GridData = GridData { gridMaxPos :: Int
+ , gridLineLength :: Int
+ , gridContents :: String } deriving (Show)
+
+-- grid data
+gridDataFromString gridString =
+ let noSpaceContents = filter (' '/=) gridString
+ lineLen = case (findIndex ('\n'==) noSpaceContents) of
+ Nothing -> 1 -- maybe a wrong formated file: assume one
+ Just ln -> ln
+ contents = (map toLower.filter ('\n'/=)) noSpaceContents
+ maxPos = (pred.length) contents
+ in GridData { gridLineLength = lineLen
+ , gridMaxPos = maxPos
+ , gridContents = contents }
+
+allUsefulWordsFromGridData g = (map (map (contents!!))) idcsList
+ where
+ lineLengh = gridLineLength g
+ maxPos = gridMaxPos g
+ contents = gridContents g
+ idcsList = allUsefulCombinationIndices (maxPos, lineLengh)
+
+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
+
+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)
+instance ParseRecord Sample
+
+main = do
+ args <- getRecord "Challennge #076 - Task #2"
+ let sample = args :: Sample
+ gridPath = case (grid sample) of
+ Nothing -> defaultGridFile
+ Just gp -> gp
+ dictPath = case (dict sample) of
+ Nothing -> defaultDictionary
+ Just dp -> dp
+ in do
+ rawData <- readFile gridPath
+ putStrLn $ "Grid Contents:\n" ++ rawData
+ let gridWords = (wordTreeGetAllWords
+ .wordTreeFromGridData
+ .gridDataFromString) rawData
+ 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...
diff --git a/challenge-076/jeongoon/perl/CombinationsIndex.pm b/challenge-076/jeongoon/perl/CombinationsIndex.pm
new file mode 100644
index 0000000000..47dbcde67f
--- /dev/null
+++ b/challenge-076/jeongoon/perl/CombinationsIndex.pm
@@ -0,0 +1,121 @@
+# -*- Mode: cperl; cperl-indent-level:4; tab-width: 8; indent-tabs-mode: nil -*-
+# Copyright (c) 2013,2020 JEON Myoungjin <jeongoon@gmail.com>
+use strict; use warnings;
+
+use version 0.77 our $VERSION = version->declare( '0.2' );
+package CombinationsIndex;
+
+use parent 'Exporter';
+our @EXPORT_OK = qw(combinationsIndex);
+
+=pod
+
+=head1 Basic concept
+
+If we find the combintions when choosing 3 digits from index of 0 .. 4
+which shown below
+
+ 0 1 2 3 4
+ ^1 ^2 ^3 initial selection: index position: ( 0, 1, 2 )
+
+to get next combination we can move ^3 cursor from 2 to 3
+
+ 0 1 2 3 4
+ ^1 ^2 ^3 note: ^3 can move up to 4
+
+as you can see ^3 can only go up to 4, next movement we can imagine is that
+moving ^2 to next one and ^3 is just followed by ^2
+and next movement will be again ^3 to the index 4
+
+ 0 1 2 3 4 => 0 1 2 3 4 => 0 1 2 3 4
+ ^1 ^2 ^3 ^1 ^2 ^3 ^1 ^2 ^3
+
+and last case of combinations will be
+
+ 0 1 2 3 4
+ ^1 ^2 ^3
+
+so I make two arrays to record
+ 1. where each cursor is pointing now,
+ 2. how many rooms left for each cursor to move
+
+and also remember what is the current cursor move next.
+
+so we can also make combinations without recursive routine.
+
+=cut
+
+sub combinationsIndex ( $$ ) {
+ my $N = $_[0]; # number of selection
+ my $M = $_[1]; # choice" 0 .. ($M - 1)
+
+ my @result;
+
+ # minimum sanity check
+ if ( $M < $N ) {
+ warn "unable to choose $N from given selection of $M";
+ return ();
+ }
+
+ my ( @room, # number of spaces(rooms) each
+ @pos, # current position of cursor
+ $next_csr # next cursor to move
+ );
+
+ # set initial values ...
+ {
+ # each finger can move to right number of ( M-N ) space(s).
+ @room = ( $M-$N ) x $N;
+ @pos = 0 .. ($N - 1);
+ $next_csr = $N - 1; # last cursor at rightmost
+
+ # initial record; note: use not index number but real value
+ push @result, [ @pos ];
+ }
+
+ {
+ if ( $room[$next_csr] > 0 ) {
+ # current csr can move to right so just do it.
+ ++$pos[ $next_csr];
+ --$room[$next_csr]; # room decreased of course
+
+ # and make a record
+ push @result, [ @pos ];
+ redo;
+ }
+ else {
+ # no more room to move
+ # so find the next cursor to move
+ my $found = 0;
+ for ( my $i = $next_csr; $i > 0; --$i ) {
+ if ( $room[ $i-1 ] > 0 ) {
+ $next_csr = $i-1;
+ $found = 1;
+ last ;
+ }
+ }
+
+ if ( $found ) {
+ # move all the cursors which are starts from
+ # $next_csr to last one
+ @pos[ $next_csr .. ($N-1) ]
+ = map { $pos[$next_csr] + $_ } 1 .. ($N-$next_csr);
+ # note: all these finger has same room when moved
+ @room[ $next_csr .. ($N-1) ]
+ = ( $room[ $next_csr ] - 1 ) x ($N-$next_csr);
+
+ # and make a record
+ push @result, [ @pos ];
+
+ # next finger to move will be ($N-1)
+ # or even if it is not next loop will find anohter
+ $next_csr = ($N-1);
+
+ redo; # if we can move next cursor
+ }
+ }
+ }
+ @result;
+}
+
+!!"^^";
diff --git a/challenge-076/jeongoon/perl/ch-1.pl b/challenge-076/jeongoon/perl/ch-1.pl
new file mode 100644
index 0000000000..2b627450b0
--- /dev/null
+++ b/challenge-076/jeongoon/perl/ch-1.pl
@@ -0,0 +1,65 @@
+#!/usr/bin/env perl
+# -*- Mode: cperl; cperl-indent-level:4 tab-width: 8; indent-tabs-mode: nil -*-
+# -*- coding: utf-8 -*-
+
+use strict; use warnings;
+use List::Util qw(min);
+use v5.26;
+
+# solution
+sub combiPrimeSum { # dejavu !
+ my $S = shift;
+ my @RPN = ( @_ == 0 ? reverse pnumbers( $S ) : @_ );
+ my $fp = shift @RPN;
+
+ defined $fp or ( warn "no prime number found", return () );
+
+ my @result;
+ my $maxNop = int $S / $fp;
+ for my $nop ( reverse 0 .. $maxNop ) {
+ my $remainer = $S - $fp * $nop;
+ my @pnums = ( $fp ) x $nop;
+ if ( $remainer > 0 ) {
+ next if @RPN == 0;
+ push @result, map { [ @pnums, @$_ ] } combiPrimeSum( $remainer, @RPN );
+ }
+ else { push @result, [ @pnums ] }
+ }
+ @result;
+}
+
+sub pnumbers ($) { # a poor brute forced prime number generator
+ my @p = (3);
+ my $limit = shift;
+ my $candi = 3;
+ return [2] if $limit == 2;
+ return [2,3] if $limit < 5;
+
+ NewNumber:
+ while ( ($candi += 2) <= $limit ) {
+ for my $p (@p) {
+ ($candi % $p) or next NewNumber;
+ }
+ push @p, $candi;
+ }
+ return 2, @p;
+}
+
+# testing
+package main;
+
+sub usage {
+ say "perl ch-1.pl <sum>";
+}
+sub raku_array { "[".(join ", ", @_)."]" }
+
+scalar @ARGV != 1 and ( usage, exit -1 );
+
+my $N = shift;
+my @combi = combiPrimeSum( $N );
+
+say "Input: \$N = $N";
+
+say "Output: " . min( map { scalar @$_ } @combi );
+say "possible ways are:";
+say "@{[raku_array @$_ ]}" for @combi;
diff --git a/challenge-076/jeongoon/perl/ch-2.pl b/challenge-076/jeongoon/perl/ch-2.pl
new file mode 100644
index 0000000000..77387e1bf6
--- /dev/null
+++ b/challenge-076/jeongoon/perl/ch-2.pl
@@ -0,0 +1,254 @@
+#!/usr/bin/env perl
+# -*- Mode: cperl; cperl-indent-level:4 tab-width: 8; indent-tabs-mode: nil -*-
+# -*- coding: utf-8 -*-
+
+=pod Word Search
+
+=head1 Usage
+
+perl ch-2.pl --grid <word search grid file path> --dict <dictionary file path>
+
+=head1 Solution
+
+#. assumption: dictionary already stored in ascending order.
+
+1. store every possible words in every direction into array (and sorted)
+ this words has possibly quite a huge amount of sub sequences
+ but I guess the list of words in dictionary could be larger than ones
+ in the grid.
+
+2. compare against the dictionary
+
+=head1 Comment
+
+this was really heavy solution than I thought it would be.
+
+=cut
+
+use strict; use warnings;
+no warnings "experimental::smartmatch";
+use v5.14; # state, say, switch
+
+use Getopt::Long qw(:config gnu_compat);
+use Pod::Usage;
+use List::MoreUtils qw(uniq);
+use File::Spec;
+use FindBin;
+use lib ( $FindBin::Bin );
+
+use CombinationsIndex qw(combinationsIndex);
+
+BEGIN {
+ sub fs { "File::Spec" }
+ $::debugging = 0;
+
+ my $help = 0;
+
+ GetOptions( "debug" => \$::debugging,
+ "grid=s" => \$::gridPath,
+ "dict=s" => \$::dictPath,
+ "help" => \$help,
+ ) or pod2usage(2);
+
+ pod2usage( -exitval => 0, -verbose => 2 ) if $help;
+
+ our $dprint = sub( @ ) {
+ ++$|;
+ print @_;
+ };
+
+ *::dprint = $::debugging ? $dprint : sub {};
+}
+
+# solution ... a long solution ...
+# all the directions in a linear form
+sub allColumnIndices ($$) {
+ my ( $maxPos, $lineLen ) = @_;
+ ( $lineLen == 0 ) and ( warn ( "line number is zero!!!" ), return () );
+ my $rowsIdx = int $maxPos / $lineLen;
+ map { my $c = $_;
+ [ map { my $p = $c + $lineLen * $_;
+ $p > $maxPos ? () : $p } 0 .. $rowsIdx ] } 0 .. $lineLen -1
+}
+
+sub allRowIndices ($$) {
+ my ( $maxPos, $lineLen ) = @_;
+ my $rowsIdx = int $maxPos / $lineLen;
+ map { my $r = $_ * $lineLen;
+ [ map { my $p = $r + $_;
+ $p > $maxPos ? () : $p } 0 .. $lineLen - 1 ] } 0 .. $rowsIdx
+}
+
+sub allTopLeftToBottomRightIndices ($$) {
+ my ( $maxPos, $lineLen ) = @_;
+ my $rowsIdx = int $maxPos / $lineLen;
+ 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 )
+}
+
+sub allTopRightToBottomLeftIndices ($$) {
+ my ( $maxPos, $lineLen ) = @_;
+ my $rowsIdx = int $maxPos / $lineLen;
+
+ map { my $b = $_;
+ my $col = $b % $lineLen;
+ [ $b, map {
+ my $p = $b + $_; $p > $maxPos ? () : $p
+ } (map {$_*($lineLen-1)} 1 .. $col) ] }
+ ( 0 .. ($lineLen -1), map { $lineLen*$_ -1 } 2 .. $rowsIdx )
+}
+
+sub allIndices ($$) { # summary of directions shown above
+ my ( $maxPos, $lineLen ) = @_;
+ map { $_->( $maxPos, $lineLen ) }
+ \&allColumnIndices, \&allRowIndices,
+ \&allTopLeftToBottomRightIndices,\&allTopRightToBottomLeftIndices;
+}
+
+sub bothDirection {
+ ( @_ == 1 ) and return [@_]; # reversing one element not useful
+ return [@_], [reverse @_];
+}
+
+sub subsequences {
+ # if the length of dictionary is short, we don't actually need to
+ # make subsequences because we can compare the words in dictionary
+ # against a whole possible line. but... my dictionary contains 127,466 lines
+ ( @_ == 1 ) and return [ @_ ];
+
+ [ $_[0] ], map { [ @_[ $$_[0] .. $$_[1] ] ] } combinationsIndex( 2, scalar @_ )
+}
+
+sub allSubsequencesIndices { # final summary of indices
+ my ( $maxPos, $lineLen ) = @_;
+ map { subsequences @$_ }
+ map { bothDirection @$_ } allIndices( $maxPos, $lineLen );
+}
+
+sub genWordsOrganized {
+ my ( $maxPos, $lineLen, $gridString ) = @_;
+ my @allPossibleIndices = allSubsequencesIndices( $maxPos, $lineLen );
+ my @gridChars = split "", lc $gridString;
+
+ ::dprint "[DBG] the grid string (in lower case):\n$gridString\n\n";
+ local $" = '';
+ sort(
+ uniq( map { "@gridChars[@$_]" }
+ 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" );
+
+ open( my $fh, '<', $chaosPath ) or
+ die "could not open chaos: $chaosPath";
+
+ local $/ = undef;
+ my $data = <$fh>;
+ close $fh;
+ $data
+}
+
+sub prepareGridData ($) {
+ my $gdata = shift; # raw data
+ $gdata =~ s/ *//g;
+ my $lineLen = index $gdata, $/;
+ $gdata =~ s/\n//g;
+ my $maxPos = (length $gdata) -1;
+
+ $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.. $#_ ] );
+
+ 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;
+ }
+ }
+ }
+ @result;
+}
+
+sub raku_array { "[".(join ", ", @_)."]" }
+
+# testing ...
+package main;
+
+if ( not defined $::dictPath ) {
+ $::dictPath //= fs->catfile( $FindBin::Bin, qw(.. data tinyDict.txt) );
+ ::dprint "[WRN] using default dictionary file: $::dictPath\n";
+}
+
+if ( not defined $::gridPath ) {
+ $::gridPath //= fs->catfile( $FindBin::Bin, qw(.. data grid.txt) );
+ ::dprint "[WRN] using default word grid search file: $::gridPath\n";
+}
+
+my $dictFh = unsafe_openDict( $::dictPath );
+my $rawGridData = unsafe_readChaos( $::gridPath );
+
+my @gridWordsOrganized = genWordsOrganized( prepareGridData( $rawGridData ) );
+
+if ( $::debugging ) {
+ my $cnt = scalar @gridWordsOrganized;
+ ::dprint "[DBG] Total $cnt possible words in the word-search grid.\n";
+ my $wd = length $cnt; # for fixed length of count
+ my $i = 0;
+ ::dprint(sprintf("%${wd}d ",++$i), $_, $/) for @gridWordsOrganized;
+}
+
+my @matchedWords = grepMatchedWords( $dictFh, \@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-1.raku b/challenge-076/jeongoon/raku/ch-1.raku
new file mode 100644
index 0000000000..576219074b
--- /dev/null
+++ b/challenge-076/jeongoon/raku/ch-1.raku
@@ -0,0 +1,49 @@
+#!/usr/bin/env raku
+# -*- Mode: Raku; indent-tabs-mode: nil; coding: utf-8 -*-
+# vim: set et ts=4 sw=4:
+
+use v6.d;
+
+subset PrimeNum of Int where { $^a > 1 }
+
+multi minCombiPrimeSum ( PrimeNum:D $S ) {
+ minCombiPrimeSum( $S, prime-numbers($S) );
+}
+
+multi minCombiPrimeSum ( PrimeNum:D $S, @pnums ) {
+ my @rpn = @pnums.
+ #sort. # already sorted in prime-numbers()
+ reverse;
+
+ say @rpn.raku if 0;
+ # find only one possible combination
+ for 1 .. @rpn.elems -> $noc {
+ for @rpn.combinations( $noc ) -> @pn {
+ ($S == sum @pn) and @pn.return;
+ }
+ }
+
+ # not found
+ [].return;
+}
+
+sub prime-numbers ( PrimeNum:D $limit ) { # a poor prime number generator
+ my PrimeNum @p = 3;
+ my $candi = 3;
+ [2].return if $limit == 2;
+ [2,3].return if $limit < 5;
+
+ NEW-NUMBER:
+ while ( ($candi += 2) <= $limit ) {
+ for @p -> $p { ($candi %% $p) and next NEW-NUMBER; }
+ push @p, $candi;
+ }
+ [ 2, |@p ].return;
+}
+
+sub MAIN ( PrimeNum \S ) {
+ my @a-combi = minCombiPrimeSum( S );
+ say "Input: " ~ S;
+ say "Output: " ~ @a-combi.elems;
+ say "a possible combination is {@a-combi.raku}";
+}
diff --git a/challenge-076/jeongoon/raku/ch-2.raku b/challenge-076/jeongoon/raku/ch-2.raku
new file mode 100644
index 0000000000..4c3bca5246
--- /dev/null
+++ b/challenge-076/jeongoon/raku/ch-2.raku
@@ -0,0 +1,183 @@
+#!/usr/bin/env raku
+# -*- Mode: Raku; indent-tabs-mode: nil; coding: utf-8 -*-
+# vim: set et ts=4 sw=4:
+
+use v6.d;
+
+our $debugging = False;
+
+subset Nat of Int where { $^a > 0 }
+
+class GridSizeInfo {
+ has UInt ( $.max-pos is ro, $.line-len is ro, $!rows-idx );
+
+ submethod BUILD( :$!max-pos!, :$!line-len! ) {
+ $!rows-idx = $!max-pos div $!line-len;
+ }
+
+ # all the indices when data in a string(linear form)
+ method all-columns-indices {
+ ( 0 ..^ $!line-len ).map( # for every column index
+ -> $c { ( 0 .. $!rows-idx ). # for every row index
+ map( -> $r { my $p = $c + $!line-len * $r;
+ $p > $!max-pos and last; $p } ) } );
+ }
+
+ 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
+ -> $c { my $p = $r + $c;
+ $p > $!max-pos and last; $p } ) } );
+ }
+
+ method all-topleft-bottomright-indices {
+ # for every starting point: ex) |(0,1,2), |(3,6,9)
+ ( |(0 ...^ $!line-len),
+ |($!line-len, 2*$!line-len ... $!max-pos) ).map(
+ -> $b {
+ my $col = $b % $!line-len;
+ $b, |( $!line-len+1, 2*($!line-len+1) ... $!max-pos ).map(
+ -> $dt { my $p = $b + $dt;
+ # ex) when 0 -> 4 -> 8 -> 9(X)
+ ( ($p <= $!max-pos) and
+ ($p % $!line-len) > $col ) or last;
+ $p } ) } );
+ }
+
+ method all-topright-bottomleft-indices {
+ # for every starting point: ex) |(0,1,2) |(5,8)
+ ( |(0 ...^ $!line-len),
+ |(2*$!line-len-1, 3*$!line-len-1 ... $!max-pos) ).map(
+ -> $b {
+ my $col = $b % $!line-len;
+ $b, |( $!line-len-1, 2*($!line-len-1) ... $!max-pos ).map(
+ -> $dt { my $p = $b + $dt;
+ # ex) when 1 -> 3 -> 8(X)
+ ( ($p <= $!max-pos) and
+ ($p % $!line-len) < $col ) or last;
+ $p } ) } );
+ }
+
+ multi method all-indices {
+ with self {
+ return |.all-columns-indices, |.all-rows-indices,
+ |.all-topleft-bottomright-indices, |.all-topright-bottomleft-indices
+ }
+ }
+
+ multi method all-indices( Bool :$both-direction ) {
+ my @direction = callwith();
+ $both-direction or @direction.List.return;
+ @direction.map(
+ -> @o {
+ |(@o, ( @o.elems > 1 ?? @o.reverse !! Empty ));
+ } );
+ }
+
+ # finay result =.=;
+ method all-subsequences-indices {
+ self.all-indices( :both-direction ).map(
+ -> @i { |( |@i.combinations(1),
+ |@i[ (^@i.elems).combinations(2)
+ .map( -> @two { Range.new( |@two ) } ) ] ) } );
+ }
+}
+
+class GridSearchData {</