Project-Euler-025

Problem

The Fibonacci sequence is defined by the recurrence relation:

$$
Fn = F{n-1} + F_{n-2} \text{ where } F_1 = 1 \text{ and } F_2 = 1
$$

Hence the first 12 terms will be:

$$
\begin{split}
F_1 &= 1 \
F_2 &= 1 \
F_3 &= 2 \
F_4 &= 3 \
F_5 &= 5 \
F_6 &= 8 \
F_7 &= 13 \
F_8 &= 21 \
F9 &= 34 \
F
{10} &= 55 \
F{11} &= 89 \
F
{12} &= 144
\end{split}
$$

The 12th term, $F_{12}$, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

阅读更多
Perceptron with Margin

It is a simple simulation of Perceptron Algorithm using p5.js.

You can insert the data-points belonging to two classes as well as change the Learning Rate and Threshold(or Margin) on canvas at runtime using Sliders and simulate how the Linear Seperater converges to classify the given data.

You can interact on web browsers by simply click the index.html file on your browser.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<!DOCTYPE html>
<html>
<head>
<meta name="viewport" width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0>
<style> body {padding: 0; margin: 0;} </style>
<script src="../p5.min.js"></script>
<script src="../addons/p5.dom.min.js"></script>
<script src="../addons/p5.sound.min.js"></script>
<script src="sketch.js"></script>
<style>
body {
padding: 0;
margin: 0;
}
canvas {
vertical-align: top;
}
html {
font-family: monospace;
color: #333;
font-size: 20px;
}
</style>
</head>
<body>
</body>
</html>

User can insert the data-points belonging to two classes as well as change the Learning Rate and Threshold or Margin on canvas at runtime using Sliders and simulate how the Linear Separater converges to classify the given data. sketch.js contains the core logic for the simulation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
instruction = "Tap on the Screen to Insert Data Points...";

var epsilonSlider, epsilonSpan;
var minPointsSlider;
var changeColor;

// Data
X1 = [];
X2 = [];
Y = [];

// Hyperparameters
b = 0.0;
w1 = 0.0;
w2 = 0.0;

var threshold = 100.0;
var learning_rate = 0.1;

// Parameters
var x1, x2;
var y1, y2;
var m, b;
var type = 1;

var flag = false;

function setup() {
createCanvas(windowWidth, windowHeight - 25);

createSpan("Learning Rate: ");
epsilonSlider = createSlider(0, 100, 10);
epsilonSpan = createSpan(epsilonSlider.value());
createSpan(" | ");
createSpan("Threshold: ");
minPointsSlider = createSlider(0, 300, 100);
minPointsSpan = createSpan(epsilonSlider.value());
createSpan(" | ");
changeColor = createButton("Change Color");
changeColor.mousePressed(swap);
createSpan(" | ");
train = createButton("Start Training");
train.mousePressed(function () {
flag = true;
});
}

function draw() {
background(51);

learning_rate = epsilonSlider.value() / 1000;
epsilonSpan.html(learning_rate.toString());
threshold = minPointsSlider.value();
minPointsSpan.html(threshold.toString());

fill(250);
noStroke();
textFont('monospace');
textSize(25);
text("Perceptron with Margin", 15, 40);
textSize(20);
text(instruction, 15, windowHeight - 60);

noStroke();
for (var i = 0; i < X1.length; i++) {
Y[i] == 1 ? fill(255, 0, 0) : fill(0, 0, 255);
ellipse(X1[i], X2[i], 8, 8);
}

if (flag) {
fit();
}

drawLine();
stroke(255, 0, 255);
line(x1, y1+threshold, x2, y2+threshold);
line(x1, y1-threshold, x2, y2-threshold);

stroke(255, 255, 0);
line(x1, y1, x2, y2);
}

function mouseClicked() {
X1.push(mouseX);
X2.push(mouseY);
Y.push(type);
}

function swap() {
type = -type;
}

function activate(y, threshold) {
if (y > threshold) {
return 1;
} else if (y <= -threshold) {
return -1;
}
return 0;
}

function fit() {
for (var i = 0; i < X1.length; i++) {
y = w1 * X1[i] + w2 * X2[i] + b;
y = activate(y, threshold);

console.log(" " + y + " " + Y[i]);

if (y != Y[i]) {
console.log("Here");

var x1 = map(X1[i], 0, width, 0, 1);
var x2 = map(X2[i], 0, height, 0, 1);

w1 += learning_rate * Y[i] * x1;
w2 += learning_rate * Y[i] * x2;
b += learning_rate * Y[i];
}
}
}

function keyPressed() {
if (keyCode == ENTER) {
swap();
} else if (keyCode == ESCAPE) {
flag = true;
}
}

function drawLine() {
x1 = 0;
x2 = width;

m = -(w1 / w2);
c = -(b / w2);

y1 = m * x1 + c;
y2 = m * x2 + c;
}



LeetCode Notes 025

Find All Numbers Disappeared in an Array

Given an array of integers where $1 ≤ a[i] ≤ n$ (n = size of array), some elements appear twice and others appear once.

Find all the elements of $[1, n]$ inclusive that do not appear in this array.

Could you do it without extra space and in $O(n)$ runtime? You may assume the returned list does not count as extra space.

阅读更多
Project-Euler-024

Problem

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

$$012, 021, 102, 120, 201, 210$$

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

阅读更多
LeetCode Notes 024

Excel Sheet Column Number

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

1
2
3
4
5
6
7
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28

阅读更多
LeetCode Notes 023

Diagonal Traverse

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:

1
2
3
4
5
6
7
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,4,7,5,3,6,8,9]

Explanation:



Note:

  1. The total number of elements of the given matrix will not exceed 10,000.
阅读更多