ICFP 2007 Contest: https://web.archive.org/web/20090301164728/https://save-endo.cs.uu.nl/
drubery.com
1use std::iter::Peekable;
2use std::str::Chars;
3
4pub type Error = &'static str;
5
6pub fn assemble(asm: &str) -> Result<Vec<u8>, Error> {
7 Assembler::new(asm).assemble()
8}
9
10struct Assembler<'a> {
11 iter: Peekable<Chars<'a>>,
12 output: Vec<u8>,
13}
14
15enum IntPadding {
16 NoPadding,
17 PaddedTo(usize),
18}
19
20impl<'a> Assembler<'a> {
21 fn new(buf: &'a str) -> Assembler<'a> {
22 Assembler {
23 iter: buf.chars().peekable(),
24 output: Vec::new(),
25 }
26 }
27
28 fn expect(&mut self, c: char) -> Option<()> {
29 match self.iter.next() {
30 Some(d) => {
31 if c == d {
32 Some(())
33 } else {
34 None
35 }
36 }
37 None => None,
38 }
39 }
40
41 fn emit(&mut self, s: &str) {
42 self.output.extend_from_slice(s.as_bytes());
43 }
44
45 fn read_to(&mut self, any_of: &str) -> Option<String> {
46 let mut s = String::new();
47 loop {
48 if let Some(c) = self.iter.peek()
49 && any_of.contains(*c)
50 {
51 return Some(s);
52 }
53
54 match self.iter.next() {
55 Some(c) => s.push(c),
56 None => return None,
57 }
58 }
59 }
60
61 fn parse_int(s: &str) -> Option<usize> {
62 let is_hex = s.starts_with("0x");
63 let base = if is_hex { 16 } else { 10 };
64 let mut ret = 0;
65 let mut iter = s.chars();
66 if is_hex {
67 iter.nth(1);
68 }
69
70 for c in iter {
71 ret *= base;
72 ret += c.to_digit(base)?;
73 }
74
75 return Some(ret as usize);
76 }
77
78 fn encode_int(mut n: usize, p: IntPadding) -> String {
79 let mut s = String::new();
80 while n > 0 {
81 if n % 2 == 1 {
82 s += "C";
83 } else {
84 s += "I";
85 }
86
87 n /= 2;
88 }
89
90 if let IntPadding::PaddedTo(p) = p {
91 for _ in s.len()..(p - 1) {
92 s += "I";
93 }
94 }
95
96 s += "P";
97 return s;
98 }
99
100 fn emit_consts(&mut self, s: &str) {
101 for c in s.chars() {
102 match c {
103 'I' => self.emit("C"),
104 'C' => self.emit("F"),
105 'F' => self.emit("P"),
106 'P' => self.emit("IC"),
107 _ => {}
108 }
109 }
110 }
111
112 fn assemble(mut self) -> Result<Vec<u8>, Error> {
113 loop {
114 match self.iter.next() {
115 Some('I') => self.emit("C"),
116 Some('C') => self.emit("F"),
117 Some('F') => self.emit("P"),
118 Some('P') => self.emit("IC"),
119 Some('!') => {
120 self.expect('{').ok_or("Skip followed by non-{")?;
121 let n = self.read_to("}").ok_or("Skip failed to terminate")?;
122 let n = Self::parse_int(&n).ok_or("Invalid int inside skip")?;
123 self.emit("IP");
124 self.emit(&Self::encode_int(n, IntPadding::NoPadding));
125 self.expect('}').ok_or("Skip failed to terminate")?;
126 }
127 Some('?') => {
128 self.expect('{').ok_or("Search followed by non-?")?;
129 let s = self.read_to("}").ok_or("Search failed to terminate")?;
130 self.emit("IFF");
131 self.emit_consts(&s);
132 self.expect('}').ok_or("Search failed to terminate")?;
133 }
134 Some('(') => self.emit("IIP"),
135 Some(')') => self.emit("IIC"),
136 Some(';') => self.emit("IIC"),
137 Some('{') => {
138 let n = self.read_to("},").ok_or("Reference failed terminate")?;
139 let n = Self::parse_int(&n).ok_or("Reference group index invalid")?;
140 let l = match self.iter.next() {
141 Some('}') => String::from("0"),
142 Some(',') => {
143 let l = self.read_to("}").ok_or("Reference failed to terminate")?;
144 self.expect('}');
145 l
146 }
147 _ => return Err("Reference failed to terminate"),
148 };
149 let l = Self::parse_int(&l).ok_or("Reference level invalid")?;
150 self.emit("IP");
151 self.emit(&Self::encode_int(l, IntPadding::NoPadding));
152 self.emit(&Self::encode_int(n, IntPadding::NoPadding));
153 }
154 Some('|') => {
155 let n = self.read_to("|").ok_or("Length failed to terminate")?;
156 let n = Self::parse_int(&n).ok_or("Length group index invalid")?;
157 self.emit("IIP");
158 self.emit(&Self::encode_int(n, IntPadding::NoPadding));
159 self.expect('|').ok_or("Length failed to terminate")?;
160 }
161 Some('n') => {
162 self.expect('{');
163 let n = self
164 .read_to("},")
165 .ok_or("Int constant failed to terminate")?;
166 let n = Self::parse_int(&n).ok_or("Int constant invalid")?;
167 match self.iter.next() {
168 Some('}') => {
169 self.emit(&Self::encode_int(n, IntPadding::NoPadding));
170 }
171 Some(',') => {
172 let pad = self
173 .read_to("}")
174 .ok_or("Int constant failed to terminate")?;
175 let pad =
176 Self::parse_int(&pad).ok_or("Int constant padding invalid")?;
177 self.emit_consts(&Self::encode_int(n, IntPadding::PaddedTo(pad)));
178 self.expect('}').ok_or("Int constant failed to terminate")?;
179 }
180 _ => return Err("Int constant failed to terminate"),
181 };
182 }
183 Some(' ') | Some('\n') => {}
184 None => return Ok(self.output),
185 Some(c) => {
186 println!("{}", c);
187 return Err("Invalid character");
188 }
189 }
190 }
191 }
192}
193
194#[cfg(test)]
195mod tests {
196 use super::*;
197
198 #[test]
199 fn test_assemble_bases() {
200 let asm = assemble(&"ICFP").unwrap();
201 assert_eq!(b"CFPIC", &asm[..]);
202 }
203
204 #[test]
205 fn test_assemble_skip() {
206 let asm = assemble(&"!{1} !{0x10}").unwrap();
207 assert_eq!(b"IPCPIPIIIICP", &asm[..]);
208 }
209
210 #[test]
211 fn test_assemble_search() {
212 let asm = assemble(&"?{ICFP}").unwrap();
213 assert_eq!(b"IFFCFPIC", &asm[..]);
214 }
215
216 #[test]
217 fn test_assemble_groups() {
218 let asm = assemble(&"()()").unwrap();
219 assert_eq!(b"IIPIICIIPIIC", &asm[..]);
220 }
221
222 #[test]
223 fn test_assemble_pattern_template() {
224 let asm = assemble(&"!{2} ; II ;").unwrap();
225 assert_eq!(b"IPICPIICCCIIC", &asm[..]);
226 }
227
228 #[test]
229 fn test_assemble_pattern_quote() {
230 let asm = assemble(&"{2}").unwrap();
231 assert_eq!(b"IPPICP", &asm[..]);
232
233 let asm = assemble(&"{2,3}").unwrap();
234 assert_eq!(b"IPCCPICP", &asm[..]);
235 }
236
237 #[test]
238 fn test_assemble_pattern_length() {
239 let asm = assemble(&"|3|").unwrap();
240 assert_eq!(b"IIPCCP", &asm[..]);
241 }
242
243 #[test]
244 fn test_assemble_pattern_constant() {
245 let asm = assemble(&"n{4,5}").unwrap();
246 assert_eq!(b"CCFCIC", &asm[..]);
247
248 let asm = assemble(&"n{0x123,24}").unwrap();
249 assert_eq!(b"FFCCCFCCFCCCCCCCCCCCCCCIC", &asm[..]);
250 }
251}