Reverse Factorization

main.go

package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"sort"
	"strconv"
	"strings"
)

// Language: Go
//
// Running:
//
// ```go
// $ go run main.go
// 12 3
// 2 3 4
// 1 3 12
// $
// ```

func main() {
	// Read input from STDIN
	reader := bufio.NewReader(os.Stdin)
	line := readline(reader)
	args := strings.Split(line, " ")
	numberTmp, err := strconv.ParseInt(args[0], 10, 64)
	checkError(err)
	// Final number N
	number := int(numberTmp)
	line = readline(reader)
	checkError(err)
	// Elements contains the array of numbers.
	// Then the elements are filtered to contain only
	// factors of N.
	// The elements are then filtered to match the
	// the smallest path.
	elements := make([]int, 0)
	for _, n := range strings.Split(line, " ") {
		element, err := strconv.ParseInt(n, 10, 64)
		checkError(err)
		elements = append(elements, int(element))
	}
	filtered := elements[:0]
	for _, n := range elements {
		if number%n == 0 {
			filtered = append(filtered, n)
		}
	}
	sort.Ints(filtered)
	path := make([]int, 0)
	path = append(path, 1)
	// If there is a path, we iterate the path elements
	// multiplying each element by N to print the way
	// up to N.
	if solved, path := solve(filtered, 1, number, path); solved {
		number := 1
		for _, n := range path {
			number *= n
			fmt.Printf("%d ", number)
		}
		fmt.Printf("\n")
		return
	}
	fmt.Printf("-1")
}

func solve(elements []int, current int, number int, path []int) (bool, []int) {
	// If N == 1, there is only one element path.
	if number == 1 {
		return true, path
	}
	// If N < 1 or the current element is out of range,
	// there is not path from this current element.
	if number < 1 || current >= len(elements) {
		return false, path
	}
	// If the current element is a factor of N
	// we append the current element to the path
	// and recursively find the path elements
	// by dividing N by the current element.
	// The elements are then multiplied by N
	// when output is shown.
	if (number % elements[current]) == 0 {
		path = append(path, elements[current])
		if solved, newPath := solve(elements, current, number/elements[current], path); solved {
			return true, newPath
		}
		path = path[:len(path)-1]
	}
	// If the current element is not a factor of N
	// we move to the next element in the array.
	return solve(elements, current+1, number, path)
}

func readline(reader *bufio.Reader) string {
	line, _, err := reader.ReadLine()
	if err == io.EOF {
		return ""
	}
	return strings.TrimRight(string(line), "\r\n")
}

func checkError(err error) {
	if err != nil {
		panic(err)
	}
}