Code jam

13 files changed, 347 insertions, 0 deletions

diff --git a/code-jam22/round1/3d-printing.jl b/code-jam22/round1/3d-printing.jl
new file mode 100644
index 0000000..c003a4b
--- /dev/null
+++ b/code-jam22/round1/3d-printing.jl
@@ -0,0 +1,26 @@
+cases = parse(Int, readline())
+
+for case = 1:cases
+    colors = reduce(hcat, map(1:3) do ()
+        parse.(Int, split(readline()))
+    end)
+    print("Case #", case, ": ")
+    m = map(1:4) do c minimum(colors[c, :]) end
+    over = sum(m) - 1_000_000
+    if over < 0
+        println("IMPOSSIBLE")
+    else
+        i = 1
+        while over > 0
+            if m[i] ≥ over
+                m[i] -= over
+                break
+            else
+                over -= m[i]
+                m[i] = 0
+                i += 1
+            end
+        end
+        println(join(m, ' '))
+    end
+end
diff --git a/code-jam22/round1/d1000000.jl b/code-jam22/round1/d1000000.jl
new file mode 100644
index 0000000..c1db6e1
--- /dev/null
+++ b/code-jam22/round1/d1000000.jl
@@ -0,0 +1,11 @@
+t = parse(Int, readline())
+
+for case = 1:t
+    readline()
+    ds = readline() |> split .|> (x -> parse(Int, x)) |> sort
+    at = 0
+    for d = ds
+        at += d > at
+    end
+    println("Case #", case, ": ", at)
+end
diff --git a/code-jam22/round1/punched-cards.jl b/code-jam22/round1/punched-cards.jl
new file mode 100644
index 0000000..16bd228
--- /dev/null
+++ b/code-jam22/round1/punched-cards.jl
@@ -0,0 +1,12 @@
+t = parse(Int, readline())
+for i = 1:t
+    r, c = parse.(Int, split(readline()))
+    println("Case #", i, ":")
+    println("..+" * "-+" ^ (c - 1))
+    println("..|" * ".|" ^ (c - 1))
+    for y = 1:(r-1)
+        println("+" * "-+" ^ c)
+        println("|" * ".|" ^ c)
+    end
+    println("+" * "-+" ^ c)
+end
diff --git a/code-jam22/round1b/a-se-dat-ab/Cargo.lock b/code-jam22/round1b/a-se-dat-ab/Cargo.lock
new file mode 100644
index 0000000..dfb0ec3
--- /dev/null
+++ b/code-jam22/round1b/a-se-dat-ab/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "a-se-dat-ab"
+version = "0.1.0"
diff --git a/code-jam22/round1b/a-se-dat-ab/Cargo.toml b/code-jam22/round1b/a-se-dat-ab/Cargo.toml
new file mode 100644
index 0000000..c2064ae
--- /dev/null
+++ b/code-jam22/round1b/a-se-dat-ab/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "a-se-dat-ab"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
diff --git a/code-jam22/round1b/a-se-dat-ab/src/local_testing_tool.py b/code-jam22/round1b/a-se-dat-ab/src/local_testing_tool.py
new file mode 100644
index 0000000..63015fb
--- /dev/null
+++ b/code-jam22/round1b/a-se-dat-ab/src/local_testing_tool.py
@@ -0,0 +1,131 @@
+"""judge.py for asedatab."""
+
+# Usage: `judge.py test_number`, where the argument test_number is 0 (visible)
+# This can also be run as `python3 testing_tool.py test_number`.
+
+from __future__ import print_function
+import sys
+import random
+
+# Use raw_input in Python2.
+try:
+  input = raw_input
+except NameError:
+  pass
+
+T = 100
+S = 8
+MAX_TURNS = 300
+
+INVALID_OUTPUT = -1
+RUN_OUT_OF_TURNS = -1
+
+class Error(Exception):
+  pass
+
+INVALID_LINE_ERROR = "Couldn't read a valid line."
+RUN_OUT_OF_TURNS_ERROR = "Run out of turns"
+UNEXPECTED_LENGTH = "Expect line with length {}, but actually get {}".format
+UNEPECTED_CHAR = "Input contains unexpected character {}".format
+EXCEPTION_AFTER_END_ERROR = "Exception raised while reading input after all cases finish."
+ADDITIONAL_INPUT_ERROR = "Additional input after all cases finish: {}".format
+
+CASE_FAILED_ERROR = "Case #{} failed: {}".format
+
+def ReadValue(line):
+  line = line.strip()
+  if len(line) != S:
+    raise Error(UNEXPECTED_LENGTH(S, len(line)))
+  for c in line:
+    if c not in {'1', '0'}:
+      raise Error(UNEPECTED_CHAR(c))
+  return line
+
+def GetNewRecord(old_record, newp):
+  new_record = ""
+  for i in range(S):
+    new_record += '1' if old_record[i] != newp[i] else '0'
+  return new_record
+
+def GetNumberOfOne(record):
+  number_of_one = 0
+  for i in range(S):
+    number_of_one += 1 if record[i] == '1' else 0
+  return number_of_one
+
+def RunCase():
+  def Output(line):
+    print(line)
+    sys.stdout.flush()
+
+  # choose a random record that is not all 0
+  record = "0"*S
+  while record == "0"*S:
+    record = ""
+    for i in range(S):
+      record += chr(random.randrange(2) + ord('0'))
+
+  for i in range(MAX_TURNS):
+    try:
+      line = input()
+      p = ReadValue(line)
+      r = random.randrange(S)
+      # right rotate r is same as left rotate (S - r)
+      r = S - r
+      newp = p[r:] + p[:r]
+      record = GetNewRecord(record, newp)
+      number_of_one = GetNumberOfOne(record)
+      if number_of_one == 0:
+        # output 0 if the record is set to 0 and mark the test as completed.
+        Output(0)
+        return True
+      elif i < MAX_TURNS - 1:
+        # output the number of 1s in the record if it isn't the last turn
+        Output(number_of_one)
+      else:
+        # output -1 (Run out of turns) if it is the last turn and the record
+        # is not yet set to 0. Also mark the test as failed
+        Output(RUN_OUT_OF_TURNS)
+        return False
+    except Error as err:
+      Output(INVALID_OUTPUT)
+      raise Error(err)
+    except:
+      Output(INVALID_OUTPUT)
+      raise Error(INVALID_LINE_ERROR)
+
+def RunCases(t):
+  for i in range(1, t + 1):
+    # The implementation of randomness here is not guaranteed to match the
+    # implementation of randomness in the real judge.
+    random.seed(2 + i)
+    try:
+      res = RunCase()
+      if not res:
+        raise Error(RUN_OUT_OF_TURNS_ERROR)
+    except Error as err:
+      raise Error(CASE_FAILED_ERROR(i, err))
+
+  try:
+    extra_input = input()
+  except Exception:
+    return
+  raise Error(ADDITIONAL_INPUT_ERROR(extra_input[:100]))
+
+def main():
+  try:
+    print(T)
+    sys.stdout.flush()
+    try:
+      RunCases(T)
+    except Error as err:
+      print(str(err)[:1000], file=sys.stderr)
+      sys.exit(1)
+  except Exception as exception:
+    print(INVALID_OUTPUT)
+    sys.stdout.flush()
+    print(('JUDGE_ERROR! Internal judge exception: {}'.format(exception))
+          [:1000], file=sys.stderr)
+
+if __name__ == "__main__":
+  main()
diff --git a/code-jam22/round1b/a-se-dat-ab/src/main.rs b/code-jam22/round1b/a-se-dat-ab/src/main.rs
new file mode 100644
index 0000000..a0cbb6b
--- /dev/null
+++ b/code-jam22/round1b/a-se-dat-ab/src/main.rs
@@ -0,0 +1,37 @@
+use std::io::{stdin, stdout, BufRead, Write};
+
+fn main() {
+    let stdin = stdin();
+    let mut lines = stdin.lock().lines().map(|l| l.unwrap());
+    let mut line = || lines.next().unwrap();
+    let stdout = stdout();
+    let mut stdout = stdout.lock();
+
+    let mut state = 8473859;
+    let mut r = || {
+        state = state * 252533 % 33554393;
+        state
+    };
+
+    for _ in 1u8..=line().parse().unwrap() {
+        stdout.write_all(b"00000000\n").unwrap();
+        loop {
+            let n = line().parse::<i8>().unwrap();
+            if n == -1 {
+                return; // Wrong answer
+            }
+            if n == 0 {
+                break;
+            }
+            let mut out = *b"00000000\n";
+            for _ in 0..n {
+                let mut v = r() % 8;
+                while out[v] != b'0' {
+                    v = r() % 8;
+                }
+                out[v] = b'1';
+            }
+            stdout.write_all(&out).unwrap();
+        }
+    }
+}
diff --git a/code-jam22/round1b/controlled-inflation/Cargo.lock b/code-jam22/round1b/controlled-inflation/Cargo.lock
new file mode 100644
index 0000000..2683c5a
--- /dev/null
+++ b/code-jam22/round1b/controlled-inflation/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "controlled-inflation"
+version = "0.1.0"
diff --git a/code-jam22/round1b/controlled-inflation/Cargo.toml b/code-jam22/round1b/controlled-inflation/Cargo.toml
new file mode 100644
index 0000000..a28fdcd
--- /dev/null
+++ b/code-jam22/round1b/controlled-inflation/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "controlled-inflation"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
diff --git a/code-jam22/round1b/controlled-inflation/src/main.rs b/code-jam22/round1b/controlled-inflation/src/main.rs
new file mode 100644
index 0000000..6204dd1
--- /dev/null
+++ b/code-jam22/round1b/controlled-inflation/src/main.rs
@@ -0,0 +1,50 @@
+use std::{
+    cmp::Reverse,
+    collections::BinaryHeap,
+    io::{stdin, Read},
+    usize,
+};
+
+fn diff(a: usize, b: usize) -> usize {
+    a.max(b) - a.min(b)
+}
+
+fn main() {
+    let mut input = String::new();
+    stdin().lock().read_to_string(&mut input).unwrap();
+    let mut ints = input
+        .split_ascii_whitespace()
+        .map(|i| i.parse::<usize>().unwrap());
+    let mut get = || ints.next().unwrap();
+
+    for case in 1..=get() {
+        let (n, p) = (get(), get());
+        let xs = (0..n)
+            .map(|_| {
+                let (mut min, mut max) = (usize::MAX, 0);
+                for _ in 0..p {
+                    let x = get();
+                    min = min.min(x);
+                    max = max.max(x);
+                }
+                (min, max)
+            })
+            .collect::<Vec<(_, _)>>();
+
+        let mut q = BinaryHeap::new();
+        q.push((Reverse(0), 0, 0));
+        while let Some((Reverse(dist), i, v)) = q.pop() {
+            // eprintln!("dist = {}; i = {}; v = {}", dist, i, v);
+            if i == n {
+                println!("Case #{}: {}", case, dist);
+                break;
+            }
+            let (min, max) = xs[i];
+
+            let dist_a = dist + diff(v, min) + diff(min, max);
+            q.push((Reverse(dist_a), i + 1, max));
+            let dist_b = dist + diff(v, max) + diff(max, min);
+            q.push((Reverse(dist_b), i + 1, min));
+        }
+    }
+}
diff --git a/code-jam22/round1b/pancake-deque/Cargo.lock b/code-jam22/round1b/pancake-deque/Cargo.lock
new file mode 100644
index 0000000..d8d3902
--- /dev/null
+++ b/code-jam22/round1b/pancake-deque/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "pancake-deque"
+version = "0.1.0"
diff --git a/code-jam22/round1b/pancake-deque/Cargo.toml b/code-jam22/round1b/pancake-deque/Cargo.toml
new file mode 100644
index 0000000..24aa3a3
--- /dev/null
+++ b/code-jam22/round1b/pancake-deque/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "pancake-deque"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
diff --git a/code-jam22/round1b/pancake-deque/src/main.rs b/code-jam22/round1b/pancake-deque/src/main.rs
new file mode 100644
index 0000000..9b0685b
--- /dev/null
+++ b/code-jam22/round1b/pancake-deque/src/main.rs
@@ -0,0 +1,35 @@
+use std::{
+    collections::VecDeque,
+    io::{stdin, Read},
+};
+
+fn main() {
+    let mut input = String::new();
+    stdin().lock().read_to_string(&mut input).unwrap();
+    let mut ints = input
+        .split_ascii_whitespace()
+        .map(|i| i.parse::<i32>().unwrap());
+    let mut get = || ints.next().unwrap();
+
+    for case in 0..get() {
+        let n = get();
+        let mut ds: VecDeque<_> = (0..n).map(|_| get()).collect();
+        let mut ans = 0;
+        let mut max = 0;
+        while !ds.is_empty() {
+            let f = ds.front().unwrap();
+            let b = ds.back().unwrap();
+            let d = if f < b {
+                ds.pop_front().unwrap()
+            } else {
+                ds.pop_back().unwrap()
+            };
+            if d >= max {
+                ans += 1;
+                max = d;
+            }
+        }
+
+        println!("Case #{}: {}", case + 1, ans);
+    }
+}