Project P139
Tolerance grouping
Measurements the same within a tolerance - reflexive and symmetric but not transitive - grouped by first match, which depends on the order, and by chaining, which joins values far apart; and records matched on name, email or phone that chain the same way.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-17
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
Measurements count as the same when they differ by at most a tolerance. Grouping them by that rule gives different answers depending on how the grouping is done and in what order the values come.
main.eml- the menu, the values, the relation's properties, grouping in this order and in every order, records matched on any of three fields, and the settingsnear.eml- the relation and its properties, first match and chaining, every order, and the records
How each part works:
- Values are whole tenths of a millimetre; the default ones are 10.0, 10.3, 10.6, 10.9, 11.2 and 13.0 with a tolerance of 0.3.
- As in the corpus case
tolerance-equality-grouping, the relation is reflexive and symmetric every time, and not transitive: 10.0 ~ 10.3 and 10.3 ~ 10.6, but not 10.0 ~ 10.6. So it does not split the values into groups at all. - First match puts each value in the first group whose first value is near it: over the 720 orders it gives 6 different groupings, of 3 or 4 groups, and never puts values more than twice the tolerance apart. Chaining joins every group a value is near: the same grouping in every order, and 10.0 and 11.2, 1.2 mm apart, in one group.
- As in the corpus case
match-predicate-not-transitive, four records match when they share a name, an email or a phone: r0 ~ r1 ~ r2 ~ r3, while r0 and r3 share nothing. First match gives 3 different answers over the 24 orders; chaining puts all four together.
What is checked: menu choices 1 to 8; 2 to 7 values from 0.0 to 99.9 with at most one decimal; a tolerance from 0.0 to 5.0. An empty answer cancels.
Sessions: sessions/basic.in gives: - the values, the properties, this order, every order and the records; - the same values in another order, grouped again; - a tolerance of 1.0 mm, and every order.
sessions/bad-input.in gives: - menu choices 0 and x; - values: a cancel, one value, eight, 1.23, x, 100.0 and 1.; - tolerances: a cancel, 5.1 and -1, then 0.0: every order and the properties, with no chain at all.
Built on the verified corpus cases tolerance-equality-grouping (close enough to be the same is not an equivalence) and match-predicate-not-transitive (a record match of three clauses that does not chain).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Tolerance grouping ==
Measurements count as the same when they differ by at most a tolerance; grouping them by it.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 0
Pick a number from 1 to 8.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> x
Pick a number from 1 to 8.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 6
Values in mm with one decimal, such as 10.0 10.3 12.5 (2 to 7 values, 0.0 to 99.9).
values>
Cancelled.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 6
Values in mm with one decimal, such as 10.0 10.3 12.5 (2 to 7 values, 0.0 to 99.9).
values> 1.0
Type 2 to 7 values.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 6
Values in mm with one decimal, such as 10.0 10.3 12.5 (2 to 7 values, 0.0 to 99.9).
values> 1 2 3 4 5 6 7 8
Type 2 to 7 values.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 6
Values in mm with one decimal, such as 10.0 10.3 12.5 (2 to 7 values, 0.0 to 99.9).
values> 1.23
Each value is a number from 0.0 to 99.9, with at most one decimal.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 6
Values in mm with one decimal, such as 10.0 10.3 12.5 (2 to 7 values, 0.0 to 99.9).
values> x
Each value is a number from 0.0 to 99.9, with at most one decimal.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 6
Values in mm with one decimal, such as 10.0 10.3 12.5 (2 to 7 values, 0.0 to 99.9).
values> 100.0
Each value is a number from 0.0 to 99.9, with at most one decimal.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 6
Values in mm with one decimal, such as 10.0 10.3 12.5 (2 to 7 values, 0.0 to 99.9).
values> 1.
Each value is a number from 0.0 to 99.9, with at most one decimal.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 7
tolerance in mm (0.0 to 5.0)>
Cancelled.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 7
tolerance in mm (0.0 to 5.0)> 5.1
Type a tolerance from 0.0 to 5.0, with at most one decimal.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 7
tolerance in mm (0.0 to 5.0)> -1
Type a tolerance from 0.0 to 5.0, with at most one decimal.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 7
tolerance in mm (0.0 to 5.0)> 0
Tolerance now 0.0 mm.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 4
Every order of the 6 values, 720 orders:
first match: 1 grouping, of 6 groups
chaining: 1 grouping, the widest group spanning 0.0 mm
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 2
reflexive, a ~ a: 6 of 6 values
symmetric, a ~ b as b ~ a: 36 of 36 pairs
transitive, a ~ b ~ c gives a ~ c: 0 of 0 chains
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 8
Bye.
What was typed (27 lines)
0
x
6
6
1.0
6
1 2 3 4 5 6 7 8
6
1.23
6
x
6
100.0
6
1.
7
7
5.1
7
-1
7
0
4
2
8
basic
interpreter: byte-equal== Tolerance grouping ==
Measurements count as the same when they differ by at most a tolerance; grouping them by it.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 1
Values, in mm, in this order: 10.0 10.3 10.6 10.9 11.2 13.0
Two values are the same when they differ by at most 0.3 mm.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 2
reflexive, a ~ a: 6 of 6 values
symmetric, a ~ b as b ~ a: 36 of 36 pairs
transitive, a ~ b ~ c gives a ~ c: 0 of 6 chains
Not transitive: so it does not split the values into groups, and 'the group of x' names nothing.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 3
first match: {10.0 10.3} {10.6 10.9} {11.2} {13.0}
chaining: {10.0 10.3 10.6 10.9 11.2} {13.0}
Chaining puts values 1.2 mm apart in one group, through the ones between.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 4
Every order of the 6 values, 720 orders:
first match: 6 different groupings, from 3 to 4 groups
chaining: 1 grouping, the widest group spanning 1.2 mm
First match depends on the order the values come in; chaining does not, and joins values far apart instead.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 5
Records, matching when they share a name, an email or a phone:
r0 Pat Lee pat@home 555-0101
r1 Pat Lee kim@work 555-0199
r2 Kim Ito kim@work 555-0123
r3 Kim Ito Jr kj@mail 555-0123
r0 r1 r2 r3
r0 1 1 0 0
r1 1 1 1 0
r2 0 1 1 1
r3 0 0 1 1
Every order of the 4 records, 24 orders: first match gives 3 different answers, chaining 1.
Chaining puts r0 and r3 together, and they share nothing: the match is not transitive either.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 6
Values in mm with one decimal, such as 10.0 10.3 12.5 (2 to 7 values, 0.0 to 99.9).
values> 11.2 10.0 13.0 10.6 10.9 10.3
Values now 11.2 10.0 13.0 10.6 10.9 10.3.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 3
first match: {10.0 10.3} {10.6} {10.9 11.2} {13.0}
chaining: {10.0 10.3 10.6 10.9 11.2} {13.0}
Chaining puts values 1.2 mm apart in one group, through the ones between.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 7
tolerance in mm (0.0 to 5.0)> 1.0
Tolerance now 1.0 mm.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 4
Every order of the 6 values, 720 orders:
first match: 3 different groupings, from 2 to 3 groups
chaining: 1 grouping, the widest group spanning 1.2 mm
First match depends on the order the values come in; chaining does not, and joins values far apart instead.
1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit
choice> 8
Bye.
What was typed (12 lines)
1
2
3
4
5
6
11.2 10.0 13.0 10.6 10.9 10.3
3
7
1.0
4
8
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P139 tolerance grouping: the values, the relation's properties, grouping
# in one order and in every order, records matched on any of three fields,
# and the settings.
import near
def plain(s):
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def pad(s, n):
s => out
while len(out) < n:
out + " " => out
return out
def mm(v):
return str(int(v / 10)) + "." + str(v % 10)
def list_text(vs):
"" => out
for v in vs:
if out != "":
out + " " => out
out + mm(v) => out
return out
def groups_text(gs):
"" => out
for g in gs:
if out != "":
out + " " => out
out + "{" + list_text(g) + "}" => out
return out
def show(vs, tol):
("Values, in mm, in this order: " + list_text(vs)) ^0
("Two values are the same when they differ by at most " + mm(tol) + " mm.") ^0
def props(vs, tol):
near.properties(vs, tol) => p
(" reflexive, a ~ a: " + str(p[1]) + " of " + str(p[0]) + " values") ^0
(" symmetric, a ~ b as b ~ a: " + str(p[3]) + " of " + str(p[2]) + " pairs") ^0
(" transitive, a ~ b ~ c gives a ~ c: " + str(p[5]) + " of " + str(p[4]) + " chains") ^0
if p[5] < p[4]:
"Not transitive: so it does not split the values into groups, and 'the group of x' names nothing." ^0
def this_order(vs, tol):
near.first_match(vs, tol) => a
near.canonical(near.chaining(vs, tol)) => c
(" first match: " + groups_text(near.canonical(a))) ^0
(" chaining: " + groups_text(c)) ^0
0 => span
for g in c:
if g[len(g) - 1] - g[0] > span:
g[len(g) - 1] - g[0] => span
if span > tol:
(" Chaining puts values " + mm(span) + " mm apart in one group, through the ones between.") ^0
def every(vs, tol):
near.every_order(vs, tol) => r
("Every order of the " + str(len(vs)) + " values, " + str(r[0]) + " orders:") ^0
if r[1] == 1:
(" first match: 1 grouping, of " + str(r[2]) + " groups") ^0
else:
(" first match: " + str(r[1]) + " different groupings, from " + str(r[2]) + " to " + str(r[3]) + " groups") ^0
(" chaining: " + str(r[4]) + " grouping, the widest group spanning " + mm(r[5]) + " mm") ^0
if r[1] > 1:
"First match depends on the order the values come in; chaining does not, and joins values far apart instead." ^0
def show_records():
near.records() => rs
"Records, matching when they share a name, an email or a phone:" ^0
for k in [0:3]:
(" r" + str(k) + " " + pad(rs[k][0], 11) + pad(rs[k][1], 10) + rs[k][2]) ^0
" r0 r1 r2 r3" => head
head ^0
for i in [0:3]:
" r" + str(i) => line
for j in [0:3]:
if near.same(rs[i], rs[j]):
line + " 1" => line
else:
line + " 0" => line
line ^0
near.record_orders() => r
("Every order of the 4 records, " + str(r[0]) + " orders: first match gives " + str(r[1]) + " different answers, chaining " + str(r[2]) + ".") ^0
"Chaining puts r0 and r3 together, and they share nothing: the match is not transitive either." ^0
def set_values(vs):
"Values in mm with one decimal, such as 10.0 10.3 12.5 (2 to 7 values, 0.0 to 99.9)." ^0
plain(input("values> ")) => t
if t == "":
"Cancelled." ^0
return vs
[] => out
"" => w
for c in t + " ":
if c == " ":
if w != "":
parse(w) => v
if v < 0:
"Each value is a number from 0.0 to 99.9, with at most one decimal." ^0
return vs
out + [v] => out
"" => w
else:
w + c => w
if len(out) < 2 or len(out) > 7:
"Type 2 to 7 values." ^0
return vs
("Values now " + list_text(out) + ".") ^0
return out
def parse(w):
# tenths, or -1
"" => a
"" => b
False => dot
for c in w:
if c == "." and not dot:
True => dot
elif c >= "0" and c <= "9":
if dot:
b + c => b
else:
a + c => a
else:
return 0 - 1
if len(a) == 0 or len(a) > 2 or len(b) > 1:
return 0 - 1
if dot and len(b) == 0:
return 0 - 1
10 * int(a) => v
if len(b) == 1:
v + int(b) => v
return v
def set_tol(tol):
plain(input("tolerance in mm (0.0 to 5.0)> ")) => t
if t == "":
"Cancelled." ^0
return tol
parse(t) => v
if v < 0 or v > 50:
"Type a tolerance from 0.0 to 5.0, with at most one decimal." ^0
return tol
("Tolerance now " + mm(v) + " mm.") ^0
return v
[100, 103, 106, 109, 112, 130] => vs
3 => tol
"== Tolerance grouping ==" ^0
"Measurements count as the same when they differ by at most a tolerance; grouping them by it." ^0
True => running
while running:
"" ^0
"1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit" ^0
plain(input("choice> ")) => choice
if choice == "1":
show(vs, tol)
elif choice == "2":
props(vs, tol)
elif choice == "3":
this_order(vs, tol)
elif choice == "4":
every(vs, tol)
elif choice == "5":
show_records()
elif choice == "6":
set_values(vs) => vs
elif choice == "7":
set_tol(tol) => tol
elif choice == "8":
False => running
else:
"Pick a number from 1 to 8." ^0
"Bye." ^0
Python projection (main.py)
import near
def plain(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def pad(s, n):
out = s
while len(out) < n:
out = out + " "
return out
def mm(v):
return str(int(v / 10)) + "." + str(v % 10)
def list_text(vs):
out = ""
for v in vs:
if out != "":
out = out + " "
out = out + mm(v)
return out
def groups_text(gs):
out = ""
for g in gs:
if out != "":
out = out + " "
out = out + "{" + list_text(g) + "}"
return out
def show(vs, tol):
print("Values, in mm, in this order: " + list_text(vs))
print("Two values are the same when they differ by at most " + mm(tol) + " mm.")
def props(vs, tol):
p = near.properties(vs, tol)
print(" reflexive, a ~ a: " + str(p[1]) + " of " + str(p[0]) + " values")
print(" symmetric, a ~ b as b ~ a: " + str(p[3]) + " of " + str(p[2]) + " pairs")
print(" transitive, a ~ b ~ c gives a ~ c: " + str(p[5]) + " of " + str(p[4]) + " chains")
if p[5] < p[4]:
print("Not transitive: so it does not split the values into groups, and 'the group of x' names nothing.")
def this_order(vs, tol):
a = near.first_match(vs, tol)
c = near.canonical(near.chaining(vs, tol))
print(" first match: " + groups_text(near.canonical(a)))
print(" chaining: " + groups_text(c))
span = 0
for g in c:
if g[len(g) - 1] - g[0] > span:
span = g[len(g) - 1] - g[0]
if span > tol:
print(" Chaining puts values " + mm(span) + " mm apart in one group, through the ones between.")
def every(vs, tol):
r = near.every_order(vs, tol)
print("Every order of the " + str(len(vs)) + " values, " + str(r[0]) + " orders:")
if r[1] == 1:
print(" first match: 1 grouping, of " + str(r[2]) + " groups")
else:
print(" first match: " + str(r[1]) + " different groupings, from " + str(r[2]) + " to " + str(r[3]) + " groups")
print(" chaining: " + str(r[4]) + " grouping, the widest group spanning " + mm(r[5]) + " mm")
if r[1] > 1:
print("First match depends on the order the values come in; chaining does not, and joins values far apart instead.")
def show_records():
rs = near.records()
print("Records, matching when they share a name, an email or a phone:")
for k in range(0, 4):
print(" r" + str(k) + " " + pad(rs[k][0], 11) + pad(rs[k][1], 10) + rs[k][2])
head = " r0 r1 r2 r3"
print(head)
for i in range(0, 4):
line = " r" + str(i)
for j in range(0, 4):
if near.same(rs[i], rs[j]):
line = line + " 1"
else:
line = line + " 0"
print(line)
r = near.record_orders()
print("Every order of the 4 records, " + str(r[0]) + " orders: first match gives " + str(r[1]) + " different answers, chaining " + str(r[2]) + ".")
print("Chaining puts r0 and r3 together, and they share nothing: the match is not transitive either.")
def set_values(vs):
print("Values in mm with one decimal, such as 10.0 10.3 12.5 (2 to 7 values, 0.0 to 99.9).")
t = plain(input("values> "))
if t == "":
print("Cancelled.")
return vs
out = []
w = ""
for c in t + " ":
if c == " ":
if w != "":
v = parse(w)
if v < 0:
print("Each value is a number from 0.0 to 99.9, with at most one decimal.")
return vs
out = out + [v]
w = ""
else:
w = w + c
if len(out) < 2 or len(out) > 7:
print("Type 2 to 7 values.")
return vs
print("Values now " + list_text(out) + ".")
return out
def parse(w):
a = ""
b = ""
dot = False
for c in w:
if c == "." and not dot:
dot = True
elif c >= "0" and c <= "9":
if dot:
b = b + c
else:
a = a + c
else:
return 0 - 1
if len(a) == 0 or len(a) > 2 or len(b) > 1:
return 0 - 1
if dot and len(b) == 0:
return 0 - 1
v = 10 * int(a)
if len(b) == 1:
v = v + int(b)
return v
def set_tol(tol):
t = plain(input("tolerance in mm (0.0 to 5.0)> "))
if t == "":
print("Cancelled.")
return tol
v = parse(t)
if v < 0 or v > 50:
print("Type a tolerance from 0.0 to 5.0, with at most one decimal.")
return tol
print("Tolerance now " + mm(v) + " mm.")
return v
vs = [100, 103, 106, 109, 112, 130]
tol = 3
print("== Tolerance grouping ==")
print("Measurements count as the same when they differ by at most a tolerance; grouping them by it.")
running = True
while running:
print("")
print("1) values 2) properties 3) this order 4) every order 5) records 6) new values 7) tolerance 8) quit")
choice = plain(input("choice> "))
if choice == "1":
show(vs, tol)
elif choice == "2":
props(vs, tol)
elif choice == "3":
this_order(vs, tol)
elif choice == "4":
every(vs, tol)
elif choice == "5":
show_records()
elif choice == "6":
vs = set_values(vs)
elif choice == "7":
tol = set_tol(tol)
elif choice == "8":
running = False
else:
print("Pick a number from 1 to 8.")
print("Bye.")
near.eml
eml# P139 tolerance grouping - measurements are "the same" when they differ
# by at most the tolerance. As in the corpus case
# tolerance-equality-grouping, that relation is reflexive and symmetric and
# not transitive, so it does not split the values into groups: grouping the
# first match decides by the order the values come in, and chaining joins
# values far apart through the ones between. As in
# match-predicate-not-transitive, a record match "same email, or same
# phone, or same name" fails the same way.
#
# Values are whole tenths of a millimetre.
def near(a, b, tol):
return a - b <= tol and b - a <= tol
def properties(vs, tol):
# [values, reflexive, pairs, symmetric, chains a~b~c, transitive]
0 => refl
for a in vs:
if near(a, a, tol):
refl + 1 => refl
0 => pairs
0 => sym
0 => chains
0 => trans
for i in [0:len(vs) - 1]:
for j in [0:len(vs) - 1]:
pairs + 1 => pairs
if near(vs[i], vs[j], tol) == near(vs[j], vs[i], tol):
sym + 1 => sym
if i != j and near(vs[i], vs[j], tol):
for k in [0:len(vs) - 1]:
if k != i and k != j and near(vs[j], vs[k], tol):
chains + 1 => chains
if near(vs[i], vs[k], tol):
trans + 1 => trans
return [len(vs), refl, pairs, sym, chains, trans]
def first_match(vs, tol):
# each value joins the first group whose first value is near it
[] => groups
for v in vs:
0 - 1 => g
for k in [0:len(groups) - 1]:
if g < 0 and near(groups[k][0], v, tol):
k => g
if g < 0:
groups + [[v]] => groups
else:
groups[g] + [v] => groups[g]
return groups
def chaining(vs, tol):
# a value joins every group it is near, and those groups become one
[] => groups
for v in vs:
[v] => merged
[] => rest
for gr in groups:
False => touch
for x in gr:
if near(x, v, tol):
True => touch
if touch:
merged + gr => merged
else:
rest + [gr] => rest
rest + [merged] => groups
return groups
def canonical(groups):
# the groups as sorted values, the groups in order of their smallest
[] => gs
for g in groups:
gs + [sort(g)] => gs
return sort_groups(gs)
def sort(xs):
[] => out
for x in xs:
[] => nxt
False => placed
for y in out:
if not placed and x < y:
nxt + [x] => nxt
True => placed
nxt + [y] => nxt
if not placed:
nxt + [x] => nxt
nxt => out
return out
def sort_groups(gs):
[] => out
for g in gs:
[] => nxt
False => placed
for h in out:
if not placed and g[0] < h[0]:
nxt + [g] => nxt
True => placed
nxt + [h] => nxt
if not placed:
nxt + [g] => nxt
nxt => out
return out
def orders(xs):
if len(xs) <= 1:
return [xs]
[] => out
for i in [0:len(xs) - 1]:
[] => rest
for j in [0:len(xs) - 1]:
if j != i:
rest + [xs[j]] => rest
for p in orders(rest):
out + [[xs[i]] + p] => out
return out
def every_order(vs, tol):
# [orders, different first-match groupings, fewest and most groups,
# different chaining groupings, the widest chained group's span]
{} => fm
{} => ch
100000 => fewest
0 => most
0 => span
orders(vs) => os
for o in os:
first_match(o, tol) => a
1 => fm[str(canonical(a))]
if len(a) < fewest:
len(a) => fewest
if len(a) > most:
len(a) => most
canonical(chaining(o, tol)) => c
1 => ch[str(c)]
for g in c:
if g[len(g) - 1] - g[0] > span:
g[len(g) - 1] - g[0] => span
return [len(os), len(fm), fewest, most, len(ch), span]
def records():
# [name, email, phone]
return [["Pat Lee", "pat@home", "555-0101"], ["Pat Lee", "kim@work", "555-0199"], ["Kim Ito", "kim@work", "555-0123"], ["Kim Ito Jr", "kj@mail", "555-0123"]]
def same(a, b):
return a[0] == b[0] or a[1] == b[1] or a[2] == b[2]
def record_groups(order, chain):
# the records' numbers, grouped by first match (each joins the first
# group whose first record it matches) or by chaining
records() => rs
[] => groups
for i in order:
if chain:
[i] => merged
[] => rest
for gr in groups:
False => touch
for x in gr:
if same(rs[x], rs[i]):
True => touch
if touch:
merged + gr => merged
else:
rest + [gr] => rest
rest + [merged] => groups
else:
0 - 1 => g
for k in [0:len(groups) - 1]:
if g < 0 and same(rs[groups[k][0]], rs[i]):
k => g
if g < 0:
groups + [[i]] => groups
else:
groups[g] + [i] => groups[g]
return canonical(groups)
def record_orders():
# [orders, different first-match answers, different chaining answers]
{} => fm
{} => ch
orders([0, 1, 2, 3]) => os
for o in os:
1 => fm[str(record_groups(o, False))]
1 => ch[str(record_groups(o, True))]
return [len(os), len(fm), len(ch)]
Python projection (near.py)
def near(a, b, tol):
return a - b <= tol and b - a <= tol
def properties(vs, tol):
refl = 0
for a in vs:
if near(a, a, tol):
refl = refl + 1
pairs = 0
sym = 0
chains = 0
trans = 0
for i in range(0, len(vs)):
for j in range(0, len(vs)):
pairs = pairs + 1
if near(vs[i], vs[j], tol) == near(vs[j], vs[i], tol):
sym = sym + 1
if i != j and near(vs[i], vs[j], tol):
for k in range(0, len(vs)):
if k != i and k != j and near(vs[j], vs[k], tol):
chains = chains + 1
if near(vs[i], vs[k], tol):
trans = trans + 1
return [len(vs), refl, pairs, sym, chains, trans]
def first_match(vs, tol):
groups = []
for v in vs:
g = 0 - 1
for k in range(0, len(groups)):
if g < 0 and near(groups[k][0], v, tol):
g = k
if g < 0:
groups = groups + [[v]]
else:
groups[g] = groups[g] + [v]
return groups
def chaining(vs, tol):
groups = []
for v in vs:
merged = [v]
rest = []
for gr in groups:
touch = False
for x in gr:
if near(x, v, tol):
touch = True
if touch:
merged = merged + gr
else:
rest = rest + [gr]
groups = rest + [merged]
return groups
def canonical(groups):
gs = []
for g in groups:
gs = gs + [sort(g)]
return sort_groups(gs)
def sort(xs):
out = []
for x in xs:
nxt = []
placed = False
for y in out:
if not placed and x < y:
nxt = nxt + [x]
placed = True
nxt = nxt + [y]
if not placed:
nxt = nxt + [x]
out = nxt
return out
def sort_groups(gs):
out = []
for g in gs:
nxt = []
placed = False
for h in out:
if not placed and g[0] < h[0]:
nxt = nxt + [g]
placed = True
nxt = nxt + [h]
if not placed:
nxt = nxt + [g]
out = nxt
return out
def orders(xs):
if len(xs) <= 1:
return [xs]
out = []
for i in range(0, len(xs)):
rest = []
for j in range(0, len(xs)):
if j != i:
rest = rest + [xs[j]]
for p in orders(rest):
out = out + [[xs[i]] + p]
return out
def every_order(vs, tol):
fm = {}
ch = {}
fewest = 100000
most = 0
span = 0
os = orders(vs)
for o in os:
a = first_match(o, tol)
fm[str(canonical(a))] = 1
if len(a) < fewest:
fewest = len(a)
if len(a) > most:
most = len(a)
c = canonical(chaining(o, tol))
ch[str(c)] = 1
for g in c:
if g[len(g) - 1] - g[0] > span:
span = g[len(g) - 1] - g[0]
return [len(os), len(fm), fewest, most, len(ch), span]
def records():
return [["Pat Lee", "pat@home", "555-0101"], ["Pat Lee", "kim@work", "555-0199"], ["Kim Ito", "kim@work", "555-0123"], ["Kim Ito Jr", "kj@mail", "555-0123"]]
def same(a, b):
return a[0] == b[0] or a[1] == b[1] or a[2] == b[2]
def record_groups(order, chain):
rs = records()
groups = []
for i in order:
if chain:
merged = [i]
rest = []
for gr in groups:
touch = False
for x in gr:
if same(rs[x], rs[i]):
touch = True
if touch:
merged = merged + gr
else:
rest = rest + [gr]
groups = rest + [merged]
else:
g = 0 - 1
for k in range(0, len(groups)):
if g < 0 and same(rs[groups[k][0]], rs[i]):
g = k
if g < 0:
groups = groups + [[i]]
else:
groups[g] = groups[g] + [i]
return canonical(groups)
def record_orders():
fm = {}
ch = {}
os = orders([0, 1, 2, 3])
for o in os:
fm[str(record_groups(o, False))] = 1
ch[str(record_groups(o, True))] = 1
return [len(os), len(fm), len(ch)]