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