From 2222d48075ab6d225f3cff7b444e35c70c7472fb Mon Sep 17 00:00:00 2001 From: Lily Lin Date: Mon, 24 Oct 2022 22:46:06 -0700 Subject: Add entries --- entries/lilylin/fractran/Cargo.lock | 61 +++++++++ entries/lilylin/fractran/Cargo.toml | 12 ++ entries/lilylin/fractran/fractran-rust | Bin 0 -> 4170136 bytes entries/lilylin/fractran/src/core.rs | 40 ++++++ entries/lilylin/fractran/src/engines/mod.rs | 2 + entries/lilylin/fractran/src/engines/register.rs | 164 +++++++++++++++++++++++ entries/lilylin/fractran/src/main.rs | 28 ++++ 7 files changed, 307 insertions(+) create mode 100644 entries/lilylin/fractran/Cargo.lock create mode 100644 entries/lilylin/fractran/Cargo.toml create mode 100644 entries/lilylin/fractran/fractran-rust create mode 100644 entries/lilylin/fractran/src/core.rs create mode 100644 entries/lilylin/fractran/src/engines/mod.rs create mode 100644 entries/lilylin/fractran/src/engines/register.rs create mode 100644 entries/lilylin/fractran/src/main.rs (limited to 'entries/lilylin/fractran') diff --git a/entries/lilylin/fractran/Cargo.lock b/entries/lilylin/fractran/Cargo.lock new file mode 100644 index 0000000..b6e9f09 --- /dev/null +++ b/entries/lilylin/fractran/Cargo.lock @@ -0,0 +1,61 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "anyhow" +version = "1.0.66" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "216261ddc8289130e551ddcd5ce8a064710c0d064a4d2895c67151c92b5443f6" + +[[package]] +name = "autocfg" +version = "1.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa" + +[[package]] +name = "fractran-rust" +version = "0.1.0" +dependencies = [ + "anyhow", + "num-bigint", + "num-traits", + "primes", +] + +[[package]] +name = "num-bigint" +version = "0.4.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f93ab6289c7b344a8a9f60f88d80aa20032336fe78da341afc91c8a2341fc75f" +dependencies = [ + "autocfg", + "num-integer", + "num-traits", +] + +[[package]] +name = "num-integer" +version = "0.1.45" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "225d3389fb3509a24c93f5c29eb6bde2586b98d9f016636dff58d7c6f7569cd9" +dependencies = [ + "autocfg", + "num-traits", +] + +[[package]] +name = "num-traits" +version = "0.2.15" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "578ede34cf02f8924ab9447f50c28075b4d3e5b269972345e7e0372b38c6cdcd" +dependencies = [ + "autocfg", +] + +[[package]] +name = "primes" +version = "0.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "68a61082d8bceecd71a3870e9162002bb75f7ba9c7aa8b76227e887782fef9c8" diff --git a/entries/lilylin/fractran/Cargo.toml b/entries/lilylin/fractran/Cargo.toml new file mode 100644 index 0000000..8d733ff --- /dev/null +++ b/entries/lilylin/fractran/Cargo.toml @@ -0,0 +1,12 @@ +[package] +name = "fractran-rust" +version = "0.1.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] +anyhow = "1.0.65" +num-bigint = "0.4.3" +num-traits = "0.2.15" +primes = "0.3.0" diff --git a/entries/lilylin/fractran/fractran-rust b/entries/lilylin/fractran/fractran-rust new file mode 100644 index 0000000..0567250 Binary files /dev/null and b/entries/lilylin/fractran/fractran-rust differ diff --git a/entries/lilylin/fractran/src/core.rs b/entries/lilylin/fractran/src/core.rs new file mode 100644 index 0000000..2595d48 --- /dev/null +++ b/entries/lilylin/fractran/src/core.rs @@ -0,0 +1,40 @@ +use num_traits::Pow; + +pub type FracSize = u16; + +#[derive(Debug)] +pub struct Program { + pub fractions: Vec<(FracSize, FracSize)>, + pub initial: u64, +} + +impl Program { + pub fn fibonacci(i: u32) -> Program { + Program { + fractions: vec![ + (17, 65), + (133, 34), + (17, 19), + (23, 17), + (2233, 69), + (23, 29), + (31, 23), + (74, 341), + (31, 37), + (41, 31), + (129, 287), + (41, 43), + (13, 41), + (1, 13), + (1, 3), + ], + initial: 78 * 5u64.pow(i), + } + } +} + +pub trait FractranEngine: IntoIterator +where + Value: From, +{ +} diff --git a/entries/lilylin/fractran/src/engines/mod.rs b/entries/lilylin/fractran/src/engines/mod.rs new file mode 100644 index 0000000..6870b7c --- /dev/null +++ b/entries/lilylin/fractran/src/engines/mod.rs @@ -0,0 +1,2 @@ + +pub mod register; diff --git a/entries/lilylin/fractran/src/engines/register.rs b/entries/lilylin/fractran/src/engines/register.rs new file mode 100644 index 0000000..c7c847b --- /dev/null +++ b/entries/lilylin/fractran/src/engines/register.rs @@ -0,0 +1,164 @@ +use std::collections::HashMap; + +use crate::core::Program; + +#[derive(Debug)] +pub struct Register { + pub program: Program, + pub output_base: u64, // which prime factor registers should be used to determine output +} + +#[derive(Debug)] +struct Instruction { + conditions: Vec<(usize, u64)>, // index, amt pairs + increment: Vec<(usize, u64)>, +} + +impl Register { + fn prime_factorize(x: u64) -> Vec<(u64, u64)> { + let primes = primes::factors_uniq(x); + let mut prime_factorized = Vec::new(); + // println!("val: {:?}", x); + for prime in primes { + let mut amount = 1; + loop { + if x % prime.pow(amount + 1) != 0 { + break; + } + amount += 1; + } + // println!("{:?}, {:?}", prime, amount); + prime_factorized.push((prime, amount as u64)); + } + return prime_factorized; + } + fn convert(&self) -> (Vec, Vec, HashMap) { + let mut primes = Vec::new(); + + let mut prime_to_index = |prime: u64| { + let index: usize; + if primes.contains(&prime) { + index = primes.iter().position(|&x| x == prime).unwrap(); + } else { + index = primes.len(); + primes.push(prime); + } + return index; + }; + + let mut instrs = Vec::new(); + for fraction in &self.program.fractions { + let denom_pfs = Register::prime_factorize(fraction.1 as u64); + let num_pfs = Register::prime_factorize(fraction.0 as u64); + instrs.push(Instruction { + conditions: denom_pfs + .iter() + .map(|x| (prime_to_index(x.0), x.1)) + .collect(), + increment: num_pfs.iter().map(|x| (prime_to_index(x.0), x.1)).collect(), + }) + } + + let mut initial_registers = Vec::new(); + initial_registers.resize(primes.len(), 0); + for (prime, amt) in Register::prime_factorize(self.program.initial) { + let idx = primes.iter().position(|&x| x == prime).unwrap(); + initial_registers[idx] = amt; + } + + let output_condition: HashMap = Register::prime_factorize(self.output_base) + .iter() + .map(|(prime, amt)| (primes.iter().position(|&x| x == *prime).unwrap(), *amt)) + .collect(); + + // println!("Prime layout: {:?}", primes); + // println!("Output condition: {:?}", output_condition); + return (initial_registers, instrs, output_condition); + } +} + +impl IntoIterator for Register { + type Item = u64; + type IntoIter = RegisterIter; + + fn into_iter(self) -> Self::IntoIter { + let (registers, instructions, output_condition) = self.convert(); + RegisterIter { + instructions, + registers, + output_condition, + } + } +} + +pub struct RegisterIter { + instructions: Vec, + registers: Vec, + output_condition: HashMap, +} + +// impl RegisterIter { +// fn registers_to_val(&self) -> BigUint { +// let mut val = BigUint::zero(); +// for (amt, prime) in self.registers.iter().zip(&self.prime_mapping) { +// val += prime.to_biguint().unwrap().pow(*amt); +// } +// return val; +// } +// } + +impl Iterator for RegisterIter { + type Item = u64; + + fn next(&mut self) -> Option { + loop { + for instr in &self.instructions { + if instr + .conditions + .iter() + .all(|(idx, amt)| self.registers[*idx] >= *amt) + { + instr + .conditions + .iter() + .for_each(|(idx, amt)| self.registers[*idx] -= *amt); + instr + .increment + .iter() + .for_each(|(idx, amt)| self.registers[*idx] += *amt); + break; + } + } + + // Output condition checking + // Check that all other registers are 0 + if !self + .registers + .iter() + .enumerate() + .all(|(idx, val)| self.output_condition.contains_key(&idx) || *val == 0) + { + continue; + } + + // Check that the condition registers are multiples of the condition amounts + if !self + .output_condition + .iter() + .all(|(idx, cond)| self.registers[*idx] % cond == 0) + { + continue; + } + + // Check that condition registers are the _same_ multipel of the condition amounts + let mut xs = self + .output_condition + .iter() + .map(|(idx, cond)| self.registers[*idx] / cond); + let first = xs.next().unwrap(); + if xs.all(|y| y == first) { + return Some(first); + } + } + } +} diff --git a/entries/lilylin/fractran/src/main.rs b/entries/lilylin/fractran/src/main.rs new file mode 100644 index 0000000..a874e1d --- /dev/null +++ b/entries/lilylin/fractran/src/main.rs @@ -0,0 +1,28 @@ +#![feature(int_log)] + +use crate::core::Program; + +use anyhow::Ok; +use anyhow::Result; +use engines::register::Register; + +mod core; +mod engines; + +fn execute_fib() { + for i in 1..15 { + let engine = Register { + program: Program::fibonacci(i), + output_base: 2, + }; + let n = 1; + for val in engine.into_iter().take(n) { + print!("{:?},", val); + } + } +} + +fn main() -> Result<()> { + execute_fib(); + return Ok(()); +} -- cgit v1.2.3-70-g09d2 From bea8092ecca8f4bf61a4df88c06f4eeb61ab3a56 Mon Sep 17 00:00:00 2001 From: Lily Lin Date: Mon, 24 Oct 2022 22:52:30 -0700 Subject: Cleanup --- .gitignore | 1 + entries/lilylin/cursed-x86/README.md | 1 + entries/lilylin/fractran/src/core.rs | 4 ++++ people.json | 6 +++--- 4 files changed, 9 insertions(+), 3 deletions(-) create mode 100644 entries/lilylin/cursed-x86/README.md (limited to 'entries/lilylin/fractran') diff --git a/.gitignore b/.gitignore index c7e318c..69cff8a 100644 --- a/.gitignore +++ b/.gitignore @@ -2,3 +2,4 @@ node_modules *.log *.pem .DS_Store +entries/lilylin/fractran/target diff --git a/entries/lilylin/cursed-x86/README.md b/entries/lilylin/cursed-x86/README.md new file mode 100644 index 0000000..4cba657 --- /dev/null +++ b/entries/lilylin/cursed-x86/README.md @@ -0,0 +1 @@ +![A very cursed looking control flow graph with many many blocks, obviously something much more complicated than what a normal fib would be](./control_flow_graph.png) diff --git a/entries/lilylin/fractran/src/core.rs b/entries/lilylin/fractran/src/core.rs index 2595d48..26e1a67 100644 --- a/entries/lilylin/fractran/src/core.rs +++ b/entries/lilylin/fractran/src/core.rs @@ -9,6 +9,10 @@ pub struct Program { } impl Program { + // http://lomont.org/posts/2017/fractran/ + // A lesser known Conway FRACTRAN program is FIBONACCIGAME: + // `{17/65, 133/34, 17/19, 23/17, 2233/69, 23/29, 31/23, 74/341, 31/37, 41/31, 129/287, 41/43, 13/41, 1/13, 1/3}` + // Starting with `78*5^(n-1)`, it halts on `2^Fn` where Fn is the nth [Fibonacci number] pub fn fibonacci(i: u32) -> Program { Program { fractions: vec![ diff --git a/people.json b/people.json index 6a1852d..7c9b8a1 100644 --- a/people.json +++ b/people.json @@ -90,11 +90,11 @@ "entries": [ { "name": "fractran", - "link": "./entries/lilylin/fractran/" + "link": "./entries/lilylin/fractran/src/core.rs" }, { - "name": "cursed x86 (look at the control flow graph)", - "link": "./entries/lilylin/cursed-x86" + "name": "cursed-x86", + "link": "./entries/lilylin/cursed-x86/" }, { "name": "mov", -- cgit v1.2.3-70-g09d2