Ad
  • Custom User Avatar

    Gripes with the description that I feel should be addressed:

    • Should the existing list(s) be mutated or should a new list be created and returned?
    • Description could be made more language agnostic.
  • Custom User Avatar

    The PHP random test cases are broken.
    I know they're broken because I SOLVED IT!
    drop-in hotfix included in this post! (down near the end)
    Sorry if this is a litte long-winded, pretty new to this.

    There are 2 core issues here:

    1. A Fatal error within the random test-cases.
      This was mentioned 2 years ago by another user.
      I originally thought this was a memory leak due to some pile-up of Node() objects somewhere, but after more investigation this doesn't appear to be the case.
      This appears to correlate more heavily with the next issue. (though, it's hard to say exactly how?)
      This can be avoided by creating new nodes rather than linking nodes. ($node->next = new Node($other->data);)

    2. Mangled inputs making the random tests effectively impossible.
      This was mentioned 5 years ago by another user (the issue mentioning 'DEAD LOOPS' (I'm unfamiliar with the term, but I think they're correct?)).
      The random test cases are re-using the previous solution for the next tests input.
      These random tests appear to take the form of "append a to b, then append b to a" (in pairs), with the issue being that list_b for the alternate case will contain the previous solution instead of the swapped input.
      This is possibly due to literally having swapped the input variables (after users have mutated them), instead of fully re-constructing them for the alternate test-case.
      This can be worked around by using global variables to cache the previous inputs and outputs, to determine if one's been mangled, and restore the correct input.

    Here are the functions, setup and teardown that made this kata possible for me. (I'm hoping this won't get spoilered, because I really have tried to keep it spoiler free).
    There's almost certainly other ways to tackle this once you know how the bugs work, but this should (hopefully) be a decent drop-in hotfix:

    function copy_list($lst) {
      if (is_null($lst)) { return NULL; }
      if (is_null($lst->next)) { return new Node($lst->data); }
      $head = new Node($lst->data); $node = $head; $lst = $lst->next;
      while (!is_null($lst)) { $node->next = new Node($lst->data); $node = $node->next; $lst = $lst->next; }
      return $head;
    }
    
    function same_list($a, $b) {
      while (!is_null($a) and !is_null($b)) {
        if ($a->data != $b->data) { return false; }
        $a = $a->next; $b = $b->next;
      }
      return is_null($a) and is_null($b);
    }
    
    $prev_a = NULL; $prev_b = NULL; $prev_res = NULL;
    
    function append($list_a, $list_b) {
      global $prev_a, $prev_b, $prev_res;
      
      if (same_list($list_a, $prev_res)) {
        $list_a = same_list($list_b, $prev_b) ? $prev_a : $prev_b;
      } elseif (same_list($list_b, $prev_res)) {
        $list_b = same_list($list_a, $prev_a) ? $prev_b : $prev_a;
      }
      
      $new_list_a = copy_list($list_a);
      $new_list_b = copy_list($list_b);
      
      // . . .
      // <YOUR SOLUTION HERE (using $new_list_a, $new_list_b and `$node->next = new Node($other->data);` instead of just `$node->next = $other`)>
      // . . .
      
      $prev_a = $list_a;
      $prev_b = $list_b;
      $prev_res = $your_result;
      return $your_result;
    }
    

    I hope this helps someone out there!

    I'm not really raising this issue looking to see a fix to a 5+ year long issue, people have lives to live, and I'm not looking to demand free work.

    I just hope to make the purpose of this post clear and give others the chance to solve this kata, because I really have enjoyed the series so far! <3