number.cpp

#include <fstream>
#include <iostream>
#include <memory>
#include <unordered_set>
#include <deque>
#include <forward_list>

int SBOX[] = {0, 3, 1, 4, 2, 5};
int RBOX[] = {0, 2, 4, 1, 3, 5};

inline static unsigned long long convertSingle(int l1, int l2) {
    return l1 | (l2 << 1);
}

inline static void step(std::deque<int> &l1, std::deque<int> &l2) {
    if (l1.front() == 0) {
        l1.pop_front();
    } else {
        l2.push_front(1);
    }
    l1.push_back(0);

    for (int i = 0; i < l1.size(); ++i) {
        int p = SBOX[convertSingle(l1[i], l2[i])];
        l1[i] = p & 1;
        l2[i] = p >> 1;
    }

    while (l1.back() == 0 && l2.back() == 0) {
        l1.pop_back();
        l2.pop_back();
    }
}

inline static int count(std::deque<int> l1, std::deque<int> l2) {
    int cnt = 0;
    while (true) {
        if (l1.size() == 1 && l1.front() == 1 &&
            l2.size() == 1 && l2.front() == 0) {
            return cnt;
        }
        step(l1, l2);
        ++cnt;
    }
}

inline static std::forward_list<std::array<std::deque<int>, 2>> getNext(std::deque<int> l1, std::deque<int> l2) {
    std::forward_list<std::array<std::deque<int>, 2>> ret;
    if (l1.empty() || l2.empty() || (l1.back() == 0 && l2.back() == 0)) {
        return ret;
    }

    for (int i = 0; i < l1.size(); ++i) {
        int p = RBOX[convertSingle(l1[i], l2[i])];
        l1[i] = p & 1;
        l2[i] = p >> 1;
    }

    if (l1.back() == 0) {
        l1.pop_back();
    } else {
        l2.push_back(0);
    }

    // two possibilities
    if (l2.front() == 1 && !l1.empty() && l1.front() != 0) {
        ret.push_front({l1, std::deque<int>(l2.begin() + 1, l2.end())});
    }
    l1.push_front(0);
    ret.push_front({std::move(l1), std::move(l2)});
    return ret;
}

int maximum = 0;

static void dfs(const std::deque<int> &l1, const std::deque<int> &l2, int iter) {
    if (l1.size() >= 24) return;
    if (count(l1, l2) != iter) return;

    if (iter > maximum) {
        std::cout << (maximum = iter) << std::endl;
        for (auto &&i : l1) {
            std::cout << i << ", ";
        }
        std::cout << std::endl;
        for (auto &&i : l2) {
            std::cout << i << ", ";
        }
        std::cout << std::endl;
    }

    for (auto &&n : getNext(l1, l2)) {
        dfs(n[0], n[1], iter + 1);
    }
}

int main() {
    std::deque<int> l1 = {1};
    std::deque<int> l2 = {0};

    dfs(l1, l2, 0);
    return 0;
}

number.go

package main

import (
	"container/heap"
	"fmt"
	"math"
	"math/rand"
	"sync"
	"sync/atomic"
	"time"
)

var RBOX = [...]int{0, 2, 4, 1, 3, 5}
var SBOX = [...]int{0, 3, 1, 4, 2, 5}

func convertSingle(l1, l2 int) uint64 {
	return uint64(l1 | (l2 << 1))
}

func convert(l1, l2 []int) (ret uint64) {
	if len(l1) != len(l2) {
		panic("unequal length")
	}
	mul := uint64(1)
	for i := range l1 {
		ret += mul * convertSingle(l1[i], l2[i])
		mul *= 6
	}
	return
}

func step(l1, l2 []int) ([]int, []int) {
	if l1[0] == 0 {
		l1 = l1[1:]
	} else {
		l2 = append([]int{1}, l2...)
	}
	l1 = append(l1, 0)

	for i := range l1 {
		p := SBOX[convertSingle(l1[i], l2[i])]
		l1[i], l2[i] = p&1, p>>1
	}

	for l1[len(l1)-1] == 0 && l2[len(l2)-1] == 0 {
		l1 = l1[:len(l1)-1]
		l2 = l2[:len(l2)-1]
	}

	return l1, l2
}

func count(l1, l2 []int) int {
	cnt := 0
	for {
		if len(l1) == 1 && l1[0] == 1 &&
			len(l2) == 1 && l2[0] == 0 {
			return cnt
		}
		l1, l2 = step(l1, l2)
		cnt++
	}
}

func getNext(l1, l2 []int) (ret [][2][]int) {
	if len(l1) <= 0 || len(l2) <= 0 || l1[len(l1)-1] == 0 && l2[len(l2)-1] == 0 {
		return
	}
	for i := range l1 {
		p := RBOX[convertSingle(l1[i], l2[i])]
		l1[i], l2[i] = p&1, p>>1
	}
	if l1[len(l1)-1] != 0 {
		l2 = append(l2, 0)
	} else {
		l1 = l1[:len(l1)-1]
	}
	// two possibilities
	if l2[0] == 1 && len(l1) > 0 && l1[0] != 0 {
		ret = append(ret, [2][]int{l1, l2[1:]})
	}
	ret = append(ret, [2][]int{append([]int{0}, l1...), l2})
	return
}

var condLock = sync.Cond{L: new(sync.Mutex)}
var workHeap pq
var maximum uint64 = 0

func dfs(l1, l2 []int, iter uint64) {
	mx := atomic.LoadUint64(&maximum)
	for mx < iter {
		if atomic.CompareAndSwapUint64(&maximum, mx, iter) {
			fmt.Println(l1, l2, iter)
			break
		}
		mx = atomic.LoadUint64(&maximum)
	}
	next := getNext(l1, l2)

	n := next[0]
	if len(n[0]) >= 24 {
		return
	}

	nl1, nl2 := make([]int, len(n[0])), make([]int, len(n[1]))
	copy(nl1, n[0])
	copy(nl2, n[1])

	if count(nl1, nl2) == int(iter+1) {
		nl1, nl2 = make([]int, len(n[0])), make([]int, len(n[1]))
		copy(nl1, n[0])
		copy(nl2, n[1])

		dfs(nl1, nl2, iter+1)
	}

	for _, n := range next[1:] {
		if len(n[0]) >= 24 {
			continue
		}
		nl1, nl2 = make([]int, len(n[0])), make([]int, len(n[1]))
		copy(nl1, n[0])
		copy(nl2, n[1])

		if count(nl1, nl2) != int(iter+1) {
			continue
		}

		nl1, nl2 = make([]int, len(n[0])), make([]int, len(n[1]))
		copy(nl1, n[0])
		copy(nl2, n[1])

		condLock.L.Lock()
		heap.Push(&workHeap, &work{
			l1:   nl1,
			l2:   nl2,
			iter: iter + 1,
		})
		condLock.Signal()
		condLock.L.Unlock()
	}
}

func worker() {
	condLock.L.Lock()
	defer condLock.L.Unlock()

	for {
		for workHeap.Len() <= 0 {
			condLock.Wait()
		}
		var top *work
		if rand.Float64() < .5 {
			top = heap.Pop(&workHeap).(*work)
		} else {
			top = heap.Remove(&workHeap, rand.Intn(len(workHeap))).(*work)
		}
		condLock.L.Unlock()
		dfs(top.l1, top.l2, top.iter)
		condLock.L.Lock()
	}
}

func main() {
	l1 := []int{0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0}
	l2 := []int{0, 1, 0, 0, 0, 1, 0, 1, 1, 2, 2, 1, 1, 0, 2, 2, 1, 0, 0, 0, 2, 0, 2}

	workHeap = []*work{}

	iter := uint64(1636)
	for {
		if len(l1) == 1 && l1[0] == 1 &&
			len(l2) == 1 && l2[0] == 0 {
			break
		}
		iter--
		fmt.Println(convert(l1, l2))
		l1, l2 = step(l1, l2)
		//heap.Push(&workHeap, &work{
		//	l1:   append(([]int)(nil), l1...),
		//	l2:   append(([]int)(nil), l2...),
		//	iter: iter,
		//})
	}

	fmt.Println(convert(l1, l2))
	//for i := 0; i < runtime.NumCPU(); i++ {
	//	go worker()
	//}
	//select {}
}

func main2() {
	rand.Seed(time.Now().UnixNano())

	workHeap = []*work{{
		l1: []int{1},
		l2: []int{0},
	}}

	worker()
}

type work struct {
	l1, l2 []int
	iter   uint64
}

func (w *work) op() float64 {
	return math.Sqrt(float64(w.iter)/1500.) - .7*float64(len(w.l1))/23.
	//return float64(w.iter) / math.Pow(float64(len(w.l1)), 2)
	//return math.Pow(float64(w.iter), 0.8) / math.Pow(float64(len(w.l1)), 1.5)
	//return math.Log(float64(w.iter)) / math.Pow(float64(len(w.l1)), 0.5)
	//return math.Max(float64(w.iter)/2000., .2-math.Pow(2*float64(len(w.l1))/24.-1, 2))
	//return math.Pow(float64(w.iter), 1.-math.Pow(2*float64(len(w.l1))-1, 2))
}

type pq []*work

func (p *pq) Len() int {
	return len(*p)
}

func (p *pq) Less(i, j int) bool {
	return (*p)[i].iter < (*p)[j].iter
}

func (p *pq) Swap(i, j int) {
	(*p)[i], (*p)[j] = (*p)[j], (*p)[i]
}

func (p *pq) Push(x interface{}) {
	*p = append(*p, x.(*work))
}

func (p *pq) Pop() interface{} {
	n := len(*p)
	x := (*p)[n-1]
	*p = (*p)[:n-1]
	return x
}