package main

import (
	"fmt"
	"strconv"
)

func reverseSlice(slice []uint) {
	for i, j := 0, len(slice)-1; i < j; i, j = i+1, j-1 {
		slice[i], slice[j] = slice[j], slice[i]
	}
}

func compressedProgram(ra uint) []uint {
	out := make([]uint, 0)

	var A, B uint
	A = ra

	for {
		B = ((A % 8) ^ 2) ^ 7 ^ (A >> ((A % 8) ^ 2))
		A = A >> 3

		out = append(out, B%8)

		if A == 0 {
			break
		}
	}

	return out
}

func reversedProgram(out []uint) uint {
	reverseSlice(out)
	A := uint(0)

	for _, o := range out {
    
		// find next n bits so that o is returned
        n := 2
        searching := true
        for searching {
            n++

            // for every combination of n bits
		    for i := range 1 << n {
                A_ := (A << n) + uint(i)

                //fmt.Println("add", i, "as binary with", n, "bits")
		    	//fmt.Println("old", strconv.FormatUint(uint64(A), 2))
		    	//fmt.Println("new", strconv.FormatUint(uint64(A_), 2))

		    	if o == ((A_%8)^2)^7^(A_>>((A_%8)^2))%8 {
		    		A = A_
		    	    //fmt.Println("valid")
		    		//fmt.Println("yields", compressedProgram(A))
                    searching = false
		    		break
		    	}

		    	//fmt.Println("invalid")
		    }
        }

	}
	return A
}

func main() {
	/*


		fmt.Println(input)

		a := uint64(0)
		for _, elem := range input {

			expected_d := elem ^ 7
			for b := range 8 {
				e := uint64(b ^ 2)
				c := (((a << 3) | uint64(b)) >> (e)) % 8
				actual_d := c ^ e
				if uint64(expected_d) == actual_d {
					fmt.Println(b)
					fmt.Println(e)
					fmt.Println(c)
					a = a << 3
					a = a | uint64(b)
					fmt.Println(strconv.FormatUint(a, 2))
					fmt.Println(a, 2)
					break
				}
			}

		}
		fmt.Println(a)
		//fmt.Println(strconv.FormatUint(a, 2))
	*/

	//fmt.Println(compressedProgram(41644071))

	input := []uint{2, 4, 1, 2, 7, 5, 1, 7, 4, 4, 0, 3, 5, 5, 3, 0}
	fmt.Println("-- input: ", input, "--")
	ra := reversedProgram(input)
	fmt.Println("-- ra:    ", ra, "--")
}