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 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 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 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 pub fn to_string(&self) -> String {
167 self.iter().map(|b| Base::to_char(&b)).collect::<String>()
168 }
169}
170
171impl Deref for DnaRef {
172 type Target = Dna;
173
174 fn deref(&self) -> &Self::Target {
175 match self {
176 DnaRef::DnaRef(r) => &*r,
177 }
178 }
179}
180
181struct DnaRefIter<I>
182where
183 I: Iterator<Item = DnaRef>,
184{
185 iter: I,
186 buf: VecDeque<DnaRef>,
187}
188
189impl<I> DnaRefIter<I>
190where
191 I: Iterator<Item = DnaRef>,
192{
193 fn new(iter: I) -> DnaRefIter<I> {
194 DnaRefIter {
195 iter: iter,
196 buf: VecDeque::with_capacity(5),
197 }
198 }
199}
200
201impl<I> Iterator for DnaRefIter<I>
202where
203 I: Iterator<Item = DnaRef>,
204{
205 type Item = DnaRef;
206 fn next(&mut self) -> Option<Self::Item> {
207 while self.buf.len() < 5 {
208 let Some(x) = self.iter.next() else {
209 break;
210 };
211
212 self.buf.push_back(x);
213 }
214
215 if self.buf.len() == 5 || self.buf.len() == 3 {
216 let a = self.buf.pop_front().unwrap();
217 let b = self.buf.pop_front().unwrap();
218 let c = self.buf.pop_front().unwrap();
219
220 return Some(DnaRef::from_three_children(a, b, c));
221 } else if self.buf.len() == 4 || self.buf.len() == 2 {
222 let a = self.buf.pop_front().unwrap();
223 let b = self.buf.pop_front().unwrap();
224
225 return Some(DnaRef::from_two_children(a, b));
226 } else {
227 return None;
228 }
229 }
230}
231
232impl FromIterator<DnaRef> for DnaRef {
233 fn from_iter<I: IntoIterator<Item = DnaRef>>(iter: I) -> DnaRef {
234 // We need some kind of buffer no matter what, even if we aggregate as we go.
235 // This implementation does the easy thing and just repeatedly collects into a Vec.
236 let mut cur: Vec<DnaRef> = iter.into_iter().collect::<Vec<_>>();
237 while cur.len() > 1 {
238 cur = DnaRefIter::new(cur.into_iter()).collect();
239 }
240
241 match cur.pop() {
242 Some(dna) => dna,
243 None => DnaRef::new(),
244 }
245 }
246}
247
248pub struct DnaIterator<'a> {
249 stack: Vec<&'a DnaRef>,
250}
251
252impl<'a> Iterator for DnaIterator<'a> {
253 type Item = Base;
254
255 fn next(&mut self) -> Option<Self::Item> {
256 while let Some(node) = self.stack.pop() {
257 match &**node {
258 Dna::Empty => return None,
259 Dna::Leaf(c) => return Some(*c),
260 Dna::TwoNode(node) => {
261 let (a, b) = &node.children;
262 self.stack.push(b);
263 self.stack.push(a);
264 }
265 Dna::ThreeNode(node) => {
266 let (a, b, c) = &node.children;
267 self.stack.push(c);
268 self.stack.push(b);
269 self.stack.push(a);
270 }
271 }
272 }
273
274 return None;
275 }
276}
277
278enum AddState {
279 One(DnaRef),
280 Two(DnaRef, DnaRef),
281}
282
283fn add_helper(lhs: DnaRef, rhs: DnaRef) -> AddState {
284 if lhs.depth() == rhs.depth() {
285 AddState::Two(lhs, rhs)
286 } else if lhs.depth() < rhs.depth() {
287 match &*rhs {
288 Dna::Empty => unreachable!(),
289 Dna::Leaf(_) => AddState::One(rhs),
290 Dna::TwoNode(node) => {
291 let (a, b) = &node.children;
292 match add_helper(lhs, a.clone()) {
293 AddState::One(x) => AddState::One(DnaRef::from_two_children(x, b.clone())),
294 AddState::Two(x, y) => {
295 AddState::One(DnaRef::from_three_children(x, y, b.clone()))
296 }
297 }
298 }
299 Dna::ThreeNode(node) => {
300 let (a, b, c) = &node.children;
301 match add_helper(lhs, a.clone()) {
302 AddState::One(x) => {
303 AddState::One(DnaRef::from_three_children(x, b.clone(), c.clone()))
304 }
305 AddState::Two(x, y) => AddState::Two(
306 DnaRef::from_two_children(x, y),
307 DnaRef::from_two_children(b.clone(), c.clone()),
308 ),
309 }
310 }
311 }
312 } else {
313 match &*lhs {
314 Dna::Empty => unreachable!(),
315 Dna::Leaf(_) => AddState::One(lhs.clone()),
316 Dna::TwoNode(node) => {
317 let (a, b) = &node.children;
318 match add_helper(b.clone(), rhs) {
319 AddState::One(x) => AddState::One(DnaRef::from_two_children(a.clone(), x)),
320 AddState::Two(x, y) => {
321 AddState::One(DnaRef::from_three_children(a.clone(), x, y))
322 }
323 }
324 }
325 Dna::ThreeNode(node) => {
326 let (a, b, c) = &node.children;
327 match add_helper(c.clone(), rhs) {
328 AddState::One(x) => {
329 AddState::One(DnaRef::from_three_children(a.clone(), b.clone(), x))
330 }
331 AddState::Two(x, y) => AddState::Two(
332 DnaRef::from_two_children(a.clone(), b.clone()),
333 DnaRef::from_two_children(x, y),
334 ),
335 }
336 }
337 }
338 }
339}
340
341impl Add for DnaRef {
342 type Output = Self;
343
344 fn add(self, other: Self) -> Self {
345 match add_helper(self, other) {
346 AddState::One(a) => a,
347 AddState::Two(a, b) => Self::from_two_children(a, b),
348 }
349 }
350}
351
352impl Index<usize> for DnaRef {
353 type Output = Base;
354
355 fn index(&self, n: usize) -> &Self::Output {
356 debug_assert!(n < self.len());
357
358 match &**self {
359 Dna::Empty => unreachable!(),
360 Dna::Leaf(c) => c,
361 Dna::TwoNode(node) => {
362 let (a, b) = &node.children;
363 if n < a.len() {
364 a.index(n)
365 } else {
366 b.index(n - a.len())
367 }
368 }
369 Dna::ThreeNode(node) => {
370 let (a, b, c) = &node.children;
371 if n < a.len() {
372 a.index(n)
373 } else if n < a.len() + b.len() {
374 b.index(n - a.len())
375 } else {
376 c.index(n - a.len() - b.len())
377 }
378 }
379 }
380 }
381}
382
383#[cfg(test)]
384mod tests {
385 use super::*;
386
387 #[test]
388 fn test_empty() {
389 let dna: DnaRef = DnaRef::new();
390 assert_eq!(dna.len(), 0);
391 }
392
393 #[test]
394 fn test_to_from_string() {
395 let dna: DnaRef = DnaRef::from_string("ICFP");
396 assert_eq!(dna.to_string(), "ICFP");
397 }
398
399 #[test]
400 fn test_index() {
401 let s = "ICFP";
402 let dna: DnaRef = DnaRef::from_string(s);
403 assert_eq!(dna[0], Base::I);
404 assert_eq!(dna[1], Base::C);
405 assert_eq!(dna[2], Base::F);
406 assert_eq!(dna[3], Base::P);
407 }
408
409 #[test]
410 fn test_add() {
411 let lhs = DnaRef::from_string("IIIC");
412 let rhs = DnaRef::from_string("PFFF");
413 assert_eq!((lhs + rhs).to_string(), "IIICPFFF");
414 }
415
416 #[test]
417 fn test_split() {
418 let dna = DnaRef::from_string("IIICPFFF");
419 let (lhs, rhs) = dna.split(4);
420 assert_eq!(lhs.to_string(), "IIIC");
421 assert_eq!(rhs.to_string(), "PFFF");
422 }
423}