Tree algorithm for finding sum

algorithm.cpp

// Given a list of M integers, find those whose sum is N
#include <list>
#include <string>
#include <iostream>
#include <cassert> // assert

// This could be anything, and this is the expected sum
#define EXPECTED 72

// This is the general "run things" function. It scales to any number of
// integers.
void run(std::list<int> list);

#define ADDING true
#define SUBTRACTING false
#define UNREACHABLE() assert(("unreachable!", 0))

// Print the string however you want (e.g. printf).
void print_str(std::string* str) {
    std::cout << str;
}

template<typename T>
using shared_ptr = std::shared_ptr<T>;

template<typename T>
class Deque;

// You can modify this however you need to. An example implementation is further
// below.
shared_ptr<Deque<int>> makeDeque(const std::list<int>& list);

inline int calc(int prev, bool adding, int result) noexcept {
    return adding ? prev + result : prev - result
}

// It's usually frowned upon to make your properties public in a class, but it
// works here, so I do it quite frequently. Plus, I'm used to JavaScript, which
// doesn't have privacy.

enum class OperationType {NONE, ADD, SUB, MUL, DIV}

class Operation {
private:
    int value_;
    OperationType op_;

public:
    Operation(int value, OperationType op) : value_(value), op_(op) {}

    void print(std::string* result) noexcept {
        switch (op_) {
        case OperationType::NONE: break;
        case OperationType::ADD: result->append("+ "); break;
        case OperationType::SUB: result->append("- "); break;
        case OperationType::MUL: result->append("* "); break;
        case OperationType::DIV: result->append("/ "); break;
        default: UNREACHABLE();
        }
        result->append(std::to_string(value_));
    }
}

template<typename T>
class Deque {
public:
    shared_ptr<T> value;
    shared_ptr<Deque<T>> prev;
    shared_ptr<Deque<T>> next;

    Deque(
        const shared_ptr<T>& value_ = nullptr,
        const shared_ptr<Deque<T>>& prev_ = nullptr
    ) : value(value_), prev(prev_) {}

    ~Deque() {}

    inline shared_ptr<Deque<T>> push(const T* value) noexcept {
        Deque<T> next_value(value, this);
        next = shared_ptr(next_value);
        return next;
    }

    shared_ptr<std::list<T>> toList() {
        std::list<T> result;
        shared_ptr<Deque<T>> node = next;

        while (node) {
            result.push_back(node->value);
            node = node->next;
        }

        return shared_ptr(result);
    }
}

shared_ptr<Deque<int>> makeDeque(const std::list<int>& list) {
    auto root = std::make_shared<Deque<int>>();

    for (auto item : list) {
        auto shared_int = std::make_shared<int>(item);
        root->next = std::make_shared<Deque<int>>(shared_int, root);
        root = root->next;
    }

    return root;
}

class Tree {
private:
    shared_ptr<Operation> value_;
    Deque<shared_ptr<Tree>> root_;
    shared_ptr<Deque<Tree>> children_(root);

public:
    Tree(shared_ptr<Operation> value = nullptr) : value_(value) {}
    ~Tree() {}

    shared_ptr<Tree> add(int value, OperationType op = OperationType::NONE) {
        Tree tree(std::make_shared<Operation>(value, op));
        children_ = children_->push(tree);
        return shared_ptr(tree);
    }

private:
    void print_self(std::string* prev) {
        std::string str(*prev);
        value->print(&str);

        if (root_ == *children_) {
            // Print the string, or whatever;
            print_str(str);
        } else {
            str += " ";
            shared_ptr<Deque<Tree>> node = root.next;
            while (node) {
                node->value->print_self(&str);
                node = node->next;
            }
        }
    }

    void print() {
        std::string str;
        shared_ptr<Deque<Tree>> node = root.next;
        while (node) {
            node->value->print_self(&str)l
            node = node->next;
        }
    }
}

void iterate(
    shared_ptr<Tree> path,
    int prev,
    bool lastOp, // ADDING or SUBTRACTING
    int addAcc,
    int mulAcc,
    int last,
    shared_ptr<Deque<int>> deque
) {
    if (!deque->next) {

#define PUSH(result) \
    if (result == EXPECTED) path->add(calc(prev, lastOp, result));

        PUSH(addAcc + deque->value)
        PUSH(addAcc - deque->value)
        PUSH(mulAcc * deque->value)
        if (!(last % deque->value)) PUSH(mulAcc / deque->value)

#undef PUSH

    } else {
        shared_ptr<Tree> current(deque->value);
        shared_ptr<Tree> rest(deque->next);

#define PUSH(op, result, adding) \
    iterate(path->add(last, op),
        calc(prev, lastOp, result), adding, 0, 1, deque->value,
        deque->next);

        PUSH("+", addAcc + current, ADDING)
        PUSH("-", addAcc - current, SUBTRACTING)
        
#undef PUSH
#define PUSH(op, result, adding) \
    iterate(path->add(last, op),
        calc(prev, lastOp, result), adding, 0, 1, deque->value,
        deque->next);

        iterateMul("*", mulAcc * current)
        if (last % current == 0) iterateMul("/", mulAcc / current)
#undef PUSH

    }
}

void run(std::list<int> list) {
    switch (list.length) {
    case 0: return;
    case 1: {
        if (list[0] == EXPECTED) print_str(`${list[0]}`);
        return;
    }
    case 2: {
        if (list[0] + list[1] == EXPECTED) print_str(`${list[0]} + ${list[1]}`);
        if (list[0] - list[1] == EXPECTED) print_str(`${list[0]} - ${list[1]}`);
        if (list[0] * list[1] == EXPECTED) print_str(`${list[0]} * ${list[1]}`);

        if (list[0] % list[1] == 0) {
            if (list[0] / list[1] == EXPECTED) print_str(`${list[0]} / ${list[1]}`);
        }
        return;
    }
    default: {
        shared_ptr<Deque<int>> deque = makeDeque(&list);
        shared_ptr<Deque<int>> next = deque->next;
        auto tree = std::make_shared<Tree>();

#define ITERATE(compute) iterate(&tree, compute, "+", 0, 1, next->value, next);

        ITERATE(deque->value + next->value)
        ITERATE(deque->value - next->value)

#undef
#define ITERATE(compute)
    do { \
         \
        int value = deque->value * next->value;
        iterate(&tree, 0, "+", value, value, next->value, next);
    }


        if (deque->value % next->value == 0) {
            ITERATE(deque->value / next->value)
        }

        tree->print();

        return;
    }
    }
}

algorithm.js

// Given a list of M integers, find those whose sum is N

const ADDING = true
const SUBTRACTING = false

function calc(prev, adding, result) {
    return adding ? prev + result : prev - result
}

class Deque {
    constructor(value, prev) {
        this.value = value
        this.prev = prev
        this.next = undefined
    }

    push(value) {
        return this.next = new Deque(value, this)
    }

    toArray() {
        const result = []
        let node = this
        while (node = node.next) {
            result.push(node.value)
        }
        return result
    }
}

function makeDeque(iter) {
    let root = new Deque()

    for (const item of iter) {
        root = root.next = new Deque(item, root)
    }

    return root
}

class Tree {
    constructor(value) {
        this.value = value
        this.root = new Deque()
        this.children = this.root
    }

    add(value, op) {
        const tree = new Tree({value, op})
        this.children = this.children.push(tree)
        return tree
    }

    _print(prev) {
        let str = prev
        if (this.value.op !== undefined) {
            str += this.value.op + " " + this.value.value
        } else {
            str += this.value.value
        }

        if (this.root === this.children) {
            console.log(str)
        } else {
            let node = this.children
            while (node = node.next) {
                node.value._print(str + " ")
            }
        }
    }

    print() {
        let node = this.root

        while (node = node.next) {
            node.value._print("")
        }
    }
}

function iterate(expected, path, prev, lastOp, addAcc, mulAcc, last, deque) {
    if (deque.next == null) {
        const pushCalc = result => {
            if (result === expected) {
                path.add(calc(prev, lastOp, result))
            }
        }
        pushCalc(addAcc + deque.value)
        pushCalc(addAcc - deque.value)
        pushCalc(mulAcc * deque.value)
        if (last % deque.value === 0) pushCalc(mulAcc / deque.value)
    } else {
        const current = deque.value
        const rest = deque.next
        const iterateAdd = (op, result, adding) =>
            this.iterate(expected, path.add(last, op),
                calc(prev, lastOp, result), adding, 0, 1, deque.value,
                deque.next)

        iterateAdd("+", addAcc + current, ADDING)
        iterateAdd("-", addAcc - current, SUBTRACTING)

        const iterateMul = (op, result) =>
            this.iterate(expected, path.add(last, op), prev, lastOp, result,
                result, current, rest)

        iterateMul("*", mulAcc * current)
        if (last % current === 0) iterateMul("/", mulAcc / current)
    }
}

function run(list, expected) {
    switch (list.length) {
    case 0: return
    case 1: {
        if (list[0] === expected) console.log(`${list[0]}`)
        return
    }
    case 2: {
        if (list[0] + list[1] === expected) console.log(`${list[0]} + ${list[1]}`)
        if (list[0] - list[1] === expected) console.log(`${list[0]} - ${list[1]}`)
        if (list[0] * list[1] === expected) console.log(`${list[0]} * ${list[1]}`)

        if (list[0] % list[1] === 0) {
            if (list[0] / list[1] === expected) console.log(`${list[0]} / ${list[1]}`)
        }
        return
    }
    default: {
        const deque = makeDeque(list)
        const next = deque.next
        const tree = new Tree()
        iterate(expected, tree, deque.value + next.value, "+", 0, 1, next.value, next)
        iterate(expected, tree, deque.value - next.value, "-", 0, 1, next.value, next)

        let mul = deque.value * next.value
        iterate(expected, tree, 0, "*", mul, mul, next.value, next)

        if (deque.value % next.value === 0) {
            let div = deque.value / next.value
            iterate(expected, tree, 0, "/", div, div, next.value, next)
        }

        tree.print()

        return
    }
    }
}