summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--aufgabe3/.gitignore1
-rw-r--r--aufgabe3/Cargo.lock7
-rw-r--r--aufgabe3/Cargo.toml8
-rw-r--r--aufgabe3/input/hexmax0.txt2
-rw-r--r--aufgabe3/input/hexmax1.txt2
-rw-r--r--aufgabe3/input/hexmax2.txt2
-rw-r--r--aufgabe3/input/hexmax3.txt2
-rw-r--r--aufgabe3/input/hexmax4.txt2
-rw-r--r--aufgabe3/input/hexmax5.txt2
-rw-r--r--aufgabe3/src/main.rs364
-rw-r--r--flake.lock92
-rw-r--r--flake.nix62
12 files changed, 546 insertions, 0 deletions
diff --git a/aufgabe3/.gitignore b/aufgabe3/.gitignore
new file mode 100644
index 0000000..eb5a316
--- /dev/null
+++ b/aufgabe3/.gitignore
@@ -0,0 +1 @@
+target
diff --git a/aufgabe3/Cargo.lock b/aufgabe3/Cargo.lock
new file mode 100644
index 0000000..f2778c5
--- /dev/null
+++ b/aufgabe3/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "aufgabe3"
+version = "0.1.0"
diff --git a/aufgabe3/Cargo.toml b/aufgabe3/Cargo.toml
new file mode 100644
index 0000000..94f1a9c
--- /dev/null
+++ b/aufgabe3/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "aufgabe3"
+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/aufgabe3/input/hexmax0.txt b/aufgabe3/input/hexmax0.txt
new file mode 100644
index 0000000..e222f13
--- /dev/null
+++ b/aufgabe3/input/hexmax0.txt
@@ -0,0 +1,2 @@
+D24
+3
diff --git a/aufgabe3/input/hexmax1.txt b/aufgabe3/input/hexmax1.txt
new file mode 100644
index 0000000..746924d
--- /dev/null
+++ b/aufgabe3/input/hexmax1.txt
@@ -0,0 +1,2 @@
+509C431B55
+8
diff --git a/aufgabe3/input/hexmax2.txt b/aufgabe3/input/hexmax2.txt
new file mode 100644
index 0000000..336938f
--- /dev/null
+++ b/aufgabe3/input/hexmax2.txt
@@ -0,0 +1,2 @@
+632B29B38F11849015A3BCAEE2CDA0BD496919F8
+37
diff --git a/aufgabe3/input/hexmax3.txt b/aufgabe3/input/hexmax3.txt
new file mode 100644
index 0000000..c938995
--- /dev/null
+++ b/aufgabe3/input/hexmax3.txt
@@ -0,0 +1,2 @@
+0E9F1DB46B1E2C081B059EAF198FD491F477CE1CD37EBFB65F8D765055757C6F4796BB8B3DF7FCAC606DD0627D6B48C17C09
+121
diff --git a/aufgabe3/input/hexmax4.txt b/aufgabe3/input/hexmax4.txt
new file mode 100644
index 0000000..21028b1
--- /dev/null
+++ b/aufgabe3/input/hexmax4.txt
@@ -0,0 +1,2 @@
+1A02B6B50D7489D7708A678593036FA265F2925B21C28B4724DD822038E3B4804192322F230AB7AF7BDA0A61BA7D4AD8F888
+87
diff --git a/aufgabe3/input/hexmax5.txt b/aufgabe3/input/hexmax5.txt
new file mode 100644
index 0000000..c2ddaf3
--- /dev/null
+++ b/aufgabe3/input/hexmax5.txt
@@ -0,0 +1,2 @@
+EF50AA77ECAD25F5E11A307B713EAAEC55215E7E640FD263FA529BBB48DC8FAFE14D5B02EBF792B5CCBBE9FA1330B867E330A6412870DD2BA6ED0DBCAE553115C9A31FF350C5DF993824886DB5111A83E773F23AD7FA81A845C11E22C4C45005D192ADE68AA9AA57406EB0E7C9CA13AD03888F6ABEDF1475FE9832C66BFDC28964B7022BDD969E5533EA4F2E4EABA75B5DC11972824896786BD1E4A7A7748FDF1452A5079E0F9E6005F040594185EA03B5A869B109A283797AB31394941BFE4D38392AD12186FF6D233585D8C820F197FBA9F6F063A0877A912CCBDCB14BEECBAEC0ED061CFF60BD517B6879B72B9EFE977A9D3259632C718FBF45156A16576AA7F9A4FAD40AD8BC87EC569F9C1364A63B1623A5AD559AAF6252052782BF9A46104E443A3932D25AAE8F8C59F10875FAD3CBD885CE68665F2C826B1E1735EE2FDF0A1965149DF353EE0BE81F3EC133922EF43EBC09EF755FBD740C8E4D024B033F0E8F3449C94102902E143433262CDA1925A2B7FD01BEF26CD51A1FC22EDD49623EE9DEB14C138A7A6C47B677F033BDEB849738C3AE5935A2F54B99237912F2958FDFB82217C175448AA8230FDCB3B3869824A826635B538D47D847D8479A88F350E24B31787DFD60DE5E260B265829E036BE340FFC0D8C05555E75092226E7D54DEB42E1BB2CA9661A882FB718E7AA53F1E606
+1369
diff --git a/aufgabe3/src/main.rs b/aufgabe3/src/main.rs
new file mode 100644
index 0000000..8c32ec1
--- /dev/null
+++ b/aufgabe3/src/main.rs
@@ -0,0 +1,364 @@
+use std::env;
+use std::fmt::Display;
+use std::fs;
+use std::process;
+use std::str::FromStr;
+
+fn main() {
+ let task_file_name = match env::args().nth(1) {
+ Some(x) => x,
+ None => {
+ eprintln!("Nutzung: aufgabe3 <dateiname>");
+ process::exit(1);
+ }
+ };
+ let task_str = fs::read_to_string(task_file_name).expect("Datei kann nicht gelesen werden");
+ let task = Task::try_from(task_str.as_str()).expect("Datei enthält keine gültige Aufgabe");
+ let solution = solve_task(&task);
+ println!("{}", solution)
+}
+
+struct Task {
+ number: HexNumber,
+ max_moves: u32,
+}
+
+struct Solution {
+ states: Vec<SevenSegmentDisplayRow>,
+}
+
+fn solve_pt1(task: &Task) -> Vec<HexDigit> {
+ fn solve_pt1_internal(
+ state: &[HexDigit],
+ segment_balance: i32,
+ segment_flips_left: u32,
+ free_segments_left: u32,
+ ) -> Option<Vec<HexDigit>> {
+ if segment_balance.abs() as u32 > segment_flips_left {
+ return None;
+ }
+ if segment_balance > free_segments_left as i32 {
+ return None;
+ }
+ match state.split_first() {
+ None => match segment_balance {
+ 0 => Some(Vec::new()),
+ _ => None,
+ },
+ Some((digit, rest)) => {
+ for candidate_digit in (0x0..=0xF).rev().map(HexDigit) {
+ let digit_num_segments = digit.num_segments();
+ let segment_num_difference =
+ digit_num_segments as i32 - candidate_digit.num_segments() as i32;
+ let new_segment_balance = segment_balance + segment_num_difference;
+ let num_required_segment_flips =
+ digit.num_required_segment_flips(&candidate_digit);
+ let new_segment_flips_left =
+ match segment_flips_left.checked_sub(num_required_segment_flips) {
+ None => continue,
+ Some(x) => x,
+ };
+ let new_free_segments_left = free_segments_left - (7 - digit_num_segments);
+ match (new_segment_flips_left, new_segment_balance) {
+ (0, 0) => {
+ let mut ret = vec![candidate_digit];
+ ret.append(&mut rest.to_vec());
+ return Some(ret);
+ }
+ (0, _) => continue,
+ (_, _) => {
+ let mut new_rest = match solve_pt1_internal(
+ rest,
+ new_segment_balance,
+ new_segment_flips_left,
+ new_free_segments_left,
+ ) {
+ None => continue,
+ Some(x) => x,
+ };
+ let mut ret = vec![candidate_digit];
+ ret.append(&mut new_rest);
+ return Some(ret);
+ }
+ }
+ }
+ None
+ }
+ }
+ }
+
+ let max_segment_flips = 2 * task.max_moves;
+ let initial_free_segments = task
+ .number
+ .digits
+ .iter()
+ .fold(0, |acc, digit| acc + (7 - digit.num_segments()));
+ solve_pt1_internal(
+ task.number.digits.as_slice(),
+ 0,
+ max_segment_flips,
+ initial_free_segments,
+ )
+ .unwrap()
+}
+
+// TODO: darstellung darf nie komplett geleert werden
+fn solve_pt2(start: &[HexDigit], end: &[HexDigit]) -> Vec<SevenSegmentDisplayRow> {
+ let start_state = start.into_iter().map(|digit| digit.to_seven_segments());
+ let end_state = end.into_iter().map(|digit| digit.to_seven_segments());
+
+ struct Coordinate {
+ digit_idx: usize,
+ segment_idx: usize,
+ }
+
+ let mut on_flips: Vec<Coordinate> = Vec::new();
+ let mut off_flips: Vec<Coordinate> = Vec::new();
+
+ for (digit_idx, (segments_start, segments_end)) in
+ start_state.clone().zip(end_state).enumerate()
+ {
+ for (segment_idx, (segment_start, segment_end)) in segments_start
+ .0
+ .into_iter()
+ .zip(segments_end.0.into_iter())
+ .enumerate()
+ {
+ match (segment_start, segment_end) {
+ (false, true) => on_flips.push(Coordinate {
+ digit_idx,
+ segment_idx,
+ }),
+ (true, false) => off_flips.push(Coordinate {
+ digit_idx,
+ segment_idx,
+ }),
+ _ => {}
+ }
+ }
+ }
+
+ assert_eq!(on_flips.len(), off_flips.len());
+
+ let start_state: Vec<SevenSegmentDisplay> = start_state.collect();
+ let mut ret = vec![SevenSegmentDisplayRow {
+ displays: start_state.clone(),
+ }];
+
+ let mut current_state = start_state;
+ for (on_flip, off_flip) in on_flips.into_iter().zip(off_flips.into_iter()) {
+ current_state[on_flip.digit_idx].0[on_flip.segment_idx] = true;
+ current_state[off_flip.digit_idx].0[off_flip.segment_idx] = false;
+ ret.push(SevenSegmentDisplayRow {
+ displays: current_state.clone(),
+ })
+ }
+
+ ret
+}
+
+fn solve_task(task: &Task) -> Solution {
+ let greatest_possible_number = solve_pt1(task);
+ let states = solve_pt2(&task.number.digits, &greatest_possible_number);
+
+ Solution { states }
+}
+
+impl TryFrom<&str> for Task {
+ type Error = ();
+
+ fn try_from(value: &str) -> Result<Self, Self::Error> {
+ let mut lines = value.lines();
+ let number_str = lines.next().ok_or(())?;
+ let max_moves_str = lines.next().ok_or(())?;
+ let number = HexNumber::try_from(number_str)?;
+ let max_moves = u32::from_str(max_moves_str).map_err(|_| ())?;
+
+ Ok(Task { number, max_moves })
+ }
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
+struct HexDigit(u8);
+
+impl TryFrom<char> for HexDigit {
+ type Error = ();
+
+ fn try_from(c: char) -> Result<Self, Self::Error> {
+ match c {
+ '0' => Ok(Self(0x0)),
+ '1' => Ok(Self(0x1)),
+ '2' => Ok(Self(0x2)),
+ '3' => Ok(Self(0x3)),
+ '4' => Ok(Self(0x4)),
+ '5' => Ok(Self(0x5)),
+ '6' => Ok(Self(0x6)),
+ '7' => Ok(Self(0x7)),
+ '8' => Ok(Self(0x8)),
+ '9' => Ok(Self(0x9)),
+ 'A' => Ok(Self(0xA)),
+ 'B' => Ok(Self(0xB)),
+ 'C' => Ok(Self(0xC)),
+ 'D' => Ok(Self(0xD)),
+ 'E' => Ok(Self(0xE)),
+ 'F' => Ok(Self(0xF)),
+ _ => Err(()),
+ }
+ }
+}
+
+// reihenfolge wie hier: https://en.wikipedia.org/wiki/Seven-segment_display#/media/File:7_Segment_Display_with_Labeled_Segments.svg
+#[derive(Clone, Copy, PartialEq, Eq)]
+struct SevenSegmentDisplay([bool; 7]);
+
+impl SevenSegmentDisplay {
+ fn to_unicode(&self) -> [[char; 2]; 3] {
+ let s = self.0;
+ [
+ [
+ match (s[0], s[5]) {
+ (false, false) => ' ',
+ (false, true) => '╻',
+ (true, false) => '╺',
+ (true, true) => '┏',
+ },
+ match (s[0], s[1]) {
+ (false, false) => ' ',
+ (false, true) => '╻',
+ (true, false) => '╸',
+ (true, true) => '┓',
+ },
+ ],
+ [
+ match (s[4], s[5], s[6]) {
+ (false, false, false) => ' ',
+ (false, false, true) => '╺',
+ (false, true, false) => '╹',
+ (false, true, true) => '┗',
+ (true, false, false) => '╻',
+ (true, false, true) => '┏',
+ (true, true, false) => '┃',
+ (true, true, true) => '┣',
+ },
+ match (s[1], s[2], s[6]) {
+ (false, false, false) => ' ',
+ (false, false, true) => '╸',
+ (false, true, false) => '╻',
+ (false, true, true) => '┓',
+ (true, false, false) => '╹',
+ (true, false, true) => '┛',
+ (true, true, false) => '┃',
+ (true, true, true) => '┫',
+ },
+ ],
+ [
+ match (s[3], s[4]) {
+ (false, false) => ' ',
+ (false, true) => '╹',
+ (true, false) => '╺',
+ (true, true) => '┗',
+ },
+ match (s[2], s[3]) {
+ (false, false) => ' ',
+ (false, true) => '╸',
+ (true, false) => '╹',
+ (true, true) => '┛',
+ },
+ ],
+ ]
+ }
+}
+
+impl HexDigit {
+ fn to_seven_segments(&self) -> SevenSegmentDisplay {
+ let segments = match self.0 {
+ 0x0 => [true, true, true, true, true, true, false],
+ 0x1 => [false, true, true, false, false, false, false],
+ 0x2 => [true, true, false, true, true, false, true],
+ 0x3 => [true, true, true, true, false, false, true],
+ 0x4 => [false, true, true, false, false, true, true],
+ 0x5 => [true, false, true, true, false, true, true],
+ 0x6 => [true, false, true, true, true, true, true],
+ 0x7 => [true, true, true, false, false, false, false],
+ 0x8 => [true, true, true, true, true, true, true],
+ 0x9 => [true, true, true, true, false, true, true],
+ 0xA => [true, true, true, false, true, true, true],
+ 0xB => [false, false, true, true, true, true, true],
+ 0xC => [true, false, false, true, true, true, false],
+ 0xD => [false, true, true, true, true, false, true],
+ 0xE => [true, false, false, true, true, true, true],
+ 0xF => [true, false, false, false, true, true, true],
+ _ => unreachable!(),
+ };
+ SevenSegmentDisplay(segments)
+ }
+
+ // TODO: lookup table?
+ fn num_segments(&self) -> u32 {
+ self.to_seven_segments()
+ .0
+ .into_iter()
+ .filter(|x| *x)
+ .count() as u32
+ }
+
+ fn num_required_segment_flips(&self, other: &Self) -> u32 {
+ self.to_seven_segments()
+ .0
+ .into_iter()
+ .zip(other.to_seven_segments().0.into_iter())
+ .filter(|(segment_self, segment_other)| *segment_self != *segment_other)
+ .count() as u32
+ }
+}
+
+// in lesereihenfolge
+struct HexNumber {
+ digits: Vec<HexDigit>,
+}
+
+struct SevenSegmentDisplayRow {
+ displays: Vec<SevenSegmentDisplay>,
+}
+
+impl Display for SevenSegmentDisplayRow {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ let displays_as_unicode: Vec<[[char; 2]; 3]> = self
+ .displays
+ .iter()
+ .map(|display| display.to_unicode())
+ .collect();
+
+ for row_idx in 0..3 {
+ for unicode_digit in displays_as_unicode.iter() {
+ let row = unicode_digit[row_idx].into_iter().collect::<String>();
+ write!(f, "{}", row)?;
+ }
+ writeln!(f, "")?;
+ }
+
+ Ok(())
+ }
+}
+
+impl Display for Solution {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ for state in &self.states {
+ state.fmt(f)?;
+ }
+ Ok(())
+ }
+}
+
+impl TryFrom<&str> for HexNumber {
+ type Error = ();
+
+ fn try_from(value: &str) -> Result<Self, Self::Error> {
+ let digits = value
+ .chars()
+ .map(|c| HexDigit::try_from(c))
+ .collect::<Result<Vec<HexDigit>, ()>>()?;
+
+ Ok(HexNumber { digits })
+ }
+}
diff --git a/flake.lock b/flake.lock
new file mode 100644
index 0000000..11414ad
--- /dev/null
+++ b/flake.lock
@@ -0,0 +1,92 @@
+{
+ "nodes": {
+ "flake-utils": {
+ "locked": {
+ "lastModified": 1631561581,
+ "narHash": "sha256-3VQMV5zvxaVLvqqUrNz3iJelLw30mIVSfZmAaauM3dA=",
+ "owner": "numtide",
+ "repo": "flake-utils",
+ "rev": "7e5bf3925f6fbdfaf50a2a7ca0be2879c4261d19",
+ "type": "github"
+ },
+ "original": {
+ "owner": "numtide",
+ "repo": "flake-utils",
+ "type": "github"
+ }
+ },
+ "mozilla": {
+ "flake": false,
+ "locked": {
+ "lastModified": 1629225446,
+ "narHash": "sha256-HJX4Pc5ZUAg4apxB/XHuJ+6ukzvRQqeZMjscOBst2bA=",
+ "owner": "mozilla",
+ "repo": "nixpkgs-mozilla",
+ "rev": "0510159186dd2ef46e5464484fbdf119393afa58",
+ "type": "github"
+ },
+ "original": {
+ "owner": "mozilla",
+ "repo": "nixpkgs-mozilla",
+ "type": "github"
+ }
+ },
+ "naersk": {
+ "inputs": {
+ "nixpkgs": "nixpkgs"
+ },
+ "locked": {
+ "lastModified": 1632266297,
+ "narHash": "sha256-J1yeJk6Gud9ef2pEf6aKQemrfg1pVngYDSh+SAY94xk=",
+ "owner": "nmattia",
+ "repo": "naersk",
+ "rev": "ee7edec50b49ab6d69b06d62f1de554efccb1ccd",
+ "type": "github"
+ },
+ "original": {
+ "owner": "nmattia",
+ "repo": "naersk",
+ "type": "github"
+ }
+ },
+ "nixpkgs": {
+ "locked": {
+ "lastModified": 1631118067,
+ "narHash": "sha256-tEcFvm3a6ToeBGwHdjfB2mVQwa4LZCZTQYE2LnY3ycA=",
+ "path": "/nix/store/6dcqil119qr3sad2lp9ykkkc852ppmqm-source",
+ "rev": "09cd65b33c5653d7d2954fef4b9f0e718c899743",
+ "type": "path"
+ },
+ "original": {
+ "id": "nixpkgs",
+ "type": "indirect"
+ }
+ },
+ "nixpkgs_2": {
+ "locked": {
+ "lastModified": 1634436779,
+ "narHash": "sha256-D/nrXTWpe1bPIjFy85sgiLHYqu+AeaC6v5/+KlA9PRg=",
+ "owner": "NixOS",
+ "repo": "nixpkgs",
+ "rev": "9aeeb7574fb784eaf6395f4400705b5f619e6cc3",
+ "type": "github"
+ },
+ "original": {
+ "owner": "NixOS",
+ "ref": "nixos-unstable",
+ "repo": "nixpkgs",
+ "type": "github"
+ }
+ },
+ "root": {
+ "inputs": {
+ "flake-utils": "flake-utils",
+ "mozilla": "mozilla",
+ "naersk": "naersk",
+ "nixpkgs": "nixpkgs_2"
+ }
+ }
+ },
+ "root": "root",
+ "version": 7
+}
diff --git a/flake.nix b/flake.nix
new file mode 100644
index 0000000..4b7dbad
--- /dev/null
+++ b/flake.nix
@@ -0,0 +1,62 @@
+{
+ inputs = {
+ flake-utils.url = "github:numtide/flake-utils";
+ mozilla = {
+ url = "github:mozilla/nixpkgs-mozilla";
+ flake = false;
+ };
+ naersk.url = "github:nmattia/naersk";
+ nixpkgs.url = "github:NixOS/nixpkgs/nixos-unstable";
+ };
+ outputs = { self, flake-utils, mozilla, naersk, nixpkgs }: flake-utils.lib.eachDefaultSystem (
+ system:
+ let
+ overlay = final: prev:
+ let
+ # rustChannel = final.rustChannelOf {
+ # channel = "stable";
+ # date = "2021-09-09";
+ # sha256 = "sha256-HNIlEerJvk6sBfd8zugzwSgSiHcQH8ZbqWQn9BGfmpo=";
+ # };
+ rustChannel = final.rustChannelOf {
+ channel = "nightly";
+ date = "2021-10-25";
+ sha256 = "sha256-/zS2GztCeH6kc3ZjhBRvT7Pbnea5JvGBuWdZmagh788=";
+ };
+ rust = rustChannel.rust.override {
+ extensions = [ "rust-src" ];
+ };
+ in
+ {
+ rustc = rust;
+ cargo = rust;
+ };
+ pkgs = import nixpkgs {
+ inherit system;
+ overlays = [
+ (import "${mozilla}/rust-overlay.nix")
+ overlay
+ ];
+ };
+ naerskLib = pkgs.callPackage "${naersk}/default.nix" {};
+ persea = naerskLib.buildPackage {
+ pname = "persea";
+ src = ./.;
+ };
+ in
+ {
+ defaultPackage = persea;
+ devShell = pkgs.mkShell {
+ buildInputs = with pkgs; [
+ cargo
+ cargo-edit
+ rust-analyzer
+ rustfmt
+
+ pkg-config
+ openssl
+ ];
+ };
+ }
+ );
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-03-21 12:52:40 +0000