ICFP 2007 Contest: https://web.archive.org/web/20090301164728/https://save-endo.cs.uu.nl/
drubery.com
1use crate::dna::Base;
2use crate::dna::DnaRef;
3use crate::parser::Parser;
4use crate::pattern::Pattern;
5use crate::pattern::PatternItem;
6use crate::rna::Rna;
7use crate::template::TemplateItem;
8
9struct MatchResult {
10 end: usize,
11 groups: Vec<(usize, usize)>,
12}
13
14fn do_match(dna: &DnaRef, start: usize, pattern: &Pattern) -> Option<MatchResult> {
15 let mut index = start;
16 let mut env = Vec::new();
17 let mut opens = Vec::new();
18 for p in pattern.iter() {
19 match p {
20 PatternItem::Base(b) => {
21 if index >= dna.len() || dna[index] != *b {
22 return None;
23 }
24
25 index += 1;
26 }
27 PatternItem::Skip(n) => {
28 index += n;
29 if index > dna.len() {
30 return None;
31 }
32 }
33 PatternItem::Search(s) => {
34 let mut fallback = Vec::new();
35 fallback.reserve(s.len());
36 fallback.push(0);
37 fallback.push(0);
38 for i in 2..s.len() {
39 let mut j = fallback[i - 1];
40 while j > 0 && s[j] != s[i - 1] {
41 j = fallback[j];
42 }
43 if s[i - 1] == s[j] {
44 fallback.push(j + 1);
45 } else {
46 fallback.push(0);
47 }
48 }
49
50 let mut cur = 0;
51 loop {
52 if cur == s.len() {
53 break;
54 } else if index >= dna.len() {
55 return None;
56 } else if dna[index] == s[cur] {
57 index += 1;
58 cur += 1;
59 } else if cur == 0 {
60 index += 1;
61 } else {
62 cur = fallback[cur];
63 }
64 }
65 }
66 PatternItem::Open => {
67 opens.push(index);
68 }
69 PatternItem::Close => {
70 let start = opens.pop()?;
71 env.push((start, index));
72 }
73 }
74 }
75
76 return Some(MatchResult {
77 end: index,
78 groups: env,
79 });
80}
81
82pub fn protect(dna: DnaRef, level: usize) -> DnaRef {
83 if level == 0 {
84 return dna;
85 }
86
87 let mut cur = dna.clone();
88 for _ in 0..level {
89 cur = cur
90 .iter()
91 .flat_map(|b| match b {
92 Base::I => [Base::C].iter(),
93 Base::C => [Base::F].iter(),
94 Base::F => [Base::P].iter(),
95 Base::P => [Base::I, Base::C].iter(),
96 })
97 .map(|b| DnaRef::from_base(*b))
98 .collect::<DnaRef>();
99 }
100
101 return cur;
102}
103
104pub fn asnat(n: usize) -> DnaRef {
105 let mut v = Vec::new();
106 let mut cur = n;
107 while cur > 0 {
108 if cur % 2 == 1 {
109 v.push(Base::C);
110 } else {
111 v.push(Base::I);
112 }
113
114 cur /= 2;
115 }
116 v.push(Base::P);
117 return v.iter().map(|b| DnaRef::from_base(*b)).collect::<DnaRef>();
118}
119
120pub fn match_replace(dna: DnaRef, rna: &mut Vec<Rna>) -> Option<DnaRef> {
121 let mut parser = Parser::new(&dna);
122 let pattern = parser.pattern(rna)?;
123 let template = parser.template(rna)?;
124 let index = parser.index();
125
126 if let Some(matched) = do_match(&dna, index, &pattern) {
127 let mut replace = DnaRef::new();
128 for t in template.into_iter() {
129 match t {
130 TemplateItem::Base(b) => {
131 replace += DnaRef::from_base(b);
132 }
133 TemplateItem::Ref(n, l) => {
134 let (start, end) = matched.groups[n];
135 let (_, rhs) = dna.split(start);
136 let (group, _) = rhs.split(end - start);
137 replace += protect(group, l);
138 }
139 TemplateItem::Len(n) => {
140 let (start, end) = matched.groups[n];
141 replace += asnat(end - start);
142 }
143 }
144 }
145 let (_, remainder) = dna.split(matched.end);
146 return Some(replace + remainder);
147 } else {
148 let (_, rhs) = dna.split(index);
149 return Some(rhs);
150 }
151}
152
153#[cfg(test)]
154mod tests {
155 use super::*;
156
157 #[test]
158 fn test_match_bases() {
159 // ICFP -> III on ICFP
160 let dna = DnaRef::from_string("CFPICIIC CCCIIC ICFP");
161 let mut rna = Vec::new();
162 let res = match_replace(dna, &mut rna);
163 assert!(res.is_some());
164 assert_eq!(res.unwrap().to_string(), "III");
165 }
166
167 #[test]
168 fn test_match_skip() {
169 // !{10} -> III on ICFPICFPICFP
170 let dna = DnaRef::from_string("IPICICPIIC CCCIIC ICFPICFPICFP");
171 let mut rna = Vec::new();
172 let res = match_replace(dna, &mut rna);
173 assert!(res.is_some());
174 assert_eq!(res.unwrap().to_string(), "IIIFP");
175 }
176
177 #[test]
178 fn test_match_search() {
179 // ?{IIIC} -> <empty> on ICIICIIICICFP
180 let dna = DnaRef::from_string("IFFCCCFIIC IIC ICIICIIICICFP");
181 let mut rna = Vec::new();
182 let res = match_replace(dna, &mut rna);
183 assert!(res.is_some());
184 assert_eq!(res.unwrap().to_string(), "ICFP");
185 }
186
187 #[test]
188 fn test_match_groups() {
189 // (!{1})(!{1})(!{1})(!{1}) -> {3}{2}{1}{0} on ICFP
190 let dna = DnaRef::from_string(
191 "IIPIPCPIICIIPIPCPIICIIPIPCPIICIIPIPCPIICIIC IPPCCPIPPICPIPPCPIPPPIIC ICFP",
192 );
193 let mut rna = Vec::new();
194 let res = match_replace(dna, &mut rna);
195 assert!(res.is_some());
196 assert_eq!(res.unwrap().to_string(), "PFCI");
197 }
198
199 #[test]
200 fn test_match_protect() {
201 // (!{4}) -> {0}{0,1}{0,2}{0,3} on ICFP
202 let dna = DnaRef::from_string("IIPIPIICPIICIIC IPPPIPCPPIPICPPIPCCPPIIC ICFP");
203 let mut rna = Vec::new();
204 let res = match_replace(dna, &mut rna);
205 assert!(res.is_some());
206 assert_eq!(res.unwrap().to_string(), "ICFPCFPICFPICCFPICCFFP");
207 }
208
209 #[test]
210 fn test_match_asnat() {
211 // (!{10}) -> |0| on ICFPICFPICFP
212 let dna = DnaRef::from_string("IIPIPICICPIICIIC IIPPIIC ICFPICFPICFP");
213 let mut rna = Vec::new();
214 let res = match_replace(dna, &mut rna);
215 assert!(res.is_some());
216 assert_eq!(res.unwrap().to_string(), "ICICPFP");
217 }
218
219 #[test]
220 fn test_match_rna() {
221 // RIPIPIPI -> RCFCFCFC on ICFP
222 let dna = DnaRef::from_string("IIIIPIPIPIIIC IIICFCFCFCIIC ICFP");
223 let mut rna = Vec::new();
224 let res = match_replace(dna, &mut rna);
225 assert!(res.is_some());
226 assert_eq!(res.unwrap().to_string(), "ICFP");
227 assert_eq!(
228 rna,
229 vec![
230 [
231 Base::I,
232 Base::P,
233 Base::I,
234 Base::P,
235 Base::I,
236 Base::P,
237 Base::I
238 ],
239 [
240 Base::C,
241 Base::F,
242 Base::C,
243 Base::F,
244 Base::C,
245 Base::F,
246 Base::C
247 ]
248 ]
249 )
250 }
251
252 #[test]
253 fn test_from_task() {
254 let dna = DnaRef::from_string("IIPIPICPIICICIIFICCIFPPIICCFPC");
255 let mut rna = Vec::new();
256 let res = match_replace(dna, &mut rna);
257 assert!(res.is_some());
258 assert_eq!(res.unwrap().to_string(), "PICFC");
259
260 let dna = DnaRef::from_string("IIPIPICPIICICIIFICCIFCCCPPIICCFPC");
261 let mut rna = Vec::new();
262 let res = match_replace(dna, &mut rna);
263 assert!(res.is_some());
264 assert_eq!(res.unwrap().to_string(), "PIICCFCFFPC");
265
266 let dna = DnaRef::from_string("IIPIPIICPIICIICCIICFCFC");
267 let mut rna = Vec::new();
268 let res = match_replace(dna, &mut rna);
269 assert!(res.is_some());
270 assert_eq!(res.unwrap().to_string(), "I");
271 }
272}