aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.gitignore1
-rw-r--r--entries/lilylin/fractran/Cargo.lock61
-rw-r--r--entries/lilylin/fractran/Cargo.toml12
-rw-r--r--entries/lilylin/fractran/fractran-rustbin4170136 -> 0 bytes
-rw-r--r--entries/lilylin/fractran/fractran.py36
-rw-r--r--entries/lilylin/fractran/src/core.rs44
-rw-r--r--entries/lilylin/fractran/src/engines/mod.rs2
-rw-r--r--entries/lilylin/fractran/src/engines/register.rs164
-rw-r--r--entries/lilylin/fractran/src/main.rs28
-rw-r--r--people.json2
10 files changed, 37 insertions, 313 deletions
diff --git a/.gitignore b/.gitignore
index 69cff8a..c7e318c 100644
--- a/.gitignore
+++ b/.gitignore
@@ -2,4 +2,3 @@ node_modules
*.log
*.pem
.DS_Store
-entries/lilylin/fractran/target
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
Binary files 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<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(());
-}
diff --git a/people.json b/people.json
index e8089f6..a6e6686 100644
--- a/people.json
+++ b/people.json
@@ -94,7 +94,7 @@
"entries": [
{
"name": "fractran",
- "link": "./entries/lilylin/fractran/src/core.rs"
+ "link": "./entries/lilylin/fractran/fractran.py"
},
{
"name": "cursed-x86",
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2024-11-22 07:48:10 +0000