Skip to content

Instantly share code, notes, and snippets.

@apua

apua/algorithm.py

Last active December 24, 2016 10:21
Show Gist options
  • Save apua/8d565a8a8365a1399b8fae1664b43d65 to your computer and use it in GitHub Desktop.
Save apua/8d565a8a8365a1399b8fae1664b43d65 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
algorithm.py
r"""
>>> main(1)
1 2 3 4 5 6 7 8 9
>>> main(2)
1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20 21 23 24 25 26 27 28 29 30 31 32 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 56 57 58 59 60 61 62 63 64 65 67 68 69 70 71 72 73 74 75 76 78 79 80 81 82 83 84 85 86 87 89 90 91 92 93 94 95 96 97 98
>>> main(3)
1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20 21 23 24 25 26 27 28 29 30 31 32 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 56 57 58 59 60 61 62 63 64 65 67 68 69 70 71 72 73 74 75 76 78 79 80 81 82 83 84 85 86 87 89 90 91 92 93 94 95 96 97 98 102 103 104 105 106 107 108 109 120 123 124 125 126 127 128 129 130 132 134 135 136 137 138 139 140 142 143 145 146 147 148 149 150 152 153 154 156 157 158 159 160 162 163 164 165 167 168 169 170 172 173 174 175 176 178 179 180 182 183 184 185 186 187 189 190 192 193 194 195 196 197 198 201 203 204 205 206 207 208 209 210 213 214 215 216 217 218 219 230 231 234 235 236 237 238 239 240 241 243 245 246 247 248 249 250 251 253 254 256 257 258 259 260 261 263 264 265 267 268 269 270 271 273 274 275 276 278 279 280 281 283 284 285 286 287 289 290 291 293 294 295 296 297 298 301 302 304 305 306 307 308 309 310 312 314 315 316 317 318 319 320 321 324 325 326 327 328 329 340 341 342 345 346 347 348 349 350 351 352 354 356 357 358 359 360 361 362 364 365 367 368 369 370 371 372 374 375 376 378 379 380 381 382 384 385 386 387 389 390 391 392 394 395 396 397 398 401 402 403 405 406 407 408 409 410 412 413 415 416 417 418 419 420 421 423 425 426 427 428 429 430 431 432 435 436 437 438 439 450 451 452 453 456 457 458 459 460 461 462 463 465 467 468 469 470 471 472 473 475 476 478 479 480 481 482 483 485 486 487 489 490 491 492 493 495 496 497 498 501 502 503 504 506 507 508 509 510 512 513 514 516 517 518 519 520 521 523 524 526 527 528 529 530 531 532 534 536 537 538 539 540 541 542 543 546 547 548 549 560 561 562 563 564 567 568 569 570 571 572 573 574 576 578 579 580 581 582 583 584 586 587 589 590 591 592 593 594 596 597 598 601 602 603 604 605 607 608 609 610 612 613 614 615 617 618 619 620 621 623 624 625 627 628 629 630 631 632 634 635 637 638 639 640 641 642 643 645 647 648 649 650 651 652 653 654 657 658 659 670 671 672 673 674 675 678 679 680 681 682 683 684 685 687 689 690 691 692 693 694 695 697 698 701 702 703 704 705 706 708 709 710 712 713 714 715 716 718 719 720 721 723 724 725 726 728 729 730 731 732 734 735 736 738 739 740 741 742 743 745 746 748 749 750 751 752 753 754 756 758 759 760 761 762 763 764 765 768 769 780 781 782 783 784 785 786 789 790 791 792 793 794 795 796 798 801 802 803 804 805 806 807 809 810 812 813 814 815 816 817 819 820 821 823 824 825 826 827 829 830 831 832 834 835 836 837 839 840 841 842 843 845 846 847 849 850 851 852 853 854 856 857 859 860 861 862 863 864 865 867 869 870 871 872 873 874 875 876 879 890 891 892 893 894 895 896 897 901 902 903 904 905 906 907 908 910 912 913 914 915 916 917 918 920 921 923 924 925 926 927 928 930 931 932 934 935 936 937 938 940 941 942 943 945 946 947 948 950 951 952 953 954 956 957 958 960 961 962 963 964 965 967 968 970 971 972 973 974 975 976 978 980 981 982 983 984 985 986 987
"""
def gen(length, digits=''):
if len(digits)==length:
yield int(digits)
else:
for d in map(str, range(len(digits)==0, 10)):
if d not in digits:
yield from gen(length, digits + d)
def main(N: str) -> None:
from itertools import chain
print(*chain(*map(gen, range(1, N+1))))
Raw
gen_ws.py
"""
usage: python3 gen_ws.py xxx.ws.orig [-c|-b|-w]
save file → xxx.ws
-c color
-b bbs
-w whitespace
"""
import re
import sys
if len(sys.argv) != 3:
exit(__doc__)
else:
input_filename = sys.argv[1]
output_type = sys.argv[2]
if output_type == '-c':
D = {ord('S'): '\033[47m \033[m',
ord('T'): '\033[43m \033[m',
ord('L'): '\033[44m \033[m\n'}
elif output_type == '-b':
D = {ord('S'): '\u2587',
ord('T'): '\u2588',
ord('L'): '\n'}
elif output_type == '-w':
D = dict(zip(map(ord, 'STL'), ' \t\n'))
else:
exit(__doc__)
if re.match(r'.*\.ws\.orig$', input_filename) is not None:
output_filename = input_filename.strip('.orig')
else:
exit('ERROR: filename extension must be ".ws.orig"')
s = open(input_filename).read()
with open(output_filename, 'w') as f:
for line in s.strip().splitlines():
f.write(re.sub(r'#.*|[^STL]', '', line).translate(D))
print(open(output_filename).read().__repr__())
Raw
reduced.py
"""
>>> main.__globals__['input_value'] = lambda:0
>>> main.__globals__['N'] = 2
>>> main()
1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20 21 23 24 25 26 27 28 29 30 31 32 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 56 57 58 59 60 61 62 63 64 65 67 68 69 70 71 72 73 74 75 76 78 79 80 81 82 83 84 85 86 87 89 90 91 92 93 94 95 96 97 98
"""
# heap
# +----------+---------------------------------+-----------------------+
# | address | value | use |
# +==========+=================================+=======================+
# | 0~9 | 1 ~ 9 if first digit else 0 ~ 9 | digit in verify |
# +----------+---------------------------------+-----------------------+
# | 10~19 | 0 ~ 9 | acked digit |
# +----------+---------------------------------+-----------------------+
# | ord('N') | 1 ~ 10 | input value |
# +----------+---------------------------------+-----------------------+
# | ord('n') | 1 ~ N | length for generation |
# +----------+---------------------------------+-----------------------+
# | ord('i') | 0 ~ n - 1 | last acked digit |
# +----------+---------------------------------+-----------------------+
# | ord('s') | 0 (True), 1 (False) | show sep or not |
# +----------+---------------------------------+-----------------------+
S = [-1] * 10
H = [-1] * 10
N = -1
n = -1
i = -1
s = 1
# common output function
o = lambda c: __import__('sys').stdout.write(c)
def print_number(): # label: p
global n, s
if s==0:
o(chr(32))
s = 0
t = 0
while 1:
o(str(H[t]))
t += 1
if t - n < 0:
continue
else:
break
def rec_or_print(): # label: r
global n, i
if i + 1 - n != 0:
i+=1 ; generate() ; i-=1
else:
print_number()
def set_digit_if_valid(): # label: v
global i
if i != 0:
d = 0
while 1:
if d - i == 0:
break
if H[d] - S[i] == 0:
return
d += 1
H[i] = S[i] ; rec_or_print()
def generate(): # label: g
global i
S[i] = 1
if i!=0:
S[i] = 0
while 1:
set_digit_if_valid()
S[i] += 1
if S[i] - 10 < 0:
continue
else:
break
def input_value(): # label: i
global N
N = int(input())
def main():
global N, n, i
input_value()
n = 0
while 1:
n += 1
i = 0 ; generate()
if n - N < 0:
continue
else:
break
o(chr(10))
if __name__=='__main__':
main()
Raw
solve.ws.orig
# ====================
# main
# ====================
# declaration
LST STTSSTSSL
# input_value
LST STTSTSSTL
# push 'n' → push 0 → set heap
SS STTSTTTSL SS SSL TTS
# label 'm'
LSS STTSTTSTL
# push 'i' → push 0 → set heap
SS STTSTSSTL SS SSL TTS
# generate
LST STTSSTTTL
# push 'n' → get heap → push 1 → +=
# → dup → push 'n' → swap → set heap
# → push 'N' → get heap → -= → jump 'm' if < 0
SS STTSTTTSL TTT SS STL TSSS
SLS SS STTSTTTSL SLT TTS
SS STSSTTTSL TTT TSST LTT STTSTTSTL
# unit test of print_number
#LST STTTSTSTL
#LST STTTSTSTL
# unit test of set_digit_if_valid
#LST TTTTSTSTL
# push '\n' → output chr
SS STSTSL TLSS
# end
LLL
# ====================
# declaration
# ====================
# label 'd'
LSS STTSSTSSL
# push 20
SS SSSTSTSSL
# label 20
LSS SSSTSTSSL
# push 1 → -=
SS STL TSST
# dup → push -1 → set heap
SLS SS TTL TTS
# dup → push -1 → *= → jump 20 if < 0
SLS SS TTL TSSL LTT SSSTSTSSL
# pop
SLL
# 'N' → push -1 → set heap
SS STSSTTTSL SS TTL TTS
# 'n' → push -1 → set heap
SS STTSTTTSL SS TTL TTS
# 'i' → push -1 → set heap
SS STTSTSSTL SS TTL TTS
# 's' → push 0 → set heap
SS STTTSSTTL SS SSL TTS
LTL
# ====================
# input_value
# ====================
# label 'i'
LSS STTSTSSTL
# push 'N' → input int
SS STSSTTTSL TLTT
LTL
# ====================
# generate
# ====================
# label 'g'
LSS STTSSTTTL
# push 'i' → get heap
# dup → push 1 → set heap
# dup → jump '-g' if == 0
SS STTSTSSTL TTT
SLS SS STL TTS
SLS LTS TTTSSTTTL
# dup → push 0 → set heap
SLS SS SSL TTS
# label '-g'
LSS TTTSSTTTL
# pop
SLL
# label 'G'
LSS STSSSTTTL
# set_digit_if_valid
LST STTTSTTSL
# push 'i' → get heap
# → dup → dup → get heap → push 1 → += → set heap
# → get heap → push 10 → -= → jump 'G' if < 0
SS STTSTSSTL TTT
SLS SLS TTT SS STL TSSS TTS
TTT SS STSTSL TSST LTT STSSSTTTL
LTL
# ====================
# set_digit_if_valid
# ====================
# label 'v'
LSS STTTSTTSL
# push 'i' → get heap → jump 'V' if == 0
SS STTSTSSTL TTT LTS STSTSTTSL
# push 0
SS SSL
# label 'w'
LSS STTTSTTTL
# dup → push 'i' → get heap → -= → jump '-w' if == 0
SLS SS STTSTSSTL TTT TSST LTS TTTTSTTTL
# dup → push 10 → += → get heap
# → push 'i' → get heap → get heap
# → -= → jump '-V' if == 0
SLS SS STSTSL TSSS TTT
SS STTSTSSTL TTT TTT
TSST LTS TTSTSTTSL
# push 1 → += → jump 'w'
SS STL TSSS LSL STTTSTTTL
# label '-V'
LSS TTSTSTTSL
# pop
SLL
# return
LTL
# label '-w'
LSS TTTTSTTTL
# pop
SLL
# label 'V'
LSS STSTSTTSL
# push 'i' → get heap → push 10 → +=
# push 'i' → get heap → get heap
# set heap
SS STTSTSSTL TTT SS STSTSL TSSS
SS STTSTSSTL TTT TTT
TTS
# rec_or_print
LST STTTSSTSL
# print_number for unit test of set_digit_if_valid
#LST STTTSSSSL
# return
LTL
# ====================
# rec_or_print
# ====================
# label 'r'
LSS STTTSSTSL
# push 'i' → get heap → push 'n' → get heap → -=
SS STTSTSSTL TTT SS STTSTTTSL TTT TSST
# jump '-r' if i - n == 0
LTS TTTTSSTSL
# push 'i' → dup → get heap → push 1 → += → set heap
SS STTSTSSTL SLS TTT SS STL TSSS TTS
# generate
LST STTSSTTTL
# push 'i' → dup → get heap → push 1 → -= → set heap
SS STTSTSSTL SLS TTT SS STL TSST TTS
# return
LTL
# label '-r'
LSS TTTTSSTSL
# print_number
LST STTTSSSSL
# return
LTL
# ====================
# print_number
# ====================
# label 'p'
LSS STTTSSSSL
# push 's' → get heap → jump '-p' if == 0
SS STTTSSTTL TTT LTS TTTTSSSSL
# push ' ' → output chr
SS STSSSSSL TLSS
# label '-p'
LSS TTTTSSSSL
# push 0
SS SSL
# label 'P'
LSS STSTSSSSL
# dup → push 10 → += → get heap → push int
SLS SS STSTSL TSSS TTT TLST
# push 1 → +=
SS STL TSSS
# dup → push 'n' → get heap → push 1 → += → -=
# → jump 'P' if < 0
SLS SS STTSTTTSL TTT SS STL TSSS TSST
LTT STSTSSSSL
# pop
SLL
# push 's' → push 1 → set heap
SS STTTSSTTL SS STL TTS
LTL
# ====================
# unit test of print_number
# ====================
# label 'u'
LSS STTTSTSTL
# set heap "236", n = 2
SS STTSTTTSL SS STSL TTS
SS STSTSL SS STSL TTS
SS STSTTL SS STTL TTS
SS STTSSL SS STTSL TTS
# print_number
LST STTTSSSSL
LTL
# ====================
# unit test of set_digit_if_valid
# ====================
# label '-u'
LSS TTTTSTSTL
# n = i = 3 ; S[i] = 7 ; H[:i] = 134
SS STTSTTTSL SS STTL TTS
SS STTSTSSTL SS STTL TTS
SS STTL SS STTTL TTS
SS STSTSL SS STL TTS
SS STSTTL SS STTL TTS
SS STTSSL SS STSSL TTS
LST STTTSTTSL
# n = i = 3 ; S[i] = 3 ; H[:i] = 134
SS STTSTTTSL SS STTL TTS
SS STTSTSSTL SS STTL TTS
SS STTL SS STTL TTS
SS STSTSL SS STL TTS
SS STSTTL SS STTL TTS
SS STTSSL SS STSSL TTS
LST STTTSTTSL
# n = i = 0 ; S[i] = 7 ; H[:i] = ''
SS STTSTTTSL SS SSL TTS
SS STTSTSSTL SS SSL TTS
SS SSL SS STTTL TTS
LST STTTSTTSL
# expected result: 1347, 7
LTL
# ====================
# debug
# ====================
# label 'b'
LSS STTSSSTSL
SS SSSSSL TTT TLST
SS SSSSTL TTT TLST
SS SSSTSL TTT TLST
SS SSSTTL TTT TLST
SS SSTSSL TTT TLST
SS SSTSTL TTT TLST
SS SSTTSL TTT TLST
SS SSTTTL TTT TLST
SS STSSSL TTT TLST
SS STSSTL TTT TLST
SS STSTSL TLSS
SS STSTSL TTT TLST
SS STSSTL TTT TLST
SS STSTTL TTT TLST
SS STTSSL TTT TLST
SS STTSTL TTT TLST
SS STTTSL TTT TLST
SS STTTTL TTT TLST
SS STSSSSL TTT TLST
SS STSSSTL TTT TLST
SS STSSTSL TTT TLST
SS STSTSL TLSS
LTL
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment