Merge pull request #7966 from LubosKolouch/master

Challenge 214 LK Perl Python

17 files changed, 404 insertions, 0 deletions

diff --git a/challenge-070/lubos-kolouch/bash/ch-2.sh b/challenge-070/lubos-kolouch/bash/ch-2.sh
new file mode 100644
index 0000000000..de8c2e9c84
--- /dev/null
+++ b/challenge-070/lubos-kolouch/bash/ch-2.sh
@@ -0,0 +1,20 @@
+#!/bin/bash
+
+N=4
+gray_code=("0" "1")
+
+for ((i=2; i<=N; i++)); do
+    rev_gray_code=("${gray_code[@]}")
+    for ((j=${#rev_gray_code[@]}-1; j>=0; j--)); do
+        rev_gray_code[j]="1${rev_gray_code[j]}"
+    done
+    for ((j=0; j<${#gray_code[@]}; j++)); do
+        gray_code[j]="0${gray_code[j]}"
+    done
+    gray_code+=("${rev_gray_code[@]}")
+done
+
+for x in "${gray_code[@]}"; do
+    echo -n "$((2#$x)) "
+done
+echo
diff --git a/challenge-070/lubos-kolouch/cpp/ch-2.cpp b/challenge-070/lubos-kolouch/cpp/ch-2.cpp
new file mode 100644
index 0000000000..2e2bd18cdd
--- /dev/null
+++ b/challenge-070/lubos-kolouch/cpp/ch-2.cpp
@@ -0,0 +1,23 @@
+#include <iostream>
+#include <vector>
+#include <string>
+#include <algorithm>
+
+int main() {
+    int N = 4;
+    std::vector<std::string> grayCode = {"0", "1"};
+
+    for (int i = 2; i <= N; i++) {
+        std::vector<std::string> revGrayCode(grayCode.rbegin(), grayCode.rend());
+        for (auto &x : grayCode) x = '0' + x;
+        for (auto &x : revGrayCode) x = '1' + x;
+        grayCode.insert(grayCode.end(), revGrayCode.begin(), revGrayCode.end());
+    }
+
+    for (const auto &x : grayCode) {
+        std::cout << std::stoi(x, nullptr, 2) << ' ';
+    }
+    std::cout << '\n';
+
+    return 0;
+}
diff --git a/challenge-070/lubos-kolouch/go/ch-2.go b/challenge-070/lubos-kolouch/go/ch-2.go
new file mode 100644
index 0000000000..95739f95ab
--- /dev/null
+++ b/challenge-070/lubos-kolouch/go/ch-2.go
@@ -0,0 +1,32 @@
+package main
+
+import (
+    "fmt"
+    "strconv"
+)
+
+func main() {
+    N := 4
+    grayCode := []string{"0", "1"}
+
+    for i := 2; i <= N; i++ {
+        revGrayCode := make([]string, len(grayCode))
+        copy(revGrayCode, grayCode)
+        for j := 0; j < len(revGrayCode)/2; j++ {
+            revGrayCode[j], revGrayCode[len(revGrayCode)-j-1] = revGrayCode[len(revGrayCode)-j-1], revGrayCode[j]
+        }
+        for j := 0; j < len(grayCode); j++ {
+            grayCode[j] = "0" + grayCode[j]
+        }
+        for j := 0; j < len(revGrayCode); j++ {
+            revGrayCode[j] = "1" + revGrayCode[j]
+        }
+        grayCode = append(grayCode, revGrayCode...)
+    }
+
+    for _, x := range grayCode {
+        n, _ := strconv.ParseInt(x, 2, 64)
+        fmt.Print(n, " ")
+    }
+    fmt.Println()
+}
diff --git a/challenge-070/lubos-kolouch/java/ch-2.java b/challenge-070/lubos-kolouch/java/ch-2.java
new file mode 100644
index 0000000000..be3c4a7ca3
--- /dev/null
+++ b/challenge-070/lubos-kolouch/java/ch-2.java
@@ -0,0 +1,25 @@
+public class Main {
+    public static void main(String[] args) {
+        int N = 4;
+        ArrayList<String> grayCode = new ArrayList<>();
+        grayCode.add("0");
+        grayCode.add("1");
+
+        for (int i = 2; i <= N; i++) {
+            ArrayList<String> revGrayCode = new ArrayList<>(grayCode);
+            Collections.reverse(revGrayCode);
+            for (int j = 0; j < grayCode.size(); j++) {
+                grayCode.set(j, "0" + grayCode.get(j));
+            }
+            for (int j = 0; j < revGrayCode.size(); j++) {
+                revGrayCode.set(j, "1" + revGrayCode.get(j));
+            }
+            grayCode.addAll(revGrayCode);
+        }
+
+        for (String x : grayCode) {
+            System.out.print(Integer.parseInt(x, 2) + " ");
+        }
+        System.out.println();
+    }
+}
diff --git a/challenge-070/lubos-kolouch/javascript/ch-2.js b/challenge-070/lubos-kolouch/javascript/ch-2.js
new file mode 100644
index 0000000000..44602ebfca
--- /dev/null
+++ b/challenge-070/lubos-kolouch/javascript/ch-2.js
@@ -0,0 +1,12 @@
+const N = 4;
+let grayCode = ['0', '1'];
+
+for (let i = 2; i <= N; i++) {
+    let revGrayCode = grayCode.slice().reverse();
+    grayCode = grayCode.map(x => '0' + x);
+    revGrayCode = revGrayCode.map(x => '1' + x);
+    grayCode = grayCode.concat(revGrayCode);
+}
+
+grayCode = grayCode.map(x => parseInt(x, 2));
+console.log(grayCode);
diff --git a/challenge-070/lubos-kolouch/perl/ch-1.pl b/challenge-070/lubos-kolouch/perl/ch-1.pl
new file mode 100644
index 0000000000..bc18e6f7fa
--- /dev/null
+++ b/challenge-070/lubos-kolouch/perl/ch-1.pl
@@ -0,0 +1,16 @@
+#!/usr/bin/perl
+use strict;
+use warnings;
+
+my $S = 'perlandraku';
+my $C = 3;
+my $O = 4;
+my $N = length($S);
+
+for my $i ( 1 .. $C ) {
+    my $x = $i % $N;
+    my $y = ( $i + $O ) % $N;
+    substr( $S, $x, 1, substr( $S, $y, 1, substr( $S, $x, 1 ) ) );
+}
+
+print "$S\n";
diff --git a/challenge-070/lubos-kolouch/perl/ch-2.pl b/challenge-070/lubos-kolouch/perl/ch-2.pl
new file mode 100644
index 0000000000..a368fca1ba
--- /dev/null
+++ b/challenge-070/lubos-kolouch/perl/ch-2.pl
@@ -0,0 +1,16 @@
+#!/usr/bin/perl
+use strict;
+use warnings;
+
+my $N         = 4;
+my @gray_code = ( 0, 1 );
+
+for my $i ( 2 .. $N ) {
+    my @rev_gray_code = reverse @gray_code;
+    @gray_code     = map { "0$_" } @gray_code;
+    @rev_gray_code = map { "1$_" } @rev_gray_code;
+    push @gray_code, @rev_gray_code;
+}
+
+@gray_code = map { oct("0b$_") } @gray_code;
+print join( ", ", @gray_code ), "\n";
diff --git a/challenge-070/lubos-kolouch/php/ch-2.php b/challenge-070/lubos-kolouch/php/ch-2.php
new file mode 100644
index 0000000000..b85f40040b
--- /dev/null
+++ b/challenge-070/lubos-kolouch/php/ch-2.php
@@ -0,0 +1,16 @@
+<?php
+
+$N = 4;
+$grayCode = ['0', '1'];
+
+for ($i = 2; $i <= $N; $i++) {
+    $revGrayCode = array_reverse($grayCode);
+    $grayCode = array_map(function ($x) { return '0' . $x; }, $grayCode);
+    $revGrayCode = array_map(function ($x) { return '1' . $x; }, $revGrayCode);
+    $grayCode = array_merge($grayCode, $revGrayCode);
+}
+
+$grayCode = array_map(function ($x) { return bindec($x); }, $grayCode);
+echo implode(', ', $grayCode), "\n";
+
+?>
diff --git a/challenge-070/lubos-kolouch/python/ch-1.py b/challenge-070/lubos-kolouch/python/ch-1.py
new file mode 100644
index 0000000000..21cbaaff44
--- /dev/null
+++ b/challenge-070/lubos-kolouch/python/ch-1.py
@@ -0,0 +1,16 @@
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+S = "perlandraku"
+C = 3
+O = 4
+N = len(S)
+S = list(S)
+
+for i in range(1, C + 1):
+    x = i % N
+    y = (i + O) % N
+    S[x], S[y] = S[y], S[x]
+
+S = "".join(S)
+print(S)
diff --git a/challenge-070/lubos-kolouch/python/ch-2.py b/challenge-070/lubos-kolouch/python/ch-2.py
new file mode 100644
index 0000000000..48ab086970
--- /dev/null
+++ b/challenge-070/lubos-kolouch/python/ch-2.py
@@ -0,0 +1,14 @@
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+N = 4
+gray_code = ["0", "1"]
+
+for i in range(2, N + 1):
+    rev_gray_code = gray_code[::-1]
+    gray_code = ["0" + x for x in gray_code]
+    rev_gray_code = ["1" + x for x in rev_gray_code]
+    gray_code += rev_gray_code
+
+gray_code = [int(x, 2) for x in gray_code]
+print(gray_code)
diff --git a/challenge-070/lubos-kolouch/raku/ch-2.raku b/challenge-070/lubos-kolouch/raku/ch-2.raku
new file mode 100644
index 0000000000..2f56076cd0
--- /dev/null
+++ b/challenge-070/lubos-kolouch/raku/ch-2.raku
@@ -0,0 +1,12 @@
+my $N = 4;
+my @gray-code = <0 1>;
+
+for 2..$N -> $i {
+    my @rev-gray-code = @gray-code.reverse;
+    @gray-code = @gray-code.map: { "0$_" };
+    @rev-gray-code = @rev-gray-code.map: { "1$_" };
+    @gray-code.append: @rev-gray-code;
+}
+
+@gray-code .= map: { :2($_) };
+say @gray-code.join(', ');
diff --git a/challenge-070/lubos-kolouch/ruby/ch-2.rb b/challenge-070/lubos-kolouch/ruby/ch-2.rb
new file mode 100644
index 0000000000..5144b5f350
--- /dev/null
+++ b/challenge-070/lubos-kolouch/ruby/ch-2.rb
@@ -0,0 +1,12 @@
+N = 4
+gray_code = ['0', '1']
+
+(2..N).each do |i|
+    rev_gray_code = gray_code.reverse
+    gray_code = gray_code.map { |x| '0' + x }
+    rev_gray_code = rev_gray_code.map { |x| '1' + x }
+    gray_code += rev_gray_code
+end
+
+gray_code = gray_code.map { |x| x.to_i(2) }
+puts gray_code.join(', ')
diff --git a/challenge-070/lubos-kolouch/vba/ch-2.vb b/challenge-070/lubos-kolouch/vba/ch-2.vb
new file mode 100644
index 0000000000..5a34c51940
--- /dev/null
+++ b/challenge-070/lubos-kolouch/vba/ch-2.vb
@@ -0,0 +1,26 @@
+Sub GrayCode()
+    Dim N As Integer
+    N = 4
+    Dim grayCode As New Collection
+    grayCode.Add "0"
+    grayCode.Add "1"
+
+    Dim i As Integer
+    For i = 2 To N
+        Dim revGrayCode As New Collection
+        Dim j As Integer
+        For j = grayCode.Count To 1 Step -1
+            revGrayCode.Add "1" & grayCode(j)
+        Next j
+        For j = 1 To grayCode.Count
+            grayCode(j) = "0" & grayCode(j)
+        Next j
+        For j = 1 To revGrayCode.Count
+            grayCode.Add revGrayCode(j)
+        Next j
+    Next i
+
+    For i = 1 To grayCode.Count
+        Debug.Print CStr(CLng("&B" & grayCode(i))) & " ";
+    Next i
+End Sub
diff --git a/challenge-214/lubos-kolouch/perl/ch-1.pl b/challenge-214/lubos-kolouch/perl/ch-1.pl
new file mode 100644
index 0000000000..c0b67d75eb
--- /dev/null
+++ b/challenge-214/lubos-kolouch/perl/ch-1.pl
@@ -0,0 +1,44 @@
+#!/usr/bin/perl
+use strict;
+use warnings;
+use Test::More;
+
+sub rank_scores {
+    my @scores = @_;
+    my @sorted_scores = sort { $b <=> $a } @scores;
+    my %ranks;
+    my $rank = 1;
+    for my $i (0 .. $#sorted_scores) {
+        if ($i > 0 && $sorted_scores[$i] == $sorted_scores[$i - 1]) {
+            $ranks{$sorted_scores[$i]} = $ranks{$sorted_scores[$i - 1]};
+        } else {
+            $ranks{$sorted_scores[$i]} = $rank;
+        }
+        $rank++;
+    }
+    my @output;
+    for my $score (@scores) {
+        if ($ranks{$score} == 1) {
+            push @output, 'G';
+        } elsif ($ranks{$score} == 2) {
+            push @output, 'S';
+        } elsif ($ranks{$score} == 3) {
+            push @output, 'B';
+        } else {
+            push @output, $ranks{$score};
+        }
+    }
+    return \@output;
+}
+
+my @test_cases = (
+    { input => [1,2,4,3,5], output => ['5','4','S','B','G'] },
+    { input => [8,5,6,7,4], output => ['G','4','B','S','5'] },
+    { input => [3,5,4,2], output => ['B','G','S','4'] },
+    { input => [2,5,2,1,7,5,1], output => ['4','S','4','6','G','S','6'] },
+);
+
+for my $test_case (@test_cases) {
+    is_deeply(rank_scores(@{ $test_case->{input} }), $test_case->{output});
+}
+
diff --git a/challenge-214/lubos-kolouch/perl/ch-2.pl b/challenge-214/lubos-kolouch/perl/ch-2.pl
new file mode 100644
index 0000000000..5314086d5e
--- /dev/null
+++ b/challenge-214/lubos-kolouch/perl/ch-2.pl
@@ -0,0 +1,46 @@
+use strict;
+use warnings;
+
+sub max_score {
+    my @numbers = @_;
+    return helper(\@numbers, {});
+}
+
+sub helper {
+    my ($numbers, $memo) = @_;
+
+    return 0 if scalar(@$numbers) == 0;
+
+    my $key = join(',', @$numbers);
+    return $memo->{$key} if exists $memo->{$key};
+
+    my $max_score = 0;
+    my $i = 0;
+    while ($i < scalar(@$numbers)) {
+        my $j = $i;
+        while ($j < scalar(@$numbers) && $numbers->[$j] == $numbers->[$i]) {
+            $j++;
+        }
+
+        my $length = $j - $i;
+        my @next_numbers = (@$numbers[0 .. $i - 1], @$numbers[$j .. scalar(@$numbers) - 1]);
+        my $score = $length * $length + helper(\@next_numbers, $memo);
+        $max_score = $max_score > $score ? $max_score : $score;
+        $i = $j;
+    }
+
+    $memo->{$key} = $max_score;
+    return $max_score;
+}
+
+# Test cases
+my @numbers1 = (2, 4, 3, 3, 3, 4, 5, 4, 2);
+my @numbers2 = (1, 2, 2, 2, 2, 1);
+my @numbers3 = (1);
+my @numbers4 = (2, 2, 2, 1, 1, 2, 2, 2);
+
+print max_score(@numbers1), "\n";  # Output: 23
+print max_score(@numbers2), "\n";  # Output: 20
+print max_score(@numbers3), "\n";  # Output: 1
+print max_score(@numbers4), "\n";  # Output: 40
+
diff --git a/challenge-214/lubos-kolouch/python/ch-1.py b/challenge-214/lubos-kolouch/python/ch-1.py
new file mode 100644
index 0000000000..710c81ea42
--- /dev/null
+++ b/challenge-214/lubos-kolouch/python/ch-1.py
@@ -0,0 +1,31 @@
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+from typing import List
+
+
+def rank_scores(scores: List[int]) -> List[str]:
+    sorted_scores = sorted(scores, reverse=True)
+    ranks = {}
+    rank = 1
+    for i in range(len(sorted_scores)):
+        if i > 0 and sorted_scores[i] == sorted_scores[i - 1]:
+            ranks[sorted_scores[i]] = ranks[sorted_scores[i - 1]]
+        else:
+            ranks[sorted_scores[i]] = rank
+        rank += 1
+    output = []
+    for score in scores:
+        if ranks[score] == 1:
+            output.append('G')
+        elif ranks[score] == 2:
+            output.append('S')
+        elif ranks[score] == 3:
+            output.append('B')
+        else:
+            output.append(str(ranks[score]))
+    return output
+
+
+scores = [1, 2, 4, 3, 5]
+result = rank_scores(scores)
+print(result)
diff --git a/challenge-214/lubos-kolouch/python/ch-2.py b/challenge-214/lubos-kolouch/python/ch-2.py
new file mode 100644
index 0000000000..72d7207b50
--- /dev/null
+++ b/challenge-214/lubos-kolouch/python/ch-2.py
@@ -0,0 +1,43 @@
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+
+def max_score(numbers):
+
+    def helper(numbers, memo):
+        if not numbers:
+            return 0
+
+        key = tuple(numbers)
+        if key in memo:
+            return memo[key]
+
+        max_score = 0
+        i = 0
+        while i < len(numbers):
+            j = i
+            while j < len(numbers) and numbers[j] == numbers[i]:
+                j += 1
+
+            length = j - i
+            next_numbers = numbers[:i] + numbers[j:]
+            score = length * length + helper(next_numbers, memo)
+            max_score = max(max_score, score)
+            i = j
+
+        memo[key] = max_score
+        return max_score
+
+    return helper(numbers, {})
+
+
+# Test cases
+numbers1 = [2, 4, 3, 3, 3, 4, 5, 4, 2]
+numbers2 = [1, 2, 2, 2, 2, 1]
+numbers3 = [1]
+numbers4 = [2, 2, 2, 1, 1, 2, 2, 2]
+
+print(max_score(numbers1))  # Output: 23
+print(max_score(numbers2))  # Output: 20
+print(max_score(numbers3))  # Output: 1
+print(max_score(numbers4))  # Output: 40