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/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 ++++ 4 files changed, 234 insertions(+) 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/src') 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/src') 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