Rego Riddle: Power Set

[srenatus]

🖊️ Exercise: Write a function ps such that the following tests pass, and that ps(s) is the power-set of any arbitrarily large input set s.

package ps

test_empty_set {
	ps(set()) = {set()}
}

test_one_element_set {
	ps({"foo"}) = {set(), {"foo"}}
}

test_multiple_elements {
	ps({"foo", "bar"}) = {set(), {"foo"}, {"bar"}, {"foo", "bar"}}
}

test_three_elements {
	ps({1, 2, 3}) = {set(), {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
}

test_ten_elements {
	count(ps({ i | i := numbers.range(1, 10)[_] })) == 1024
}

Who's up for it? I'll share my solution eventually, but I'm curious how others might do it 😄

---

Caveats:

• This probably isn't straightforward, and it's more of a riddle than your everyday rego policy code.
• No http.send. Or actually why not. Anything goes 😎
• If your opa test call takes too long, add --timeout 30s(or more)

[srenatus]

🎊 Posting my solution:

Spoiler 🙈

package ps

ps(xs) = y {
	n := pow2(count(xs))
	es := selectors(n)
	xs0 := [ x | xs[x] ]
	y := { select(e, xs0) | e := split(es[_], "") }
}

selectors(n) = { reverse(format_int(i, 2)) | numbers.range(0, n-1)[i] }
select(e, xs) = { xs[i] | e[i] == "1" }

# 2^^n
pow2(0) = 1
pow2(n) = m {
	n > 0
	b := sprintf("0b1%s", [concat("", ["0" | numbers.range(0, n-1)[_]])])
	m := to_number(yaml.unmarshal(b))
}

# ordinary string reverse, "100" -> "001"
reverse(r) = t {
	some i
	rs := split(r, "")
	n := count(rs)
	ts := [ rs[n-i-1] | _ = rs[i] ]
	t := concat("", ts)
}