FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
aima-python/utils.py at master · riversxiao/aima-python · GitHub
riversxiao
/
aima-python
Public
forked from
aimacode/aima-python
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Wiki
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
aima-python
/
utils.py
Copy path
More file actions
More file actions
Latest commit
History
History
History
799 lines (566 loc) · 22.2 KB
Breadcrumbs
aima-python
/
utils.py
Copy path
File metadata and controls
799 lines (566 loc) · 22.2 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
"""Provides some utilities widely used by other modules"""
import
bisect
import
collections
import
collections
.
abc
import
operator
import
os
.
path
import
random
import
math
import
functools
# ______________________________________________________________________________
# Functions on Sequences and Iterables
def
sequence
(
iterable
):
"""Coerce iterable to sequence, if it is not already one."""
return
(
iterable
if
isinstance
(
iterable
,
collections
.
abc
.
Sequence
)
else
tuple
(
iterable
))
def
removeall
(
item
,
seq
):
"""Return a copy of seq (or string) with all occurences of item removed."""
if
isinstance
(
seq
,
str
):
return
seq
.
replace
(
item
,
''
)
else
:
return
[
x
for
x
in
seq
if
x
!=
item
]
def
unique
(
seq
):
# TODO: replace with set
"""Remove duplicate elements from seq. Assumes hashable elements."""
return
list
(
set
(
seq
))
def
count
(
seq
):
"""Count the number of items in sequence that are interpreted as true."""
return
sum
(
bool
(
x
)
for
x
in
seq
)
def
product
(
numbers
):
"""Return the product of the numbers, e.g. product([2, 3, 10]) == 60"""
result
=
1
for
x
in
numbers
:
result
*=
x
return
result
def
first
(
iterable
,
default
=
None
):
"""Return the first element of an iterable or the next element of a generator; or default."""
try
:
return
iterable
[
0
]
except
IndexError
:
return
default
except
TypeError
:
return
next
(
iterable
,
default
)
def
is_in
(
elt
,
seq
):
"""Similar to (elt in seq), but compares with 'is', not '=='."""
return
any
(
x
is
elt
for
x
in
seq
)
def
mode
(
data
):
"""Return the most common data item. If there are ties, return any one of them."""
[(
item
,
count
)]
=
collections
.
Counter
(
data
).
most_common
(
1
)
return
item
# ______________________________________________________________________________
# argmin and argmax
identity
=
lambda
x
:
x
argmin
=
min
argmax
=
max
def
argmin_random_tie
(
seq
,
key
=
identity
):
"""Return a minimum element of seq; break ties at random."""
return
argmin
(
shuffled
(
seq
),
key
=
key
)
def
argmax_random_tie
(
seq
,
key
=
identity
):
"""Return an element with highest fn(seq[i]) score; break ties at random."""
return
argmax
(
shuffled
(
seq
),
key
=
key
)
def
shuffled
(
iterable
):
"""Randomly shuffle a copy of iterable."""
items
=
list
(
iterable
)
random
.
shuffle
(
items
)
return
items
# ______________________________________________________________________________
# Statistical and mathematical functions
def
histogram
(
values
,
mode
=
0
,
bin_function
=
None
):
"""Return a list of (value, count) pairs, summarizing the input values.
Sorted by increasing value, or if mode=1, by decreasing count.
If bin_function is given, map it over values first."""
if
bin_function
:
values
=
map
(
bin_function
,
values
)
bins
=
{}
for
val
in
values
:
bins
[
val
]
=
bins
.
get
(
val
,
0
)
+
1
if
mode
:
return
sorted
(
list
(
bins
.
items
()),
key
=
lambda
x
: (
x
[
1
],
x
[
0
]),
reverse
=
True
)
else
:
return
sorted
(
bins
.
items
())
def
dotproduct
(
X
,
Y
):
"""Return the sum of the element-wise product of vectors X and Y."""
return
sum
(
x
*
y
for
x
,
y
in
zip
(
X
,
Y
))
def
element_wise_product
(
X
,
Y
):
"""Return vector as an element-wise product of vectors X and Y"""
assert
len
(
X
)
==
len
(
Y
)
return
[
x
*
y
for
x
,
y
in
zip
(
X
,
Y
)]
def
matrix_multiplication
(
X_M
,
*
Y_M
):
"""Return a matrix as a matrix-multiplication of X_M and arbitary number of matrices *Y_M"""
def
_mat_mult
(
X_M
,
Y_M
):
"""Return a matrix as a matrix-multiplication of two matrices X_M and Y_M
>>> matrix_multiplication([[1, 2, 3],
[2, 3, 4]],
[[3, 4],
[1, 2],
[1, 0]])
[[8, 8],[13, 14]]
"""
assert
len
(
X_M
[
0
])
==
len
(
Y_M
)
result
=
[[
0
for
i
in
range
(
len
(
Y_M
[
0
]))]
for
j
in
range
(
len
(
X_M
))]
for
i
in
range
(
len
(
X_M
)):
for
j
in
range
(
len
(
Y_M
[
0
])):
for
k
in
range
(
len
(
Y_M
)):
result
[
i
][
j
]
+=
X_M
[
i
][
k
]
*
Y_M
[
k
][
j
]
return
result
result
=
X_M
for
Y
in
Y_M
:
result
=
_mat_mult
(
result
,
Y
)
return
result
def
vector_to_diagonal
(
v
):
"""Converts a vector to a diagonal matrix with vector elements
as the diagonal elements of the matrix"""
diag_matrix
=
[[
0
for
i
in
range
(
len
(
v
))]
for
j
in
range
(
len
(
v
))]
for
i
in
range
(
len
(
v
)):
diag_matrix
[
i
][
i
]
=
v
[
i
]
return
diag_matrix
def
vector_add
(
a
,
b
):
"""Component-wise addition of two vectors."""
return
tuple
(
map
(
operator
.
add
,
a
,
b
))
def
scalar_vector_product
(
X
,
Y
):
"""Return vector as a product of a scalar and a vector"""
return
[
X
*
y
for
y
in
Y
]
def
scalar_matrix_product
(
X
,
Y
):
"""Return matrix as a product of a scalar and a matrix"""
return
[
scalar_vector_product
(
X
,
y
)
for
y
in
Y
]
def
inverse_matrix
(
X
):
"""Inverse a given square matrix of size 2x2"""
assert
len
(
X
)
==
2
assert
len
(
X
[
0
])
==
2
det
=
X
[
0
][
0
]
*
X
[
1
][
1
]
-
X
[
0
][
1
]
*
X
[
1
][
0
]
assert
det
!=
0
inv_mat
=
scalar_matrix_product
(
1.0
/
det
, [[
X
[
1
][
1
],
-
X
[
0
][
1
]], [
-
X
[
1
][
0
],
X
[
0
][
0
]]])
return
inv_mat
def
probability
(
p
):
"""Return true with probability p."""
return
p
>
random
.
uniform
(
0.0
,
1.0
)
def
weighted_sample_with_replacement
(
n
,
seq
,
weights
):
"""Pick n samples from seq at random, with replacement, with the
probability of each element in proportion to its corresponding
weight."""
sample
=
weighted_sampler
(
seq
,
weights
)
return
[
sample
()
for
_
in
range
(
n
)]
def
weighted_sampler
(
seq
,
weights
):
"""Return a random-sample function that picks from seq weighted by weights."""
totals
=
[]
for
w
in
weights
:
totals
.
append
(
w
+
totals
[
-
1
]
if
totals
else
w
)
return
lambda
:
seq
[
bisect
.
bisect
(
totals
,
random
.
uniform
(
0
,
totals
[
-
1
]))]
def
rounder
(
numbers
,
d
=
4
):
"""Round a single number, or sequence of numbers, to d decimal places."""
if
isinstance
(
numbers
, (
int
,
float
)):
return
round
(
numbers
,
d
)
else
:
constructor
=
type
(
numbers
)
# Can be list, set, tuple, etc.
return
constructor
(
rounder
(
n
,
d
)
for
n
in
numbers
)
def
num_or_str
(
x
):
"""The argument is a string; convert to a number if
possible, or strip it."""
try
:
return
int
(
x
)
except
ValueError
:
try
:
return
float
(
x
)
except
ValueError
:
return
str
(
x
).
strip
()
def
normalize
(
dist
):
"""Multiply each number by a constant such that the sum is 1.0"""
if
isinstance
(
dist
,
dict
):
total
=
sum
(
dist
.
values
())
for
key
in
dist
:
dist
[
key
]
=
dist
[
key
]
/
total
assert
0
<=
dist
[
key
]
<=
1
,
"Probabilities must be between 0 and 1."
return
dist
total
=
sum
(
dist
)
return
[(
n
/
total
)
for
n
in
dist
]
def
norm
(
X
,
n
=
2
):
"""Return the n-norm of vector X"""
return
sum
([
x
**
n
for
x
in
X
])
**
(
1
/
n
)
def
clip
(
x
,
lowest
,
highest
):
"""Return x clipped to the range [lowest..highest]."""
return
max
(
lowest
,
min
(
x
,
highest
))
def
sigmoid_derivative
(
value
):
return
value
*
(
1
-
value
)
def
sigmoid
(
x
):
"""Return activation value of x with sigmoid function"""
return
1
/
(
1
+
math
.
exp
(
-
x
))
def
step
(
x
):
"""Return activation value of x with sign function"""
return
1
if
x
>=
0
else
0
def
gaussian
(
mean
,
st_dev
,
x
):
"""Given the mean and standard deviation of a distribution, it returns the probability of x."""
return
1
/
(
math
.
sqrt
(
2
*
math
.
pi
)
*
st_dev
)
*
math
.
e
**
(
-
0.5
*
(
float
(
x
-
mean
)
/
st_dev
)
**
2
)
def
truncated_svd
(
X
,
max_iter
=
1000
):
"""Computes the first component of SVD"""
def
normalize_vec
(
X
,
n
=
2
):
"""Returns normalized vector"""
norm_X
=
norm
(
X
,
n
)
Y
=
[
x
/
norm_X
for
x
in
X
]
return
Y
m
,
n
=
len
(
X
),
len
(
X
[
0
])
A
=
[[
0
for
_
in
range
(
n
+
m
)]
for
_
in
range
(
n
+
m
)]
for
i
in
range
(
m
):
for
j
in
range
(
n
):
A
[
i
][
j
]
=
A
[
m
+
j
][
n
+
i
]
=
X
[
i
][
j
]
X
=
[
random
.
random
()
for
_
in
range
(
n
+
m
)]
X
=
normalize_vec
(
X
)
for
_
in
range
(
max_iter
):
old_X
=
X
X
=
matrix_multiplication
(
A
, [[
x
]
for
x
in
X
])
X
=
[
x
[
0
]
for
x
in
X
]
X
=
normalize_vec
(
X
)
# check for convergence
if
norm
([
x1
-
x2
for
x1
,
x2
in
zip
(
old_X
,
X
)])
<=
1e-10
:
break
projected_X
=
matrix_multiplication
(
A
, [[
x
]
for
x
in
X
])
projected_X
=
[
x
[
0
]
for
x
in
projected_X
]
eival
=
norm
(
projected_X
,
1
)
/
norm
(
X
,
1
)
eivec_n
=
normalize_vec
(
X
[:
n
])
eivec_m
=
normalize_vec
(
X
[
n
:])
return
(
eivec_m
,
eivec_n
,
eival
)
try
:
# math.isclose was added in Python 3.5; but we might be in 3.4
from
math
import
isclose
except
ImportError
:
def
isclose
(
a
,
b
,
rel_tol
=
1e-09
,
abs_tol
=
0.0
):
"""Return true if numbers a and b are close to each other."""
return
abs
(
a
-
b
)
<=
max
(
rel_tol
*
max
(
abs
(
a
),
abs
(
b
)),
abs_tol
)
# ______________________________________________________________________________
# Grid Functions
orientations
=
EAST
,
NORTH
,
WEST
,
SOUTH
=
[(
1
,
0
), (
0
,
1
), (
-
1
,
0
), (
0
,
-
1
)]
turns
=
LEFT
,
RIGHT
=
(
+
1
,
-
1
)
def
turn_heading
(
heading
,
inc
,
headings
=
orientations
):
return
headings
[(
headings
.
index
(
heading
)
+
inc
)
%
len
(
headings
)]
def
turn_right
(
heading
):
return
turn_heading
(
heading
,
RIGHT
)
def
turn_left
(
heading
):
return
turn_heading
(
heading
,
LEFT
)
def
distance
(
a
,
b
):
"""The distance between two (x, y) points."""
xA
,
yA
=
a
xB
,
yB
=
b
return
math
.
hypot
((
xA
-
xB
), (
yA
-
yB
))
def
distance_squared
(
a
,
b
):
"""The square of the distance between two (x, y) points."""
xA
,
yA
=
a
xB
,
yB
=
b
return
(
xA
-
xB
)
**
2
+
(
yA
-
yB
)
**
2
def
vector_clip
(
vector
,
lowest
,
highest
):
"""Return vector, except if any element is less than the corresponding
value of lowest or more than the corresponding value of highest, clip to
those values."""
return
type
(
vector
)(
map
(
clip
,
vector
,
lowest
,
highest
))
# ______________________________________________________________________________
# Misc Functions
def
memoize
(
fn
,
slot
=
None
,
maxsize
=
32
):
"""Memoize fn: make it remember the computed value for any argument list.
If slot is specified, store result in that slot of first argument.
If slot is false, use lru_cache for caching the values."""
if
slot
:
def
memoized_fn
(
obj
,
*
args
):
if
hasattr
(
obj
,
slot
):
return
getattr
(
obj
,
slot
)
else
:
val
=
fn
(
obj
,
*
args
)
setattr
(
obj
,
slot
,
val
)
return
val
else
:
@
functools
.
lru_cache
(
maxsize
=
maxsize
)
def
memoized_fn
(
*
args
):
return
fn
(
*
args
)
return
memoized_fn
def
name
(
obj
):
"""Try to find some reasonable name for the object."""
return
(
getattr
(
obj
,
'name'
,
0
)
or
getattr
(
obj
,
'__name__'
,
0
)
or
getattr
(
getattr
(
obj
,
'__class__'
,
0
),
'__name__'
,
0
)
or
str
(
obj
))
def
isnumber
(
x
):
"""Is x a number?"""
return
hasattr
(
x
,
'__int__'
)
def
issequence
(
x
):
"""Is x a sequence?"""
return
isinstance
(
x
,
collections
.
abc
.
Sequence
)
def
print_table
(
table
,
header
=
None
,
sep
=
' '
,
numfmt
=
'{}'
):
"""Print a list of lists as a table, so that columns line up nicely.
header, if specified, will be printed as the first row.
numfmt is the format for all numbers; you might want e.g. '{:.2f}'.
(If you want different formats in different columns,
don't use print_table.) sep is the separator between columns."""
justs
=
[
'rjust'
if
isnumber
(
x
)
else
'ljust'
for
x
in
table
[
0
]]
if
header
:
table
.
insert
(
0
,
header
)
table
=
[[
numfmt
.
format
(
x
)
if
isnumber
(
x
)
else
x
for
x
in
row
]
for
row
in
table
]
sizes
=
list
(
map
(
lambda
seq
:
max
(
map
(
len
,
seq
)),
list
(
zip
(
*
[
map
(
str
,
row
)
for
row
in
table
]))))
for
row
in
table
:
print
(
sep
.
join
(
getattr
(
str
(
x
),
j
)(
size
)
for
(
j
,
size
,
x
)
in
zip
(
justs
,
sizes
,
row
)))
def
open_data
(
name
,
mode
=
'r'
):
aima_root
=
os
.
path
.
dirname
(
__file__
)
aima_file
=
os
.
path
.
join
(
aima_root
,
*
[
'aima-data'
,
name
])
return
open
(
aima_file
)
# ______________________________________________________________________________
# Expressions
# See https://docs.python.org/3/reference/expressions.html#operator-precedence
# See https://docs.python.org/3/reference/datamodel.html#special-method-names
class
Expr
(
object
):
"""A mathematical expression with an operator and 0 or more arguments.
op is a str like '+' or 'sin'; args are Expressions.
Expr('x') or Symbol('x') creates a symbol (a nullary Expr).
Expr('-', x) creates a unary; Expr('+', x, 1) creates a binary."""
def
__init__
(
self
,
op
,
*
args
):
self
.
op
=
str
(
op
)
self
.
args
=
args
# Operator overloads
def
__neg__
(
self
):
return
Expr
(
'-'
,
self
)
def
__pos__
(
self
):
return
Expr
(
'+'
,
self
)
def
__invert__
(
self
):
return
Expr
(
'~'
,
self
)
def
__add__
(
self
,
rhs
):
return
Expr
(
'+'
,
self
,
rhs
)
def
__sub__
(
self
,
rhs
):
return
Expr
(
'-'
,
self
,
rhs
)
def
__mul__
(
self
,
rhs
):
return
Expr
(
'*'
,
self
,
rhs
)
def
__pow__
(
self
,
rhs
):
return
Expr
(
'**'
,
self
,
rhs
)
def
__mod__
(
self
,
rhs
):
return
Expr
(
'%'
,
self
,
rhs
)
def
__and__
(
self
,
rhs
):
return
Expr
(
'&'
,
self
,
rhs
)
def
__xor__
(
self
,
rhs
):
return
Expr
(
'^'
,
self
,
rhs
)
def
__rshift__
(
self
,
rhs
):
return
Expr
(
'>>'
,
self
,
rhs
)
def
__lshift__
(
self
,
rhs
):
return
Expr
(
'<<'
,
self
,
rhs
)
def
__truediv__
(
self
,
rhs
):
return
Expr
(
'/'
,
self
,
rhs
)
def
__floordiv__
(
self
,
rhs
):
return
Expr
(
'//'
,
self
,
rhs
)
def
__matmul__
(
self
,
rhs
):
return
Expr
(
'@'
,
self
,
rhs
)
def
__or__
(
self
,
rhs
):
"""Allow both P | Q, and P |'==>'| Q."""
if
isinstance
(
rhs
,
Expression
):
return
Expr
(
'|'
,
self
,
rhs
)
else
:
return
PartialExpr
(
rhs
,
self
)
# Reverse operator overloads
def
__radd__
(
self
,
lhs
):
return
Expr
(
'+'
,
lhs
,
self
)
def
__rsub__
(
self
,
lhs
):
return
Expr
(
'-'
,
lhs
,
self
)
def
__rmul__
(
self
,
lhs
):
return
Expr
(
'*'
,
lhs
,
self
)
def
__rdiv__
(
self
,
lhs
):
return
Expr
(
'/'
,
lhs
,
self
)
def
__rpow__
(
self
,
lhs
):
return
Expr
(
'**'
,
lhs
,
self
)
def
__rmod__
(
self
,
lhs
):
return
Expr
(
'%'
,
lhs
,
self
)
def
__rand__
(
self
,
lhs
):
return
Expr
(
'&'
,
lhs
,
self
)
def
__rxor__
(
self
,
lhs
):
return
Expr
(
'^'
,
lhs
,
self
)
def
__ror__
(
self
,
lhs
):
return
Expr
(
'|'
,
lhs
,
self
)
def
__rrshift__
(
self
,
lhs
):
return
Expr
(
'>>'
,
lhs
,
self
)
def
__rlshift__
(
self
,
lhs
):
return
Expr
(
'<<'
,
lhs
,
self
)
def
__rtruediv__
(
self
,
lhs
):
return
Expr
(
'/'
,
lhs
,
self
)
def
__rfloordiv__
(
self
,
lhs
):
return
Expr
(
'//'
,
lhs
,
self
)
def
__rmatmul__
(
self
,
lhs
):
return
Expr
(
'@'
,
lhs
,
self
)
def
__call__
(
self
,
*
args
):
"Call: if 'f' is a Symbol, then f(0) == Expr('f', 0)."
if
self
.
args
:
raise
ValueError
(
'can only do a call for a Symbol, not an Expr'
)
else
:
return
Expr
(
self
.
op
,
*
args
)
# Equality and repr
def
__eq__
(
self
,
other
):
"'x == y' evaluates to True or False; does not build an Expr."
return
(
isinstance
(
other
,
Expr
)
and
self
.
op
==
other
.
op
and
self
.
args
==
other
.
args
)
def
__hash__
(
self
):
return
hash
(
self
.
op
)
^
hash
(
self
.
args
)
def
__repr__
(
self
):
op
=
self
.
op
args
=
[
str
(
arg
)
for
arg
in
self
.
args
]
if
op
.
isidentifier
():
# f(x) or f(x, y)
return
'{}({})'
.
format
(
op
,
', '
.
join
(
args
))
if
args
else
op
elif
len
(
args
)
==
1
:
# -x or -(x + 1)
return
op
+
args
[
0
]
else
:
# (x - y)
opp
=
(
' '
+
op
+
' '
)
return
'('
+
opp
.
join
(
args
)
+
')'
# An 'Expression' is either an Expr or a Number.
# Symbol is not an explicit type; it is any Expr with 0 args.
Number
=
(
int
,
float
,
complex
)
Expression
=
(
Expr
,
Number
)
def
Symbol
(
name
):
"""A Symbol is just an Expr with no args."""
return
Expr
(
name
)
def
symbols
(
names
):
"""Return a tuple of Symbols; names is a comma/whitespace delimited str."""
return
tuple
(
Symbol
(
name
)
for
name
in
names
.
replace
(
','
,
' '
).
split
())
def
subexpressions
(
x
):
"""Yield the subexpressions of an Expression (including x itself)."""
yield
x
if
isinstance
(
x
,
Expr
):
for
arg
in
x
.
args
:
yield
from
subexpressions
(
arg
)
def
arity
(
expression
):
"""The number of sub-expressions in this expression."""
if
isinstance
(
expression
,
Expr
):
return
len
(
expression
.
args
)
else
:
# expression is a number
return
0
# For operators that are not defined in Python, we allow new InfixOps:
class
PartialExpr
:
"""Given 'P |'==>'| Q, first form PartialExpr('==>', P), then combine with Q."""
def
__init__
(
self
,
op
,
lhs
):
self
.
op
,
self
.
lhs
=
op
,
lhs
def
__or__
(
self
,
rhs
):
return
Expr
(
self
.
op
,
self
.
lhs
,
rhs
)
def
__repr__
(
self
):
return
"PartialExpr('{}', {})"
.
format
(
self
.
op
,
self
.
lhs
)
def
expr
(
x
):
"""Shortcut to create an Expression. x is a str in which:
- identifiers are automatically defined as Symbols.
- ==> is treated as an infix |'==>'|, as are <== and <=>.
If x is already an Expression, it is returned unchanged. Example:
>>> expr('P & Q ==> Q')
((P & Q) ==> Q)
"""
if
isinstance
(
x
,
str
):
return
eval
(
expr_handle_infix_ops
(
x
),
defaultkeydict
(
Symbol
))
else
:
return
x
infix_ops
=
'==> <== <=>'
.
split
()
def
expr_handle_infix_ops
(
x
):
"""Given a str, return a new str with ==> replaced by |'==>'|, etc.
>>> expr_handle_infix_ops('P ==> Q')
"P |'==>'| Q"
"""
for
op
in
infix_ops
:
x
=
x
.
replace
(
op
,
'|'
+
repr
(
op
)
+
'|'
)
return
x
class
defaultkeydict
(
collections
.
defaultdict
):
"""Like defaultdict, but the default_factory is a function of the key.
>>> d = defaultkeydict(len); d['four']
4
"""
def
__missing__
(
self
,
key
):
self
[
key
]
=
result
=
self
.
default_factory
(
key
)
return
result
class
hashabledict
(
dict
):
"""Allows hashing by representing a dictionary as tuple of key:value pairs
May cause problems as the hash value may change during runtime
"""
def
__tuplify__
(
self
):
return
tuple
(
sorted
(
self
.
items
()))
def
__hash__
(
self
):
return
hash
(
self
.
__tuplify__
())
def
__lt__
(
self
,
odict
):
assert
isinstance
(
odict
,
hashabledict
)
return
self
.
__tuplify__
()
<
odict
.
__tuplify__
()
def
__gt__
(
self
,
odict
):
assert
isinstance
(
odict
,
hashabledict
)
return
self
.
__tuplify__
()
>
odict
.
__tuplify__
()
def
__le__
(
self
,
odict
):
assert
isinstance
(
odict
,
hashabledict
)
return
self
.
__tuplify__
()
<=
odict
.
__tuplify__
()
def
__ge__
(
self
,
odict
):
assert
isinstance
(
odict
,
hashabledict
)
return
self
.
__tuplify__
()
>=
odict
.
__tuplify__
()
# ______________________________________________________________________________
# Queues: Stack, FIFOQueue, PriorityQueue
# TODO: queue.PriorityQueue
# TODO: Priority queues may not belong here -- see treatment in search.py
class
Queue
:
"""Queue is an abstract class/interface. There are three types:
Stack(): A Last In First Out Queue.
FIFOQueue(): A First In First Out Queue.
PriorityQueue(order, f): Queue in sorted order (default min-first).
Each type supports the following methods and functions:
q.append(item) -- add an item to the queue
q.extend(items) -- equivalent to: for item in items: q.append(item)
q.pop() -- return the top item from the queue
len(q) -- number of items in q (also q.__len())
item in q -- does q contain item?
Note that isinstance(Stack(), Queue) is false, because we implement stacks
as lists. If Python ever gets interfaces, Queue will be an interface."""
def
__init__
(
self
):
raise
NotImplementedError
def
extend
(
self
,
items
):
for
item
in
items
:
self
.
append
(
item
)
def
Stack
():
"""Return an empty list, suitable as a Last-In-First-Out Queue."""
return
[]
class
FIFOQueue
(
Queue
):
"""A First-In-First-Out Queue."""
def
__init__
(
self
,
maxlen
=
None
,
items
=
[]):
self
.
queue
=
collections
.
deque
(
items
,
maxlen
)
def
append
(
self
,
item
):
if
not
self
.
queue
.
maxlen
or
len
(
self
.
queue
)
<
self
.
queue
.
maxlen
:
self
.
queue
.
append
(
item
)
else
:
raise
Exception
(
'FIFOQueue is full'
)
def
extend
(
self
,
items
):
if
not
self
.
queue
.
maxlen
or
len
(
self
.
queue
)
+
len
(
items
)
<=
self
.
queue
.
maxlen
:
self
.
queue
.
extend
(
items
)
else
:
raise
Exception
(
'FIFOQueue max length exceeded'
)
def
pop
(
self
):
if
len
(
self
.
queue
)
>
0
:
return
self
.
queue
.
popleft
()
else
:
raise
Exception
(
'FIFOQueue is empty'
)
def
__len__
(
self
):
return
len
(
self
.
queue
)
def
__contains__
(
self
,
item
):
return
item
in
self
.
queue
class
PriorityQueue
(
Queue
):
"""A queue in which the minimum (or maximum) element (as determined by f and
order) is returned first. If order is min, the item with minimum f(x) is
returned first; if order is max, then it is the item with maximum f(x).
Also supports dict-like lookup."""
def
__init__
(
self
,
order
=
min
,
f
=
lambda
x
:
x
):
self
.
A
=
[]
self
.
order
=
order
self
.
f
=
f
def
append
(
self
,
item
):
bisect
.
insort
(
self
.
A
, (
self
.
f
(
item
),
item
))
def
__len__
(
self
):
return
len
(
self
.
A
)
def
pop
(
self
):
if
self
.
order
==
min
:
return
self
.
A
.
pop
(
0
)[
1
]
else
:
return
self
.
A
.
pop
()[
1
]
def
__contains__
(
self
,
item
):
return
any
(
item
==
pair
[
1
]
for
pair
in
self
.
A
)
def
__getitem__
(
self
,
key
):
for
_
,
item
in
self
.
A
:
if
item
==
key
:
return
item
def
__delitem__
(
self
,
key
):
for
i
, (
value
,
item
)
in
enumerate
(
self
.
A
):
if
item
==
key
:
self
.
A
.
pop
(
i
)
# ______________________________________________________________________________
# Useful Shorthands
class
Bool
(
int
):
"""Just like `bool`, except values display as 'T' and 'F' instead of 'True' and 'False'"""
__str__
=
__repr__
=
lambda
self
:
'T'
if
self
else
'F'
T
=
Bool
(
True
)
F
=
Bool
(
False
)
Back
|
FazBrowse Home
|
New Git URL