[Answer and Winners] Mathematics × Programming Competition #4 [答案及得...

Mathematics × Programming Competition #4
Announcement of Answer and Winners

For Chinese version please scroll to the bottom. 中文版請見文末。

Question

The following map shows the location of three cities A, B and C. The black lines represent roads. Ken wants to travel from A to C, subject to the following rules:-

In each move, he travels from one junction to another junction via the roads.
Throughout the whole journey, he only moves towards the North or the East, but not any other directions.
He needs to pass through B.

How many ways are there for Ken to complete his journey?

Answer: 8820

We can see that the problem can be split into two parts, which are travelling from A to B, and from B to C. We can calculate the number of possible combinations for these two parts separately, and then multiple them together to give the answer, as they can be considered as independent events. As for calculating the number of possible combinations, we can solve it mathematically or programmatically:-

Mathematical approach

Consider the journey from A to B, which is a 3 × 4 matrix. To travel from A to B, 7 moves are required. Out of these 7 moves, there must be 3 eastward moves and 4 northward moves. Thus the problem can be simplified as having 7 seats labelled from 1 to 7, and we need to pick 3 seats to put the letter 'E' on them. For the rest of the seats, they would be filled with 'N' automatically. Now when we read aloud the letters on the seats from left to right, this would be Ken's journey. Therefore moving from A to B, the number of possible combinations is ₇C₃.

Similarly, the journey from B to C is a 5 × 5 matrix. So the number of possible combinations would be ₁₀C₅.

Finally we have the answer ₇C₃ × ₁₀C₅ = 8820.

Programming approach

We can use recursion to count the number of moves from A to B. Here is a simple way of trying all possible ways of travelling from A to B, and once we arrive at the destination we increase the counter by 1.

JavaScript:

var count = 0;

function countMove(currentX, currentY, destinationX, destinationY){
    if (currentX == destinationX && currentY == destinationY){ // arrived at destination
        count += 1;
    } else if (currentX <= destinationX && currentY <= destinationY){ // not yet arrived at destination
        countMove(currentX + 1, currentY, destinationX, destinationY); // move towards east
        countMove(currentX, currentY + 1, destinationX, destinationY); // move towards north
    }
}
countMove(0,0,3,4);
console.log(count);

Output: 35

Similarly, we can change the line countMove(0,0,3,4) to countMove(0,0,5,5), which gives the output 252. Multiplying 35 and 252, we have 8820.

This is just the most direct way of solving the problem by programming, of course there are many other better ways in doing this. Please take a look at the section Other approaches below to learn more!

If you want to learn JavaScript, visit @adnanrahic 's blog to learn JavaScript!

The JavaScript Journey 1 - Values
The JavaScript Journey 2 - Arithmetic and Operators
The JavaScript Journey #3 - Logical Operators
The JavaScript Journey #4 - Special Values & Precise Comparisons
The JavaScript Journey #5 - Expressions and Statements

Other approaches

Here is a list of attempts by other participants! Feel free to take a look at their methods as well!

@jubi Solving the problem by simple counting: @jubi/kenchung
@tvb Solving by PHP programming: @tvb/mathematics-programming-competition-4-i-ve-try-please-correct
@justyy Advanced programming approach with optimization: @justyy/software-engineer-interview-question-how-many-ways-from-a-to-c-via-b-a-b-c

Winners

Among 25 participants, there are 12 people who got the correct answers. Thank you for your participation!

@rayccy @arkoko @victorier @krischy @pizzachain @jubi @justyy @nationalpark @tensaix2j @firstamendment @apsu @hansenator @misko @nocturnal @doughtaker @jeffreytong @wilkinshui @mrkool @davor27 @tking77798 @daut44 @carobetc @jstoddard @tvb @kelkoo

Prize pool = Prize pool balance carried forward (5.409 SBD) + SBD payout of the the question post (28.443 SBD) = 33.852 SBD

Besides, @steemstem has generously sponsored 7.5 SP, 5 SP and 2.5 SP for the first, second and third prizes!

The winners and prizes are tabulated below:

Winner	Prize	SBD
@rayccy	First prize	33.852 / 8 = 4.231 SBD + 7.5 SP
@arkoko	Second prize	33.852 / 8 = 4.231 SBD + 5 SP
@krischy	Third prize	33.852 / 8 = 4.231 SBD + 2.5 SP
@justyy	Consolation prize	33.852 / 8 = 4.231 SBD
@tensaix2j	Consolation prize	33.852 / 8 = 4.231 SBD
@doughtaker	Consolation prize	33.852 / 8 = 4.231 SBD
@wilkinshui	Consolation prize	33.852 / 8 = 4.231 SBD
@tvb	Consolation prize	33.852 / 8 = 4.231 SBD

Prize carried forward = 0 SBD

Congratulations to the winners!

The steemSTEM project (@steemstem) is a community-supported project aiming to increase the quality and the visibility of STEM (STEM is the acronym for Science, Technology, Engineering and Mathematics) articles on Steemit. Please support steemSTEM by following @steemstem, joining the chat channel and following the curation trail on Streemian! In order to further promote the use of the chat channel, I will stop announcing the time of next competition via a post. Instead I will announce the time in advance in the chat channel!

數學 × 程式編寫比賽 (第四回)
答案及得獎名單公佈

問題

以下地圖顯示了三個城市A，B和C的位置，其中的黑線代表道路。Ken希望從A步行到C，但須遵守以下規則：

他在道路上從一個交叉路口行走到另一個交界處時視為一個行動。
整個旅程中，他只會向北或東方移動。
他需要通過B。

問Ken有多少個不同的方法完成這次旅程？

答案: 8820

不難發現問題可以分為從A到B以及從B到C的兩個部分。我們可以分別計算這兩個部分的可能組合的數目，而由於它們是獨立事件，我們可以將數目相乘得出答案。至於計算可能組合的數目，我們可以用數學或編程方式來解決：

數學方法

從A到B的旅程是一個3×4矩陣，因此需要7次移動。在這7次移動中，必須有3次向東移動和4次向北移動。因此，這個問題可以簡化為有一列編上1至7的座位，我們需要挑3個座位，把「東」寫在座位上，而其餘的座位則自動填上「北」。現在我們只需由左至右讀出座位上的標示，這便是Ken今次的旅程。因此，從A移動到B的方法共有₇C₃種。

同樣地，從B到C的旅程是一個5×5矩陣。因此，完成這次旅程的方法共有₁₀C₅種。

最後我們可得出答案：₇C₃ × ₁₀C₅ = 8820。

編程方法

我們可以使用遞歸方法來計算從A到B的移動次數。以下是一種窮舉方法，一旦我們到達目的地，我們將計數器增加1。

JavaScript:

var count = 0;

function countMove(currentX, currentY, destinationX, destinationY){
    if (currentX == destinationX && currentY == destinationY){ // 抵達目的地
        count += 1;
    } else if (currentX <= destinationX && currentY <= destinationY){ // 尚未抵達目的地
        countMove(currentX + 1, currentY, destinationX, destinationY); // 向東移動
        countMove(currentX, currentY + 1, destinationX, destinationY); // 向北移動
    }
}
countMove(0,0,3,4);
console.log(count);

輸出：35

同樣地，我們可將 countMove(0,0,3,4) 改成 countMove(0,0,5,5)，從而得出252。兩者相乘，可得出8820。

這只是最易明的編程方法，當然還有很多其他更好的方法。請看下面的其他方法了解更多！

如果你想學習JavaScript，不妨參閱 @adnanrahic 的文章！

其他方法

以下是其他參與者的方法，大家不妨看看他們的做法！

@jubi 以數數來簡單地解決問題! @jubi/kenchung
@tvb PHP編程 @tvb/mathematics-programming-competition-4-i-ve-try-please-correct
@justyy 進屆編程及優化 @justyy/software-engineer-interview-question-how-many-ways-from-a-to-c-via-b-a-b-c

得獎者

在25個參加者之中，有12人答對。多謝大家的熱烈參與！

是次獎池 = 上回比賽剩餘獎金 (5.409 SBD) + 比賽題目帖文的SBD收入 (28.443 SBD) = 33.852 SBD

另外，@steemstem慷慨贊助了7.5 SP、5 SP以及2.5 SP予是次比賽的第一、二及三等獎！

下表顯示得獎者及其所得獎金：

得獎者	獎項	SBD
@rayccy	一等獎	33.852 / 8 = 4.231 SBD + 7.5 SP
@arkoko	二等獎	33.852 / 8 = 4.231 SBD + 5 SP
@krischy	三等獎	33.852 / 8 = 4.231 SBD + 2.5 SP
@justyy	安慰獎	33.852 / 8 = 4.231 SBD
@tensaix2j	安慰獎	33.852 / 8 = 4.231 SBD
@doughtaker	安慰獎	33.852 / 8 = 4.231 SBD
@wilkinshui	安慰獎	33.852 / 8 = 4.231 SBD
@tvb	安慰獎	33.852 / 8 = 4.231 SBD

下回比賽獎池現有 = 0 SBD

恭喜所有得獎者！

steemSTEM（@steemstem）是一個由steemit社群支持的項目，旨在宣傳STEM（STEM是科學，技術，工程和數學的首字母縮略詞）。請通過以下方式來支持steemSTEM：追蹤@steemSTEM，加入聊天頻道和加入Streemian！為了進一步推廣聊天頻道的使用，我將不再透過發文來宣布下一場比賽的時間，我會在聊天頻道中提前公佈比賽時間！

[Answer and Winners] Mathematics × Programming Competition #4 [答案及得獎名單] 數學 × 程式編寫比賽 (第四回)

Mathematics × Programming Competition #4Announcement of Answer and Winners