Last active
March 8, 2021 19:44
Star
You must be signed in to star a gist
calculate path into a binary tree for some element
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
% -*- mode: Prolog -*- | |
% See https://twitter.com/krismicinski/status/1368611779107053570?s=03 | |
% gives a program in Racket; I've written my version in | |
% non-deterministic Prolog. | |
% Tested with SWI-Prolog 8.3.20 | |
% (You can also try this out at https://swish.swi-prolog.org/) | |
% The problem is (using Racket terminology): | |
% Write a function (tree-path t elt) that returns a list of either | |
% ‘left, ‘right, or ‘here that computes the path into the tree for | |
% some element. Your function should return the empty list if the | |
% element is not present in the tree. | |
% A Racket solution is given here (with some typos): | |
% https://gist.github.com/kmicinski/f3db68d8374a43edf471702f664e17ce | |
tree_path(node(V, _, _), V, [here]). | |
tree_path(node(_, Left, _Right), V, [left|Path]) :- | |
tree_path(Left, V, Path). | |
tree_path(node(_, _Left, Right), V, [right|Path]) :- | |
tree_path(Right, V, Path). | |
% Test cases. | |
:- use_module(library(plunit)). | |
:- begin_tests(tree_path). | |
% (tree-path ‘(leaf 5) 5) => ‘(here) | |
test(t1, [nondet, true(Path == [here])]) :- | |
tree_path(node(5, empty, empty), 5, Path). | |
% (tree-path ‘(node 10 (node 5 empty empty) (node 20 (node 12 empty empty) empty)) 5) => ‘(left here) | |
test(t2, [nondet, true(Path == [left, here])]) :- | |
tree_path(node(10, | |
node(5, empty, empty), | |
node(20, | |
node(12, empty, empty), | |
empty)), | |
5, Path). | |
% (tree-path ‘(node 10 (node 5 empty empty) (node 20 (node 12 empty empty) empty)) 20) => ‘(right here) | |
test(t3, [nondet, true(Path == [right, here])]) :- | |
tree_path(node(10, | |
node(5, empty, empty), | |
node(20, | |
node(12, empty, empty), | |
empty)), | |
20, Path). | |
% (tree-path ‘(node 10 (node 5 empty empty) (node 20 (node 12 empty empty) empty)) 12) => ‘(right right here) | |
% ^^^^^ | |
test(t4, [nondet, true(Path == [right, left, here])]) :- | |
tree_path(node(10, | |
node(5, empty, empty), | |
node(20, | |
node(12, empty, empty), empty)), | |
12, Path). | |
% (tree-path ‘(node 10 (node 5 empty empty) (node 20 (node 12 empty empty) empty)) 50) => ‘() | |
test(t5, [fail]) :- | |
tree_path(node(10, | |
node(5, empty, empty), | |
node(20, | |
node(12, empty, empty), | |
empty)), | |
50, _Path). | |
:- end_tests(tree_path). | |
:- run_tests. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment