1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

/*!
 * # Usage
 * ```
 * use bftextmaker::gen_code;
 * let (code,memory_used)=gen_code("The quick brown fox jumps over the lazy dog",15);
 * println!("Your code is: {}",code);
 * println!("Used {} cells",memory_used);
 * ```
 */
use std::collections::HashSet;

/// Generates code for the given text.
/// Uses up to the max_memory. Reccomended max is 15.
/// Returns the code as well as the memory actually used
pub fn gen_code(input: &str, max_memory: usize) ->(String,usize) {
    let mut absolute_best:Option<String>=None;
    let chars = input.as_bytes();
    let mut unique:Vec<u8>=chars.iter().fold(HashSet::new(), |mut set,item|{
        set.insert(*item);
        set
    }).into_iter().collect();
    unique.sort();
    let unique_amount=unique.len();
    let mut best_mem=0;
    // just brute force pretending we have different amounts of memory available
    for mem in 2..max_memory {
        let memory_for_chars = std::cmp::min(mem - 1, unique_amount);
        // good enough
        let mut initializers:Vec<u8> = unique.clone().into_iter().take(memory_for_chars).collect();
        let mut shortest_code = gen_init_code(&initializers, 1);
        let max=match chars.iter().max(){
            Some(max)=>max,
            None=>return (String::new(),0)
        };
        for i in 2..*max*2 {
            let code = gen_init_code(&initializers, i);
            if code.len() < shortest_code.len() {
                shortest_code = code;
            }
        }
        let mut pointer = initializers.len() - 1;
        let mut last_target=0;
        for char in chars {
            // find the best cell to edit in order to get our desired letter
            let mut best_score: Option<(usize, &u8, usize)> = None;
            for (i, init) in initializers.iter().enumerate() {
                let score = init.abs_diff(*char) as u32 + pointer.abs_diff(i) as u32;
                if let Some(old) = best_score {
                    if score < old.1.abs_diff(*char) as u32 + old.2.abs_diff(i) as u32 {
                        best_score = Some((i, init, pointer))
                    }
                } else {
                    best_score = Some((i, init, pointer))
                }
            }
            let target = match best_score {
                Some(t) => (t.0, t.1),
                None => continue,
            };
            last_target=target.0;
            if pointer > target.0 {
                shortest_code += &"<".repeat(pointer.abs_diff(target.0))
            } else {
                shortest_code += &">".repeat(pointer.abs_diff(target.0))
            }
            pointer = target.0;
            if target.1 > char {
                shortest_code += &"-".repeat(target.1.abs_diff(*char).into())
            } else {
                shortest_code += &"+".repeat(target.1.abs_diff(*char).into())
            }
            shortest_code += ".";
            initializers[pointer] = *char;
        }
        shortest_code+=&(">".repeat(mem-(last_target+2)));
        if let Some(ref current)=absolute_best{
            if shortest_code.len()<current.len(){
                absolute_best=Some(shortest_code);
                best_mem=mem
            }
        }else{
            absolute_best=Some(shortest_code);
            best_mem=mem
        }
    }
    (absolute_best.unwrap_or_default(),best_mem)
}

fn gen_init_code(initializers: &[u8], divisor: u8) -> String {
    let mut remainders = Vec::new();
    let mut divided = Vec::new();
    for init in initializers {
        divided.push(init / divisor);
        remainders.push(init % divisor);
    }
    let mut code = "+".repeat(divisor as usize);
    code += "[-";
    for cell_goal in divided.iter() {
        code += ">";
        code += &"+".repeat(*cell_goal as usize);
    }
    code += &"<".repeat(initializers.len());
    code += "]";
    for remainder in remainders {
        code += ">";
        code += &"+".repeat(remainder as usize)
    }
    code
}