Metro line planning based on Node.js — reference breadth-first search algorithm

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Reference algorithm link

Code tools

VSCode

The source code

Subway line information, executed only once, stored in substrain.txt

Const subMessage = {'1 ': 'Guangzhou East Railway Station @3 North Extension = Sports Center = Tiyu West Road @3 @3 North Extension = Yangji @5 = Dongshankou @6 = Martyrs' Cemetery = Nongzhuosuo = Park Front @2 = West Gate = Chenjiaci = Changshou Road = Huangsha @6 = Fangcun = Huatiwan = Pothole = Xilang @ Guangfo ', '2 ': 'guangzhou south station @ 7 = = rock @ 7 will jiang nanpu multitude of = = = = east xiao nan = = jiangtai road south state chang gang @ = = Jiang Naxi = 8, 2 palace hiazhu square @ # 6 = park before @ # 1 = = = memorial hall, yuexiu park, guangzhou railway station @ 5 = = = = white clouds fly park park in ternary baiyun cultural square = Xiao Gang = jiangxia = = golden harvest as huang gang @ # 3 north Delay period ', '3' : 'the tianhe bus @ 6 top = = = = middle five mountain hills, ling bridge = 1 sports road west @ @ # 3 north extension period of = = guangzhou pearl river new town @ 5 tower @ APM @ 8 = DaTang = = guest village drain kau = mansion kau = stone = han creek long lung = = panyu city bridge square', 'no. 3 north extension period of' : 'Airport South = Renhe = Longgui = Jiahe Wanggang @ # 2 = Baiyun Avenue North = Yongtai = Tonghe = Jingxi Nanfang Hospital = Meihuayuan = Yantang @ # 6 = Guangzhou East Railway Station @ # 1 = Linhe West @APM= Tiyu West Road @ # 1 @ # 3 ', '4 ': 'huangcun = car vicious = vicious south @ = 5 maxell @ around 8 north = = = officer state university university made = = new stone acer = south of the city waterfront huangge motor city of = = = low swell = tung chung huangge = = jinzhou Manila door', '5' : 'beijiao port = = temple tail @ 6 zhongshan eight = = west village west field = guangzhou railway station @ # 2 little north gold = = = @ # 6 = = zoo zhuang Yang basket @ # 1 = wuyang estate = zhujiang new town @ 3 = hunting DE = = = member pool village village family rhyme road = car vicious @ south east nursery = = 4 sanxi = fish bead = big sand = ShaDong = wen chong', '6' : 'invertors peak arrival bei river sand of = = = = horizontal sand sand jotham tail @ # 5 = best fang = sand @ # 1 = = a-de way culture park = hiazhu square @ # 2 = = = mass of a big square Beijing road east east lake = pass @ = 1 zhuang @ 5 = Huang Huagang = = = balance frame shahe top yan tong @ # 3 north long delay period of bus terminal @ # 3 = = tianhe Ban = longdong = = botanical garden kembat long = Gao Tang stone Huangpi = Jinfeng = Siem Gang = Suyuan = Luogang = Xiangxue ', 'No. 7 ': 'Guangzhou South Railway Station @2 = Shibi @2 = Xecun = Zhongcun = Hanxi Chimelong @3 = Nancun Wanbo = Yuangang = Banqiao = South of university City ', '8' : 'maxell @ around 4 = pazhou = = = red post grinding disc sand Newport @ # 3 = = guest village lujiang = = cuhk hiu kong @ # 2 = = chang hills, Po road garden phoenix saemaul undong = = = sand and the west cultural park @ # 6 = = = waring temple Chen clan academy @ # 1 = = = west village bridge @ 5 lantern temple = with DE = shangbu = julong = so dragon pond = small flat = ishii = = kau pavilion Heart ', '9', 'fly eling = huadu auto city = guangzhou north station @ 8 = = = = flower square huaguo mountain park huacheng road ma on shan park = clear then LianTang Village = = white eel pond = increase @ # 3', 'the guangfo' : 'new east lotus lanshi = = = dongping = century chief strange way = = = temple, tongji road = PuJun JiHua garden north road = the Ann = keijo = south guangxi road = = = financial thousand lamp lake high-tech zone Lei hills, stream of = = chrysanthemum tree = west lang @ = hedong = sand boil = 1 sand garden @ = 8 YanGang = = = stony brook south state drain kau', 'APM' : 'and west @ # 3 north Lin delay period of south = = sports center day henan = = = = children center huangpu avenue huacheng avenue theatre = = tower in guangzhou sea heart sand @ # 3', '13' : 'fish bead @ = 5 yu fung wai @ 7 = = double hills, the south China sea temple = Xia Yuan @ 5 = nangang = WenChong = Bai Jiang = xintang @ 16 = = after chang officer lake bridge', '14' : At post = baiyun dongping = 'golden tai Xia Liang = = = bamboo material clock fell tam Ma Li = new and = = peace = = = = god hills, deng village conghua passenger stations of dongfeng', '14 side: 'Xinhe = North of Knowledge City = Matouzhuang = Fengxia Village = Knowledge City = South of Knowledge City = Wangcun = Kangda = Zhenlongbei = Zhenlong@ No.21 ', '21 ':' Yuancun @5 = Tianhe Park = Tangdong = Huangcun @4 = Daguan South Road = Tianhe Smart City = Shenzhou Road = Science City = Suyuan @6 = Shuixi @7 = Changping = Jinkeng = Zhenlong west = Zhenlong @14 Branch line = Zhongxin = Kengbei = Fenggang = Zhucun = Shantian = Zhonggang = Zengcheng Square '} for (let key in subMessage) { // console.log(key); // console.log(subMessage[key]); fs.appendFileSync('./subway.txt', key + ':' + subMessage[key]+'\n','utf-8'); }Copy the code

The introduction of package

const fs = require('fs')
const readline = require('readline')
const lodash = require('lodash')
Copy the code

A partial method of encapsulation

Read the file and get the array of objects

function readSubwayFlie() {
    let showLine = fs.readFileSync('./subway.txt', 'utf-8');
    let subStr = showLine.split('\n');
    subStr.pop();
    showLine = [];
    let stred = [];
    for (let i = 0; i < subStr.length; i++) {
        stred = subStr[i].split(':');
        showLine.push({
            name: stred[0],
            line: stred[1]
        })
    }
    return showLine;
}
Copy the code

Reads an array of route objects corresponding to a station name

function stationToLine(station) { let subMessage = readSubwayFlie(); let Lines = []; for (let i = 0; i < subMessage.length; i++) { if (subMessage[i].line.includes(station)) Lines.push(subMessage[i]) } return Lines; } stationToLine(' Jiahe Wanggang ')Copy the code

Pass in name and an array of checked names to determine if the route has been checked

function isChecked(line, lineStr) {
    for (let i = 0; i < lineStr.length; i++) {
        if (lineStr[i] === line) return true
    }
    return false;
}
Copy the code

Pass in an array of route objects and a checked array of names to get a changeStation array, each of which is an object, {start:,changeToLine:}

function LineToChangeStation(Lines, checked) { let changeStation = []; let t; for (let i = 0; i < Lines.length; i++) { if (typeof (Lines[i].line) == 'string') { t = Lines[i].line.split('='); for (let j = 0; j < t.length; j++) { if (t[j].indexOf('@') > 0) { if (t[j].split('@').length === 2) { if (! isChecked(t[j].split('@')[1], checked)) { changeStation.push({ start: t[j].slice(0, t[j].indexOf('@')), changeToLine: t[j].slice(t[j].indexOf('@') + 1) }) } } else { if (! isChecked(t[j].split('@')[1], checked)) { changeStation.push({ start: t[j].slice(0, t[j].indexOf('@')), changeToLine: t[j].split('@')[1] }) } if (! isChecked(t[j].split('@')[2], checked)) { changeStation.push({ start: t[j].slice(0, t[j].indexOf('@')), changeToLine: t[j].split('@')[2] }) } } } } } } return changeStation; }Copy the code

Check if the route is in the destination route array, pass in name and the route route object array

function lineIsRequest(line, str) {
    for (let i = 0; i < str.length; i++) {
        if (line === str[i].name) return true
    }
    return false
}
Copy the code

• Gets the route line with the name name

function getOneLine(lineName) {
    let subMessage = readSubwayFlie();
    for (let i = 0; i < subMessage.length; i++) {
        if (subMessage[i].name == lineName) return subMessage[i].line
    }
    return null;
}
Copy the code

• Put the path of the buffer into “memory” and the buffer is cleared

function bufferToRAM(buffer, checked) {
    for (let i = 0; i < buffer.length; i++) {
        checked.push(buffer[i])
    }
    buffer = [];
}
Copy the code

Algorithm implementation function

Incoming to the beginning and the end

function mainFn(first, last) { let finish = false; let firstLine = stationToLine(first); let lastLine = stationToLine(last); let result = []; let checkedLine = []; // Let bufferCheckedLine = []; Let middleStation = []; let middleStation = []; For (let I = 0; i < firstLine.length; i++) { for (let j = 0; j < lastLine.length; j++) { if (firstLine[i].name === lastLine[j].name) { result.push({ start: first, line: firstLine[i].name }) finish = true; }} BufferCheckedLine.push (firstLine[I].name)} // Two lines to if (finish === false) {let already = 0; let one = LineToChangeStation(firstLine, bufferCheckedLine); bufferToRAM(bufferCheckedLine, checkedLine); for (let i = 0; i < one.length; i++) { if (lineIsRequest(one[i].changeToLine, lastLine)) { middleStation[0] = one[i]; finish = true; already = 1; } bufferCheckedLine.push(one[I].changetoline)}} finish) { let one = LineToChangeStation(firstLine, checkedLine); let two = []; let chang = []; BufferToRAM (bufferCheckedLine, checkedLine) for (let I = 0; i < one.length; i++) { middleStation[0] = one[i]; chang[0] = { name: one[i].changeToLine, line: getOneLine(one[i].changeToLine) }; two = LineToChangeStation(chang, checkedLine); for (let j = 0; j < two.length; j++) { if (lineIsRequest(two[j].changeToLine, lastLine)) { middleStation[1] = two[j]; finish = true; } bufferCheckedLine.push(two[j].changeToLine) } if (finish) break; If (finish === false) {checkedLine = []; bufferCheckedLine = []; let chang = []; for (let i = 0; i < firstLine.length; i++) { bufferCheckedLine.push(firstLine[i].name) } bufferToRAM(checkedLine, bufferCheckedLine) middleStation = []; let one = LineToChangeStation(firstLine, bufferCheckedLine); for (let i = 0; i < one.length; i++) { middleStation[0] = one[i]; chang[0] = { name: one[i].changeToLine, line: getOneLine(one[i].changeToLine) }; for (let m = 0; m < one.length; m++) { bufferCheckedLine.push(one[m].changeToLine) } two = LineToChangeStation(chang, bufferCheckedLine); for (let j = 0; j < two.length; j++) { middleStation[1] = two[j]; chang[0] = { name: two[j].changeToLine, line: getOneLine(two[j].changeToLine) } for (let m = 0; m < two.length; m++) { bufferCheckedLine.push(two[m].changeToLine) } three = LineToChangeStation(chang, bufferCheckedLine) for (let k = 0; k < three.length; k++) { if (lineIsRequest(three[k].changeToLine, lastLine)) { middleStation[1] = three[k]; finish = true; } } if (finish) break; } if (finish) break; bufferCheckedLine = []; for (let n = 0; n < checkedLine.length; n++) { bufferCheckedLine.push(checkedLine[n]) } } } if (! Finish) {console.log(' under development '); } if (result.length ! == 0) { let i = 0; for (i = 0; i < firstLine.length; i++){ if(firstLine[i].line.includes(last))break } let f = firstLine[i].line.indexOf(first) let l = firstLine[i].line.indexOf(last) console.log(firstLine[i].name); if (f > l) { console.log(firstLine[i].line.slice(l,f+first.length)); } else { console.log(firstLine[i].line.slice(f,l+last.length)); } } else if(finish){ let i = 0; for (i = 0; i < firstLine.length; i++){ if(firstLine[i].line.includes(middleStation[0].start))break } let f = firstLine[i].line.indexOf(first) let l = firstLine[i].line.indexOf(middleStation[0].start) console.log(firstLine[i].name); if (f > l) { console.log(firstLine[i].line.slice(l,f+first.length)); } else { console.log(firstLine[i].line.slice(f,l+middleStation[0].start.length)); } for (let j = 0; j < middleStation.length; j++){ let sub = getOneLine(middleStation[j].changeToLine); console.log(middleStation[j].changeToLine); if (j ! = middleStation.length - 1) { f = sub.indexOf(middleStation[j].start) l = sub.indexOf(middleStation[j + 1].start) if (f > l) { console.log(sub.slice(l, f + middleStation[j].start.length)); } else { console.log(sub.slice(f, l + middleStation[j+1].start.length)); } } else { f = sub.indexOf(middleStation[j].start) l = sub.indexOf(last) if (f > l) { console.log(sub.slice(l, f + middleStation[j].start.length)); } else { console.log(sub.slice(f,l+last.length)); } } } } }Copy the code

The main function

function main(){
    const rl = readline.createInterface(process.stdin, process.stdout);
    rl.question('input now ', answer => {
        let ans = answer.split(' ')
        if (ans.length === 2) {
            showSubLine(ans)
        } else if (ans.length === 6) {
            searchSub(ans)
        } else if (ans.length === 7) {
            mainFn(ans[1],ans[2])
        } else {
            console.log('input error');
        }
        rl.close()
    })
}
main()
Copy the code

Implemented functions

MainFn () : mainFn() : mainFn() : mainFn() : mainFn() : mainFn() : mainFn() : mainFn() : mainFn() : mainFn() : mainFn() : mainFn() : mainFn() : mainFn(

Existing problems

• The subway line is copied from the Internet, but there are problems between the logic of the line and the transfer, resulting in some output errors

• The algorithm implementation process can not take into account the user to transfer 5 or more lines of implementation, which I node.js has not been implemented

• There was a small problem with the format of the output. I was lazy and only output the line that the user wanted to sit on instead of one station at a time