Skip to content

Instantly share code, notes, and snippets.

@m1el
Last active June 19, 2020 09:28
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save m1el/a349b783c4be1a91acce0e8fb4ca5c9b to your computer and use it in GitHub Desktop.
ZERO = (lambda hf: (lambda ax: ax))
TWENTY_SIX = lambda vf: lambda vx: \
vf(vf(vf(vf(vf(vf(vf(vf(vf(vf(vf(vf(vf(vf(vf(vf(vf(vf(vf(vf(vf(vf(vf(vf(vf(vf(vx))))))))))))))))))))))))))
INCREMENT = (lambda jnum: lambda jf: lambda jx: jf(jnum(jf)(jx)))
Z_COMBINATOR = (lambda gf:
((lambda gx: gf(lambda gy: gx(gx)(gy)))
(lambda gx: gf(lambda gy: gx(gx)(gy)))))
TRUE = (lambda bx: lambda by: bx)
FALSE = (lambda cx: lambda cy: cy)
IS_ZERO = (lambda mnum:
mnum(lambda mx:
(lambda cx: lambda cy: cy))
((lambda bx: lambda by: bx)))
IS_NIL = (lambda tx: tx(lambda ta: lambda tb: FALSE))
NODE_VALUE = (lambda qx:
qx(lambda qa:
(lambda qb: qa)))
NODE_NEXT = (lambda rx:
rx(lambda ra:
(lambda rb: rb)))
CHURCH_LENGTH = (Z_COMBINATOR
(lambda recurse: lambda llist:
(IS_NIL(llist)
(lambda ua: ZERO)
(lambda ua: INCREMENT(recurse(NODE_NEXT(llist)))))
(ZERO)))
NTH_ELEMENT = (lambda index: lambda llist:
NODE_VALUE
(index(NODE_NEXT)(llist)))
COUNT_CHARS = (Z_COMBINATOR
(lambda recurse: lambda llist: lambda char:
(IS_NIL(llist)
(lambda za: ZERO)
(lambda za:
(EQUALS(NODE_VALUE(llist))(char))
(INCREMENT(recurse(NODE_NEXT(llist))(char)))
(recurse(NODE_NEXT(llist))(char)))
(ZERO))))
DECREMENT = (lambda kn: lambda kf: lambda kx:
kn(lambda kg: lambda kh: kh(kg(kf)))
(lambda ku: kx)
(lambda ku: ku))
AND = (lambda ex: lambda ey:
ex
(ey(TRUE)(FALSE))
(FALSE))
SUB = (lambda la: lambda lb: lb(DECREMENT)(la))
EQUALS = (lambda oa: lambda ob:
AND
(IS_ZERO(SUB(oa)(ob)))
(IS_ZERO(SUB(ob)(oa))))
def to_church_number(xx):
xx = ord(xx) - ord('a')
def tmp(f):
def applier(x):
for _ in range(xx):
x = f(x)
return x
return applier
return tmp
#def to_church_number(adx):
# return ((lambda ff:
# ff(ff))(lambda abf:
# lambda abn:
# ZERO
# if abn == 0 else
# INCREMENT(((lambda ff:
# ff(ff))(abf))(abn-1))))(ord(adx)-ord("a"))
def to_church_list(source):
return (Z_COMBINATOR
(lambda recurse: lambda acl:
(lambda px: (lambda bx: lambda by: bx))
if acl==[] else
(lambda sx:
(lambda sy:
(lambda sp:
(sp(sx)(sy)))))
(acl[0])
(recurse(acl[1:])))) \
(source)
def outer(words):
[first, second] = words.split()
first = to_church_list(list(map(to_church_number,list(first))))
second = to_church_list(list(map(to_church_number,list(second))))
EQUAL_LENGTH = (lambda a: lambda b:
EQUALS
(CHURCH_LENGTH(a))
(CHURCH_LENGTH(b)))
EQUAL_FIRST_LAST = (lambda a: lambda b:
AND
(EQUALS
(NTH_ELEMENT(ZERO)(a))
(NTH_ELEMENT(ZERO)(b)))
(EQUALS
(NTH_ELEMENT(DECREMENT(CHURCH_LENGTH(a)))(a))
(NTH_ELEMENT(DECREMENT(CHURCH_LENGTH(b)))(b))))
IS_PERMUTATION = (
Z_COMBINATOR
(lambda recurse: lambda a: lambda b: lambda char:
((EQUALS(char)(ZERO))
(lambda aaa: TRUE)
(lambda aaa:
(AND
(recurse(a)(b)(DECREMENT(char)))
(EQUALS
(COUNT_CHARS(a)(char))
(COUNT_CHARS(b)(char)))))
(ZERO))))
return (lambda a: lambda b:
EQUAL_LENGTH(a)(b)
((EQUAL_FIRST_LAST(a)(b))
((IS_PERMUTATION(a)(b)(TWENTY_SIX))
(TRUE)
(FALSE))
(FALSE))
(FALSE)) \
(first) \
(second)
assert(outer("abc cba")(True)(False) == False)
assert(outer("aaa aab")(True)(False) == False)
assert(outer("abc abc")(True)(False) == True)
assert(outer("acbbbc abcbbc")(True)(False) == True)
assert(outer("test test")(True)(False) == True)
assert(outer("test tset")(True)(False) == True)
assert(outer("aaaa aaaa")(True)(False) == True)
print("tests ok")
# words = input("Enter words: ")
# result = outer(words)
# out = result("Correct")("Incorrect")
# print(out)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment