Tough logic puzzle

[godelian]

Are you iterating over all possible states and finding the one that matches (or that doesn't contradict, rather) all the given parameters?

It starts with [1,2,3,4,5] for the doors.
Then, there are all the permutations of ["black","brunette","grey","red","blonde"], of which there are 5!=120.

So, you end up with potentially 5 x 120 = 600 partial solutions that look like:

[(1,"black")(2,,"brunette"),(3,"grey"),(4,"red"),(5,"blonde")]

or

[(3,"black")(5,,"brunette"),(1,"grey"),(4,"red"),(2,"blonde")]

...

Even at this stage, with just two properties injected, i.e. door_index and hair_color, quite a few partial solutions will turn out to be invalid.

Next, multiply the solution space by nationality. The solution space will have JavaScript objects with 3 assignments each. And so on.

[Flannel Jesus]

I see, pretty much brute forcing it. It gets the job done.

[godelian]

I see, pretty much brute forcing it. It gets the job done.

If a partial solution is invalid, the algorithm cuts off the entire branch of associated completed solutions. If I remember it right, the size of the solution space never grows larger than around a 1000 partial candidates.

[Flannel Jesus]

I see, pretty much brute forcing it. It gets the job done.

If a partial solution is invalid, the algorithm cuts off the entire branch of associated completed solutions. If I remember it right, the size of the solution space never grows larger than around a 1000 partial candidates.

Oh so it can detect early that a partial solution breaks the rules. Brute forcing with a short cut to make it more efficient

[godelian]

Oh so it can detect early that a partial solution breaks the rules.

Yes.

Brute forcing with a short cut to make it more efficient

Checking the 5^6 solutions at the end or refusing to keep invalid partial solutions during build-up, require the same amount of source code. It doesn't simplify the algorithm. It is also not faster because you end up verifying 15000+ complete solutions instead of at most 1000+ partial ones.

You can speed up things by turning the symbols into numbers. E.g. black=1, red=2, ... Integer comparison is slightly faster in JavaScript but not by that much.

In C, however, integer comparison would be a lot faster. You could also convert pretty much all JavaScript arrays and objects into fixed-size C arrays of 5 bytes.

Only the solution space would still have to be a dynamically growing array. Actually, not even. You could allocate a maximum of 5 arrays of the maximum number of solutions, i.e. 5^6=15000+ solution pointers which would point to a solution, which is an array of 5 assignments of five property values (a byte each).

You can actually do the C solution without any heap allocations, and by doing only omparisons of byte values.

But then again, prototyping in C is much harder than in JavaScript. Once you have a script that works, it is often not hard to turn it into a native program. But then again, once you have the output of the program, you don't really need the program anymore ...

[Flannel Jesus]

Do you think you can solve it by hand?

[godelian]

Do you think you can solve it by hand?

I don't know.
I would probably never try.

It looks very boring to do.

It will always amount to repeating manually some stupid and boring operation again and again. If there were a smarter way to do it, I would just write a smarter program.

[Flannel Jesus]

Do you think you can solve it by hand?

I don't know.
I would probably never try.

It looks very boring to do.

It will always amount to repeating manually some stupid and boring operation again and again. If there were a smarter way to do it, I would just write a smarter program.

Fair enough.

I guess I've always liked a good Sudoku, and this is just a different type of that.

[godelian]

Do you think you can solve it by hand?

I don't know.
I would probably never try.

It looks very boring to do.

It will always amount to repeating manually some stupid and boring operation again and again. If there were a smarter way to do it, I would just write a smarter program.

Fair enough.

I guess I've always liked a good Sudoku, and this is just a different type of that.

I wonder if there is a strategy that is better at eliminating potential solutions?
The maximum number of potential solutions is (5!)^5 = 24883200000.
The strategy I used, manages to painstakingly keep a lid on the otherwise exponential growth of solutions:

$ time ./doors-artists.js

:: injecting [hair_color]
-> number of partial solutions: 24

:: injecting [nationality]
-> number of partial solutions: 2880

:: injecting [musical_style]
-> number of partial solutions: 1296

:: injecting [door_color]
-> number of partial solutions: 1152

:: injecting [profession]
-> number of partial solutions: 1

final number of complete solutions: 1

real 0m3.112s
user 0m3.104s
sys 0m0.005s

The script runs in around 3 seconds. The algorithm manages to keep the number of partial solutions below 3000. If you do this manually, you will need to eliminate potential solutions much more decisively than that because otherwise you will never manage to finish. I wonder how exactly to do that? Is there really a faster algorithm than this? Or would it just depend on sheer luck?

[Gary Childress]

Do you think you can solve it by hand?

I don't know.
I would probably never try.

It looks very boring to do.

It will always amount to repeating manually some stupid and boring operation again and again. If there were a smarter way to do it, I would just write a smarter program.

So, maybe none of us knows the solution to the puzzle other than maybe the one who created the puzzle and anyone who the creator of the puzzle told the solution to?