txia > Assembly of Trivial Thoughts

Flutter + Firebase 开发流水账

Sunday, January 31st, 2021

上个学期的时候，因为疫情的缘故，我所在的学校为了控制食堂的人流量，引入了一款预约饭点的第三方移动应用。简单地说，这款应用的功能就是在完成身份验证后，让用户选取取餐的地点和时间，软件在点单完成后发送确认邮件，然后用户凭确认邮件去食堂取餐。可以说，业务并不复杂，实现得好应该也不难，但是不知为何这个APP设计得就很烂，用户体验特别差，预约步骤特别麻烦，每次需要：

指纹解锁APP -> 等待APP跳转到下一个界面 -> 点击“Start an order” -> 等待APP跳转到下一个界面 -> 选择预约地点 -> 等待APP加载数据 -> 选择日期时间 -> 等待APP加载数据 -> 将早饭/中饭/晚饭加入购物车 -> 等待APP跳转到下一个界面 -> 结算购物车 -> 等待确认邮件

整个流程下来如果运气好那么要30-45秒，如果运气不好，刚好处在点餐高峰期，应用后端便会不堪重负，前端数据永远加载不出来，然后应用直接崩溃挂掉。这款应用还会经常莫名其妙地闪退，或者出现整个界面失去响应，导致用户只能强制关闭。而且到了食堂要掏出手机，翻出那封可能早已经被其他邮件所淹没的确认邮件，给食堂门口那几位生无可恋的工作人员肉眼检票。刚开始大家还比较遵守规矩，会按照下单的时间和地点去食堂取饭，但到了学期中大家都被搞疲了，于是出现了五花八门各式蒙混工作人员的手段，有修图改确认邮件时间的，也有使用过期的邮件截图欺负食堂大妈眼神不好的，更有直接闯卡的。总而言之，这款应用不光使用体验巨差，也根本达不到原来控制人流量的设计目标。

寒假的时候闲来无事，就和另外两位CS系的同学，用Flutter和Firebase替学校的Dining Service开发了一款更加简单易用的预约软件，准备在春天投放使用，改善一下大家的预约订餐体验。比起原有的APP，新开发的APP主要有以下一些方面的改进：

改用Google Account一次验证登录用户，省去了每次解锁APP的流程
日期、地点和时间选择全部放在同一界面上，前端数据实时刷新，方便用户一键预约
在就餐地点部署PROX读卡设备，用户点单后可以直接刷卡进入
新增历史订单查看和取消功能

这个项目前前后后，断断续续大概折腾了一个月，最近总算是弄完了。这几天刚好有空，就胡乱写点东西记录记录开发过程，假装一下博客还在更新。

Continued reading >

Filed in Development | Tagged Dart, Firebase, Flutter, 移动开发 | Permalink | Comments (0)

Mapping Qing Relay Stations

Wednesday, May 20th, 2020

The beta stage site is here.

During the Qing dynasty, the large network of postal and military stations, connecting the ruling kernel with China proper, Manchuria, Mongolia, Sinkiang, and Tibet, were venues of information and military logistics for monitoring the empire, and also routes which officials, scholars, merchants traveled. I felt that if I could transform the system into a GIS database, it would be an invaluable research foundation on which future investigations into Qing commercial or cultural history could be built. My project since then has been one of retracing these routes. I will give a very brief technical overview of the backstage process here, and more blogs concerning specific routes will be posted in the coming months(most likely in Chinese).

Data Aggregation

The main primary source that I used was The Jiaqing Administrative Code of the Qing Dynasty (Jiaqing Huidian 嘉慶會典). My initial plan was to extract the information using OCR and then geocoding the raw data with a Google API. However, most of the OCR software that I tried was quite abysmal at discerning Chinese characters that were oriented vertically. I tinkered around a lot with various software parameters and have even thought of writing my own OCR specialized for this purpose but to no avail. In the end, I decided that for my data size, it was faster to have a flawed OCRed result and then eyeball the data for corrections. Geocoding was also pretty challenging: the Google API could only identify place names that had not changed since the Qing period and I had to do a lot of textual research in travel logs and gazettes to uncover the present-day location. For anyone interested, Xiao fang hu zhai yu di cong chao (小方壺齋輿地叢鈔) is a good source to look into.

Continued reading >

Filed in History | Tagged Digital Humanities, GeoJSON, Historical Geography, Qing | Permalink | Comments (1)

World War II Visualization

Thursday, December 26th, 2019

I have always been interested in how history can talk to the quantitative…so as part of a small data science project I thought it was a good idea to put together a visualization of World War II using R. After some searching, I found several interesting data sources:

Wikipedia: Most of the WWII battles in Wikipedia have a conflict infobox with the date the coordinates of the battle. Naval loss tables can also be scraped from various pages. It would be rather nice to visualize them in time and space using Leaflet
Wikidata & DBpedia: These two databases have structured data that saves us from scraping and cleaning raw data from HTML Wikipedia pages.
Naval History and Heritage Command: Almost all of the losses of the Imperial Japanese Navy during World War II can be found here, including
Data.World: Data of all the bombs dropped by the Allies since WWI.

We can put then together four main datasets from these sources 1. land warfare with the date and location 2. naval loss data 3. aerial bombing data 4. command network data

Land Warfare

Fortunately, there is a list that links us to most of the WWII battles on Wikipedia (saves us from crawling). We scrap, clean and put the links into a data frame:

library(mdsr)
library(rvest)
links <- "https://en.wikipedia.org/wiki/List_of_World_War_II_battles" %>%
  read_html() %>%
  html_nodes("a") %>%
  html_attr("href")%>%
  as.data.frame()

start <- grep('/wiki/African_Theatres_of_World_War_II', links$.) %>%
  as.numeric()
end <- grep('/wiki/Operation_Tiderace', links$.)[1] %>%
  as.numeric()

links <- links %>%
  slice(start:end) %>%
  filter(grepl("(Theatre|index|File|cite)", .) == FALSE) %>%
  mutate(temp = "https://en.wikipedia.org") %>%
  unite(url, temp, ".", sep = "")

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

library(mdsr)

library(rvest)

links <- "https://en.wikipedia.org/wiki/List_of_World_War_II_battles" %>%

read_html() %>%

html_nodes("a") %>%

html_attr("href")%>%

as.data.frame()

start <- grep('/wiki/African_Theatres_of_World_War_II', links$.) %>%

as.numeric()

end <- grep('/wiki/Operation_Tiderace', links$.)[1] %>%

as.numeric()

links <- links %>%

slice(start:end) %>%

filter(grepl("(Theatre|index|File|cite)", .) == FALSE) %>%

mutate(temp = "https://en.wikipedia.org") %>%

unite(url, temp, ".", sep = "")

We can now follow the link to each battle and scrap the data from military infoboxes on the right-hand side of each page. An Xpath locator is particularly handy here to extract particular elements. We can write a function that does all the work for us. Some of the pages do not have any data and will crash the function. To make it work, a try() function can be used to skip the faulty pages and move on to the next:

Continued reading >

Filed in History | Tagged Data Science, Digital Humanities, R, WWII | Permalink | Comments (0)

RMQ-ST

Sunday, May 28th, 2017

无趣的RMQ-ST 模板。

const int maxn=50001;
int n, q, x, y;
int a[maxn], max_r[maxn][16], min_r[maxn][16];

void pre()
{
    for(int i=1; i<=n; i++)
        min_r[i][0]=max_r[i][0];
    int t=log(n)/log(2);

    for(int j=1; j<=t; j++)
        for(int i=1; i+(1 << (j-1))-1<=n; i++)
        {
            max_r[i][j]=max(max_r[i][j-1], max_r[i+(1 << (j-1))][j-1]);
            min_r[i][j]=min(min_r[i][j-1], min_r[i+(1 << (j-1))][j-1]);
        }
}

int rmq(int l, int r)
{
    int k=int(log((double)(r-l+1))/log(2.0));
    int a1=max(max_r[l][k], max_r[r-(1 << k)+1][k]);
    int a2=min(min_r[l][k], min_r[r-(1 << k)+1][k]);
    printf("%d%d\n", a1, a2);
}

int main()
{
    scanf("%d%d", &n, &q);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    pre();
    while(q--)
    {
        scanf("%d%d", &x, &y);
        rmq(x, y);
    }
    return 0;
}

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

const int maxn=50001;

int n, q, x, y;

int a[maxn], max_r[maxn][16], min_r[maxn][16];

void pre()

{

for(int i=1; i<=n; i++)

min_r[i][0]=max_r[i][0];

int t=log(n)/log(2);

for(int j=1; j<=t; j++)

for(int i=1; i+(1 << (j-1))-1<=n; i++)

{

max_r[i][j]=max(max_r[i][j-1], max_r[i+(1 << (j-1))][j-1]);

min_r[i][j]=min(min_r[i][j-1], min_r[i+(1 << (j-1))][j-1]);

}

int rmq(int l, int r)

{

int k=int(log((double)(r-l+1))/log(2.0));

int a1=max(max_r[l][k], max_r[r-(1 << k)+1][k]);

int a2=min(min_r[l][k], min_r[r-(1 << k)+1][k]);

printf("%d%d\n", a1, a2);

}

int main()

{

scanf("%d%d", &n, &q);

for(int i=1; i<=n; i++) scanf("%d", &a[i]);

pre();

while(q--)

{

scanf("%d%d", &x, &y);

rmq(x, y);

}

return 0;

}

Filed in Algorithms | Tagged RMQ | Permalink | Comments (0)

[BZOJ1003] 物流运输

Tuesday, May 16th, 2017

水一发dp+spfa

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cfloat>
#include<cctype>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;

const int maxn=1001, maxm=101, INF=1<<29;
int n, m, k, e; //n:days, m:nodes, k:fee, e:number of edges;
int p, a, b;//p:point, a:start, b:end;

int dp[maxn], cost[maxn][maxn];
int vis[maxn], ban[maxn][maxn], mark[maxn], dis[maxn];
int head[maxn], cnt;

struct node{
  int to, next, w;
}edge[maxm];

void AddEdge(int u, int v, int w)
{
  edge[cnt].to=v;
  edge[cnt].w=w;
  edge[cnt].next=head[u];
  head[u]=cnt++;
}

int spfa(int start, int end)
{
  for(int i=0; i<=m; i++)
  {
    dis[i]=INF;
    vis[i]=0;
    mark[i]=0;
  }
  
  queue<int> Q;
  Q.push(1);
  dis[1]=0;
  
  for(int i=start; i<=end; i++)
    for(int u=1; u<=m; u++)
      if(ban[u][i]) mark[u]=1;
  
  while(!Q.empty())
  {
    int u=Q.front(); vis[u]=false; Q.pop();
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
      int v=edge[i].to;
      int w=edge[i].w;
      if(!mark[v] && dis[v]>dis[u]+w)
      {
        dis[v]=dis[u]+w;
        if(!vis[v])
        {
          vis[v]=true;
          Q.push(v);
        }
      }
    }
  }
  return dis[m]*(dis[m]>=INF?1:end-start+1);
}

int solve()
{
  for(int i=1; i<=n; i++)
    for(int j=i; j<=n; j++)
      cost[i][j]=spfa(i, j);
  
  for(int i=0; i<=n; i++) dp[i]=INF;
  dp[0]=-k;
  for(int i=1; i<=n; i++)
    for(int j=0; j<i; j++)
      dp[i]=min(dp[i], dp[j]+cost[j+1][i]+k);
      
  printf("%d", dp[n]);
}

int init()
{
  memset(head, -1, sizeof(head));
  scanf("%d%d%d%d", &n, &m, &k, &e);
  int u, v, w;
  for(int i=1; i<=e; i++)
  {
    scanf("%d%d%d", &u, &v, &w);
    AddEdge(u, v, w);
    AddEdge(v, u, w);
  }
  scanf("%d", &e);
  for(int i=1; i<=e; i++)
  {
    scanf("%d%d%d", &p, &a, &b);
    for(int i=a; i<=b; i++) ban[p][i]=1;
  }
}

int main()
{
  init();
  solve();
  return 0;
}

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

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cfloat>

#include<cctype>

#include<cmath>

#include<vector>

#include<queue>

using namespace std;

const int maxn=1001, maxm=101, INF=1<<29;

int n, m, k, e; //n:days, m:nodes, k:fee, e:number of edges;

int p, a, b;//p:point, a:start, b:end;

int dp[maxn], cost[maxn][maxn];

int vis[maxn], ban[maxn][maxn], mark[maxn], dis[maxn];

int head[maxn], cnt;

struct node{

int to, next, w;

}edge[maxm];

void AddEdge(int u, int v, int w)

{

edge[cnt].to=v;

edge[cnt].w=w;

edge[cnt].next=head[u];

head[u]=cnt++;

}

int spfa(int start, int end)

{

for(int i=0; i<=m; i++)

{

dis[i]=INF;

vis[i]=0;

mark[i]=0;

}

queue<int> Q;

Q.push(1);

dis[1]=0;

for(int i=start; i<=end; i++)

for(int u=1; u<=m; u++)

if(ban[u][i]) mark[u]=1;

while(!Q.empty())

{

int u=Q.front(); vis[u]=false; Q.pop();

for(int i=head[u]; i!=-1; i=edge[i].next)

{

int v=edge[i].to;

int w=edge[i].w;

if(!mark[v] && dis[v]>dis[u]+w)

{

dis[v]=dis[u]+w;

if(!vis[v])

{

vis[v]=true;

Q.push(v);

}

return dis[m]*(dis[m]>=INF?1:end-start+1);

}

int solve()

{

for(int i=1; i<=n; i++)

for(int j=i; j<=n; j++)

cost[i][j]=spfa(i, j);

for(int i=0; i<=n; i++) dp[i]=INF;

dp[0]=-k;

for(int i=1; i<=n; i++)

for(int j=0; j<i; j++)

dp[i]=min(dp[i], dp[j]+cost[j+1][i]+k);

printf("%d", dp[n]);

}

int init()

{

memset(head, -1, sizeof(head));

scanf("%d%d%d%d", &n, &m, &k, &e);

int u, v, w;

for(int i=1; i<=e; i++)

{

scanf("%d%d%d", &u, &v, &w);

AddEdge(u, v, w);

AddEdge(v, u, w);

}

scanf("%d", &e);

for(int i=1; i<=e; i++)

{

scanf("%d%d%d", &p, &a, &b);

for(int i=a; i<=b; i++) ban[p][i]=1;

}

int main()

{

init();

solve();

return 0;

}

Filed in Code | Tagged SPFA, 动态规划 | Permalink | Comments (0)

txia

Flutter + Firebase 开发流水账

Mapping Qing Relay Stations

Data Aggregation

World War II Visualization

Land Warfare

RMQ-ST

[BZOJ1003] 物流运输

Search

Categories

Recent Posts

Archives

Tags

Friend Links

Subscribe to Blog via Email