ICFP 2007 Contest: https://web.archive.org/web/20090301164728/https://save-endo.cs.uu.nl/
drubery.com
1use std::collections::VecDeque;
2use std::ops::Add;
3use std::ops::Deref;
4use std::ops::Index;
5use std::rc::Rc;
6
7#[derive(Copy, Clone, PartialEq, Debug)]
8pub enum Base {
9 I,
10 C,
11 F,
12 P,
13}
14
15#[derive(Clone, Debug)]
16pub enum Dna {
17 Empty,
18 Leaf(Base),
19 TwoNode(TwoNode),
20 ThreeNode(ThreeNode),
21}
22
23#[derive(Clone, Debug)]
24// Wrap Rc in a single-value enum so I can implement traits for it.
25pub enum DnaRef {
26 DnaRef(Rc<Dna>),
27}
28
29#[derive(Clone, Debug)]
30pub struct TwoNode {
31 len: usize,
32 depth: usize,
33 children: (DnaRef, DnaRef),
34}
35
36#[derive(Clone, Debug)]
37pub struct ThreeNode {
38 len: usize,
39 depth: usize,
40 children: (DnaRef, DnaRef, DnaRef),
41}
42
43impl Base {
44 pub fn from_char(c: char) -> Option<Base> {
45 match c {
46 'I' => Some(Base::I),
47 'C' => Some(Base::C),
48 'F' => Some(Base::F),
49 'P' => Some(Base::P),
50 _ => None,
51 }
52 }
53
54 pub fn to_char(&self) -> char {
55 match self {
56 Base::I => 'I',
57 Base::C => 'C',
58 Base::F => 'F',
59 Base::P => 'P',
60 }
61 }
62}
63
64impl DnaRef {
65 pub fn new() -> Self {
66 Self::DnaRef(Rc::new(Dna::Empty))
67 }
68
69 pub fn from_base(b: Base) -> Self {
70 Self::DnaRef(Rc::new(Dna::Leaf(b)))
71 }
72
73 fn from_two_children(a: DnaRef, b: DnaRef) -> Self {
74 debug_assert_eq!(a.depth(), b.depth());
75 Self::DnaRef(Rc::new(Dna::TwoNode(TwoNode {
76 len: a.len() + b.len(),
77 depth: a.depth() + 1,
78 children: (a, b),
79 })))
80 }
81
82 fn from_three_children(a: DnaRef, b: DnaRef, c: DnaRef) -> Self {
83 debug_assert_eq!(a.depth(), b.depth());
84 debug_assert_eq!(a.depth(), c.depth());
85 Self::DnaRef(Rc::new(Dna::ThreeNode(ThreeNode {
86 len: a.len() + b.len() + c.len(),
87 depth: a.depth() + 1,
88 children: (a, b, c),
89 })))
90 }
91
92 pub fn from_string(s: &str) -> Self {
93 s.chars()
94 .filter_map(|c| Base::from_char(c))
95 .map(|b| DnaRef::from_base(b))
96 .collect::<DnaRef>()
97 }
98
99 pub fn len(&self) -> usize {
100 match &**self {
101 Dna::Empty => 0,
102 Dna::Leaf(_) => 1,
103 Dna::TwoNode(node) => node.len,
104 Dna::ThreeNode(node) => node.len,
105 }
106 }
107
108 fn depth(&self) -> usize {
109 match &**self {
110 Dna::Empty => 0,
111 Dna::Leaf(_) => 1,
112 Dna::TwoNode(node) => node.depth,
113 Dna::ThreeNode(node) => node.depth,
114 }
115 }
116
117 pub fn iter<'a>(&'a self) -> DnaIterator<'a> {
118 let mut stack = Vec::new();
119 stack.push(self);
120 DnaIterator { stack }
121 }
122
123 pub fn split(&self, n: usize) -> (DnaRef, DnaRef) {
124 debug_assert!(n <= self.len());
125 match &**self {
126 Dna::Empty => (DnaRef::new(), DnaRef::new()),
127 Dna::Leaf(b) => {
128 if n == 0 {
129 (DnaRef::new(), DnaRef::from_base(*b))
130 } else {
131 (DnaRef::from_base(*b), DnaRef::new())
132 }
133 }
134 Dna::TwoNode(node) => {
135 let (a, b) = &node.children;
136 if n < a.len() {
137 let (x, y) = a.split(n);
138 (x, y + b.clone())
139 } else if n == a.len() {
140 (a.clone(), b.clone())
141 } else {
142 let (x, y) = b.split(n - a.len());
143 (a.clone() + x, y)
144 }
145 }
146 Dna::ThreeNode(node) => {
147 let (a, b, c) = &node.children;
148 if n < a.len() {
149 let (x, y) = a.split(n);
150 (x, y + b.clone() + c.clone())
151 } else if n == a.len() {
152 (a.clone(), b.clone() + c.clone())
153 } else if n - a.len() < b.len() {
154 let (x, y) = b.split(n - a.len());
155 (a.clone() + x, y + c.clone())
156 } else if n == a.len() + b.len() {
157 (a.clone() + b.clone(), c.clone())
158 } else {
159 let (x, y) = c.split(n - a.len() - b.len());
160 (a.clone() + b.clone() + x, y)
161 }
162 }
163 }
164 }
165
166 #[cfg(test)]
167 pub fn to_string(&self) -> String {
168 self.iter().map(|b| Base::to_char(&b)).collect::<String>()
169 }
170}
171
172impl Deref for DnaRef {
173 type Target = Dna;
174
175 fn deref(&self) -> &Self::Target {
176 match self {
177 DnaRef::DnaRef(r) => &*r,
178 }
179 }
180}
181
182struct DnaRefIter<I>
183where
184 I: Iterator<Item = DnaRef>,
185{
186 iter: I,
187 buf: VecDeque<DnaRef>,
188}
189
190impl<I> DnaRefIter<I>
191where
192 I: Iterator<Item = DnaRef>,
193{
194 fn new(iter: I) -> DnaRefIter<I> {
195 DnaRefIter {
196 iter: iter,
197 buf: VecDeque::with_capacity(5),
198 }
199 }
200}
201
202impl<I> Iterator for DnaRefIter<I>
203where
204 I: Iterator<Item = DnaRef>,
205{
206 type Item = DnaRef;
207 fn next(&mut self) -> Option<Self::Item> {
208 while self.buf.len() < 5 {
209 let Some(x) = self.iter.next() else {
210 break;
211 };
212
213 self.buf.push_back(x);
214 }
215
216 if self.buf.len() == 5 || self.buf.len() == 3 {
217 let a = self.buf.pop_front().unwrap();
218 let b = self.buf.pop_front().unwrap();
219 let c = self.buf.pop_front().unwrap();
220
221 return Some(DnaRef::from_three_children(a, b, c));
222 } else if self.buf.len() == 4 || self.buf.len() == 2 {
223 let a = self.buf.pop_front().unwrap();
224 let b = self.buf.pop_front().unwrap();
225
226 return Some(DnaRef::from_two_children(a, b));
227 } else {
228 return None;
229 }
230 }
231}
232
233impl FromIterator<DnaRef> for DnaRef {
234 fn from_iter<I: IntoIterator<Item = DnaRef>>(iter: I) -> DnaRef {
235 // We need some kind of buffer no matter what, even if we aggregate as we go.
236 // This implementation does the easy thing and just repeatedly collects into a Vec.
237 let mut cur: Vec<DnaRef> = iter.into_iter().collect::<Vec<_>>();
238 while cur.len() > 1 {
239 cur = DnaRefIter::new(cur.into_iter()).collect();
240 }
241
242 match cur.pop() {
243 Some(dna) => dna,
244 None => DnaRef::new(),
245 }
246 }
247}
248
249pub struct DnaIterator<'a> {
250 stack: Vec<&'a DnaRef>,
251}
252
253impl<'a> Iterator for DnaIterator<'a> {
254 type Item = Base;
255
256 fn next(&mut self) -> Option<Self::Item> {
257 while let Some(node) = self.stack.pop() {
258 match &**node {
259 Dna::Empty => return None,
260 Dna::Leaf(c) => return Some(*c),
261 Dna::TwoNode(node) => {
262 let (a, b) = &node.children;
263 self.stack.push(b);
264 self.stack.push(a);
265 }
266 Dna::ThreeNode(node) => {
267 let (a, b, c) = &node.children;
268 self.stack.push(c);
269 self.stack.push(b);
270 self.stack.push(a);
271 }
272 }
273 }
274
275 return None;
276 }
277}
278
279enum AddState {
280 One(DnaRef),
281 Two(DnaRef, DnaRef),
282}
283
284fn add_helper(lhs: DnaRef, rhs: DnaRef) -> AddState {
285 if lhs.depth() == rhs.depth() {
286 AddState::Two(lhs, rhs)
287 } else if lhs.depth() < rhs.depth() {
288 match &*rhs {
289 Dna::Empty => unreachable!(),
290 Dna::Leaf(_) => AddState::One(rhs),
291 Dna::TwoNode(node) => {
292 let (a, b) = &node.children;
293 match add_helper(lhs, a.clone()) {
294 AddState::One(x) => AddState::One(DnaRef::from_two_children(x, b.clone())),
295 AddState::Two(x, y) => {
296 AddState::One(DnaRef::from_three_children(x, y, b.clone()))
297 }
298 }
299 }
300 Dna::ThreeNode(node) => {
301 let (a, b, c) = &node.children;
302 match add_helper(lhs, a.clone()) {
303 AddState::One(x) => {
304 AddState::One(DnaRef::from_three_children(x, b.clone(), c.clone()))
305 }
306 AddState::Two(x, y) => AddState::Two(
307 DnaRef::from_two_children(x, y),
308 DnaRef::from_two_children(b.clone(), c.clone()),
309 ),
310 }
311 }
312 }
313 } else {
314 match &*lhs {
315 Dna::Empty => unreachable!(),
316 Dna::Leaf(_) => AddState::One(lhs.clone()),
317 Dna::TwoNode(node) => {
318 let (a, b) = &node.children;
319 match add_helper(b.clone(), rhs) {
320 AddState::One(x) => AddState::One(DnaRef::from_two_children(a.clone(), x)),
321 AddState::Two(x, y) => {
322 AddState::One(DnaRef::from_three_children(a.clone(), x, y))
323 }
324 }
325 }
326 Dna::ThreeNode(node) => {
327 let (a, b, c) = &node.children;
328 match add_helper(c.clone(), rhs) {
329 AddState::One(x) => {
330 AddState::One(DnaRef::from_three_children(a.clone(), b.clone(), x))
331 }
332 AddState::Two(x, y) => AddState::Two(
333 DnaRef::from_two_children(a.clone(), b.clone()),
334 DnaRef::from_two_children(x, y),
335 ),
336 }
337 }
338 }
339 }
340}
341
342impl Add for DnaRef {
343 type Output = Self;
344
345 fn add(self, other: Self) -> Self {
346 match add_helper(self, other) {
347 AddState::One(a) => a,
348 AddState::Two(a, b) => Self::from_two_children(a, b),
349 }
350 }
351}
352
353impl Index<usize> for DnaRef {
354 type Output = Base;
355
356 fn index(&self, n: usize) -> &Self::Output {
357 debug_assert!(n < self.len());
358
359 match &**self {
360 Dna::Empty => unreachable!(),
361 Dna::Leaf(c) => c,
362 Dna::TwoNode(node) => {
363 let (a, b) = &node.children;
364 if n < a.len() {
365 a.index(n)
366 } else {
367 b.index(n - a.len())
368 }
369 }
370 Dna::ThreeNode(node) => {
371 let (a, b, c) = &node.children;
372 if n < a.len() {
373 a.index(n)
374 } else if n < a.len() + b.len() {
375 b.index(n - a.len())
376 } else {
377 c.index(n - a.len() - b.len())
378 }
379 }
380 }
381 }
382}
383
384#[cfg(test)]
385mod tests {
386 use super::*;
387
388 #[test]
389 fn test_empty() {
390 let dna: DnaRef = DnaRef::new();
391 assert_eq!(dna.len(), 0);
392 }
393
394 #[test]
395 fn test_to_from_string() {
396 let dna: DnaRef = DnaRef::from_string("ICFP");
397 assert_eq!(dna.to_string(), "ICFP");
398 }
399
400 #[test]
401 fn test_index() {
402 let s = "ICFP";
403 let dna: DnaRef = DnaRef::from_string(s);
404 assert_eq!(dna[0], Base::I);
405 assert_eq!(dna[1], Base::C);
406 assert_eq!(dna[2], Base::F);
407 assert_eq!(dna[3], Base::P);
408 }
409
410 #[test]
411 fn test_add() {
412 let lhs = DnaRef::from_string("IIIC");
413 let rhs = DnaRef::from_string("PFFF");
414 assert_eq!((lhs + rhs).to_string(), "IIICPFFF");
415 }
416
417 #[test]
418 fn test_split() {
419 let dna = DnaRef::from_string("IIICPFFF");
420 let (lhs, rhs) = dna.split(4);
421 assert_eq!(lhs.to_string(), "IIIC");
422 assert_eq!(rhs.to_string(), "PFFF");
423 }
424}