The Wrong Way to Hang a Painting

This is probably how you hang your paintings:

Cat, Henriëtte Ronner-Knip, 1897

But this is how I hang mine:

Unfortunately, management has noticed that your painting hangs perfectly well from a single nail. Naturally, they’ve cut your nail budget in half.

You could accept this. Or you could find a way to hang the painting so that it stays up with both nails, but falls when either one is removed.

Can you make both nails indispensable?

Back to Basics

Let’s simplify it to just one nail. Suppose you have the cord wrapped clockwise around the nail.

The cord would fall if somehow your wrap was undone. So you can, in a way, wrap it again counterclockwise to undo what you did.

Let’s represent a clockwise wrap with A and a counterclockwise wrap with a.

Mathematicians may prefer A⁻¹. We've gone with a to satiate management's hatred for mathematicians.

We can now write what we just did as Aa. The A and a cancel each other, so the cord falls.

NEED MORE NAILS

If you wanted A and a to not immediately cancel each other, you’d have to separate them somehow.

You can do just this by introducing nail B.

So how would ABa behave? Notice that removing B leaves just Aa, which cancel each other. But removing nail A leaves B, which means it will still hang onto nail B.

If we wanted B to cancel out too, we'd just have to add its inverse (which is b). So it becomes ABab. That is clockwise A, clockwise B, counterclockwise A, counterclockwise B.

Code it Up

Let's put the cancellation rule into code.

// assert!(are_inverses('A', 'a'));
// assert!(!are_inverses('A', 'A'));
fn are_inverses(a: char, b: char) -> bool {
    a != b && a.eq_ignore_ascii_case(&b)
}

fn reduce(word: &str) -> String {
    let mut stack = Vec::new();

    for letter in word.chars() {
        match stack.last() {
            Some(&last) if are_inverses(last, letter) => {
                stack.pop();
            }
            _ => stack.push(letter),
        }
    }

    stack.into_iter().collect()
}

The original code was written in Python, but management asked us to simply rewrite it in Rust.

Each letter either cancels the one on top of the stack or gets added to the stack.

assert_eq!(reduce("ABba"), "");     // Bb cancels, then Aa.
assert_eq!(reduce("ABab"), "ABab"); // No neighbors cancel.

Make Every Nail Count

With your newfound ability, you decide to ask management for even more nails, promising to make each nail count.

One nail

Let’s call the number of nails n. With n = 1, a single clockwise wrap does the job.

Two nails

For n = 2, take that hanging, wrap around B, undo the previous hanging, then undo B.

Three nails

For n = 3, the previous hanging is the whole of ABab. Treat it as one piece and repeat the same pattern with C.

To undo a whole word, reverse its order and flip each letter’s case. So the inverse of ABab is BAba.

fn inverse(word: &str) -> String {
    word.chars()
        .rev()
        .map(|letter| {
            if letter.is_ascii_uppercase() {
                letter.to_ascii_lowercase()
            } else {
                letter.to_ascii_uppercase()
            }
        })
        .collect()
}

fn solve(n: u8) -> String {
    // We only have 26 letters!
    assert!((1..=26).contains(&n));
    let mut word = String::from("A");

    for nail in (b'A'..=b'Z').take(n as usize).skip(1) {
        let letter = char::from(nail);
        let undo_word = inverse(&word);
        let undo_letter = letter.to_ascii_lowercase();
        word = format!("{word}{letter}{undo_word}{undo_letter}");
    }

    word
}

Try adding more nails:

Divide and Unwrap

All that wrapping is making you tired. You read somewhere that you should “work smarter, not harder”, so you decide to stop adding nails one at a time.

Say you want to solve for n=4. You already know how to solve for n=2: ABab. For C and D it's also essentially the same: CDcd. Now you only need a way to combine these two.

Remember that when we wanted to avoid Aa reducing right away, we had to add the new nail in the middle and add its undo at the end.

So with this one we can do the same: insert CDcd between ABab and its undo (BAba) and add CDcd's undo (DCdc) at the end.

We still do first hanging, second hanging, undo first, undo second. But now we are doing it in batches. Four nails take 16 wraps instead of 22.

fn solve_balanced(n: u8) -> String {
    assert!((1..=26).contains(&n));
    let nails: Vec<String> = ('A'..='Z')
        .take(n as usize)
        .map(|nail| nail.to_string())
        .collect();
    build_balanced(&nails)
}

fn build_balanced(seq: &[String]) -> String {
    // Keep splitting until each group contains just one word
    if seq.len() == 1 {
        return seq[0].clone();
    }

    let (left, right) = seq.split_at(seq.len() / 2);
    let x = build_balanced(left);
    let y = build_balanced(right);
    let undo_x = inverse(&x);
    let undo_y = inverse(&y);
    format!("{x}{y}{undo_x}{undo_y}")
}

At eight nails, we're down to 64 wraps instead of 382. Each nail is still indispensable.

Back to the cat:

Safety Inspection

Management has discovered that removing any nail causes a catastrophe.

They demand redundancy: either A or B can cover for the other, and so can C or D. The painting should fall only when both nails in either pair are gone.

We can represent that falling condition like this: (A and B) or (C and D).

In the logic representation, letters mean a nail has been removed, not wraps.

First we need a way to represent our rule in code.

enum Rule {
  Nail(u8),
  And(Vec<Rule>),
  Or(Vec<Rule>),
}

use Rule::*;

// (A and B) or (C and D)
let rule = Or(vec![
  And(vec![Nail(b'A'), Nail(b'B')]),
  And(vec![Nail(b'C'), Nail(b'D')]),
]);

A and B has multiple solutions: AB, Ab, aB, ab. Let's choose the first one for now and generalize it: in order to and, we add the first word to the second word.

We already have the code to generate wrapping when any one of the n nails is removed, so we can trivially solve for something like A or B or C or D using our existing build_balanced.

The neat thing is that build_balanced also already works for words as well as letters, so we could give it AB or CD.

For (A and B) or (C and D):
Left AND: X = AB
Right AND: Y = CD
Outer OR: X Y inverse(X) inverse(Y)
Result: ABCDbadc

fn solve_rule(rule: &Rule) -> String {
  match rule {
      Rule::Nail(nail) => char::from(*nail).to_string(),

      Rule::And(rules) => {
          // Solve the inner rule and concat the results
          rules.iter().map(solve_rule).collect::<Vec<_>>().concat()
      }

      Rule::Or(rules) => {
          let words: Vec<_> = rules.iter().map(solve_rule).collect();
          build_balanced(&words)
      }
  }
}

Edge Cases

Consider this rule: A or A. Our current solver produces AAaa which immediately reduces.

Also for (A and B) or (A and C), the solver produces:
X = AB
Y = AC
Word = ABACbaca
Remove B and C:
ABACbaca → AAaa → empty
The picture falls, but the condition is false: both branches require removing A, which is still present.

The problem is that build_balanced doesn't handle repeated letters reliably and can cause unintended cancellation. In this example we can fix repeated letters by factoring A, giving A and (B or C). But it won't work for all rules; for example, however we factor (A and B) or (A and C) or (B and C), we're still left with repeated letters.

We need a way to make sure each or operation contains only distinct letters. We can do this by converting (A and B) or (A and C) into (A or A) and (A or C) and (B or A) and (B or C). After simplifying: A and (A or C) and (B or A) and (B or C).

Management has asked us not to mention that mathematicians call this: "conjunctive normal form (CNF): an AND of groups, where each group contains OR-connected letters" because of reasons stated before. So as far as you're concerned CNF means Company Nail Format.

// Outer list: AND
// Inner lists: OR
type Cnf = Vec<Vec<u8>>;

fn to_cnf(rule: &Rule) -> Cnf {
  let mut groups = match rule {
      Rule::Nail(nail) => vec![vec![*nail]],

      Rule::And(rules) => {
          assert!(!rules.is_empty());
          rules.iter().flat_map(to_cnf).collect()
      }

      Rule::Or(rules) => rules
          .iter()
          .map(to_cnf)
          .reduce(distribute)
          .expect("OR needs at least one rule"),
  };

  // Descending starting letters prevent cancellation between boundaries.
  groups.sort_by(|a, b| b[0].cmp(&a[0]));
  groups
}

fn distribute(left: Cnf, right: Cnf) -> Cnf {
    let mut groups = Vec::new();

    for a in &left {
        for b in &right {
            let mut group = a.clone();
            group.extend(b);
            // [A, B, A] -> [A, A, B] -> [A, B]
            group.sort_unstable();
            group.dedup();
            groups.push(group);
        }
    }

    groups
}

[
    [A, B],
    [A, C],
]

Rule::Nail(nail) => vec![vec![*nail]],

[
    [A]
]

(A)

Rule::And(rules) => {
    rules.iter().flat_map(to_cnf).collect()
}

rules.iter()

Nail(A),
Nail(B),

.map(to_cnf)

[[A]]
[[B]]

[A]
[B]

[
    [A],
    [B],
]

fn distribute(left: Cnf, right: Cnf) -> Cnf {
    let mut result = Vec::new();

    for a in &left {
        for b in &right {
            let mut group = a.clone();
            group.extend(b);

            group.sort_unstable();
            group.dedup();

            result.push(group);
        }
    }

    result
}

left=[
    [A],
    [B],
]
right=[
    [A],
    [C],
]

for a in &left {
    for b in &right {

[A] × [A]
[A] × [C]
[B] × [A]
[B] × [C]

a = [A]
b = [A]

let mut group = a.clone();
group.extend(b);

[A, A]

[
    [A, A],
    [A, C],
    [B, A],
    [B, C],
]

group.sort_unstable();
group.dedup();

[
  [A],
  [A, C],
  [A, B],
  [B, C],
]

Rule::Or(rules) => {
    rules
        .iter()
        .map(to_cnf)
        .reduce(distribute)
        .expect("OR needs at least one rule")
}

[[A]]
[[B]]
[[C]]

distribute([[A]], [[B]])

[[A, B]]

distribute([[A, B]], [[C]])

[[A, B, C]]

groups.sort_by(|a, b| b[0].cmp(&a[0]));

Converting back to Rule

fn cnf_to_rule(groups: Cnf) -> Rule {
    Rule::And(
        groups
            .into_iter()
            .map(|group| Rule::Or(group.into_iter().map(Rule::Nail).collect()))
            .collect(),
    )
}

let normalized = cnf_to_rule(to_cnf(&rule));
let word = solve_rule(&normalized);

Now you can write any rule using and, or, and parentheses:

See if you can write a rule to fall if any 2 of the 4 nails are removed.

A Change of Scenery

So far we've been drilling nails into the wall in a relatively straight line, but to your amusement, the wrapping rules don't care where each nail is.

Budget Cuts

There is one final optimization you could do.

fn simplify_cnf(mut groups: Cnf) -> Cnf {
  // Smaller groups can make larger groups redundant.
  groups.sort_by_key(Vec::len);

  let mut kept: Cnf = Vec::new();

  for group in groups {
      let redundant = kept.iter().any(|smaller| {
          smaller.iter().all(|nail| group.contains(nail))
      });

      if !redundant {
          kept.push(group);
      }
  }

  // Restore the ordering used when joining the wrapping words.
  kept.sort_by(|a, b| b[0].cmp(&a[0]));
  kept
}

This converts something like:

[A]
[A, C]
[A, B]
[B, C]

to

[B, C]
[A]

Because those larger groups' logic is already covered by the smaller group.

You've Been Promoted

Congratulations, you can now decide where each nail goes and which ones matter.

The code for this article is available at:
https://github.com/tholoo/hanging-painting-puzzle