Merge branch 'main' of github.com:braxtonhall/fib

7 files changed, 311 insertions, 0 deletions

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
--- /dev/null
+++ b/entries/lilylin/fractran/fractran-rust
diff --git a/entries/lilylin/fractran/src/core.rs b/entries/lilylin/fractran/src/core.rs
new file mode 100644
index 0000000..26e1a67
--- /dev/null
+++ b/entries/lilylin/fractran/src/core.rs
@@ -0,0 +1,44 @@
+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
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<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
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(());
+}