19
\$\begingroup\$

As you may very well know python has lists. As you might not know these lists can contain themselves.

a = []
a.append(a)

Python 2

Python 3

These are cool and there are lots of interesting things you can do with them, however you cannot compare them.

a = []
a.append(a)
b = []
b.append(b)
a == b

Python 2

Python 3

Task

Your job is to write a function in Python (or any language that can handle python objects directly) that will take two lists that may contain themselves and compare them.

Two lists are equal if they are the same length and there does not exist sequence of numbers such that indexing both of the lists by that sequence results in two objects that are not equal under this definition of equal. All non-list objects contained in a list will be python integers for simplicity and should be compared with python's builtin equality for integers.

Your program should not rely on the recursion depth of python to determine if a list is infinitely deep. That is:

def isInfinite(a,b):
 try:
  a==b
  return False
 except RunTimeError:
  return True

Is not a valid way of determining if two lists are self referential.

Testcases

Assumes you define a function equal

a = []
a.append(a)
b = []
b.append(b)
print(equal(a,b))

True

a = []
b = []
a.append(b)
b.append(a)
print(equal(a,b))

True

a = []
b = []
a.append(1)
a.append(b)
b.append(1)
b.append(a)
print(equal(a,b))

True

a = []
a.append(a)
b = [a]
print(equal(a,b))

True

a = []
b = []
c = []
a.append(b)
b.append(c)
c.append(a)
equal(a,b)

True

a=[1,[2]]
b=[1,[2,[1]]]
a[1].append(a)
b[1][1].append(b[1])

True

a = []
a.append(a)
b = [1]
b.append(a)
c = [1]
c.append([c])
print(equal(b,c))

False

a = []
b = []
a.append(1)
a.append(b)
b.append(a)
b.append(1)
print(equal(a,b))

False

a = []
b = []
a.append(a)
b.append(b)
b.append(b)
print f(a,b)

False
\$\endgroup\$
  • 17
    \$\begingroup\$ As a side note to potential voters: Note that generally language specific challenges are frowned upon except for in certain circumstances (like tasks that are only interesting in certain languages). IMO, this is a wonderful example of a language-specific challenge. \$\endgroup\$ – DJMcMayhem Apr 20 '17 at 18:25
  • \$\begingroup\$ @WheatWizard That's not exactly enough -- the nested lists need to also be the same lengths as well. \$\endgroup\$ – xnor Apr 20 '17 at 19:09
  • \$\begingroup\$ @WheatWizard You actually can compare them. In Python, you only get a "recursion limited exceeded" if they aren't equal. tio.run/nexus/… \$\endgroup\$ – mbomb007 Apr 20 '17 at 19:10
  • \$\begingroup\$ @mbomb007 Thats because python by default compares the references. If you have two identical objects that have different references it fails, hence the challenge. \$\endgroup\$ – Sriotchilism O'Zaic Apr 20 '17 at 19:12
  • 2
    \$\begingroup\$ Can you extend this challenge to all languages where lists can contain themselves? \$\endgroup\$ – CalculatorFeline Jul 12 '17 at 21:38
9
\$\begingroup\$

Python 2, 94 bytes

g=lambda c,*p:lambda a,b:c in p or all(map(g((id(a),id(b)),c,*p),a,b))if a>[]<b else a==b
g(0)

Try it online!

An improvement on isaacg's very clever solution of storing the id pairs of lists being processed and declaring them equal if the same comparison comes up on a lower level.

The recursive step all(map(...,a,b)) says that a and b are equal if all corresponding pair of elements in them are equal. This works nicely to reject unequal-length because map pads the shortest list with None, unlike zip which truncates. Since none of the actual lists contain None, these padded lists will always be rejected.

\$\endgroup\$
  • \$\begingroup\$ What is the purpose of the , after the c? \$\endgroup\$ – Sriotchilism O'Zaic Apr 20 '17 at 21:01
  • \$\begingroup\$ It makes it a tuple. \$\endgroup\$ – mbomb007 Apr 20 '17 at 21:02
  • \$\begingroup\$ a=[];a+=[a,1];b=[];b+=[b,2];f(a,b) overflows the stack, and a=[1];b=[2];f(a,b);f(a,b) looks like a reusability problem. \$\endgroup\$ – Anders Kaseorg Jul 12 '17 at 18:09
  • \$\begingroup\$ @AndersKaseorg I see, mutating the list was asking for trouble. I think this fixes it. \$\endgroup\$ – xnor Jul 12 '17 at 23:35
  • 1
    \$\begingroup\$ @AndersKaseorg And I see you wrote basically the same function-in-a-function solution. There's a 95-byte solution without that: f=lambda a,b,p=[0]:p[0]in p[1:]or all(map(f,a,b,[[(id(a),id(b))]+p]*len(a)))if a>[]<b else a==b. Maybe there's a nicer way to handle the map. \$\endgroup\$ – xnor Jul 12 '17 at 23:55
5
\$\begingroup\$

Python, 233 218 197 217 bytes

d=id
def q(a,b,w):
 w[(d(a),d(b))]=0
 if d(a)==d(b):return 1
 if(a>[]and[]<b)-1:return a==b
 if len(a)!=len(b):return 0
 for x,y in zip(a,b):
  if((d(x),d(y))in w or q(x,y,w))-1:return 0
 return 1
lambda a,b:q(a,b,{})

The anonymous function on the last line performs the desired function.

This is still in the process of being golfed, I just wanted to show that this is possible.

Essentially, we put an entry in w if we're working on a given check. Two things are equal if they're the same object, if they're not lists, and they're equal, or if all their elements are either equal or being worked on.

\$\endgroup\$
  • \$\begingroup\$ Can't you use a>[] instead of i(a,list)? \$\endgroup\$ – mbomb007 Apr 20 '17 at 19:48
  • \$\begingroup\$ @mbomb007 This was written before the "Everything is lists or ints" rule was added. Will update. \$\endgroup\$ – isaacg Apr 20 '17 at 19:59
  • \$\begingroup\$ You can use a>[]<b and len(a)-len(b) \$\endgroup\$ – mbomb007 Apr 20 '17 at 20:03
  • \$\begingroup\$ @ETHproductions Oh, his byte count is wrong. That's why \$\endgroup\$ – mbomb007 Apr 20 '17 at 20:13
  • \$\begingroup\$ Can d(a)==d(b) be a is b? That would cut two uses of d. \$\endgroup\$ – xnor Apr 20 '17 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.