Well I was trying to work out how to write a program to find all possible solutions, and was just going to check all permutations of the stack order against whatever criteria made a solution valid. Then it occurred to me that the folds joining different sections couldn't overlap, so I tried to find a way that could help. Then when visualising how the folds worked I noticed they would always be on a constant side, so groups of folds could be checked against each other to find the solution. As for the code to write it, I cycles through all permutations of the stack with the sections in an array, and for each permutation check each pair of a fold against each other pair on the same side to make sure they are both higher, both lower, or nested within the other pair... iterate through all that and reject any that fail and I was left with just the valid solutions. I'm thinking of doing another video on how this generalises to other sizes of sheets.
At 06:43 your substitution rule giving letters for numbers is not correct. After having found a feasible stacking order of the paper segments 0 - 7 without any crossing of the folds on either side you do not replace 0 by A, 1 by B and so on. Instead you have to walk through the sequence of paper segments from left to right (which is physically from top to bottom of the stack) and placing the letters A - H in that order on the paper segment indicated by the actual digit representing this segment. Interestingly your letter combinations presented at 06:47 - 07:33 are all correct. However the stack segment orders represented by digits at 06:40 are not all correct. The top left stacking order 01237654 is correct and represents ABCDHGFE as shown. But the second stacking order 01275436 is not a valid solution. After correct digit-by-letter replacement this gives ABCGFEHD which cannot be done. Another example is the first (yellow) puzzle AHGDBCFE which was used at 04:44 - 05:58 and has a stacking order of 04537621. This stacking order is not included at 06:40 and the letter combination AHGDBCFE has been replaced from 07631254 which stands for AEFDHGCB and again is not a valid stacking order.
Damn, you're right! My main focus was on trying to get the algorithm to work out the number of possible permutations, so converting to letters was more of an after thought for the video. I think I'm going do a short follow-up video on this same concept with other sized sheets, so I'll correct this in that video if I get around to making it!
I know, and I've been trying to think of how to do that, but having seen the solutions to the 2 puzzles in the Stand-up Maths video, I don't think there's any way to describe the fold method for all cases mathematically. Some of the folds are really strange
@@JamesExplains I've come very close to logically describing it. I was using a 3d array. Before making a given fold, it can check how many places one side of it can go to the other side, whether it be on the top, the bottom, or inside / in between itself (origami thing). It can see if it's possible by checking if the connections between the panels will cause any intersections. That means it must also iterate between all the things that can fold, which can either be one bend or multiple bends if the neighboring connections allow it (which means the first of Matt's puzzles where the (SPOILER) inside of it actually folds would be checked as well) (And it should also contains a method to see if two given panels are connected and on which side) Matt's second puzzle is where I halted.....
Hi, i wrote a program in javascript to solve all possibles puzzles of this problem and this is the results i get: Number of generated puzzles = 40320 Number of resolved puzzles (having a solution) = 168 (0,416% of total puzzles) Number of puzzles with no solution = 40152 (99,583 of total puzzles) Some examples of puzzles having a solution: HGAB/EFDC DAGH/CBFE EDGB/FCHA :-) The code: const FOLD_TYPE_COL = 'COLUMN'; const FOLD_TYPE_LI = 'LINE'; const FOLD_SIGN_POS = '+'; const FOLD_SIGN_NEG = '-'; //This function clones a multi dimensional array function clone_array(Data) { if (Array.isArray(Data)) { return Data.map((x) => clone_array(x)); } else { //Not an array return it as a value return Data; } } //Init data function init_data() { let data = []; for (let col = 0; col 0) { return solution; } } } //Get recursively all possible combinations for a puzzle (Array of two dimensions) function get_puzzle_combinations(values_set) { let combinations = []; let size = values_set.length; if (size === 1) { return [values_set]; } values_set.forEach(element => { let values_set_rest = values_set.filter((x) => x !== element); //recursive call if (values_set_rest.length > 0) { let sub_combinations = get_puzzle_combinations(values_set_rest); sub_combinations.forEach(sub_comb => { combinations.push([...[element], ...sub_comb]); }); } }); return combinations; } //Generate all possible puzzles function generate_all_possible_puzzles(values_set) { let puzzles = []; let combinations = get_puzzle_combinations(values_set); combinations.forEach(element => { puzzles.push( [ [ [element[0]], [element[1]] ], [ [element[2]], [element[3]] ], [ [element[4]], [element[5]] ], [ [element[6]], [element[7]] ], [ [], [] ], [ [], [] ], [ [], [] ] ] ); }); return puzzles; } let puzzles = generate_all_possible_puzzles(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']); let nb_resolved_puzzles = 0; let nb_non_resolved_puzzles = 0; puzzles.forEach(puzzle => { let solution = recursive_search_solution(puzzle, []); if (Array.isArray(solution)) { console.log("For puzzle"); console.log(puzzle); console.log("Solution found:"); console.log(solution); nb_resolved_puzzles++; } else{ nb_non_resolved_puzzles++; } }); console.log("Finished"); console.log("Nb of generated puzzles = ", puzzles.length); console.log("Number of resolved puzzles = " , nb_resolved_puzzles); console.log("No solutions for puzzles = " , nb_non_resolved_puzzles);
Nice work! Looks like your code checks for all possible permutations, not just those with the first section being A. I changed my code to do this and it looks like we have the same number of puzzles, but mine gives 320 possible solutions instead of 168. Not sure why we are getting different results, but I'll let you know if I work it out!
Ah, I see what the difference is now! Your code generates solutions based off the order the folds are made. It misses those that cant be made with simple folds. This almost got me at first until I tried the puzzles in Matt Parker's original video and realised that they aren't possible just by folding the sheet in a certain order, and they require more complicated folds that are hard to simulate.
@@JamesExplains Hi James and thank you for your feedback. Right I do not take into account only folds producing "A" visible (will do it as next step) I maybe missed something but i thought i did take into account all physically possible folds. But one thing i do is to ignore the "duplicates", i mean i do not count twice same folds giving exactly the same result (ex. folding right to the left from the top and folding left to right from the top) if i do so i would have 336 solutions. That's why i take into account in my program only folding left to right and top to bottom. What are exactly the folds that are hard to simulate and that are not decomposable into simple folds ? (my english is very bad, so that's maybe i did not understand it)
Its hard to explain what a non-simple fold is, but if you get a piece of paper and fold it into 2x3 and label it AFB/DEC, that will give you and idea of what the fold would look like. If you fold the bottom half up behind the top half, then fold from the right, around the back, into the left. However the complicated bit is how the paper nests. The right end section (B,C) has to tuck inside the left end (A,D). Not too hard to do in real life, but not something that can be simulated by a folding order. I only realised this concern when I tried to solve the puzzles from Matt Parker's individual video and realised it can't be generate by just doing the folds in a certain order.
Good job :)
I'm very interested to see what will happen of you release the requirements or make the grid bigger.
Working on the video right now!
Really nice explanation
At 4:53 it seems that your graphic is incorrect, the bottom right G should've been an E. Other than that small detail, great video.
You're right! Must have copied it down wrong when making the graphic
How did you think of the solution though?
which solution in particular?
@@JamesExplains the whole problem actually 😅
I mean how you approached the problem
Well I was trying to work out how to write a program to find all possible solutions, and was just going to check all permutations of the stack order against whatever criteria made a solution valid. Then it occurred to me that the folds joining different sections couldn't overlap, so I tried to find a way that could help. Then when visualising how the folds worked I noticed they would always be on a constant side, so groups of folds could be checked against each other to find the solution.
As for the code to write it, I cycles through all permutations of the stack with the sections in an array, and for each permutation check each pair of a fold against each other pair on the same side to make sure they are both higher, both lower, or nested within the other pair... iterate through all that and reject any that fail and I was left with just the valid solutions.
I'm thinking of doing another video on how this generalises to other sizes of sheets.
@@JamesExplains woow thanks for the reply
At 06:43 your substitution rule giving letters for numbers is not correct.
After having found a feasible stacking order of the paper segments 0 - 7 without any crossing of the folds on either side you do not replace 0 by A, 1 by B and so on.
Instead you have to walk through the sequence of paper segments from left to right (which is physically from top to bottom of the stack) and placing the letters A - H in that order on the paper segment indicated by the actual digit representing this segment.
Interestingly your letter combinations presented at 06:47 - 07:33 are all correct. However the stack segment orders represented by digits at 06:40 are not all correct.
The top left stacking order 01237654 is correct and represents ABCDHGFE as shown.
But the second stacking order 01275436 is not a valid solution. After correct digit-by-letter replacement this gives ABCGFEHD which cannot be done.
Another example is the first (yellow) puzzle AHGDBCFE which was used at 04:44 - 05:58 and has a stacking order of 04537621. This stacking order is not included at 06:40 and the letter combination AHGDBCFE has been replaced from 07631254 which stands for AEFDHGCB and again is not a valid stacking order.
Damn, you're right! My main focus was on trying to get the algorithm to work out the number of possible permutations, so converting to letters was more of an after thought for the video. I think I'm going do a short follow-up video on this same concept with other sized sheets, so I'll correct this in that video if I get around to making it!
Good, but a solution that provides a method to fold the paper would be even better.
I know, and I've been trying to think of how to do that, but having seen the solutions to the 2 puzzles in the Stand-up Maths video, I don't think there's any way to describe the fold method for all cases mathematically. Some of the folds are really strange
@@JamesExplains I've come very close to logically describing it. I was using a 3d array. Before making a given fold, it can check how many places one side of it can go to the other side, whether it be on the top, the bottom, or inside / in between itself (origami thing). It can see if it's possible by checking if the connections between the panels will cause any intersections.
That means it must also iterate between all the things that can fold, which can either be one bend or multiple bends if the neighboring connections allow it (which means the first of Matt's puzzles where the (SPOILER) inside of it actually folds would be checked as well)
(And it should also contains a method to see if two given panels are connected and on which side)
Matt's second puzzle is where I halted.....
Hi, i wrote a program in javascript to solve all possibles puzzles of this problem and this is the results i get:
Number of generated puzzles = 40320
Number of resolved puzzles (having a solution) = 168 (0,416% of total puzzles)
Number of puzzles with no solution = 40152 (99,583 of total puzzles)
Some examples of puzzles having a solution:
HGAB/EFDC
DAGH/CBFE
EDGB/FCHA
:-)
The code:
const FOLD_TYPE_COL = 'COLUMN';
const FOLD_TYPE_LI = 'LINE';
const FOLD_SIGN_POS = '+';
const FOLD_SIGN_NEG = '-';
//This function clones a multi dimensional array
function clone_array(Data) {
if (Array.isArray(Data)) {
return Data.map((x) => clone_array(x));
}
else { //Not an array return it as a value
return Data;
}
}
//Init data
function init_data() {
let data = [];
for (let col = 0; col 0) {
return solution;
}
}
}
//Get recursively all possible combinations for a puzzle (Array of two dimensions)
function get_puzzle_combinations(values_set) {
let combinations = [];
let size = values_set.length;
if (size === 1) {
return [values_set];
}
values_set.forEach(element => {
let values_set_rest = values_set.filter((x) => x !== element);
//recursive call
if (values_set_rest.length > 0) {
let sub_combinations = get_puzzle_combinations(values_set_rest);
sub_combinations.forEach(sub_comb => {
combinations.push([...[element], ...sub_comb]);
});
}
});
return combinations;
}
//Generate all possible puzzles
function generate_all_possible_puzzles(values_set) {
let puzzles = [];
let combinations = get_puzzle_combinations(values_set);
combinations.forEach(element => {
puzzles.push(
[
[ [element[0]], [element[1]] ],
[ [element[2]], [element[3]] ],
[ [element[4]], [element[5]] ],
[ [element[6]], [element[7]] ],
[ [], [] ],
[ [], [] ],
[ [], [] ]
]
);
});
return puzzles;
}
let puzzles = generate_all_possible_puzzles(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']);
let nb_resolved_puzzles = 0;
let nb_non_resolved_puzzles = 0;
puzzles.forEach(puzzle => {
let solution = recursive_search_solution(puzzle, []);
if (Array.isArray(solution)) {
console.log("For puzzle");
console.log(puzzle);
console.log("Solution found:");
console.log(solution);
nb_resolved_puzzles++;
}
else{
nb_non_resolved_puzzles++;
}
});
console.log("Finished");
console.log("Nb of generated puzzles = ", puzzles.length);
console.log("Number of resolved puzzles = " , nb_resolved_puzzles);
console.log("No solutions for puzzles = " , nb_non_resolved_puzzles);
Nice work! Looks like your code checks for all possible permutations, not just those with the first section being A. I changed my code to do this and it looks like we have the same number of puzzles, but mine gives 320 possible solutions instead of 168.
Not sure why we are getting different results, but I'll let you know if I work it out!
Ah, I see what the difference is now! Your code generates solutions based off the order the folds are made. It misses those that cant be made with simple folds. This almost got me at first until I tried the puzzles in Matt Parker's original video and realised that they aren't possible just by folding the sheet in a certain order, and they require more complicated folds that are hard to simulate.
@@JamesExplains Hi James and thank you for your feedback. Right I do not take into account only folds producing "A" visible (will do it as next step)
I maybe missed something but i thought i did take into account all physically possible folds. But one thing i do is to ignore the "duplicates", i mean i do not count twice same folds giving exactly the same result (ex. folding right to the left from the top and folding left to right from the top) if i do so i would have 336 solutions. That's why i take into account in my program only folding left to right and top to bottom. What are exactly the folds that are hard to simulate and that are not decomposable into simple folds
? (my english is very bad, so that's maybe i did not understand it)
Its hard to explain what a non-simple fold is, but if you get a piece of paper and fold it into 2x3 and label it AFB/DEC, that will give you and idea of what the fold would look like. If you fold the bottom half up behind the top half, then fold from the right, around the back, into the left. However the complicated bit is how the paper nests. The right end section (B,C) has to tuck inside the left end (A,D). Not too hard to do in real life, but not something that can be simulated by a folding order. I only realised this concern when I tried to solve the puzzles from Matt Parker's individual video and realised it can't be generate by just doing the folds in a certain order.