Bruteforce Solution to Mathematics × Programming Competition #5 暴力搜索[問題] 數學 × 程式編寫比賽 (第五回)steemCreated with Sketch.

in cn •  2 years ago  (edited)

@kenchung 第五次比赛 #steemstem, 题目主要是A到P 16个字母填到4X4的格子中,1-16只能各用一次,并且有12个条件。
Quesiton: https://steemit.com/contest/@kenchung/question-mathematics-programming-competition-5

Solution:
16 integers, but the total combination is huge i.e. 16! (A has 16 possibilities, B has 15 possibilities and so on).

如果不算条件限制,一共有16!种方案,比如第一格可以填1-16,第二格可以有15种可能,第三格14种 以此类推....

The good thing is that we have a few of restrictions such as A can only be 2, 4, 6 or 8 and etc. Therefore, we can loop just few variables and base on pre-known conditions to get the values of others.

还好有些条件限制,我们可以穷举未知变量,然后通过已知的条件来推算出其它的变量。

The following JS code is ugly, which implements the bruteforce search, however it works.. Let me think of better ways to write it and I'd share with you in a few days time.

下面的JS代码比较丑,我并不是很喜欢,但它却可以很有效的算出这些值,让我这几天想想怎么把它变好看。


//4,6,13,15,10,16,9,7,12,2,8,5,3,14,1,11

for (var a = 2; a <= 8; a += 2) {
    var l = 9 - a;
    var g = 13 - a;
    var k = 12 - a;
    if (k == a) {
        continue;
    }
    if ((k != 2) && (k != 4) && (k != 6) && (k != 8)) {
        continue;
    }       
    var b = 14 - k;
    if ((b == a) || (b == k)) {
        continue;
    }
    if ((b != 2) && (b != 4) && (b != 6) && (b != 8)) {
        continue;
    }
    var o = 9 - k;
    var m = 9 - b;
    for (var j = 2; j <= 8; j += 2) {
        if ((j != a) && (j != b) && (j != k)) {
            // c, d, e, f, h, i, n, p
            // c + p = 24
            // d + e = 25
            // |e - n| = 4
            // e + f = 26
            // c + i = 25
            console.log('a = ' + a);
            console.log('b = ' + b);
            console.log('g = ' + g);
            console.log('k = ' + k);
            console.log('o = ' + o);
            console.log('m = ' + m);
            console.log('j = ' + j);
            console.log('l = ' + l);
            for (var c = 1; c <= 16; c ++) {
                if ((c != a) && (c != b) && (c != g) && (c != k) && (c != o) && (c != m) && (c != j) && (c != l)) {
                    var p = 24 - c;
                    if (c == p) continue;
                    if ((p < 1) || (p > 16)) continue;
                    var i = 25 - c;
                    if ((i < 1) || (i > 16)) continue;
                    for (d = 1; d <= 16; d ++) {
                        if ((d != c) && (d != a) && (d != b) && (d != g) && (d != k) && (d != o) && (d != m) && (d != j) && (d != l)) {
                            var e = 25 - d;
                            if ((e < 1) || (e > 16)) continue;
                            var f = 26 - e;
                            if ((f < 1) || (f > 16)) continue;
                            n = e + 4;
                            if ((n < 1) || (n > 16)) continue;
                            if (
                                    (i == n) || 
                                    (n == f) || 
                                    (i == d) || 
                                    (p == k) || 
                                    (n == k) || 
                                    (n == b) || 
                                    (e == f) || 
                                    (p == e) || 
                                    (i == f) || 
                                    (p == f) || 
                                    (p == n) || 
                                    (p == g) || 
                                    (c == f)
                            ) {
                                continue;   
                            } 
                            console.log("p = " + p);
                            console.log("i = " + i);                            
                            console.log("n = " + n);
                            console.log("e = " + e);
                            console.log("f = " + f);
                            console.log("c = " + c);
                            console.log("d = " + d);
                        }
                    }
                }
            }
        }
    }
}

This outputs:

a = 4
b = 6
g = 9
k = 8
o = 1
m = 3
j = 2
l = 5
p = 11
i = 12
n = 14
e = 10
f = 16
c = 13
d = 15
[Finished in 0.7s]

Wait, the h is not printed (in the 12 pre-known relations, h is not specified)... but you know what to do. ;)

h 值没有被打出来,因为这是唯一一个没有给定限制条件的变量,不过你应该知道怎么做了。

Originally published at https://steemit.com Thank you for reading my post, feel free to Follow, Upvote, Reply, ReSteem (repost) @justyy which motivates me to create more quality posts.

原文首发于 https://Steemit.com 首发。感谢阅读,如有可能,欢迎Follow, Upvote, Reply, ReSteem (repost) @justyy 激励我创作更多更好的内容。

// Later, it will be reposted to my blogs: justyy.com, helloacm.com and codingforspeed.com 稍后同步到我的中文博客和英文计算机博客

近期热贴

Recent Popular Posts


Tags: #cn #cn-programming #programming #steemstem

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!
Sort Order:  

Did you write this code?

yes, i know this is ugly, but i do that to win the contest.

I like math, interesting quiz :) idk but I'm not good at programming so I decided to look if I can get here system to solve it with gauss method :D well I just passed, programming is better anyway for finding solution and checking all 16! Possibilities

我纯推的 花了点时间。哈哈

NB,菊大哥推理功力很强。

这个用编程的话觉得是非常暴力的循环,我还是喜欢你的方法。

话说 @justyy 管你叫菊大哥,昨天在网上看了一篇文章,好像是桔皮的52个作用,我觉得以后管你叫桔皮,也不错哈哈哈

我也是用javascript寫的,不過是用recursion,程式是短一些但要寫出來的時間也不短,你這方法可能寫的時候還快一點呢

嗯,我也是为了赶紧写出来,所以这代码很丑。

这个我直接放弃了,我觉得太暴力了

Nice!
Do you know Prolog? I solved this problem using it. The idea is the same as you did. Only all the loops to try new values for each variable are automatically handled by the Prolog engine 😼
You can see my solution here:
https://steemit.com/contest/@armandocat/mathematics-programming-competition-5-prolog-solution

  ·  2 years ago Reveal Comment