From d44b903e2ad1a2a2ad4bf652b859240bcd08c7ba Mon Sep 17 00:00:00 2001 From: Myoungjin JEON Date: Thu, 27 Aug 2020 07:55:43 +1000 Subject: [ch-075/jeongoon] add Haskell and Common-lisp solution with bonus --- challenge-075/jeongoon/.gitignore | 2 + challenge-075/jeongoon/commmon-lisp/ch-1.lsp | 65 +++++++++++++ challenge-075/jeongoon/commmon-lisp/ch-2.lsp | 116 ++++++++++++++++++++++++ challenge-075/jeongoon/haskell/JCombinations.hs | 45 +++++++++ challenge-075/jeongoon/haskell/ch-1.hs | 60 ++++++++++++ challenge-075/jeongoon/haskell/ch-2.hs | 53 +++++++++++ 6 files changed, 341 insertions(+) create mode 100644 challenge-075/jeongoon/commmon-lisp/ch-1.lsp create mode 100644 challenge-075/jeongoon/commmon-lisp/ch-2.lsp create mode 100644 challenge-075/jeongoon/haskell/JCombinations.hs create mode 100644 challenge-075/jeongoon/haskell/ch-1.hs create mode 100644 challenge-075/jeongoon/haskell/ch-2.hs diff --git a/challenge-075/jeongoon/.gitignore b/challenge-075/jeongoon/.gitignore index a109a701fc..23c7e03022 100644 --- a/challenge-075/jeongoon/.gitignore +++ b/challenge-075/jeongoon/.gitignore @@ -1,3 +1,5 @@ ch-1 ch-2 *~ +elm-stuff +index.html diff --git a/challenge-075/jeongoon/commmon-lisp/ch-1.lsp b/challenge-075/jeongoon/commmon-lisp/ch-1.lsp new file mode 100644 index 0000000000..075e153215 --- /dev/null +++ b/challenge-075/jeongoon/commmon-lisp/ch-1.lsp @@ -0,0 +1,65 @@ +;; tested with: +;; sbcl --script ch-1.lsp 6 1 2 4 # first one: sum; rest: coins +;; ( sollution ... ) +(defun combi-coin-sum (coin-sum coin-list) + (if (null coin-list) nil + ;; else + (let* + ((sorted-coin-list (sort coin-list #'<)) + (first-coin (car sorted-coin-list)) + (max-noc (floor coin-sum first-coin)) + (other-coins (cdr sorted-coin-list)) + (all-combi)) + (loop for noc from max-noc downto 0 + do + (let* ((small-change (- coin-sum (* first-coin noc)))) + (if (= small-change 0) + (let ((all-first-coins + (make-list noc :initial-element first-coin))) + (if (null all-combi) (setq all-combi (list all-first-coins)) + (nconc all-combi (list all-first-coins)))) + ;; else + (let ((sub-combis (combi-coin-sum small-change other-coins))) + (if (null sub-combis) nil + ;; else + (let ((head-combi + (make-list noc :initial-element first-coin))) + (map 'list + #'(lambda (a-sub-combi) + (let ((new-combi + (append head-combi a-sub-combi))) + (if (null all-combi) + (setq all-combi (list new-combi)) + (nconc all-combi (list new-combi))))) + sub-combis))))))) ;; if sub-combis is nil, + (remove-if #'null all-combi)))) ;; map will return nil + +;; ( testing ... ) +(defun get-command-line () + (or + #+CLISP *args* + #+SBCL *posix-argv* + #+LISPWORKS system:*line-arguments-list* + #+CMU extensions:*command-line-words* + nil)) + +(defparameter *cmdline* (get-command-line)) + +(defun print-usage () + (format t "Usage: sbcl --script ch-1.lsp " + (first *cmdline*))) + +(when (< (length *cmdline*) 3) (print-usage) (quit)) + +(defparameter *coin-sum* (parse-integer (second *cmdline*))) +(defparameter *coin-lst* (map 'list #'parse-integer (cddr *cmdline*))) +(format t "Input:~%@C = ( ~{~d~^, ~} )~%" *coin-lst*) +(format t "$S = ~d~%" *coin-sum*) + +(let ((total-combi (combi-coin-sum *coin-sum* *coin-lst*))) + (format t "Output: ~d~%~%" (length total-combi)) + (format t "possible ways are:~%") + (map nil + #'(lambda (combi) + (progn + (format t "( ~{~d~^, ~} )~%" combi))) total-combi)) diff --git a/challenge-075/jeongoon/commmon-lisp/ch-2.lsp b/challenge-075/jeongoon/commmon-lisp/ch-2.lsp new file mode 100644 index 0000000000..bd4626846c --- /dev/null +++ b/challenge-075/jeongoon/commmon-lisp/ch-2.lsp @@ -0,0 +1,116 @@ +;; ( solution ... ) +;; which depends on combinations function +(defun get-largest-rect-area (histogram-data) + (let* + ((histogram-size (length histogram-data)) + (all-possible-area + (append + histogram-data ;; by size of width 1 + (map 'list + #'(lambda (pos) + (let* ((x1 (apply #'min pos)) ;; ensure x1 < x2 + (x2 (apply #'max pos)) + (common-height + (apply #'min (subseq histogram-data x1 (1+ x2))))) + (* common-height (1+ (- x2 x1))))) + (combinations-index 2 histogram-size))))) + (apply #'max all-possible-area))) + +;; ( bonus ... ) +(defun print-histogram (histogram-data) + (let* ((histogram-size (length histogram-data)) + (max-height (apply #'max histogram-data)) + (word-width (1+ (length (format nil "~d" max-height)))) + (fmt-string (format nil "~~~d@a" word-width))) + + (loop for y from max-height downto 1 collect + (let* ((line (format nil fmt-string y)) ;; first column: y scale + ) + ;; whitespace or sharpmark + (map nil + #'(lambda (x-data) + (let* ((current-word + (format nil fmt-string + (if (< x-data y) "" "#")))) + (setq line(concatenate 'string line current-word)))) + histogram-data) + (format t "~a~%" line) + line)) + (format t "~a~%" (make-string (* word-width (1+ histogram-size)) + :initial-element #\_)) + (format t fmt-string "") + (map nil + #'(lambda (x-data) (format t fmt-string x-data)) histogram-data) + (format t "~%"))) + +;; ( dependecies ... ) +(defun make-range (minv maxv &optional (step 1)) ;; from #072 + (when (<= minv maxv) + (cons minv (make-range (+ minv step) maxv step)))) + +(defun make-vector-range (min max &optional (step 1)) + (let* ((range (make-range min max step)) + (size (length range))) + (make-array (list size) :initial-contents range))) + +(defun combinations-index (n m) ;; translated from ch-2.pl + ;; a non-recursive method for making combinations + (when (>= m n) + (let* ((initial-room-size (- m n)) + (room (make-array (list n) :initial-element initial-room-size)) + (pos (make-array (list n) + :initial-contents (make-vector-range 0 (1- n)))) + (next-cursor (1- n)) + (combi (list (coerce pos 'list)))) ;; coerce makes a copy of array + (loop named moving-element do + (if (> (aref room next-cursor) 0) + ;; still current element move to right + (let ((ref-room (aref room next-cursor)) + (ref-pos (aref pos next-cursor))) + (setf (aref room next-cursor) (1- ref-room)) + (setf (aref pos next-cursor) (1+ ref-pos)) + (nconc combi (list (coerce pos 'list)))) + ;; else + ;; no more room left on the right for current element + ;; have to move cursor to point next avaiable one. + (let* + ((cursor-moved + (loop named moving-cursor for i from next-cursor above 0 + do + (when (> (aref room (1- i)) 0) + (setq next-cursor (1- i)) + (return-from moving-cursor t))))) + (if cursor-moved + (let ((room-size (1- (aref room next-cursor))) + (base-pos (aref pos next-cursor))) + (loop for i from next-cursor below n + for p from 1 do + (progn + (setf (aref room i) room-size) + (setf (aref pos i) (+ base-pos p)))) + (nconc combi (list (coerce pos 'list))) + (setq next-cursor (1- n))) + ;; else : "no more movement" means we found all combinations + (return-from moving-element combi)))))))) + +;; ( testing ... ) +(defun get-command-line () + (or + #+CLISP *args* + #+SBCL *posix-argv* + #+LISPWORKS system:*line-arguments-list* + #+CMU extensions:*command-line-words* + nil)) + +(defparameter *cmdline* (get-command-line)) + +(defun print-usage () + (format t "Usage: sbcl --script ch-2.lsp ..." + (first *cmdline*))) + +(when (< (length *cmdline*) 2) (print-usage) (quit)) + +(defparameter *histogram-data* (map 'list #'parse-integer (cdr *cmdline*))) +(format t "Input: @A = ~A~%" *histogram-data*) +(format t "Ouput: ~d~%" (get-largest-rect-area *histogram-data*)) +(print-histogram *histogram-data*) diff --git a/challenge-075/jeongoon/haskell/JCombinations.hs b/challenge-075/jeongoon/haskell/JCombinations.hs new file mode 100644 index 0000000000..07456e689c --- /dev/null +++ b/challenge-075/jeongoon/haskell/JCombinations.hs @@ -0,0 +1,45 @@ +module JCombinations + ( combinationsIndex + ) where + +combinationsIndex :: Int -> Int -> [[Int]] +combinationsIndex n m -- return always sorted members and sorted list + | m < n = [] + | otherwise = + -- acc room nextId to move + impli [[0 .. (n-1)]] (replicate n (m-n)) (n-1) + where + incrAt idx list = take idx list + ++ ((list !! idx) +1) : drop (idx+1) list + dcrAt idx list = take idx list + ++ ((list !! idx) -1) : drop (idx+1) list + impli acc roomLs nextCsr = + if roomLs !! nextCsr > 0 -- still current cursor is movable + then impli (acc ++ [newPosLs]) (dcrAt nextCsr roomLs) nextCsr + else -- no more room to move + -- find the next element available to move + case (pointNextCsr nextCsr) of + Nothing -> acc -- if we cannot move any of them which means + -- we found all cases. + Just newCsr -> -- move all cursors + -- and try to move last cursor next time + impli ( acc ++ [updatePosLsFrom newCsr] ) + (updateRoomFrom newCsr) (n-1) + where + posLs = last acc + newPosLs = (incrAt nextCsr posLs) + + updatePosLsFrom fromCsr = -- move all cursors + take (fromCsr) posLs -- keep until fromCsr + -- and reset others to leftmost part of the elements + ++ take (n -fromCsr) [ ((posLs !! fromCsr)+1) .. ] + updateRoomFrom fromCsr = + take (fromCsr) roomLs + -- reduce each room by one + ++ replicate (n -fromCsr) ((roomLs !! fromCsr) -1) + + pointNextCsr curcsr + | curcsr == 0 = Nothing + | otherwise = if roomLs !! nxtcsr > 0 then Just nxtcsr + else pointNextCsr nxtcsr + where nxtcsr = curcsr - 1 diff --git a/challenge-075/jeongoon/haskell/ch-1.hs b/challenge-075/jeongoon/haskell/ch-1.hs new file mode 100644 index 0000000000..ff4b6f036b --- /dev/null +++ b/challenge-075/jeongoon/haskell/ch-1.hs @@ -0,0 +1,60 @@ +{-# LANGUAGE DeriveGeneric #-} +{-# LANGUAGE OverloadedStrings #-} +import Options.Generic +import Data.List (sortBy, unfoldr) +import Data.Maybe (fromJust, isJust) + +{- Tested with: +runhaskell ch-1.hs --coinsum=6 --c=1 --c=2 --c=4 +-} + +-- solution +totalNumberOfCombinations = length.combiCoinSum +combiCoinSum ( targetSum, coins ) = + case ( combCS targetSum coins ) of + Nothing -> [] + Just xs -> xs + where + combCS :: Int -> [Int] -> Maybe [[Int]] + combCS targetSum coins + | null coins = Nothing + | otherwise = Just $ (joinCombi.grepCombi) goThroughThisCoin + where + thisCoin = head sortedCoinsDesc + otherCoins = tail sortedCoinsDesc + sortedCoinsDesc = sortBy (\a b -> compare b a) coins + maxNoc = targetSum `div` thisCoin -- Noc : Number Of Coins + joinCombi = foldr (++) [] + grepCombi = (map fromJust).(filter isJust) + + goThroughThisCoin = unfoldr goThroughThisCoinInner maxNoc + goThroughThisCoinInner noc + | noc < 0 = Nothing + | otherwise = + if smallChange == 0 then -- generate from nocMax to 0 + Just ( Just [fillThisCoin], (pred noc) ) + else case (combCS smallChange otherCoins) of + Nothing -> Just ( Nothing, (pred noc) ) + Just p -> Just ( Just ( + map (\r -> fillThisCoin ++ r) p), (pred noc)) + where + fillThisCoin = (replicate noc thisCoin) + smallChange = targetSum - ( thisCoin * noc ) + +data Sample = Sample { coinsum :: Int, c :: [Int] } + deriving (Generic, Show) +instance ParseRecord Sample + +-- testing +main = do + args <- getRecord "Challennge #076 - Task #1" + let sample = args :: Sample + sSum = coinsum sample + sCoins = c sample in + do + putStrLn "Input:" + putStrLn $ "@C = " ++ (show sCoins) + putStrLn $ "$S = " ++ (show sSum) + putStrLn $ "Output:" ++ (show (totalNumberOfCombinations(sSum, sCoins))) + putStrLn $ "possible ways are: " + mapM_ (putStrLn.show) (combiCoinSum(sSum, sCoins)) diff --git a/challenge-075/jeongoon/haskell/ch-2.hs b/challenge-075/jeongoon/haskell/ch-2.hs new file mode 100644 index 0000000000..482bbf3175 --- /dev/null +++ b/challenge-075/jeongoon/haskell/ch-2.hs @@ -0,0 +1,53 @@ +{-# LANGUAGE DeriveGeneric #-} +{-# LANGUAGE OverloadedStrings #-} +import Options.Generic +import JCombinations (combinationsIndex) +import Data.List (unfoldr) +import System.Exit (die) + +-- solution + +getLargestRectArea :: [Int] -> Int +getLargestRectArea hdata = maximum allPossibleAreas where + allPossibleAreas = map calcArea1 [ 0 .. (dataLen - 1) ] + ++ map calcArea2 (combinationsIndex 2 dataLen) + where + dataLen = length hdata + calcArea1 = (hdata !!) + calcArea2 = (\xs -> (commonH xs) * ((last xs)-(head xs)+1)) + commonH xs = (minimum.map (hdata !!)) [ (head xs) .. (last xs) ] + +-- bonus +printHistogram :: [Int] -> IO () +printHistogram hdata = do + mapM_ putStrLn lineBuffers where + hdataLen = length hdata + maxH = maximum hdata + lineBuffers = unfoldr forYaxis maxH + forYaxis (y) + | y == 0 = Just( replicate (wordWidth * (hdataLen +1)) '_', y-1 ) + | y == -1 = Just( whiteSpace + ++ (foldl (\acc x -> + acc ++ (fixedNumber x)) "" hdata) , y-1 ) + | y < -1 = Nothing + | otherwise = Just( yScale ++ allColumnData, y-1 ) + where + wordWidth = ((length.show) maxH) +1 + whiteSpace = replicate wordWidth ' ' + yScale = fixedNumber y + fixedNumber n = (preWhiteSpace n) ++ (show n) + sharpMark = (replicate (wordWidth - 1) ' ') ++ ['#'] + preWhiteSpace n = replicate (wordWidth - (length (show n))) ' ' + allColumnData = + foldl (\acc x -> acc ++ (if x < y + then whiteSpace else sharpMark )) "" hdata + +-- testing +main = do + args <- getRecord "Challenge #075 - Task #2" + let sample = args::[Int] in do + if null sample then die "list not given: runhaskell ch-2.hs " + else return () + putStrLn ("Input: " ++ (show sample)) + putStrLn ("Output: " ++ (show (getLargestRectArea sample))) + printHistogram sample -- cgit From 259dac5ffd3c11744f484a2493403ebc6a16249e Mon Sep 17 00:00:00 2001 From: Myoungjin JEON Date: Fri, 28 Aug 2020 00:28:53 +1000 Subject: add Perl and Raku solution --- challenge-075/jeongoon/haskell/ch-2.hs | 1 - challenge-075/jeongoon/perl/CombinationsIndex.pm | 121 +++++++++++++++++ challenge-075/jeongoon/perl/ch-1.pl | 49 +++++++ challenge-075/jeongoon/perl/ch-2.pl | 159 +++++++++++++++++++++++ challenge-075/jeongoon/raku/ch-1.raku | 47 +++++++ challenge-075/jeongoon/raku/ch-2.raku | 62 +++++++++ 6 files changed, 438 insertions(+), 1 deletion(-) create mode 100644 challenge-075/jeongoon/perl/CombinationsIndex.pm create mode 100644 challenge-075/jeongoon/perl/ch-1.pl create mode 100644 challenge-075/jeongoon/perl/ch-2.pl create mode 100644 challenge-075/jeongoon/raku/ch-1.raku create mode 100644 challenge-075/jeongoon/raku/ch-2.raku diff --git a/challenge-075/jeongoon/haskell/ch-2.hs b/challenge-075/jeongoon/haskell/ch-2.hs index 482bbf3175..934aad2211 100644 --- a/challenge-075/jeongoon/haskell/ch-2.hs +++ b/challenge-075/jeongoon/haskell/ch-2.hs @@ -6,7 +6,6 @@ import Data.List (unfoldr) import System.Exit (die) -- solution - getLargestRectArea :: [Int] -> Int getLargestRectArea hdata = maximum allPossibleAreas where allPossibleAreas = map calcArea1 [ 0 .. (dataLen - 1) ] diff --git a/challenge-075/jeongoon/perl/CombinationsIndex.pm b/challenge-075/jeongoon/perl/CombinationsIndex.pm new file mode 100644 index 0000000000..47dbcde67f --- /dev/null +++ b/challenge-075/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 +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-075/jeongoon/perl/ch-1.pl b/challenge-075/jeongoon/perl/ch-1.pl new file mode 100644 index 0000000000..e089621853 --- /dev/null +++ b/challenge-075/jeongoon/perl/ch-1.pl @@ -0,0 +1,49 @@ +#!/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 feature qw(say); + +# solution +sub combiCoinSum { + my $S = shift; + my @RC = sort { $b <=> $a } @_; # (R)est of (C)oins (sorted) + my $fc = shift @RC; # (f)irst (c)oin + + defined $fc or ( warn "no coins provided", return ()); + + my @result; + + my $maxNoc = int $S / $fc ; + for my $noc ( reverse 0 .. $maxNoc ) { + my $change = $S -$fc * $noc; + my @coins = ( $fc ) x $noc; + if ( $change > 0 ) { + push @result, map { [ @coins, @$_ ] } combiCoinSum( $change, @RC ); + } + else { push @result, [ @coins ] } + } + @result; +} + +# testing +package main; + +sub usage { + say "perl ch-1.pl \n"; +} +sub raku_array { "[".(join ", ", @_)."]" } + +scalar @ARGV < 2 and ( usage, exit -1 ); + +my $S = shift; +my @C = @ARGV; +my @combi = combiCoinSum( $S, @C ); + +say "Input:"; +say "\@C = @{[raku_array @C]}"; +say "\$S = $S"; +say "Output: @{[scalar @combi ]}"; +say "possible ways are:"; +say "@{[raku_array @$_ ]}" for @combi; diff --git a/challenge-075/jeongoon/perl/ch-2.pl b/challenge-075/jeongoon/perl/ch-2.pl new file mode 100644 index 0000000000..029cab4a47 --- /dev/null +++ b/challenge-075/jeongoon/perl/ch-2.pl @@ -0,0 +1,159 @@ +#!/usr/bin/env perl +# -*- Mode: cperl; cperl-indent-level:4 tab-width: 8; indent-tabs-mode: nil -*- +# -*- coding: utf-8 -*- + +use utf8; +use strict; use warnings; +no warnings "experimental::smartmatch"; +use v5.14; # say, switch + +use Getopt::Long qw(:config gnu_compat); +use Pod::Usage; +use Term::ANSIColor; +use List::Util qw(min max); + +use FindBin; +use lib ( $FindBin::Bin ); +use CombinationsIndex qw(combinationsIndex); + +BEGIN { + $::utf8 = 1; + $::colour = 1; + + GetOptions( 'help' => \$::help, + 'utf8!' => \$::utf8, + 'color|colour!' => \$::colour, + ) or pod2usage(2); + if ( $::utf8 ) { + binmode( STDERR, ':utf8' ); + binmode( STDOUT, ':utf8' ); + } +} + +=pod Largest Rectangle Histogram + +perl ch-2.pl [--help] [--no-utf8] [--no-color] + +=cut + +# I guess List::Util is a standard library +#sub min { +# scalar @_ == 0 and warn "no values are given"; +# my $min = shift; +# ( $_ < $min ) and ( $min = $_ ) for @_; +# $min +#} +#sub max { +# scalar @_ == 0 and warn "no values are given"; +# my $max = shift; +# ( $_ > $max ) and ( $max = $_ ) for @_; +# $max +#} + +# solution +sub allPairOfAreaRange { +# return as [ area1, area2 ... ], [ [range1], [range2], ... ] in the same order + my @H = @_; + my @range; + my @area; + + # there are chance one peak data can create the largest area + push @range, map { [$_, $_] } @H; + push @area, map { $_ } @H; # areas by (width of one) X (each height) + + # range combinations + my @range_comb = combinationsIndex 2, (scalar @H); + push @range, @range_comb; + push @area, map { + # my ( $i0, $i1 ) = ( min @$_, max @$_ ); + my ( $i0, $i1 ) = @$_; # combinationsIndex always return sorted values. + my $common_h = min @H[ $i0 .. $i1 ]; + $common_h * ( $i1 - $i0 +1 ); + } @range_comb; + + [ @area ], [ @range ] +} + +sub getLargestRectArea { max @{ (allPairOfAreaRange@_ )[0] } } + +# bonus +sub raku_array { "[".(join ", ", @_)."]" } # from ch-1.pl +# from #074/ch-1.pl +sub ssprintf ($$) { sprintf "%#$_[0]s", $_[1] } +sub map_ssprintf { map { sprintf "%#$_[0]s", $_ } @_[1..$#_] } +sub u_($) { + return $_[0] unless $::utf8; + my $ch; + for ($_[0]) { + $ch = '└' when '`'; + $ch = '─' when '-'; + $ch = '│' when '|'; + $ch = '■' when '#'; + default { $ch = $_[0] } + } + $ch; +} + +sub printLargestRectArea { + my @H = @_; + my @result = allPairOfAreaRange @H; + my @ar = @{$result[0]}; + my @rg = @{$result[1]}; + + my $maxh = max @H; # max height + my $ww = 1 + length $maxh; # word width + + my $arL = max @ar; # area Largest + my @rgL; + + for my $i ( 0..$#ar ) { + $ar[$i] == $arL and ( push @rgL, $rg[$i] ) # multiple largest area ?? + } + + say "Input: " . raku_array( @H ); + say "Output: " . $arL; + say "Where:"; + + for my $y ( reverse 1 .. $maxh ) { + my $line = ssprintf $ww, $y; + $line .= u_"|"; + + if ( $::colour ) { + for my $x ( 0 .. $#H ) { # go through histogram data + my $ch = " "; + my $x_in_largest_rectangle = 0; + if ( $H[$x] >= $y ) { + for my $r (@rgL) { + if ( $$r[0] <= $x and $x <= $$r[1] ) { + my $common_h = min @H[ $$r[0] .. $$r[1] ]; + $x_in_largest_rectangle = $common_h >= $y; + } + } + $line .= colored( [ $x_in_largest_rectangle + ? 'black on_yellow' + :'black on_white' ], ssprintf $ww, u_$ch ); + } + else { + $line .= ssprintf $ww, " "; + } + } + } + else { + $line .= join "", + map_ssprintf $ww, ( map { $_ >= $y ? u_"#" : u_" " } @H ); + } + say $line; + } + + say ssprintf( $ww, " " ), u_"`", + map_ssprintf( $ww, ( (u_("-") x $ww ) x scalar @H ) ); + say ssprintf($ww, " "), " ",map_ssprintf( $ww, @H ); +} + +# testing +package main; + +( $::help or scalar @ARGV < 1 ) + and pod2usage( -exitval => 0 -verbose => 2 ); + +printLargestRectArea @ARGV; diff --git a/challenge-075/jeongoon/raku/ch-1.raku b/challenge-075/jeongoon/raku/ch-1.raku new file mode 100644 index 0000000000..7cb85944b5 --- /dev/null +++ b/challenge-075/jeongoon/raku/ch-1.raku @@ -0,0 +1,47 @@ +#!/usr/bin/env raku +# -*- Mode: Raku; indent-tabs-mode: nil; coding: utf-8 -*- +# vim: set et ts=4 sw=4: + +use v6.d; + +subset Coin of Int where { $^a > 0 } + +# solution +sub combiCoinSum ( Coin:D $S, @C ) { + my @result; + my @RC = @C.sort( { $^b <=> $^a } ); # (R)est of (C)oins + my $fc = shift @RC; # (f)irst (c)oin + + $fc.defined or ().return; + + my $max-noc = $S div $fc; + for $max-noc ... 0 -> $noc { + my $change = $S - $fc * $noc; + my @coins = $fc xx $noc; + if $change > 0 { + with (combiCoinSum( $change, @RC )) { + if .elems > 0 { + .map( -> @rest-coins + { @result.push( [ |@coins, |@rest-coins ] ) } ); + } + } + } + elsif @coins.elems > 0 { + @result.push( @coins ); + } + } + @result; +} + +# testing +sub MAIN ( + Coin:D $S, #= sum of coins + **@C where { @C.elems > 0 and @C.all ~~ Coin } #= coin list +) { + @C = @C>>.Int; + my @combi = combiCoinSum( $S, @C ); + say "Input:\n\@C = {@C.raku}\n\$S = {$S}"; + say "Output: {@combi.elems}"; + say "possible ways are:"; + .say for @combi>>.Array; +} diff --git a/challenge-075/jeongoon/raku/ch-2.raku b/challenge-075/jeongoon/raku/ch-2.raku new file mode 100644 index 0000000000..c413e1f17f --- /dev/null +++ b/challenge-075/jeongoon/raku/ch-2.raku @@ -0,0 +1,62 @@ +#!/usr/bin/env raku +# -*- Mode: Raku; indent-tabs-mode: nil; coding: utf-8 -*- +# vim: set et ts=4 sw=4: + +use v6.d; + +# solution +class Rect { + has ( @.x, $.h ); + method x-range() { (min @!x) .. (max @!x) } + method area () { + $!h * (@!x.elems == 1 ?? 1 !! 1 + abs( [-] @!x ) ) + } +} + +sub all-possible-rect ( @H ) { + ( ^@H.elems ).combinations( 1..2 ).map( + -> @range { + Rect.new( :x(@range), + :h( @H[ min(@range) .. max(@range) ].min ) ); + } ); +} + +sub get-largest-ares ( Rect:D @rects ) { + @rects.map( *.area ).max; +} + +sub ssprintf ( UInt:D $w, $str ) { sprintf( "%#{$w}s", $str ) } + +# bonus +sub print-histogram ( :histogram-data(@H), :all-rects(@rects) ) { + my $max-area = get-largest-ares( @rects ); + my @ma-rects = @rects.grep( -> $r { $r.area == $max-area } ); + my $mh = max @H; + my $ww = $mh.chars + 1; + for $mh ... 1 -> $y { + my $line = ssprintf( $ww, $y ) ~ '│'; + for 0 .. @H.end Z @H -> ($i, $h) { + my $ch = " "; + if $h >= $y { + $ch = "#"; + for @ma-rects -> $r { + $ch = "■" if $r.h >= $y and $i (elem) $r.x-range; + } + } + $line ~= ssprintf( $ww, $ch ); + } + $line.say; + } + say ssprintf( $ww, " " ) ~ '└' ~ ( "─" x ( $ww * @H.elems ) ); + say ssprintf( $ww, " " ) ~ ' ' ~ [~] @H.map( -> $h { ssprintf( $ww, $h ) }); +} + +sub MAIN ( **@H where { @H.elems > 0 and @H.all ~~ UInt } ) { + @H = @H>>.UInt; + my Rect @rects = all-possible-rect( Array[UInt].new(@H) ); + my $largest = get-largest-ares( @rects ); + say "Input: {@H.raku}"; + say "Output: {$largest}"; + say "Where:"; + print-histogram( :histogram-data(@H), :all-rects( @rects ) ); +} -- cgit