Merge pull request #12969 from deadmarshal/TWC346

TWC346

9 files changed, 298 insertions, 0 deletions

diff --git a/challenge-346/deadmarshal/blog.txt b/challenge-346/deadmarshal/blog.txt
new file mode 100644
index 0000000000..49b2fe825f
--- /dev/null
+++ b/challenge-346/deadmarshal/blog.txt
@@ -0,0 +1 @@
+https://deadmarshal.blogspot.com/2025/11/twc346.html
diff --git a/challenge-346/deadmarshal/elixir/ch1.ex b/challenge-346/deadmarshal/elixir/ch1.ex
new file mode 100644
index 0000000000..d8bb0982a8
--- /dev/null
+++ b/challenge-346/deadmarshal/elixir/ch1.ex
@@ -0,0 +1,36 @@
+defmodule Ch1 do
+  @spec longest_parenthesis(s :: String.t()) :: integer
+  def longest_parenthesis(s) do
+    s
+    |> String.graphemes()
+    |> dp([], 0)
+  end
+
+  defp dp([], _, result), do: result
+
+  defp dp(["(" | tail], stack, result) do
+    dp(tail, [0 | stack], result)
+  end
+
+  defp dp([")" | tail], stack, result) do
+    {new_stack, new_result} = pop_until(stack, [])
+
+    dp(tail, new_stack, max(result, new_result))
+  end
+
+  defp pop_until([], _), do: {[], 0}
+
+  defp pop_until([0 | tail], rest) do
+    n = List.first(tail)
+    n = if n, do: n, else: 0
+    tail = if n > 0, do: tl(tail), else: tail
+    result = Enum.sum(rest) + n + 2
+    
+    {[result | tail], result}
+  end
+
+  defp pop_until([h | tail], rest) do
+    pop_until(tail, [h | rest])
+  end
+end
+
diff --git a/challenge-346/deadmarshal/elixir/ch2.ex b/challenge-346/deadmarshal/elixir/ch2.ex
new file mode 100644
index 0000000000..f44e7728e7
--- /dev/null
+++ b/challenge-346/deadmarshal/elixir/ch2.ex
@@ -0,0 +1,38 @@
+defmodule Ch2 do
+  @spec magic_expression(num :: String.t(),
+    target :: integer) :: [String.t()]
+  def magic_expression(num,target) do
+    dfs([],num,0,String.length(num),0,0,target,[])
+  end
+
+  defp dfs(ans, num, i, len, acc, pre, target, exp) do
+    if i == len do
+      if acc == target do
+        [exp |> Enum.reverse() |> Enum.join() | ans]
+      else
+        ans
+      end
+    else
+      i..(len - 1)
+      |> Enum.reduce_while(ans, fn j, ans ->
+        if j > i && String.at(num, i) == "0" do
+          {:halt, ans}
+        else
+          e = String.slice(num, i..j)
+          n = String.to_integer(e)
+
+          if i == 0 do
+            {:cont, dfs(ans, num, j + 1, len, n, n, target, [e | exp])}
+          else
+            {:cont,
+             ans
+             |> dfs(num, j + 1, len, acc + n, n, target, [e, "+" | exp])
+             |> dfs(num, j + 1, len, acc - n, -n, target, [e, "-" | exp])
+             |> dfs(num, j + 1, len, acc - pre + pre * n, pre * n, target, [e, "*" | exp])}
+          end
+        end
+      end)
+    end
+  end
+end
+
diff --git a/challenge-346/deadmarshal/go/ch1.go b/challenge-346/deadmarshal/go/ch1.go
new file mode 100644
index 0000000000..682f07ad3f
--- /dev/null
+++ b/challenge-346/deadmarshal/go/ch1.go
@@ -0,0 +1,43 @@
+package main
+
+import (
+	"fmt"
+)
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}
+
+func longestParenthesis(s string) int {
+	stk := []int{}
+	start, res := 0, 0
+	for i, c := range s {
+		if c == '(' {
+			stk = append(stk, i)
+		} else {
+			if len(stk) == 0 {
+				start = i + 1
+			} else {
+				stk = stk[:len(stk)-1]
+				temp := i - start + 1
+				if len(stk) == 0 {
+					res = max(res, temp)
+				} else {
+					res = max(res, i-stk[len(stk)-1])
+				}
+			}
+		}
+	}
+	return res
+}
+
+func main() {
+	fmt.Println(longestParenthesis("(()())"))
+	fmt.Println(longestParenthesis(")()())"))
+	fmt.Println(longestParenthesis("((()))()(((()"))
+	fmt.Println(longestParenthesis("))))((()("))
+	fmt.Println(longestParenthesis("()(()"))
+}
diff --git a/challenge-346/deadmarshal/go/ch2.go b/challenge-346/deadmarshal/go/ch2.go
new file mode 100644
index 0000000000..ff6592c241
--- /dev/null
+++ b/challenge-346/deadmarshal/go/ch2.go
@@ -0,0 +1,45 @@
+package main
+
+import (
+	"fmt"
+	"strconv"
+)
+
+func magicExpression(num string, target int) []string {
+	out := []string{}
+	var backtrack func(string, string, int, int)
+	backtrack = func(num, prefix string, val, last int) {
+		if len(num) == 0 {
+			if val == target {
+				out = append(out, prefix)
+			}
+			return
+		}
+		for i := 1; i <= len(num); i++ {
+			str := num[:i]
+			digit, _ := strconv.Atoi(str)
+			if num[0] == '0' && i != 1 {
+				continue
+			}
+
+			if prefix == "" {
+				backtrack(num[i:], str, digit, digit)
+			} else {
+				backtrack(num[i:], prefix+"+"+str, val+digit, digit)
+				backtrack(num[i:], prefix+"-"+str, val-digit, -digit)
+				backtrack(num[i:], prefix+"*"+str, val-last+last*digit,
+					last*digit)
+			}
+		}
+	}
+	backtrack(num, "", 0, 0)
+	return out
+}
+
+func main() {
+	fmt.Println(magicExpression("123", 6))
+	fmt.Println(magicExpression("105", 5))
+	fmt.Println(magicExpression("232", 8))
+	fmt.Println(magicExpression("1324", 10))
+	fmt.Println(magicExpression("1001", 2))
+}
diff --git a/challenge-346/deadmarshal/java/Ch1.java b/challenge-346/deadmarshal/java/Ch1.java
new file mode 100644
index 0000000000..947b1f411e
--- /dev/null
+++ b/challenge-346/deadmarshal/java/Ch1.java
@@ -0,0 +1,27 @@
+import java.util.Stack;
+
+public class Ch1 {
+  public static void main(String[] args) {
+    System.out.println(longest_parenthesis("(()())"));
+    System.out.println(longest_parenthesis(")()())"));
+    System.out.println(longest_parenthesis("((()))()(((()"));
+    System.out.println(longest_parenthesis("))))((()("));
+    System.out.println(longest_parenthesis("()(()"));
+  }
+
+  private static int longest_parenthesis(String s) {
+    Stack<Integer> stk = new Stack<>();
+    stk.push(-1);
+    int maxlen = 0;
+    for(int i = 0; i < s.length(); ++i) {
+      if(s.charAt(i) == '(') stk.push(i);
+      else {
+	stk.pop();
+	if(stk.isEmpty()) stk.push(i);
+	else maxlen = Math.max(maxlen,i-stk.peek());
+      }
+    }
+    return maxlen;
+  }
+}
+
diff --git a/challenge-346/deadmarshal/java/Ch2.java b/challenge-346/deadmarshal/java/Ch2.java
new file mode 100644
index 0000000000..0890b52b15
--- /dev/null
+++ b/challenge-346/deadmarshal/java/Ch2.java
@@ -0,0 +1,52 @@
+import java.util.List;
+import java.util.ArrayList;
+
+public class Ch2 {
+  public static void main(String[] args) {
+    var s = new Solution();
+    System.out.println(s.magic_expression("123",6));
+    System.out.println(s.magic_expression("105",5));
+    System.out.println(s.magic_expression("232",8));
+    System.out.println(s.magic_expression("1324",10));
+    System.out.println(s.magic_expression("1001",2));
+  }
+}
+
+class Solution {
+  private List<String> ans;
+  private String num;
+  private int target;
+
+  public Solution() {
+    this.ans = null;
+    this.num = "";
+    this.target = 0;
+  }
+  
+  public List<String> magic_expression(String num,int target) {
+    ans = new ArrayList<>();
+    this.num = num;
+    this.target = target;
+    dfs(0,0,0,"");
+    return ans;
+  }
+
+  private void dfs(int u, long prev, long curr, String path) {
+    if(u == num.length()) {
+      if(curr == target) ans.add(path);
+      return;
+    }
+    for(int i = u; i < num.length(); i++) {
+      if(i != u && num.charAt(u) == '0') break;
+      long next = Long.parseLong(num.substring(u,i+1));
+      if(u == 0) {
+	dfs(i+1,next,next,path+next);
+      } else {
+	dfs(i+1,next,curr+next,path+"+"+next);
+	dfs(i+1,-next,curr-next,path+"-"+next);
+	dfs(i+1,prev*next,curr-prev+prev*next,path+"*"+next);
+      }
+    }
+  }
+}
+
diff --git a/challenge-346/deadmarshal/perl/ch-1.pl b/challenge-346/deadmarshal/perl/ch-1.pl
new file mode 100644
index 0000000000..fe6bc716eb
--- /dev/null
+++ b/challenge-346/deadmarshal/perl/ch-1.pl
@@ -0,0 +1,27 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use List::Util qw(max);
+
+sub longest_parenthesis{
+  my @s = split '',$_[0];
+  my ($max,@stk) = (0,-1);
+  foreach my $i(0..$#s) {
+    if($s[$i] eq '(') {push @stk,$i}
+    else {
+      pop @stk;
+      if(@stk == 0) {push @stk,$i}
+      else {
+	$max = max($max,$i - $stk[$#stk])
+      }
+    }
+  }
+  $max
+}
+
+printf "%d\n",longest_parenthesis('(()())');
+printf "%d\n",longest_parenthesis(')()())');
+printf "%d\n",longest_parenthesis('((()))()(((()');
+printf "%d\n",longest_parenthesis('))))((()(');
+printf "%d\n",longest_parenthesis('()(()');
+
diff --git a/challenge-346/deadmarshal/perl/ch-2.pl b/challenge-346/deadmarshal/perl/ch-2.pl
new file mode 100644
index 0000000000..fb83b57a5b
--- /dev/null
+++ b/challenge-346/deadmarshal/perl/ch-2.pl
@@ -0,0 +1,29 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use Algorithm::Combinatorics qw(variations_with_repetition);
+use List::Util qw(mesh);
+use Data::Show;
+
+sub magic_expression{
+  my ($str,$target) = @_;
+  my @ds = split '',$str;
+  my $it = variations_with_repetition(['+','-',,'*',''],$#ds);
+  my @res;
+  while(my $ops = $it->next) {
+    my $expr = join '',mesh(\@ds,[@$ops,'']);
+    next if $expr =~ /\b0[0-9]/;
+    my $eval = $expr =~ s/-/+-/gr;
+    $eval =~ s/(\d+)\*(\d+)/$1*$2/ge while $eval =~ /\*/;
+    $eval =~ s/(-?\d+)\+(-?\d+)/$1+$2/ge while $eval =~ /\+/;
+    push @res,$expr if $eval == $target
+  }
+  @res
+}
+
+show magic_expression("123",6);
+show magic_expression("105",5);
+show magic_expression("232",8);
+show magic_expression("1324",10);
+show magic_expression("1001",2)
+