SHARE
TWEET

sijin

a guest Aug 29th, 2008 648 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class CrazyBobBeust
  2.     {
  3.         public static void findAll(long max) {
  4.             Digit zero = new Digit(null, 0);
  5.             Digit one = zero.next;
  6.             Listener listener = new Listener();
  7.             for (int length = 1; length <= 10; length++) {
  8.                 if (find(one, zero, length, 0, max, listener)) return;
  9.             }
  10.  
  11.             listener.output();
  12.         }
  13.  
  14.         private static bool find(Digit start, Digit head, int remaining, long value, long max, Listener listener) {
  15.             for (Digit current = start; current != null; current = current.next) {
  16.                 long newValue = value + current.value;
  17.                 if (remaining == 1) {
  18.                     if (newValue > max) return true;
  19.                     listener.hear(newValue);
  20.                 }
  21.                 else {
  22.                     current.use();
  23.                     Digit newHead = (current == head) ? head.next : head;
  24.                     if (find(newHead, newHead, remaining - 1, newValue * 10, max, listener))
  25.                         return true;
  26.                     current.yield();
  27.                 }
  28.             }
  29.             return false;
  30.         }
  31.  
  32.         class Digit
  33.         {
  34.             public readonly int value;
  35.             public Digit previous;
  36.             public Digit next;
  37.             public Digit(Digit previous, int value) {
  38.                 this.value = value;
  39.                 this.previous = previous;
  40.                 if (value < 9) next = new Digit(this, value + 1);
  41.             }
  42.  
  43.             public void use() {
  44.                 if (previous != null) previous.next = next;
  45.                 if (next != null) next.previous = previous;
  46.             }
  47.  
  48.             public void yield() {
  49.                 if (previous != null) previous.next = this;
  50.                 if (next != null) next.previous = this;
  51.             }
  52.         }
  53.  
  54.         class Listener
  55.         {
  56.             private int _total = 0;
  57.             public void hear(long value) {
  58.                 ++_total;
  59.             }
  60.  
  61.             public void output() {
  62.                 Console.WriteLine("Total: {0}", _total);
  63.             }
  64.         }
  65.     }
RAW Paste Data
Top