From 7509f7f46d0511454dccce2d52545c045cb67e57 Mon Sep 17 00:00:00 2001 From: Lily Lin Date: Tue, 25 Oct 2022 00:09:05 -0700 Subject: Much simpler fractran program Why did I commit the complex one in the first place... --- entries/lilylin/fractran/Cargo.lock | 61 --------- entries/lilylin/fractran/Cargo.toml | 12 -- entries/lilylin/fractran/fractran-rust | Bin 4170136 -> 0 bytes entries/lilylin/fractran/fractran.py | 36 +++++ entries/lilylin/fractran/src/core.rs | 44 ------ entries/lilylin/fractran/src/engines/mod.rs | 2 - entries/lilylin/fractran/src/engines/register.rs | 164 ----------------------- entries/lilylin/fractran/src/main.rs | 28 ---- 8 files changed, 36 insertions(+), 311 deletions(-) delete mode 100644 entries/lilylin/fractran/Cargo.lock delete mode 100644 entries/lilylin/fractran/Cargo.toml delete mode 100644 entries/lilylin/fractran/fractran-rust create mode 100644 entries/lilylin/fractran/fractran.py delete mode 100644 entries/lilylin/fractran/src/core.rs delete mode 100644 entries/lilylin/fractran/src/engines/mod.rs delete mode 100644 entries/lilylin/fractran/src/engines/register.rs delete 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 deleted file mode 100644 index b6e9f09..0000000 --- a/entries/lilylin/fractran/Cargo.lock +++ /dev/null @@ -1,61 +0,0 @@ -# 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 deleted file mode 100644 index 8d733ff..0000000 --- a/entries/lilylin/fractran/Cargo.toml +++ /dev/null @@ -1,12 +0,0 @@ -[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 deleted file mode 100644 index 0567250..0000000 Binary files a/entries/lilylin/fractran/fractran-rust and /dev/null differ diff --git a/entries/lilylin/fractran/fractran.py b/entries/lilylin/fractran/fractran.py new file mode 100644 index 0000000..8363609 --- /dev/null +++ b/entries/lilylin/fractran/fractran.py @@ -0,0 +1,36 @@ +import math + +def fibonacci(n): + def is_power_of_two(counter): + bin = "{0:b}".format(counter) + return bin[0] == "1" and all([x == "0" for x in bin[1:]]) + + # http://lomont.org/posts/2017/fractran/ + fractions = [ + (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), + ] + + counter = 78 * pow(5,n) + + while True: + if is_power_of_two(counter): + return int(math.log2(counter)) + for (numerator, denominator) in fractions: + if counter % denominator == 0: + counter //= denominator + counter *= numerator + break diff --git a/entries/lilylin/fractran/src/core.rs b/entries/lilylin/fractran/src/core.rs deleted file mode 100644 index 26e1a67..0000000 --- a/entries/lilylin/fractran/src/core.rs +++ /dev/null @@ -1,44 +0,0 @@ -use num_traits::Pow; - -pub type FracSize = u16; - -#[derive(Debug)] -pub struct Program { - pub fractions: Vec<(FracSize, FracSize)>, - pub initial: u64, -} - -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![ - (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 deleted file mode 100644 index 6870b7c..0000000 --- a/entries/lilylin/fractran/src/engines/mod.rs +++ /dev/null @@ -1,2 +0,0 @@ - -pub mod register; diff --git a/entries/lilylin/fractran/src/engines/register.rs b/entries/lilylin/fractran/src/engines/register.rs deleted file mode 100644 index c7c847b..0000000 --- a/entries/lilylin/fractran/src/engines/register.rs +++ /dev/null @@ -1,164 +0,0 @@ -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 deleted file mode 100644 index a874e1d..0000000 --- a/entries/lilylin/fractran/src/main.rs +++ /dev/null @@ -1,28 +0,0 @@ -#![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