Merge pull request #40 from rctcwyvrn/lily

Simplify fractran fib

8 files changed, 36 insertions, 311 deletions

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
--- a/entries/lilylin/fractran/fractran-rust
+++ /dev/null
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<Value>: IntoIterator<Item = Value>
-where
-    Value: From<u64>,
-{
-}
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<u64>, Vec<Instruction>, HashMap<usize, u64>) {
-        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<usize, u64> = 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<Instruction>,
-    registers: Vec<u64>,
-    output_condition: HashMap<usize, u64>,
-}
-
-// 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<Self::Item> {
-        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(());
-}