Check if two integer iterators have the maximum distance of one

Check if two integer iterators have the maximum distance of one

Given the interface IntIterator defined in the following, implement the method isDistanceZeroOrOne(IntIterator a, IntIterator b) to return if the distance between a and b is at most one, where the distance is defined as the minimum number of modifications to make them equal to each other. Modifications can be: 1) change an int in a. 2) insert an int to a. 3) remove an int from a. For example, the method should return true for 1, 2, 2 and 1, 3, 2, 2.

  1. public class IteratorDistanceTest {
  2.  
  3.   interface IntIterator {
  4.     boolean hasNext();
  5.     int next();
  6.   }
  7.  
  8.   static boolean isDistanceZeroOrOne(IntIterator a, IntIterator b) {
  9.     boolean trying = false;
  10.     boolean changable = false;
  11.     boolean insertable = false;
  12.     boolean removable = false;
  13.     for(int aPrevious = 0, bPrevious = 0, aCurrent = 0, bCurrent = 0;
  14.         ; aPrevious = aCurrent, bPrevious = bCurrent) {
  15.       if(a.hasNext()) {
  16.         aCurrent = a.next();
  17.         if(b.hasNext()) { // a != null, b != null.
  18.           bCurrent = b.next();
  19.           if(trying) {
  20.             if(changable) {
  21.               if(aCurrent != bCurrent) {
  22.                 changable = false;
  23.               }
  24.             }
  25.             if(insertable) {
  26.               if(bCurrent != aPrevious) {
  27.                 insertable = false;
  28.               }
  29.             }
  30.             if(removable) {
  31.               if(aCurrent != bPrevious) {
  32.                 removable = false;
  33.               }
  34.             }
  35.             if(!changable && !insertable && !removable) {
  36.               return false;
  37.             }
  38.           } else if(aCurrent != bCurrent) {
  39.             // start trying all the possibilities.
  40.             trying = true;
  41.             changable = true;
  42.             insertable = true;
  43.             removable = true;
  44.           }
  45.         } else { // a != null, b == null.
  46.           if(trying) {
  47.             if(removable && aCurrent == bPrevious) {
  48.               return !a.hasNext();
  49.             } else {
  50.               return false;
  51.             }
  52.           } else { // remove a.
  53.             return !a.hasNext();
  54.           }
  55.         }
  56.       } else {
  57.         if(b.hasNext()) { // a == null, b != null.
  58.           bCurrent = b.next();
  59.           if(trying) {
  60.             if(insertable && bCurrent == aPrevious) {
  61.               return !b.hasNext();
  62.             } else {
  63.               return false;
  64.             }
  65.           } else { // insert b.
  66.             return !b.hasNext();
  67.           }
  68.         } else { // a == null, b == null.
  69.           // can only fulfill changable if we are trying.
  70.           return trying ? (changable ? true : false) : true;
  71.         }
  72.       }
  73.     }
  74.   }
  75.  
  76.   static IntIterator from(final int[] ints) {
  77.     return new IntIterator() {
  78.  
  79.       int i = 0;
  80.  
  81.       @Override
  82.       public boolean hasNext() {
  83.         return i < ints.length;
  84.       }
  85.  
  86.       @Override
  87.       public int next() {
  88.         return ints[i++];
  89.       }
  90.     };
  91.   }
  92.  
  93.   @Test
  94.   public void test() {
  95.     Assert.assertTrue(isDistanceZeroOrOne(
  96.         from(new int[] {})
  97.         , from(new int[] {})));
  98.     Assert.assertTrue(isDistanceZeroOrOne(
  99.         from(new int[] {1})
  100.         , from(new int[] {})));
  101.     Assert.assertTrue(isDistanceZeroOrOne(
  102.         from(new int[] {})
  103.         , from(new int[] {1})));
  104.     Assert.assertTrue(isDistanceZeroOrOne(
  105.         from(new int[] {1, 2})
  106.         , from(new int[] {1, 2})));
  107.     Assert.assertTrue(isDistanceZeroOrOne(
  108.         from(new int[] {1, 2, 3})
  109.         , from(new int[] {1, 3, 3})));
  110.     Assert.assertTrue(isDistanceZeroOrOne(
  111.         from(new int[] {1, 2})
  112.         , from(new int[] {1, 3})));
  113.     Assert.assertFalse(isDistanceZeroOrOne(
  114.         from(new int[] {1, 2})
  115.         , from(new int[] {1, 3, 2, 2})));
  116.     Assert.assertFalse(isDistanceZeroOrOne(
  117.         from(new int[] {1, 3, 2, 2})
  118.         , from(new int[] {1, 2})));
  119.     Assert.assertTrue(isDistanceZeroOrOne(
  120.         from(new int[] {1, 2, 2})
  121.         , from(new int[] {1, 3, 2, 2})));
  122.     Assert.assertTrue(isDistanceZeroOrOne(
  123.         from(new int[] {1, 3, 2, 2})
  124.         , from(new int[] {1, 2, 2})));
  125.     Assert.assertTrue(isDistanceZeroOrOne(
  126.         from(new int[] {1, 2, 2, 2})
  127.         , from(new int[] {1, 3, 2, 2})));
  128.     Assert.assertTrue(isDistanceZeroOrOne(
  129.         from(new int[] {1, 3, 2, 2})
  130.         , from(new int[] {1, 2, 2, 2})));
  131.     Assert.assertFalse(isDistanceZeroOrOne(
  132.         from(new int[] {1, 3, 2, 2, 4})
  133.         , from(new int[] {1, 2, 2, 2, 5})));
  134.     Assert.assertTrue(isDistanceZeroOrOne(
  135.         from(new int[] {1, 3, 2, 3, 4, 5})
  136.         , from(new int[] {1, 2, 3, 4, 5})));
  137.     Assert.assertTrue(isDistanceZeroOrOne(
  138.         from(new int[] {1, 2, 3, 4, 5})
  139.         , from(new int[] {1, 3, 2, 3, 4, 5})));
  140.     Assert.assertFalse(isDistanceZeroOrOne(
  141.         from(new int[] {2, 2, 2, 2, 1, 1, 1, 1})
  142.         , from(new int[] {1, 1, 1, 1, 2, 2, 2, 2})));
  143.     Assert.assertTrue(isDistanceZeroOrOne(
  144.         from(new int[] {1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1})
  145.         , from(new int[] {2, 1, 2, 1, 2, 1, 2, 1, 2, 1})));
  146.     Assert.assertFalse(isDistanceZeroOrOne(
  147.         from(new int[] {1, 1})
  148.         , from(new int[] {2, 1, 1, 1})));
  149.     Assert.assertFalse(isDistanceZeroOrOne(
  150.         from(new int[] {2, 1, 1, 1})
  151.         , from(new int[] {1, 1})));
  152.     Assert.assertTrue(isDistanceZeroOrOne(
  153.         from(new int[] {1, 2})
  154.         , from(new int[] {1, 2, 3})));
  155.     Assert.assertTrue(isDistanceZeroOrOne(
  156.         from(new int[] {1, 2, 3})
  157.         , from(new int[] {1, 2})));
  158.   }
  159. }

Post new comment

The content of this field is kept private and will not be shown publicly.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Lines and paragraphs break automatically.

More information about formatting options

To prevent automated spam submissions leave this field empty.