ICFP 2007 Contest: https://web.archive.org/web/20090301164728/https://save-endo.cs.uu.nl/
drubery.com
1use crate::dna::DnaRef;
2use dna_parsing::base::Base;
3use dna_parsing::parser::Parser;
4use dna_parsing::pattern::Pattern;
5use dna_parsing::pattern::PatternItem;
6use dna_parsing::rna::Rna;
7use dna_parsing::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.into_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.iter());
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 if n < matched.groups.len() {
135 let (start, end) = matched.groups[n];
136 let (_, rhs) = dna.split(start);
137 let (group, _) = rhs.split(end - start);
138 replace += protect(group, l);
139 } else {
140 replace += protect(DnaRef::new(), l);
141 }
142 }
143 TemplateItem::Len(n) => {
144 if n < matched.groups.len() {
145 let (start, end) = matched.groups[n];
146 replace += asnat(end - start);
147 } else {
148 replace += asnat(0);
149 }
150 }
151 }
152 }
153 let (_, remainder) = dna.split(matched.end);
154 return Some(replace + remainder);
155 } else {
156 let (_, rhs) = dna.split(index);
157 return Some(rhs);
158 }
159}
160
161#[cfg(test)]
162mod tests {
163 use super::*;
164
165 #[test]
166 fn test_match_bases() {
167 // ICFP -> III on ICFP
168 let dna = DnaRef::from_string("CFPICIIC CCCIIC ICFP");
169 let mut rna = Vec::new();
170 let res = match_replace(dna, &mut rna);
171 assert!(res.is_some());
172 assert_eq!(res.unwrap().to_string(), "III");
173 }
174
175 #[test]
176 fn test_match_skip() {
177 // !{10} -> III on ICFPICFPICFP
178 let dna = DnaRef::from_string("IPICICPIIC CCCIIC ICFPICFPICFP");
179 let mut rna = Vec::new();
180 let res = match_replace(dna, &mut rna);
181 assert!(res.is_some());
182 assert_eq!(res.unwrap().to_string(), "IIIFP");
183 }
184
185 #[test]
186 fn test_match_search() {
187 // ?{IIIC} -> <empty> on ICIICIIICICFP
188 let dna = DnaRef::from_string("IFFCCCFIIC IIC ICIICIIICICFP");
189 let mut rna = Vec::new();
190 let res = match_replace(dna, &mut rna);
191 assert!(res.is_some());
192 assert_eq!(res.unwrap().to_string(), "ICFP");
193 }
194
195 #[test]
196 fn test_match_groups() {
197 // (!{1})(!{1})(!{1})(!{1}) -> {3}{2}{1}{0} on ICFP
198 let dna = DnaRef::from_string(
199 "IIPIPCPIICIIPIPCPIICIIPIPCPIICIIPIPCPIICIIC IPPCCPIPPICPIPPCPIPPPIIC ICFP",
200 );
201 let mut rna = Vec::new();
202 let res = match_replace(dna, &mut rna);
203 assert!(res.is_some());
204 assert_eq!(res.unwrap().to_string(), "PFCI");
205 }
206
207 #[test]
208 fn test_match_protect() {
209 // (!{4}) -> {0}{0,1}{0,2}{0,3} on ICFP
210 let dna = DnaRef::from_string("IIPIPIICPIICIIC IPPPIPCPPIPICPPIPCCPPIIC ICFP");
211 let mut rna = Vec::new();
212 let res = match_replace(dna, &mut rna);
213 assert!(res.is_some());
214 assert_eq!(res.unwrap().to_string(), "ICFPCFPICFPICCFPICCFFP");
215 }
216
217 #[test]
218 fn test_match_asnat() {
219 // (!{10}) -> |0| on ICFPICFPICFP
220 let dna = DnaRef::from_string("IIPIPICICPIICIIC IIPPIIC ICFPICFPICFP");
221 let mut rna = Vec::new();
222 let res = match_replace(dna, &mut rna);
223 assert!(res.is_some());
224 assert_eq!(res.unwrap().to_string(), "ICICPFP");
225 }
226
227 #[test]
228 fn test_match_rna() {
229 // RIPIPIPI -> RCFCFCFC on ICFP
230 let dna = DnaRef::from_string("IIIIPIPIPIIIC IIICFCFCFCIIC ICFP");
231 let mut rna = Vec::new();
232 let res = match_replace(dna, &mut rna);
233 assert!(res.is_some());
234 assert_eq!(res.unwrap().to_string(), "ICFP");
235 assert_eq!(
236 rna,
237 vec![
238 [
239 Base::I,
240 Base::P,
241 Base::I,
242 Base::P,
243 Base::I,
244 Base::P,
245 Base::I
246 ],
247 [
248 Base::C,
249 Base::F,
250 Base::C,
251 Base::F,
252 Base::C,
253 Base::F,
254 Base::C
255 ]
256 ]
257 )
258 }
259
260 #[test]
261 fn test_from_task() {
262 let dna = DnaRef::from_string("IIPIPICPIICICIIFICCIFPPIICCFPC");
263 let mut rna = Vec::new();
264 let res = match_replace(dna, &mut rna);
265 assert!(res.is_some());
266 assert_eq!(res.unwrap().to_string(), "PICFC");
267
268 let dna = DnaRef::from_string("IIPIPICPIICICIIFICCIFCCCPPIICCFPC");
269 let mut rna = Vec::new();
270 let res = match_replace(dna, &mut rna);
271 assert!(res.is_some());
272 assert_eq!(res.unwrap().to_string(), "PIICCFCFFPC");
273
274 let dna = DnaRef::from_string("IIPIPIICPIICIICCIICFCFC");
275 let mut rna = Vec::new();
276 let res = match_replace(dna, &mut rna);
277 assert!(res.is_some());
278 assert_eq!(res.unwrap().to_string(), "I");
279 }
280}