A linked list challenge

list.rb

# Challenge:
#
# Given a linked list of items, reorder them such that
# the items from the beginning and end are interleaved.
#
# Do it in linear time
#   (number of operations is proportional to the size of the list)
# Do it in constant memory
#   (number of objects allocated and methods called does not change
#   regardless of how big the list is)

# Pseudocode Example:
#   list =    ('a', 'b', 'c', 'd', 'e')
#   zip_ends(list)
#   list # => ('a', 'e', 'b', 'd', 'c')


class List
  def self.for(*data)
    data.reverse.inject(nil) { |head, datum| new datum, head }
  end

  attr_accessor :datum, :link

  def initialize(datum, link)
    @datum, @link = datum, link
  end

  def inspect
    inspected, crnt, seen, cycle = 'List.for(', self, {}, false
    while crnt && !cycle
      inspected << crnt.datum.inspect << ', '
      cycle      = seen[crnt]
      seen[crnt] = true
      crnt       = crnt.link
    end
    inspected.chomp! ', '
    inspected << '...' if cycle
    inspected << ')'
    inspected
  end

  def ==(other)
    self.class == other.class && datum == other.datum && link == other.link
  end
end



# n operations
def size(list)
  return 0 unless list
  size = 1
  while list.link
    size += 1
    list = list.link
  end
  size
end

# eg ("a", "b", "c", "d") becomes ("a", "b") and ("c", "d")
# n operations
def cut_at(list, n)
  (n-1).times { list &&= list.link }
  return list if list.nil?
  tail = list.link
  list.link = nil
  tail
end

# reverses in place
# n operations
def reverse!(list)
  return list if list.nil?
  predecessor = nil
  loop do
    successor, list.link = list.link, predecessor
    return list if successor.nil?
    predecessor, list = list, successor
  end
end


# performs in pace
# O(n) (where n is max(size(left), size(right)))
def interleave!(parent, left, right)
  while left && right
    next_left, next_right = left.link, right.link

    parent.link = left
    parent      = left

    parent.link = right
    parent      = right

    left, right = next_left, next_right
  end
end


# linear time (2.5n iterations = O(n))
# no memory (interpreted as "constant memory")
def zip_ends(list)
  return list if list.nil?
  size  = size(list)             # n   iterations
  half  = cut_at(list, size/2)   # n/2 iterations
  right = reverse!(half)         # n/2 iterations
  interleave!(list, list, right) # n/2 iterations
  list
end




require 'rspec/autorun'

RSpec.describe List do
  it 'has datum and a link' do
    list = List.new 'a', 123
    expect(list.datum).to eq 'a'
    expect(list.link).to eq 123
  end

  specify '.for constructs lists' do
    list = List.for('a', 'b', 'c')
    expect( list.datum           ).to eq 'a'
    expect( list.link.datum      ).to eq 'b'
    expect( list.link.link.datum ).to eq 'c'
    expect( list.link.link.link  ).to eq nil
  end

  describe 'inspect' do
    it 'inspects like an invocation of List.for' do
      # uhm, what about a null node?
      # expect(List.for().inspect        ).to eq 'nil'
      expect(List.for("a").inspect     ).to eq 'List.for("a")'
      expect(List.for("a", "b").inspect).to eq 'List.for("a", "b")'
    end

    it 'uses an elipsis when it encounters a cycle' do
      c = List.new 'c', nil
      b = List.new 'b', c
      a = List.new 'a', b

      c.link = a
      expect(a.inspect).to eq 'List.for("a", "b", "c", "a"...)'
      expect(b.inspect).to eq 'List.for("b", "c", "a", "b"...)'
      expect(c.inspect).to eq 'List.for("c", "a", "b", "c"...)'

      c.link = b
      expect(a.inspect).to eq 'List.for("a", "b", "c", "b"...)'
      expect(b.inspect).to eq 'List.for("b", "c", "b"...)'
      expect(c.inspect).to eq 'List.for("c", "b", "c"...)'
    end
  end

  describe '==' do
    it 'is not equal if compared to a non-list' do
      list = List.new('a', nil)
      expect(list).to_not eq nil
      expect(list).to_not eq 'a'
      expect(list).to_not eq ['a', nil]
      expect(list).to_not eq datum: 'a', link: nil
    end

    it 'is not equal if its data is not equal' do
      a = List.for('a')
      b = List.for('b')
      expect(a).to_not eq b
      expect(b).to_not eq a
    end

    it 'is not equal if its links are not equal' do
      ab = List.for('a', 'b')
      ac = List.for('b', 'c')
      expect(ab).to_not eq ac
      expect(ac).to_not eq ab
    end

    it 'is equal otherwise' do
      ab = List.for('a', 'b')
      ac = List.for('b', 'c')
      expect(ab).to_not eq ac
      expect(ac).to_not eq ab
    end
  end
end

RSpec.describe 'size returns the size of a list' do
  example '0 for ()' do
    expect(size List.for()).to eq 0
  end

  example '1 for ("a")' do
    expect(size List.for("a")).to eq 1
  end

  example '2 for ("a", "b")' do
    expect(size List.for("a", "b")).to eq 2
  end
end



RSpec.describe 'reverse reverses a list' do
  def assert_reverses(from:, to:)
    expect(reverse! List.for(*from)).to eq List.for(*to)
  end

  example '() goes to ()' do
    assert_reverses from: [], to: []
  end

  example '("a") goes to ("a")' do
    assert_reverses from: ['a'], to: ['a']
  end

  example '("a", "b") goes to ("b", "a")' do
    assert_reverses from: ["a", "b"], to: ["b", "a"]
  end

  example '("a", "b", "c") goes to ("c", "b", "a")' do
    assert_reverses from: ["a", "b", "c"], to: ["c", "b", "a"]
  end

  it 'is in place' do
    b = List.new 'b', nil
    a = List.new 'a', b
    reverse! a
    expect(a).to equal a
    expect(b).to equal b
  end
end


RSpec.describe 'zip_ends' do
  it 'modifies the list' do
    c = List.new("c", nil)
    b = List.new("b", c)
    a = List.new("a", b)
    zip_ends a
    expect(a).to equal a
    expect(b).to equal b
    expect(c).to equal c
  end

  describe 'interleaves the nodes from both ends' do
    def assert_zips(from:, to:)
      expect(zip_ends List.for(*from)).to eq List.for(*to)
    end

    example '() goes to ()' do
      assert_zips from: [], to: []
    end

    example '("a") goes to ("a")' do
      assert_zips from: ['a'], to: ['a']
    end

    example '("a", "b") goes to ("a", "b")' do
      assert_zips from: ['a', 'b'], to: ['a', 'b']
    end

    example '("a", "b", "c") goes to ("a", "c", "b")' do
      assert_zips from: ['a', 'b', 'c'], to: ['a', 'c', 'b']
    end

    example '("a", "b", "c", "d") goes to ("a", "d", "b", "c")' do
      assert_zips from: ['a', 'b', 'c', 'd'], to: ['a', 'd', 'b', 'c']
    end

    example '("a", "b", "c", "d", "e") goes to ("a", "e", "b", "d", "c")' do
      assert_zips from: ['a', 'b', 'c', 'd', 'e'], to: ['a', 'e', 'b', 'd', 'c']
    end
  end
end