diff options
| author | Myoungjin JEON <jeongoon@gmail.com> | 2020-11-22 22:03:26 +1100 |
|---|---|---|
| committer | Myoungjin JEON <jeongoon@gmail.com> | 2020-11-22 22:03:26 +1100 |
| commit | 1e333f99d4b1cb13a66865e5f69902ffdf946690 (patch) | |
| tree | a29e28a73ab89fa0cf21f58c8fa4386fbf0f2934 /challenge-087 | |
| parent | 2dbbd5e2cb1142e0d4c8bd9bdadd1b90d24cc829 (diff) | |
| download | perlweeklychallenge-club-1e333f99d4b1cb13a66865e5f69902ffdf946690.tar.gz perlweeklychallenge-club-1e333f99d4b1cb13a66865e5f69902ffdf946690.tar.bz2 perlweeklychallenge-club-1e333f99d4b1cb13a66865e5f69902ffdf946690.zip | |
[ch-087/jeongoon] Perl, Raku, Common-lisp, Go Solution and a Blog about Task #1 added.
Diffstat (limited to 'challenge-087')
| -rw-r--r-- | challenge-087/jeongoon/blog.txt | 1 | ||||
| -rw-r--r-- | challenge-087/jeongoon/common-lisp/ch-1.lsp | 73 | ||||
| -rw-r--r-- | challenge-087/jeongoon/common-lisp/ch-2.lsp | 206 | ||||
| -rw-r--r-- | challenge-087/jeongoon/go/ch-1.go | 83 | ||||
| -rw-r--r-- | challenge-087/jeongoon/go/ch-2.go | 232 | ||||
| -rw-r--r-- | challenge-087/jeongoon/perl/ch-1.pl | 41 | ||||
| -rw-r--r-- | challenge-087/jeongoon/perl/ch-2.pl | 232 | ||||
| -rw-r--r-- | challenge-087/jeongoon/raku/ch-1.raku | 22 | ||||
| -rw-r--r-- | challenge-087/jeongoon/raku/ch-2.raku | 113 |
9 files changed, 1003 insertions, 0 deletions
diff --git a/challenge-087/jeongoon/blog.txt b/challenge-087/jeongoon/blog.txt new file mode 100644 index 0000000000..89d247e6a0 --- /dev/null +++ b/challenge-087/jeongoon/blog.txt @@ -0,0 +1 @@ +https://dev.to/jeongoon/weekly-challenge-086-task-1-perl-raku-2hk4 diff --git a/challenge-087/jeongoon/common-lisp/ch-1.lsp b/challenge-087/jeongoon/common-lisp/ch-1.lsp new file mode 100644 index 0000000000..13f5a9bdb3 --- /dev/null +++ b/challenge-087/jeongoon/common-lisp/ch-1.lsp @@ -0,0 +1,73 @@ +;; tested with sbcl --script ch-1.lsp 1 3 2 -1 -2 -3 6 7 9 10 +;;; (output) +;; longest consecutive sequence(s): size:3 +;; (-3 -2 -1) +;; (1 2 3) + +;;; Comment: +;; I thought (sort x #'<) is sorted in place of x +;; however, it didn't work properly until I did (setq x (sort x #'<)) + + +(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 <integer> ...")) + +(when (< (length *cmdline*) 3) (print-usage) (quit)) + +(defparameter *integer-list* (map 'list #'parse-integer (rest *cmdline*))) + +;; even though I tried to coerce; still sorting has problem !!! +(defvar int-list (map 'list #'(lambda (x) (coerce x 'integer)) (remove-duplicates *integer-list*))) +(setq int-list (sort int-list #'<)) ;; (setq ... is must (tested with sbcl 2.0.5)) +(format t "~A~%" int-list) + +(when (not (= (length *integer-list*) (length int-list))) + (format t "*THIS IS SBCL BUG*:~%Orignal list: ~A~%List after sorting: ~A~%" + *integer-list* int-list)) + +(defvar longest-size 0) +(defvar longest-seq-list '()) +(defvar curr-seq '()) + +(defvar last-int (first int-list)) + + +;; (solution ...) +(loop for curr-int in (append (rest int-list) + (list (+ (apply #'max int-list) 2))) + ;; note: dummy added for last checking any sequence left + + do(if (= last-int (1- curr-int)) + (if (null curr-seq) + (setq curr-seq (list last-int curr-int)) + (nconc curr-seq (list curr-int))) + ;; else + (let ((curr-size (length curr-seq))) + (if (< longest-size curr-size) + (setq longest-size curr-size + longest-seq-list (list curr-seq)) + ;; else + (when (= longest-size curr-size) + (setq longest-seq-list + (append longest-seq-list (list curr-seq))))) + (setq curr-seq '()))) + + do(setq last-int curr-int)) + +(if (< 0 longest-size ) + (progn + (format t "longest consecutive sequence(s): size:~A~%" longest-size) + (map nil #'(lambda (a-list) (format t "~A~%" a-list)) longest-seq-list)) + (format t "0 as no consecutive sequence found")) + +(quit) diff --git a/challenge-087/jeongoon/common-lisp/ch-2.lsp b/challenge-087/jeongoon/common-lisp/ch-2.lsp new file mode 100644 index 0000000000..5faeae6023 --- /dev/null +++ b/challenge-087/jeongoon/common-lisp/ch-2.lsp @@ -0,0 +1,206 @@ +;; tested with: +;; echo "[000111][111111][001001][001111][001111] | sbcl --script ch-2.lsp +;; [000111] +;; [111111] +;; [001001] +;; [001111] +;; [001111] + +(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)) +(defparameter *rows-list* '()) +(defvar row '()) + +;; read from stdin +(loop for line = (read-line *standard-input* nil) + while line + do(loop for ch in (coerce line 'list) + do(if (or (char= ch #\1) (char= ch #\0)) + (if (null row) (setq row (list ch)) (nconc row (list ch))) + (when (or (char= ch #\]) + (and (char= ch #\newline) (not (null row)))) + (if (null *rows-list*) + (setq *rows-list* (list row)) + (nconc *rows-list* (list row))) + (setq row '()))))) + + +(defparameter *num-rows* (length *rows-list*)) +(defparameter *num-columns* (length (first *rows-list*))) + +(defun ch-087/subsequences (lines) + (let ((seqs '())) + (loop for line in lines + do(loop while (not (null line)) + do(let ((points-so-far '())) + (loop for point in line + do(progn + (if (null points-so-far) + (setq points-so-far (list point)) + (nconc points-so-far (list point))) + (if (null seqs) + (setq seqs (list (copy-list + points-so-far))) + (nconc seqs (list (copy-list + points-so-far))))))) + (setq line (rest line)))) + seqs)) + +;;; +;;; check data row by row and find lines which consist of cosecutive points +;;; +(defun find-consecuative-lines (columns) ;; a point inclusive + ;; i.e. (1 1 1 0 1) -> ((0 1 2) (4)) + ;; and more ((0) (1) (2) (0 1) (1 2) + ;; (0 1 2) (4)) + (let* ((lines '()) + (curr-points '()) + (prev (first columns))) + (when (char= #\1 prev) (setq curr-points (list 0))) + (loop for curr in (rest columns) + for i from 1 + do(if (char= #\1 prev) + (if (char= #\1 curr) + (if (null curr-points) + (setq curr-points (list (1- i) i)) ;; remember position + (nconc curr-points (list i))) + ;; current line ends here: push into lines list + (progn + (if (null lines) + (setq lines (list curr-points)) + (nconc lines (list curr-points))) + (setq curr-points '()))) + ;; there is no line we looking at currently + (when (char= #\1 curr) ;; but start new one + (setq curr-points (list i))) ;; remember position + ) + do(setq prev curr)) + (when (not (null curr-points)) ;; add if loop not executed or ended without + ;; appending last line + (if (null lines) + (setq lines (list curr-points)) + (nconc lines (list curr-points)))) + (ch-087/subsequences lines))) ;; get subsequeces as well + + +(defvar lines-per-row) +(setq lines-per-row + (loop for row in *rows-list* + for ri from 0 + collect (map 'list #'(lambda (ls) (cons ri (list ls))) + (find-consecuative-lines row)))) + +;;(format t "~A~%" lines-per-row) + +(defun ch-087/intersects (cmp-list) + ;; get intersections of all member in cmp-list + ;; but with :key #'cdr :test #'equal + (if (< (length cmp-list) 1) + '() ;; empty list + ;; else + (let* ((inters (first cmp-list))) + (loop for curr in (rest cmp-list) + do(progn + (setq inters (intersection inters curr + :key #'cdr :test #'equal)) + ;;(format t "inters: ~a~%" inters) + (when (null inters) (return)))) + (map 'list #'(lambda (x) (cadr x)) inters)))) + +(defvar lines-per-row-cp (copy-list lines-per-row)) +(defvar found-rectangles '()) + +;; +;; find possible rectangles +;; +(loop for base from 0 + ;; note: checking procedure is similar to below + ;; 1 2 3 4 -> + ;; 1 -> 1 2 -> 1 2 3 -> 1 2 3 4 + ;; 2 -> 2 3 -> 2 3 4 -> + ;; 3 -> 3 4 -> + ;; 4 + while (not (null lines-per-row-cp)) + do(let ((lines-in-rows '()) + (rows-numbers '()) + (intersection-so-far '()) + (inters '())) + (loop named adding-row + for line-in-row in lines-per-row-cp + for offset from 0 + do (progn + (if (null rows-numbers) + (setq rows-numbers (list (+ base offset))) + (nconc rows-numbers (list (+ base offset)))) + (setq lines-in-rows (append lines-in-rows + (list line-in-row))) + (setq inters + (ch-087/intersects lines-in-rows)) + (if (null inters) + (return-from adding-row) ;; no need to go further + (setq intersection-so-far + ;; making a list looks like below + ;; ( ( (row numbers ...) (points ...) ) ... ) + (map + 'list #'(lambda (x) + (cons rows-numbers (list x))) + inters))))) + + ;; sometimes collect() is working unexpectedly + ;; (probably thanks to lack of my knowledge -.-;) + ;; just do(let... setq(... )) by myself + (when (not (null intersection-so-far)) + (if (null found-rectangles) + (setq found-rectangles (copy-list intersection-so-far)) + (nconc found-rectangles (copy-list intersection-so-far))))) + ;; reducing list + do (setq lines-per-row-cp (cdr lines-per-row-cp))) + +;;(format t "~A~%" found-rectangles) + +;; +;; find largest +;; +;; ( ((0 1) (1 2)) ;; (row from 0 to 1) (column from 1 to 2) +;; ((1 2 3) (4 5)) ... ) + +(defvar largest-area 0) +(defvar largest-rectangle-list '()) + +(loop for rect in found-rectangles + do (let* ((rows (car rect)) + (cols (cadr rect)) + (curr-area (* (length rows) (length cols)))) + (if (= curr-area 1) + nil ;; ignore if it is a point + (if (< largest-area curr-area) + ;; update + (progn (setq largest-area curr-area) + (setq largest-rectangle-list (list rect))) + (when (= largest-area curr-area) + ;; append + (if (null largest-rectangle-list) + (setq largest-rectangle-list (list rect)) + (nconc largest-rectangle-list (list rect)))))))) +;; +;; show the result +;; + +(if (null largest-rectangle-list) + (format t "0 as no rectangle found") + (dolist (rect largest-rectangle-list) + (let* ((rows (car rect)) + (cols (cadr rect))) + (format t "largest area: ~d~%" largest-area) + (format t "at (r:~d,c:~d)~%" (first rows) (first cols)) + (dotimes (r (length rows)) + (format t "~{~a~^ ~}~%" + (coerce (make-array + (length cols) :initial-element #\1) 'list)))))) diff --git a/challenge-087/jeongoon/go/ch-1.go b/challenge-087/jeongoon/go/ch-1.go new file mode 100644 index 0000000000..3803d7d050 --- /dev/null +++ b/challenge-087/jeongoon/go/ch-1.go @@ -0,0 +1,83 @@ +// tested with go run ch-1.go 1 3 2 -1 -2 -3 6 7 9 10 + +package main + +import ( + "os" + "fmt" + "sort" + "strconv" +) + +func usage() { + fmt.Println( "Usage: go run ch-1.go <integer> ..." ) +} + +func main() { + switch len(os.Args[1:]) { + case 0: + usage() + os.Exit(1); + case 1: + fmt.Println("0 as only one element given") + os.Exit(0); + } + + var ns []int + + for _, nstr := range os.Args[1:] { + n, err := strconv.Atoi(nstr) + if err == nil { + ns = append(ns, n) + } else { + fmt.Fprintln(os.Stderr, nstr, "is ignored: ", err) + } + } + + sort.Ints(ns) + + longest_size := 0 + longest_seq_ls := [][]int{} + cseq := []int{} + + lv := ns[0]; // last value + ns = append(ns, ns[len(ns)-1] + 2) // add dummy + + for _, v := range ns[1:] { + switch v - lv { + case 1: // add new member to current seq + if len(cseq) == 0 { + cseq = []int{lv, v} + } else { + cseq = append(cseq, v) + } + case 0: // skip + default: + clen := len(cseq) + if longest_size < clen { // new longest ! + + // update size + longest_size = clen + // new longest seq + longest_seq_ls = [][]int{ cseq } + } else if ( longest_size == clen ) { // same longest + // add to longest_seq_ls + longest_seq_ls = append(longest_seq_ls, cseq) + } + // reset current status + cseq = []int{} + } + lv = v // update last value + } + + if len(longest_seq_ls) > 0 { + fmt.Println("longest size:", longest_size) + fmt.Println("sequence(s):") + for _, sq := range longest_seq_ls { + fmt.Println(sq) + } + } else { + fmt.Println("0") + } + +} diff --git a/challenge-087/jeongoon/go/ch-2.go b/challenge-087/jeongoon/go/ch-2.go new file mode 100644 index 0000000000..f30049cafe --- /dev/null +++ b/challenge-087/jeongoon/go/ch-2.go @@ -0,0 +1,232 @@ +/* tested with: echo '[000111][111111][001001][001111][001111]' | go run ch-2.go + * `-> example 3 + * echo '[101010][010101][101010][010101]' | go run ch-2.go + * `-> example 1 + */ +package main + +import ( + "os" + "bufio" + "fmt" + "strings" + "reflect" +) + +func usage() { + fmt.Println( "Usage: echo [1101][1100][0111][1011]' | go run ch-2.go" ) +} + +// this function will ignore any other information but "0","1","]" +func getPointsFromMatrixLines (raw string) [][]int { + var rowsOut [][]int + // remove new lines separated by [] + lines := strings.Split(raw, "\n") + joined := strings.Join(lines, "") + matrixlines := strings.Split(joined, "]") + + for ln, line := range matrixlines { + x := 0 + var points []int + // collect useful data only + for _, singleStr := range line { + switch string(singleStr) { + case "1": + points = append( points, x ) + x++ + case "0": + x++ + case "[": // okay but not used + case " ": + default: + fmt.Fprintf( os.Stderr, + "Wrong character(%s) at row: %d\n", + singleStr, ln ) + + } + } + rowsOut = append( rowsOut, points ) + } + return rowsOut +} + + +type FullHLine struct { + points []int + row int +} + +func (hl FullHLine) Length() int { + return hl.points[len(hl.points)-1] - hl.points[0] +} + +func (hl FullHLine) StartingPoint() int { + return hl.points[0] +} + +type Rect struct { + rows []int + cols []int +} + +func (rect Rect) NorthWest() (int, int) { + // ref: https://gobyexample.com/multiple-return-values + return rect.rows[0], rect.cols[0] +} + +func (rect Rect) Area() int { + return len(rect.rows) * len(rect.cols) +} + +func getSubHorizLinesFromHorizLines ( hlinesARow []FullHLine ) []FullHLine { + var subHlinesAtARow []FullHLine + for _, hline := range hlinesARow { + for hl := hline ;len(hl.points) > 0; hl.points = hl.points[1:] { + var pnts_so_far []int; + for _, pnt := range(hl.points) { + pnts_so_far = append(pnts_so_far, pnt) + subHlinesAtARow = append(subHlinesAtARow, + FullHLine {pnts_so_far, hline.row} ) + } + } + } + return subHlinesAtARow +} + +func getHorizLinesFromPoints ( pointsAtRows [][]int ) [][]FullHLine{ + var hlinesAtRows [][]FullHLine + + for r, points := range pointsAtRows { + // note: a point will be allowed as a line + // so we can make a vertical line later on + // and vertical line is regarded as a rectangle + // in my implementation + if len(points) == 0 { + continue // skip empty line + } + points = append(points, points[len(points)-1] + 2) // dummy + prev := points[0] + pnts := []int{prev} + var hlinesAtARow []FullHLine + + for _, curr := range points[1:] { + if (curr - prev) == 1 { + pnts = append(pnts, curr) + } else { + if len(pnts) > 0 { + hlinesAtARow = append(hlinesAtARow, + FullHLine { pnts, r } ) + } + pnts = []int{curr} + } + prev = curr + } + + hlinesAtRows = append(hlinesAtRows, + getSubHorizLinesFromHorizLines(hlinesAtARow)) + } + + return hlinesAtRows +} + +func findLargestRectanglesFromHorizLines (hlinesAtRows [][]FullHLine) []Rect { + var largestRects []Rect + largestArea := 0 + + /* note: checking procedure is similar to below + * 1 2 3 4 -> // each number represents row number + * 1 -> 1 2 -> 1 2 3 -> 1 2 3 4 // but intersection is decreasing + * 2 -> 2 3 -> 2 3 4 -> + * 3 -> 3 4 -> + * 4 + */ + + + for + base, har := 0, hlinesAtRows; + len(har) > 0; + base, har = base+1, har[1:] { + intersects := har[0] // initial intersection is same as first row + var rows []int + candidates: + for offset, candi:= range har { + rows = append(rows, base+offset) + var inters []FullHLine + for _, hlc := range candi { + for _, hli := range intersects { + if hli.row != hlc.row && + hlc.row - hli.row > 1 { + // ignore if not consecutive + continue; + } + if reflect.DeepEqual( + hlc.points, hli.points) { + //fmt.Println( base, ":", hlc, "~~", hli ) + // keep intersection + inters = append(inters, hlc) + r_cp := rows + c_cp := hli.points + rect := Rect { r_cp,c_cp } + narea := rect.Area() + if narea == 1 { + // skip a point + continue + } + // compare with largest + // and update largest + // if needed + if largestArea < narea { + largestArea = + narea + largestRects = + []Rect{rect} + //fmt.Println( "new largest", largestRects) + } else if largestArea == + narea { + largestRects = append( + largestRects, + rect ) + //fmt.Println( "update largest", largestRects) + } + } else { + // remove from intersec. + } + } + if len(inters) == 0 { + break candidates // no need to go further + } else { + copy(intersects, inters) + } + } + } + } + return largestRects +} + +func main() { + reader := bufio.NewReader(os.Stdin) + matrixString, _ := reader.ReadString('') + pointsAtRows := getPointsFromMatrixLines(matrixString) + hlinesAtRows := getHorizLinesFromPoints(pointsAtRows) + //fmt.Println( hlinesAtRows ) + largestRects := findLargestRectanglesFromHorizLines(hlinesAtRows) + + if len(largestRects) == 0 { + fmt.Println("0 as no rectangle found") + os.Exit(1) + } else { + fmt.Fprintln(os.Stderr, "Area:", largestRects[0].Area()) + for _, rect := range largestRects { + y, x := rect.NorthWest() + fmt.Fprintf(os.Stderr, "At: (r:%d,c:%d)\n", y, x) + for range rect.rows { + fmt.Print("1") + for range rect.cols[1:] { + fmt.Print(" 1") + } + fmt.Println("") + } + } + } + os.Exit(0) +} diff --git a/challenge-087/jeongoon/perl/ch-1.pl b/challenge-087/jeongoon/perl/ch-1.pl new file mode 100644 index 0000000000..3de5d2bc6b --- /dev/null +++ b/challenge-087/jeongoon/perl/ch-1.pl @@ -0,0 +1,41 @@ +#!/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 v5.26; + +# note: no sanity check !! +my @sorted = sort { $a <=> $b } @ARGV; +push @sorted, $sorted[-1]+2; # dummy + +my @longest_seq_list = (); +my $longest_size = 0; + +my $prev = shift @sorted; +my @curr_seq = ($prev); + +for my $curr (@sorted) { + if ( $curr - $prev == 1 ) { + push @curr_seq, ($curr); # concat. current seq + } elsif ( $curr == $prev ) { # skip + } else { # update longest + my $curr_size = scalar @curr_seq; + if ( $curr_size > $longest_size ) { + $longest_size = $curr_size; + @longest_seq_list = ( [ @curr_seq ] ); + } elsif ( $curr_size == $longest_size ) { + push @longest_seq_list, [ @curr_seq ]; + } + @curr_seq = ($curr); + } + $prev = $curr; +} + +if ( $longest_size > 0 ) { + say "longest size: ".$longest_size; + say "total ".(scalar @longest_seq_list)." sequencies found."; + for my $seq (@longest_seq_list) { + say "[", join(", ", @$seq), "]"; + } +} diff --git a/challenge-087/jeongoon/perl/ch-2.pl b/challenge-087/jeongoon/perl/ch-2.pl new file mode 100644 index 0000000000..ded784bfef --- /dev/null +++ b/challenge-087/jeongoon/perl/ch-2.pl @@ -0,0 +1,232 @@ +#!/usr/bin/env perl +# -*- Mode: cperl; cperl-indent-level:4 tab-width: 8; indent-tabs-mode: nil -*- +# -*- coding: utf-8 -*- + +# tested with: +# echo "[000111][111111][001001][001111][001111] | sbcl --script ch-2.lsp +# [000111] +# [111111] +# [001001] +# [001111] +# [001111] + +# modified from ch-084/ch-2.pl +use strict; use warnings; +use v5.26; + +use Class::Struct; + +struct PointInMat => [ row => '$', col => '$' ]; +struct HLineInMat => [ row => '$', begin => '$', end => '$' ]; +struct RectInMat => [ row_NW => '$', col_NW => '$', + row_SE => '$', col_SE => '$' ]; +struct RunAndShow => [ Run => '$', Show => '$' ]; +struct ShowDetails => [ name => '$', attrs => '@' ]; + +sub rectArea ($) { + my $rect = shift; + + ($rect->row_SE - $rect->row_NW + 1) + * + ($rect->col_SE - $rect->col_NW + 1) +} + +sub readContents { + local $/ = ''; # slurp + my $contents = <STDIN> // ''; + $contents +} + +# return as an ArrayRef of ArrayRef of PointInMat (grouped by row number) +sub getPointsAtEachRows ($) { + my $raw_string = shift; + my @lines = split( /]\s*/, $raw_string ); + + [ map { + my ( $r, $c ) = ( $_, 0 ); + + [ map { + if ( $_ eq '1' ) { + PointInMat->new( row => $r, col => $c++ ); + } elsif ( $_ eq '0' ) { + ++$c; () + } else { + () + } + } (split "", $lines[$_]) # charaters + ] # group by row + } 0 .. $#lines ]; # return as ArrayRef +} + +sub showSomethingInGroup ($$$) { + my ( $listOflist_ref, $spec, $flattening, $nth ) = ( @_[0..2], 1 ); + my @list; + if ( $flattening // 1 ) { + @list = map { @$_ } @$listOflist_ref; # flatten + } + else { + @list = @$listOflist_ref; + } + + my $listLen = scalar @list; + my $ww = length $listLen; # (w)ord (w)idth: for printf() + say "$listLen ".($spec->name)."(s) found:"; + for my $sth (@list) { + printf("%0*d", $ww, $nth++); + say ": (".join(", ", map { "$_:".($sth->$_()) } @{$spec->attrs} ).")"; + } + say ""; +} + +sub showPoints ($) { + @_ = ( $_[0], # data (ArrayRef) + ShowDetails->new( name => 'points', + attrs => [qw(row col)] ), + 1 # flattening? yes + ); + goto &showSomethingInGroup +} + +# return as an ArrayRef of ArrayRef of HLineInMat (grouped by row) +sub getHorizLinesFromPoints ($) { + my $pts_at_all_rows = shift; + [ map { + my $pts_at_the_same_row = $_; + my $prev = shift @$pts_at_the_same_row; + my @line_so_far = ($prev->col); + my $row = $prev->row; + + push @$pts_at_the_same_row, + PointInMat->new( row => $row, # add dummy + col => $$pts_at_the_same_row[-1]->col + 2 ); + my @hline; + + for my $curr ( @$pts_at_the_same_row ) { + if ( $curr->col - $prev->col == 1 ) { + push @line_so_far, $curr->col + } + elsif ( scalar @line_so_far > 0 ) { + push @hline, + HLineInMat->new( row => $row, + begin => $line_so_far[0], + end => $line_so_far[-1] ); + @line_so_far = ( $curr->col ); + } + $prev = $curr; + } + # return all possible combinations of sub lines + # single points are inclusive + my @sub_hline; + while (@hline) { + my $sub_hline = shift @hline; + push @sub_hline, $sub_hline; # itself + my @range = $sub_hline->begin .. $sub_hline->end; + for my $nsel ( reverse 1 .. $#range ) { # from larger to smaller + for my $offset ( 0.. scalar @range - $nsel ) { + push @sub_hline, + HLineInMat->new( row => $sub_hline->row, + begin => $range[$offset], + end => $range[$offset+$nsel-1] ) + } + } + } + [ @sub_hline ]; + } @$pts_at_all_rows ] +} + +sub showHorizLines ($) { + @_ = ( $_[0], + ShowDetails->new( name => 'horiz line(point inclusive)', + attrs => [qw(row begin end)] ), + 1 # flattening? yes + ); + goto &showSomethingInGroup +} + +# take ArrayRef of ArrayRef of HLine +sub findLargestRectanglesFromHorizLines ($) { + my @hlines_grouped_by_row = @{$_[0]}; # copy + my @largestRectangles = (); + my $largestArea = 0; + + # reducing rows: 1,2,3,4 -> 2,3,4 -> 3,4 -> 4 + for ( my $base = 0 ; scalar @hlines_grouped_by_row > 0; + shift @hlines_grouped_by_row, ++$base ) { + # initial intersection is same as first row + my %intersects = map { + $_->begin."~".$_->end => 1 # "begin~end" as a key + } @{$hlines_grouped_by_row[0]}; + + for my $candi_row (@hlines_grouped_by_row) { + my %new_inters = (); + last if scalar %intersects == 0; # no need to go further + for my $hline (@$candi_row) { + my $key = $hline->begin."~".$hline->end; + + if ( exists $intersects{$key} ) { + $new_inters{$key} = 1; + my $rect = RectInMat->new( + row_NW => $base, + row_SE => $hline->row, + col_NW => $hline->begin, + col_SE => $hline->end ); + + # check largest + my $new_area = rectArea( $rect ); + if ( $largestArea < $new_area ) { + $largestArea = $new_area; + @largestRectangles = ( $rect ); + } + elsif ( $largestArea == $new_area ) { + push @largestRectangles, $rect; + } + } + else { + } + } + %intersects = %new_inters; + } + } + [ @largestRectangles ] +} + +# return as an ArrayRef of PointInMat +sub showRects ($) { + @_ = ( $_[0], + ShowDetails->new( name => 'rectangles', + attrs => [ qw(row_NW col_NW row_SE col_SE) ] ), + 0 # flattening? no + ); + goto &showSomethingInGroup +} + +my @solutionComposed = + ( + # pairs of function, logger in top -> bottom in the same order of exe. + RunAndShow->new( Run => \&readContents, Show => sub { say @_ } ), + # ==> + RunAndShow->new( Run => \&getPointsAtEachRows, + Show => \&showPoints ), + # ==> + RunAndShow->new( Run => \&getHorizLinesFromPoints, + Show => \&showHorizLines ), + # ==> + RunAndShow->new( Run => \&findLargestRectanglesFromHorizLines, + Show => \&showRects ), + ); + +our $debug = 0; +my $ball; + +my @progress = map { + $ball = $_->Run->($ball); + if ( $debug ) { $_->Show->($ball); } + $ball +} @solutionComposed; + +say "Output: "; +for my $rect (@{$progress[-1]}) { + say "At (r:".$rect->row_NW.", c:".$rect->col_NW.")"; + say join(" ", (1) x ($rect->col_SE - $rect->col_NW + 1)) + for (0 .. $rect->row_SE - $rect->row_NW); +} diff --git a/challenge-087/jeongoon/raku/ch-1.raku b/challenge-087/jeongoon/raku/ch-1.raku new file mode 100644 index 0000000000..2ae8ef3e6b --- /dev/null +++ b/challenge-087/jeongoon/raku/ch-1.raku @@ -0,0 +1,22 @@ +#!/usr/bin/env raku +# -*- Mode: Raku; indent-tabs-mode: nil; coding: utf-8 -*- +# vim: set et ts=4 sw=4: + +use v6.d; + +# tested with: +# raku ch-1.raku -3 1 3 2 -2 4 6 7 -1 -4 +# [-4 -3 -2 -1] +# [1 2 3 4] + +unit sub MAIN (*@n where { @n ~~ Int, @n.elems > 0 } ); +(@n.sort.map({[$_]})). +produce( -> \a, \b { + b.first - a.tail == 1 + ?? a.append(b.first).clone + !! b.clone + } ). +classify( {.elems} ). +max. +value. +map( *.say ); diff --git a/challenge-087/jeongoon/raku/ch-2.raku b/challenge-087/jeongoon/raku/ch-2.raku new file mode 100644 index 0000000000..432ee6750c --- /dev/null +++ b/challenge-087/jeongoon/raku/ch-2.raku @@ -0,0 +1,113 @@ +#!/usr/bin/env raku +# -*- Mode: Raku; indent-tabs-mode: nil; coding: utf-8 -*- +# vim: set et ts=4 sw=4: + +# tested with: +# echo "[000100][111000][001001][111110][111110]" | raku ch-2.raku +# -> example #1 +# echo "[100][010][000]" | raku ch-2.raku +# -> 0 +# echo "[10110][11110][01110][01110][10110]" | raku ch-2.raku +#[1 0 ▨ ▨ 0] +#[1 1 ▨ ▨ 0] +#[0 1 ▨ ▨ 0] +#[0 1 ▨ ▨ 0] +#[1 0 ▨ ▨ 0] + + +use v6.d; + +sub USAGE { + say "Usage:"; + say ' echo -e "[000100][111000][001001][111110][111110]" | raku ch-2.raku',"\n"; + say "# or input ending with EOF (Ctrl-D or Ctrl-Z)"; + say "# you might need to filter the STDERR to get only answer."; +} + +unit sub MAIN; + +$*ERR.say("Input: (Ctrl-D or Ctrl-Z to finish to input.)"); +my @lines = $*IN.split(/"]" \s* "\n"* | "\n"/); # split rows by newline or `]' + +my @matrix = +@lines.elems < 1 # need one row at least +?? ( + <1 0 1 0 1 0>, + <0 1 0 1 0 1>, + <0 0 1 0 0 1>, + <1 1 1 1 1 0>, + <1 1 1 1 1 0>, ) # example #1 + +!! @lines. +map( -> $ln { next if $ln eq ""; # skip empty line + S:g/ '[' || \s+ //.comb.cache # remove unused chars. + with $ln } ); + +# confirm input +$*ERR.say(.Array) for @matrix; +$*ERR.say; + +@matrix andthen .kv.map( + -> $ri, $rw { + # find all lines which has consecutive element of "1" + ## a. find cells has value of 1 + $rw.pairs.grep( { .value eq 1 }, :k ).Slip. + ## b. make combinations from 1 to elems + combinations( 1..* ). # one column is *maybe* okay + # except when the column have + # one row (-> point) + ## c. grep only consecutive points + map( -> $cmb { + $cmb.rotor( 2 => -1 ). + map({ [-] .reverse }). # distance between two points + all == 1 # are all equal to one. + ## d. as ( points array , row index ) + ?? ( $cmb, $ri ) + !! Empty } ).Array.Slip + + } ). + +classify( {.[0].Str}, :as{ .[1] } |
