From 6c028b01bf3c365f15ed0d68af5d3e68f27b0773 Mon Sep 17 00:00:00 2001 From: Malte Voos Date: Sun, 20 Feb 2022 14:04:50 +0100 Subject: aufgabe 3 implementierung --- aufgabe3/.gitignore | 1 + aufgabe3/Cargo.lock | 7 + aufgabe3/Cargo.toml | 8 + aufgabe3/input/hexmax0.txt | 2 + aufgabe3/input/hexmax1.txt | 2 + aufgabe3/input/hexmax2.txt | 2 + aufgabe3/input/hexmax3.txt | 2 + aufgabe3/input/hexmax4.txt | 2 + aufgabe3/input/hexmax5.txt | 2 + aufgabe3/src/main.rs | 364 +++++++++++++++++++++++++++++++++++++++++++++ flake.lock | 92 ++++++++++++ flake.nix | 62 ++++++++ 12 files changed, 546 insertions(+) create mode 100644 aufgabe3/.gitignore create mode 100644 aufgabe3/Cargo.lock create mode 100644 aufgabe3/Cargo.toml create mode 100644 aufgabe3/input/hexmax0.txt create mode 100644 aufgabe3/input/hexmax1.txt create mode 100644 aufgabe3/input/hexmax2.txt create mode 100644 aufgabe3/input/hexmax3.txt create mode 100644 aufgabe3/input/hexmax4.txt create mode 100644 aufgabe3/input/hexmax5.txt create mode 100644 aufgabe3/src/main.rs create mode 100644 flake.lock create mode 100644 flake.nix 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 "); + 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, +} + +fn solve_pt1(task: &Task) -> Vec { + fn solve_pt1_internal( + state: &[HexDigit], + segment_balance: i32, + segment_flips_left: u32, + free_segments_left: u32, + ) -> Option> { + 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 { + 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 = Vec::new(); + let mut off_flips: Vec = 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 = 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 { + 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 for HexDigit { + type Error = (); + + fn try_from(c: char) -> Result { + 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, +} + +struct SevenSegmentDisplayRow { + displays: Vec, +} + +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::(); + 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 { + let digits = value + .chars() + .map(|c| HexDigit::try_from(c)) + .collect::, ()>>()?; + + 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 + ]; + }; + } + ); +} -- cgit 1.4.1