txia > Assembly of Trivial Thoughts

Mapping Qing Relay Stations

Wednesday, May 20th, 2020

The beta stage site is here.

The Motivation

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 Development, History | Tagged GeoJSON, Historical Geography, History, Qing | Permalink | Comments (0)

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 Development, History | Tagged Data Science, 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 算法笔记 | 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 题解 | Permalink | Comments (0)

txia

Mapping Qing Relay Stations

The Motivation

Data Aggregation

World War II Visualization

Land Warfare

RMQ-ST

[BZOJ1003] 物流运输

Search

Categories

Recent Posts

Archives

Tags

Friend Links

Subscribe to Blog via Email