Develop a C-based Solver with BFS

[Ant1ng2]

C code is usually faster than Python code, but we can extend Python code using C based extensions. Find a way to implement a C based solver using the standard BFS algorithm, while also conforming to the solver model.

Minimum prereqs: Knowledge of the C language and/or CS61C

Article on C based Python extensions

[Ant1ng2]

Additional project, could be done later, use SIMD instructions to parallelize the solve. Result of lscpu:

CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              8
On-line CPU(s) list: 0-7
Thread(s) per core:  2
Core(s) per socket:  4
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               94
Model name:          Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz
Stepping:            3
CPU MHz:             800.154
CPU max MHz:         4200.0000
CPU min MHz:         800.0000
BogoMIPS:            7999.96
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            8192K
NUMA node0 CPU(s):   0-7
Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi 
mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good 
nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg 
fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand 
lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority 
ept vpid fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm mpx rdseed adx smap clflushopt 
intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp 
md_clear flush_l1d```

[Ant1ng2]

Update on issue, successfully tried a C-based extension onto Hanoi. Seems very hard to parallelize BFS however, needs more research. View ants/hanoic branch for more info.

[Ant1ng2]

Unfortunately, binary extensions (CPython extensions) are very hard to maintain between operating systems as outlined in this (albeit incomplete) guide for binary extensions https://packaging.python.org/guides/packaging-binary-extensions.

There are many ways we can approach this issue:

• We continue with CPython extensions and hope for the best to cover all the possible distributions
• We use a different approach, maybe adopt Cython?

Either way this issue will be closed with another issue and discontinued.