เชื่อมต่อสามก๊ก
คุณเป็นเจ้าเหนือหัวในยุคกลางที่ได้รับมอบหมายให้ออกแบบเครือข่ายถนนระหว่างสามอาณาจักรที่วางบน\$9 \times 9\$กริด ตัวอย่างตำแหน่งของอาณาจักรอาจมีลักษณะดังนี้:
การใช้ที่ไม่ใช่เชิงพาณิชย์ของ tileset โดยdouteigami ขอบคุณ!
อาณาจักรต่างๆเรียกร้องสามประการดังต่อไปนี้:
- ถนนเครือข่ายจะต้องเชื่อมต่อ : สำหรับกระเบื้องใด ๆ บนเครือข่ายถนนที่คุณจะต้องสามารถที่จะไปถึงกระเบื้องอื่น ๆ ในเครือข่ายถนนโดยเพียงแค่การเคลื่อนย้ายในแนวนอนหรือแนวตั้งเท่านั้นพร้อมกระเบื้องถนน
- ราชอาณาจักรจะต้องเชื่อมต่อ : ทุกอาณาจักรมีอย่างน้อยหนึ่งกระเบื้องถนนทันทีที่อยู่ติดแนวนอนหรือแนวตั้ง
- เครือข่ายถนนต้องบาง : ไม่มีบล็อก\$2\times2\$ สี่เหลี่ยมทั้งหมดสามารถเป็นกระเบื้องถนน
เครือข่ายถนนทั้งสองต่อไปนี้เป็นไปตามเกณฑ์ทั้งสามข้อ:
การตั้งค่าต่อไปนี้ล้มเหลวเพื่อให้เป็นไปตามหนึ่งในสามเกณฑ์:
ท้าทาย
ป้อนข้อมูลของ\$9\times9\$ตารางที่มีสามอาณาจักรในรูปแบบใด ๆ นี่อาจเป็นสตริงหลายบรรทัดที่มีช่องว่างและอักขระรายการสตริงบรรทัดเดียวรายการของศูนย์และรายการเมทริกซ์หรือรูปแบบอื่น ๆ ที่เหมาะสมสำหรับภาษาของคุณ
ในฐานะเอาต์พุตให้เพิ่มเครือข่ายถนนเข้ากับอินพุต (ระบุด้วยวิธีที่เหมาะสม) ที่ตรงตามเกณฑ์สามข้อข้างต้น โปรดทราบว่า:
- อาณาจักรต่างๆจะไม่อยู่ติดกันในแนวนอนหรือแนวตั้ง
- ไม่มีข้อกำหนดว่าเครือข่ายถนนของคุณจะน้อยที่สุดในแง่ใด ๆ เพียง แต่เป็นไปตามกฎสามข้อ
- คุณไม่สามารถวางถนนบนอาณาจักรได้
- \$2\times2\$บล็อกที่สามกระเบื้องเป็นถนนและกระเบื้องแผ่นเดียวเป็นอาณาจักรก็โอเค ข้อ จำกัด ประการที่สามเกี่ยวข้องกับกระเบื้องสี่ช่องเท่านั้น
กรณีทดสอบ
กรณีทดสอบใช้.สำหรับพื้นที่ว่างkสำหรับอาณาจักรและ#สำหรับถนน แต่คุณสามารถป้อนข้อมูลในรูปแบบอื่น / ใช้อักขระหรือจำนวนเต็มสามตัวที่แตกต่างกันตามที่อธิบายไว้ในส่วนก่อนหน้า
Input -> Possible output
......... .........
....k.... ....k....
......... ....#....
......... ....#....
.k....... -> .k####...
......... .....#...
.....k... .....k...
......... .........
......... .........
k.k...... k#k......
......... .#.......
k........ k#.......
......... .........
......... -> .........
......... .........
......... .........
......... .........
......... .........
.k....... .k.......
k........ k#.......
.k....... .k.......
......... .........
......... -> .........
......... .........
......... .........
......... .........
......... .........
......... .........
......... .........
k........ k#.......
......... .#.......
k........ -> k#.......
......... .#.......
k........ k#.......
......... .........
......... .........
........k ...#####k
....k.... ...#k....
......... ...#.....
......... ...#.....
......... -> ...#.....
......... ####.....
......... ...#.....
....k.... ...#k....
......... ...#.....
......... .........
......... .........
......... .........
......... .........
......... -> .........
......... .........
k........ k........
.k....... #k.......
..k...... ##k......
นี่คือปัจจัยการผลิตที่เป็นรายการของรายการที่คุณต้องการ:
[[[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]], [[1, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 1, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0]]]
การให้คะแนน
รหัสที่สั้นที่สุดในหน่วยไบต์ชนะ
คำตอบ
JavaScript (ES7), 166153149137 ไบต์
ช้าและละเอียดอ่อนกว่าคำตอบแรกของฉัน แต่ก็สั้นกว่าด้วย เพียงแค่มองหาเส้นทางที่สัมผัสกับอาณาจักรทั้งหมดโดยไม่ต้องสร้าง\$2\times 2\$ บล็อกถนน
รับข้อมูลเป็นรายการเดียว 81 รายการโดยมี\$0\$สำหรับเซลล์ว่างและ\$2\$สำหรับอาณาจักร ส่งคืนรายการอื่นด้วย\$0\$สำหรับเซลล์ว่าง\$1\$สำหรับถนนและ\$3\$ สำหรับอาณาจักร
f=(a,X)=>+(z=/.*1,1.{15}1,1|2/.exec(a))?a.some((v,x)=>(a[x]++,(d=(x-X)**2)-1|x/9^X/9&&d-81?0:v?1/X&&v==2?f(a,X):0:f(a,x))||!a[x]--)&&a:!z
ลองออนไลน์!
อย่างไร?
เราใช้นิพจน์ทั่วไป/.*1,1.{15}1,1|2/เพื่อตรวจหา a \$2\times 2\$ปิดกั้นถนนหรืออาณาจักรที่เหลืออยู่ เราได้รับnullหากไม่มีสิ่งใดที่ตรงกันสตริงที่ถูกบังคับให้เป็นNaNโดยยูนารี+หากบล็อกถูกจับคู่หรือสตริงที่บังคับให้เป็น\$2\$ ถ้าอาณาจักรถูกจับคู่
เนื่องจากไม่สนใจขอบเขตด้านซ้ายและด้านขวาสภาพของถนนจึงมีข้อ จำกัด มากกว่าที่ควรจะเป็นเล็กน้อยเนื่องจากจะจับคู่กับสิ่งนั้นด้วย:
.........
........X
X.......X
X........
.........
อย่างไรก็ตามเรามีพื้นที่มากมายในการค้นหาเส้นทางที่จะใช้งานได้แม้จะไม่รวมรูปแบบนั้นด้วยก็ตาม
JavaScript (ES7), 243 236226 ไบต์
ฉันไม่ค่อยพอใจกับวิธีนี้มากนักเนื่องจากต้องอาศัยการค้นหาแบบดุร้าย ต้องมีวิธีการแก้ปัญหานี้ที่สง่างามและตรงไปตรงมามากกว่านี้ แต่มันได้ผล!
คาดว่าเมทริกซ์ที่มี\$0\$สำหรับเซลล์ว่างและ\$3\$สำหรับอาณาจักร ส่งคืนเมทริกซ์อื่นด้วย\$0\$สำหรับเซลล์ว่าง\$2\$อาณาจักรและ\$4\$ สำหรับถนน
f=(m,k)=>(M=m.map((r,y)=>r.map((v,x)=>x^k%8&&x^k%8+2+k/8%8&&y^(q=k/64&7)&&y^q+2+k/512?v:v?3:(X=x,Y=y,1))),g=(X,Y)=>M.map((r,y)=>r.map((v,x)=>(x-X)**2+(y-Y)**2-1?0:v-1?v-3?0:r[x]=2:g(x,y,r[x]=4))))(X,Y)|/1|3/.test(M)?f(m,-~k):M
ลองออนไลน์!
อย่างไร?
ปริศนาทั้งหมดสามารถแก้ไขได้1โดยวางถนนแนวนอนไม่เกิน 2 เส้นและถนนแนวตั้งสูงสุด 2 เส้นทั่วทั้งตารางไม่ว่าจะอยู่ข้างหรือ 'เหนือ' อาณาจักร
1: สิ่งนี้ได้รับการตรวจสอบเชิงประจักษ์แล้ว
ตัวอย่าง:
ให้\$k\ge 0\$เราคำนวณ:
$$x_0=k\bmod 8$$ $$x_1=x_0+2+(\lfloor k/8\rfloor \bmod 8)$$ $$y_0=\lfloor k/64\rfloor \bmod 8$$ $$y_1=y_0+2+\lfloor k/512\rfloor$$
เราวางถนนแนวตั้งที่\$x_0\$และ\$x_1\$และถนนแนวราบที่\$y_0\$และ\$y_1\$. หากค่าใด ๆ มากกว่า\$8\$มันถูกเพิกเฉย
เพราะ\$x_1\ge x_0+2\$และ\$y_1\ge y_0+2\$เราจะไม่จบลงที่\$2\times 2\$ ปิดกั้นถนน
เริ่มจากเซลล์ถนนเราเติมเส้นตารางเพื่อให้แน่ใจว่าเป็นไปตามเกณฑ์อีกสองข้อ
Perl 5 , 251 317 298 258 ไบต์
sub f{eval'forP(0..80){forT(0,1){my@r;forK(@_){X=intP/9;Y=P%9;I=intK/9;J=K%9;push@r,X*9+Y andT&&Y-J?Y-=Y<=>J:X-I?X-=X<=>I:Y-J?Y-=Y<=>J:0 whileX.Y neI.J}D="."x81;substrD,$_,1,1for@_;substrD,$_,1,0for@r;3==D=~y/1/1/&&D!~/00.{7}00/&&returnD}}'=~s/[A-Z]/\$$&/gr}
ลองออนไลน์!
ค่อนข้างไม่พอใจ:
sub f {
for$p(0..80){ #loop through all possible starting points p,
#... the crossroads in the 9x9 board
#... from which each road to each kingdom starts
for$t(0,1){ #for each starting point, try two strategies #...of movement: vertical first or horizontal first my @r; #init list of road tiles to empty for(@_){ #loop through all the three kingdoms from input $x=int$p/9; $y=$p%9; #x,y = start roads at current starting point p $X=int$_/9; $Y=$_%9; #X,Y = current kingdom push @r, $x*9+$y #register road tile while x,y not yet reached X,Y and # move x,y towards X,Y $t && $y-$Y ? $y-=$y<=>$Y : $x-$X ? $x-=$x<=>$X :
$y-$Y ? $y-=$y<=>$Y :0 # move horizontally or vertically first # ...depending on current strategy t=0 or 1 while $x.$y ne $X.$Y # continue towards current kingdom unless there } $d='.'x81; # init current board string of 81 dots
substr $d,$_,1,1 for @_; # put 1's at kingdoms
substr $d,$_,1,0 for @r; # put 0's at road tiles
3==$d=~s/1/1/g # if board has 3 kingdoms (none overrun by road) && $d!~/00.{7}00/ # and current board has no 2x2 road tiles
&& return $d # then the board is valid and is returned
# otherwise try the next of the 81 starting points
}
}
}
สามารถทำงานได้ดังนี้:
@test=( [[1,4], [4,1], [6,5]],
[[0,0], [0,2], [2,0]],
[[0,1], [1,0], [2,1]],
[[2,0], [4,0], [6,0]],
[[0,8], [1,4], [7,4]],
[[6,0], [7,1], [8,2]] );
for(@test){
my @kingdom = map $$_[0]*9+$$_[1], @$_;
print display( f(@kingdom) );
}
sub display{join('',map join(' ',split//)."\n",pop=~y/10/k#/r=~/.{9}/g).('-'x17)."\n"}
บรรทัดแรกของผลลัพธ์: (ดูลิงก์' ทดลองใช้ออนไลน์ ' ด้านบนสำหรับข้อมูลเพิ่มเติม)
# . . . . . . . .
# # # # k . . . .
# . . . . . . . .
# . . . . . . . .
# k . . . . . . .
# . . . . . . . .
# # # # # k . . .
. . . . . . . . .
. . . . . . . . .
Brachylog , 97 93 ไบต์
นี่มันเร็ว - กำลังดุร้ายใน Brachylog! คุณไม่อยากจะเชื่อเลยว่าฉันประหลาดใจแค่ไหนเมื่อฉันเพิ่มขนาดกระดาน อย่างไรก็ตามสิ่งนี้ถือว่าถนนไม่จำเป็นต้องมีทางแยก หากใครพบตัวอย่างการตอบโต้ - ขอเตือนเวอร์ชันอื่นจะไม่ทำงานตรงเวลาบน TIO! :-)
ใช้ปราสาทเป็น 2 และส่งคืนถนนเป็น 1
∧ċ{Ċℕᵐ≤ᵛ⁹}ᵐ{s₂{;.\-ᵐȧᵐ+1∧}ᵈ}ᵇP{,1↻₁}ᵐX&{iiʰgᵗc}ᶠT{ṗʰb}ˢ{,.≠&↰₃ᵐ∈ᵛ}P∧T,X≜bᵍtᵐhᵐḍ₉.¬{s₂\s₂c=₁}∧
ลองออนไลน์! หรือลองทดสอบทั้งหมด!
เวอร์ชันดั้งเดิมทำงานอย่างไร
หลายไบต์หายไปสำหรับการรับเอาต์พุตในรูปแบบเมทริกซ์เนื่องจากฉันไม่พบวิธีที่เป็นระเบียบในการเปลี่ยนจากรายการพิกัดไปเป็นการแสดงเมทริกซ์ เนื้อเรื่องคร่าวๆคือ:
ċ{l₂ℕᵐ≤ᵛ⁹}ᵐ
เรากำลังมองหาเส้นทาง: รายการพิกัดแต่ละ 0 ≤ X ≤ 9
s₂ᵇ{\-ᵐȧᵐ+}ᵛ¹hᵐ
และทุกคู่ของพิกัดที่ต่อเนื่องกันมีระยะห่าง 1.
P{,1↻₁}ᵐX
เราจะเก็บเส้นทางเป็นPและรุ่นที่มี 1 Xทุกครั้งก่อนการประสานงานเป็น
&{iiʰgᵗc}ᶠT
แปลงเมทริกซ์ในรายการของและเก็บไว้เป็น[Type, Y, X]T
{ṗʰb}ˢ
อย่างไรก็ตามตอนนี้เราสนใจเฉพาะเมืองดังนั้นเมืองTypeต้องเป็นไพรม์ (นั่นคือสาเหตุที่พวกเขามีเครื่องหมาย 2)
C,P≠
พิกัดของเมืองและเส้นทางจะต้องแตกต่างกัน
∧C{;.↰₂1∧}ᵐ∈ᵛP≜
ทุกเมืองที่ประสานกันโดยระยะทาง 1 จะต้องอยู่ในเส้นทาง
∧T,Xbᵍtᵐhᵐḍ₉
ในการTต่อท้ายไทล์X(เส้นทางที่มีType = 1คำนำหน้า) ให้จัดกลุ่มไทล์ตามพิกัดและใช้อันสุดท้าย - ดังนั้นถนนจะเขียนทับไทล์ว่าง ลดรายการเป็นTypeและแบ่งออกเป็นเมทริกซ์ 9x9
.¬{s₂\\s₂c=₁}∧
นี่เป็นผลลัพธ์อยู่แล้ว แต่ตรวจสอบให้แน่ใจว่าไม่มี 2x2 subatrix ของถนน
R , 248 257 251 264 250 245 ไบต์
แก้ไข: +9 ไบต์เพื่อแก้ไขมุมเคส (ตามตัวอักษรดู # 1 ด้านล่าง) จากนั้นตีกอล์ฟจากนั้น +13 ไบต์เพื่อแก้ไขมุมเคสอื่น (# 2 ด้านล่าง) จากนั้นตีกอล์ฟเพิ่มเติม ...
function(g,s=setdiff,S=0:8%/%3-1,`^`=`%in%`){k=which(g>0,T);v=k[,1];w=k[,2]
g[r<-max(s(v+S,v)%%9),]=g[,c<-max(s(w+S,w)%%9)]=1
for(i in 1:3){x=v[i];y=w[i]
if(!(x^(r+S)|y^(c+S)))`if`(F|x^v[-i],g[x:r,y--y^w[-i]**(y<2)]<-1,g[x,y:c]<-F<-1)}
g[k]=2;g}
ลองออนไลน์!
นี่เป็นวิธีการแก้ปัญหาแบบ 'สร้างสรรค์' แทนที่จะเป็น 'กำลังเดรัจฉาน': เราสร้างถนนชุดเดียวในลักษณะที่เงื่อนไขจะพึงพอใจแทนที่จะพยายามหาโอกาสที่เป็นไปได้ต่างๆและตรวจสอบว่าเราหรือไม่ ละเมิดเงื่อนไขอย่างน้อยหนึ่งข้อ
อินพุตคือเมทริกซ์ที่มีองค์ประกอบที่ไม่ใช่ศูนย์ซึ่งเป็นตัวแทนของอาณาจักรทั้งสาม เอาต์พุตคือเมทริกซ์ที่มีถนนแทนด้วย 1 และอาณาจักรด้วย 2
อย่างไร?
ก่อนอื่นเราสร้างถนน 'หลัก' ในรูปแบบของ '+' จากเหนือจรดใต้และจากตะวันออกไปตะวันตกผ่านองค์ประกอบที่ว่างเปล่าของเส้นตารางและสัมผัสอย่างน้อยหนึ่งใน 3 อาณาจักร ( ดูแล: มุม - กรณีที่ 2 คือเมื่ออาณาจักรทั้งหมดอยู่ในแถวขอบ / คอลัมน์ดังนั้นเราต้องตรวจสอบให้แน่ใจว่าถนน 'ที่อยู่ติดกัน' ของเรายังคงอยู่ในเส้นตาราง )
ตอนนี้เหลือเพียง 2 อาณาจักรที่ยังต้องเชื่อมต่อ
สำหรับแต่ละอาณาจักรที่ไม่ได้เชื่อมต่อกับถนน 'หลัก' เราได้สร้าง 'ถนนทางเข้า' จากอาณาจักรไปยังถนน 'หลัก' เส้นหนึ่ง
เราต้องระวังว่า 'ทางเข้า' จะไม่ถูกแยกออกจากอาณาจักรใดอาณาจักรหนึ่งดังนั้นเราจึงตรวจสอบว่าอาณาจักรที่ไม่ได้เชื่อมต่อนั้นอยู่ในแถวเดียวกับอาณาจักรอื่นหรือไม่และหากไม่ใช่เราจะสร้าง ถนนทางเข้าตะวันออก - ตะวันตก. หากอาณาจักรที่ไม่ได้เชื่อมต่อใช้แถวร่วมกับอาณาจักรอื่นเราจะตรวจสอบว่าอาณาจักรนั้นแชร์คอลัมน์ของตนด้วยหรือไม่ถ้าไม่เราจะสร้างถนนทางเข้าทิศเหนือ - ใต้ ถ้าเป็นเช่นนั้น (และแชร์แถวด้วย) เราจะมั่นใจได้ว่าคอลัมน์ที่อยู่ติดกันว่างเปล่าดังนั้นเราจึงสร้างถนนทางเข้าทิศเหนือ - ใต้ในคอลัมน์ที่อยู่ติดกับอาณาจักร ( กรณีมุม 1: สำหรับสิ่งนี้เราต้องการ เพื่อตรวจสอบว่าอาณาจักรอยู่ในคอลัมน์ 1 หรือไม่: ถ้าเป็นเช่นนั้นเราจะสร้างถนนทางเข้าในคอลัมน์ 2 หรือในคอลัมน์ y-1 )
ต่อไปนี้คือถนน (สีส้ม) ที่สร้างขึ้นสำหรับแต่ละกรณีการทดสอบ 6 กรณี (อาณาจักรที่ระบุด้วยสีขาว):
รหัสแสดงความคิดเห็น:
function(g, # g=input grid with kingdoms
s=setdiff, # s=alias to 'setdiff()' function
S=0:8%/%3-1, # S=defines adjacent indices
`^`=`%in%`){ # ^=alias to '%in%' function
k=which(g>0,T) # k=get indices of the kingdoms
v=k[,1];w=k[,2] # v=x-coordinates, w=y-coordinates of kingdoms
r<-max(s(v+S,v)%%9) # r=empty row next-to a kingdom
# (elements of v±1 that are different to v, avoiding zero and >8)
c<-max(s(w+S,w)%%9) # c=first empty column next-to a kingdom
g[r,]=g[,c]=1 # build the 'main' roads
for(i in 1:3){ # loop through each of the 3 kingdoms:
x=v[i];y=w[i] # (x,y=x- and y-coordinates of current kingdom)
if(!(xin%(r+S)|y%in%(c+S))) # if x or y are not adjacent to r or s
# (so this kingdom isn't connected to the 'main' roads)
`if`(F|x%in%v[-i], # if x is shared with the row of another kingdom, or
# 'F' indicates that we've already built an east-west 'access road':
g[x:r,y # build an north-south 'access road' from x to r
- # (either on the same row, y, or on an adjacent row
(-(y%in%w[-i]))**(y<2)<-1, # if y is shared with the col of another kingdom);
g[x,y:c]<-F<-1) # otherwise build an east-west 'access road' from y to c
}
g[k]=2; # mark the kingdoms on the grid
g # and return the grid
}
ถ่าน 196 ไบต์
≔Ｅ⁹ＳθＦ⁹Ｆ⌕Ａ§θιk⊞υ⟦ικ⟧ＦυＦ⁴Ｆ⁴«θＪ§ι¹§ι⁰Ｍ✳⊗λ≔⁰ζＷ⁼ＫＫ.«✳⊗κ#≦⊕ζ»≔ωηＦ⁻υ⟦ι⟧Ｆ⁴Ｆ⁴«Ｊ§μ¹§μ⁰Ｍ✳⊗ξ≔ＫＤ⁹✳⊗νδＭ⌕δ#✳⊗ν¿∧№δ#¬№…δ⌕δ#¦k¿⁼⌕υμ¬⌕υι≔⟦μⅈⅉν⌕δ#ξ⟧η¿∧η⊖ΣＥ⟦ⅈⅉ⟧↔⁻π§η⊕ρ≔⟦⟦ικζλ⟧η⟦μν⌕δ#ξ⟧⟧ε»⎚»θＦε«Ｊ⊟§ι⁰⊟§ι⁰Ｍ✳⊗⊟ι✳⊗⊟ι×#⊟ι
ลองออนไลน์! ลิงก์คือรหัสเวอร์ชันที่ละเอียด ทำงานโดยลากเส้นจากสี่เหลี่ยมที่อยู่ติดกับอาณาจักรหนึ่งไปยังขอบของกริดจากนั้นลากเส้นจากสี่เหลี่ยมที่อยู่ติดกับอาณาจักรอื่น ๆ เพื่อตัดกันบรรทัดแรกยกเว้นไม่ให้ทั้งสองเส้นอยู่ห่างกันเพียงแถวเดียว คำอธิบาย:
≔Ｅ⁹Ｓθ
ป้อนตาราง
Ｆ⁹Ｆ⌕Ａ§θιk⊞υ⟦ικ⟧
ค้นหาอาณาจักรทั้งหมด
ＦυＦ⁴Ｆ⁴«
วนรอบแต่ละทิศทางจากแต่ละตารางที่อยู่ติดกับแต่ละอาณาจักร
θ
พิมพ์เส้นตาราง
Ｊ§ι¹§ι⁰Ｍ✳⊗λ
ข้ามไปยังอาณาจักรที่เลือกและย้ายไปยังจัตุรัสที่อยู่ติดกันที่เลือก
≔⁰ζ
นับจำนวนช่องว่าง
Ｗ⁼ＫＫ.«
ทำซ้ำในขณะที่สแควร์ปัจจุบันว่างเปล่า ...
✳⊗κ#
... ทำเครื่องหมายด้วย#...
≦⊕ζ
... และเพิ่มจำนวน
»≔ωη
เริ่มต้นโดยไม่มีเส้นแบ่งสำหรับอาณาจักรที่สอง
Ｆ⁻υ⟦ι⟧
วนรอบอาณาจักรที่เหลือ
Ｆ⁴Ｆ⁴«
วนรอบทิศทางจากแต่ละตารางที่อยู่ติดกับอาณาจักรนี้
Ｊ§μ¹§μ⁰Ｍ✳⊗ξ
ข้ามไปที่อาณาจักรนี้และย้ายไปยังจัตุรัสที่อยู่ติดกันที่เลือก
≔ＫＤ⁹✳⊗νδ
จับเส้นในทิศทางที่เลือก
Ｍ⌕δ#✳⊗ν
ย้ายไปยังจุดที่เส้นจะตัดกันถ้าถูกต้อง
¿∧№δ#¬№…δ⌕δ#¦k
เส้นนี้ข้ามเส้นของอาณาจักรแรกหรือไม่? ถ้าเป็นเช่นนั้น:
¿⁼⌕υμ¬⌕υι
ถ้านี่คืออาณาจักรที่สอง ...
≔⟦μⅈⅉν⌕δ#ξ⟧η
... จากนั้นบันทึกเป็นบรรทัด
¿∧η⊖ΣＥ⟦ⅈⅉ⟧↔⁻π§η⊕ρ
มิฉะนั้นถ้าเส้นของอาณาจักรที่สองไม่ได้ตัดออกไปหนึ่งตาราง ...
≔⟦⟦ικζλ⟧η⟦μν⌕δ#ξ⟧⟧ε
... จากนั้นบันทึกเป็นวิธีแก้ปัญหา
»⎚
ล้างผ้าใบให้พร้อมสำหรับสี่เหลี่ยมที่อยู่ติดกันถัดไปของอาณาจักรแรกหรือผลลัพธ์สุดท้าย
»θ
พิมพ์เส้นตาราง
Ｆε«
วนรอบอาณาจักรในโซลูชันสุดท้ายที่พบ
Ｊ⊟§ι⁰⊟§ι⁰Ｍ✳⊗⊟ι
ข้ามไปยังตำแหน่งของราชอาณาจักรและย้ายไปยังจัตุรัสที่อยู่ติดกัน
✳⊗⊟ι×#⊟ι
พิมพ์บรรทัดที่พบ
โปรดทราบว่ารหัสนี้จะพยายามรวมอาณาจักรและทิศทางทั้งหมดเข้าด้วยกัน อาจไม่จำเป็นที่จะต้องลองทั้งหมดตัวอย่างเช่นฉันคิดว่าเป็นไปได้ว่าคุณสามารถลากเส้นจากด้านใดด้านหนึ่งของอาณาจักรที่อยู่ล่างสุดและเชื่อมต่ออีกสองอาณาจักรเข้ากับเส้นนั้นได้ หากเป็นจริงแสดงว่าโค้ดสามารถทำให้ง่ายขึ้นปัจจุบันประหยัด10 24 ไบต์: ลองออนไลน์! ลิงก์คือรหัสเวอร์ชันที่ละเอียด คำอธิบาย:
≔Ｅ⁹ＳθＦ⁹Ｆ⌕Ａ§θιk⊞υ⟦ικ⟧
ป้อนตารางและค้นหาอาณาจักรทั้งหมด
≔⊟υτ
รับอาณาจักรที่อยู่ล่างสุด
Ｆ³«
ตรวจสอบช่องสี่เหลี่ยมทางด้านขวาด้านบนและด้านซ้าย
θＪ§τ¹§τ⁰Ｍ✳⊗ι
พิมพ์เส้นตารางและข้ามไปยังสี่เหลี่ยมที่อยู่ติดกันที่เลือก
≔⁰ζＷ⁼ＫＫ.«↑#≦⊕ζ»
ลากเส้นให้ไกลที่สุด
≔ωη
เริ่มต้นโดยไม่มีเส้นแบ่งสำหรับอาณาจักรที่สอง
ＦυＦ⁴Ｆ⁴«
วนรอบอีกสองอาณาจักรโดยพิจารณาเส้นทั้งหมดสำหรับสี่เหลี่ยมที่อยู่ติดกันทั้งสี่ (ฉันสามารถทำเส้นซ้ายและขวาได้ แต่ปรากฎว่าทุกเส้นเป็นนักกอล์ฟมากกว่า)
Ｊ§κ¹§κ⁰Ｍ✳⊗μ
ข้ามไปที่จัตุรัสที่อยู่ติดกันของอาณาจักรนี้
≔ＫＤ⁹✳⊗λδ
จับเส้นในทิศทางที่เลือก
¿∧№δ#¬№…δ⌕δ#¦k
เส้นนี้ข้ามเส้นของอาณาจักรแรกหรือไม่? ถ้าเป็นเช่นนั้น:
¿⌕υκ«
ถ้านี่คืออาณาจักรที่สามล่ะก็ ...
¿∧η⊖↔⁻ⅉ§η¹
... ถ้าแถวของอาณาจักรที่สองไม่ได้อยู่ห่างออกไปหนึ่งแถวล่ะก็ ...
≔⟦⟦τ¹ζι⟧η⟦κλ⌕δ#μ⟧⟧ε
... บันทึกไว้เป็นแนวทางแก้ไข
»≔⟦κⅉλ⌕δ#μ⟧η
มิฉะนั้นสำหรับอาณาจักรที่สองจะบันทึกสิ่งนี้ไว้เป็นแนวของมัน
»⎚
ล้างผ้าใบให้พร้อมสำหรับสี่เหลี่ยมที่อยู่ติดกันถัดไปของอาณาจักรแรกหรือผลลัพธ์สุดท้าย
»θＦε«Ｊ⊟§ι⁰⊟§ι⁰Ｍ✳⊗⊟ι✳⊗⊟ι×#⊟ι
พิมพ์โซลูชัน
J , 139 127 ไบต์
เริ่มจาก[0,1]หรือ[0,2]สร้างสองกริด
#XX#… and .X.#…
#.#.… ####…
####… .#.#…
#.#.… ####…
ความพยายามอย่างน้อยหนึ่งใน 3 ครั้งจะประสบความสำเร็จ (ขึ้นอยู่กับสคริปต์ J ที่แฮ็กเข้าด้วยกัน) สำหรับการประหยัดไบต์ให้ลองใช้กริดเพิ่มเติม:
+u({.@\:#@~.@,"3)0|:(d|.!.0]*1+i.@$)*"2/u=:(}:"2}:"{d|.10$#:1023 682)(2=_(d=:(,-)#:i.3)&(*@]*[:>./|.!.0)(9 9$!.1]1 2 2)*1=+)"2]
ลองออนไลน์!
วิธีการทำงานคร่าวๆ
ยังควรมีบางไบต์ที่สามารถเล่นกอล์ฟได้ แต่สำหรับตอนนี้:
(}:"2}:"{d|.10$#:1023 682)
เส้นกริด - ก่อนอื่นเป็นเมทริกซ์ 10x10 เพื่อให้เราสามารถเปลี่ยนทิศทางผ่าน 4 directions ได้อย่างง่ายดายเราจะกำหนดในภายหลัง ข้อเสียเปรียบ: เราต้องลดให้เหลือ 9x9 ตอนนี้สำหรับทุกตาราง:
(9 9$!.1]1 2 2)*1=+
เมื่อใดก็ตามที่ปราสาทอยู่บนถนนให้ตั้งค่ากระเบื้องให้ว่างเปล่า นอกจากนี้ให้ระบุถนนที่[0,1]และ[0,2]ค่า 2 (หากมี) จากนั้นเราจะพบเครือข่ายถนนที่เชื่อมต่อที่ใหญ่ที่สุดในขณะนี้:
2=_(d=:(,-)#:i.3)&(*@]*[:>./|.!.0)
จนกว่าแผนที่จะไม่เปลี่ยนแปลง: เลื่อนไปรอบ ๆ และกำหนดหมายเลขถนนใหม่ให้แต่ละถนน: จำนวนสูงสุดปัจจุบันและจำนวนถนนที่เชื่อมต่อกัน (แต่ให้ 0 เป็น 0) สุดท้ายรักษาถนนที่มีเครื่องหมาย 2 ไว้ - ถนนเหล่านั้นเชื่อมต่อกับโหนดเริ่มต้น
(d|.!.0]*1+i.@$)*"2/
ตอนนี้เพื่อตรวจสอบว่าปราสาททั้งหมดเชื่อมต่อกันแล้ว: ใช้อินพุตเดิมและเลื่อนไปที่ 4 ทิศทาง ให้หมายเลขที่ไม่ซ้ำกันแต่ละปราสาท
+u({.@\:#@~.@,"3)0|:
จัดเรียงกริดตามจำนวนปราสาทที่เชื่อมต่อกัน (ตัวเลขที่ไม่ซ้ำกันหลังจากหมายเลขปราสาทที่เลื่อนจะถูกคูณด้วย 1 ของเครือข่ายถนน) เลือกสิ่งที่ดีที่สุดเพิ่มปราสาทกลับเข้าไปใน - et voilàอาณาจักรสำหรับคุณ!
ถ่าน 67 ไบต์
Ｆ⁹Ｆ⌕ＡＳk⊞υ⟦ικ⟧Ｂ⁹ψＦ⁹Ｆ⁹«Ｊκι¿¬№﹪⟦ικ⟧²﹪ΠＥυΠ⊕λ² »Ｆυ«Ｊ⊟ι⊟ιk»Ｆ³Ｆ³«Ｊ⁺³κ⁺³ι¤#
ลองออนไลน์! ลิงก์คือรหัสเวอร์ชันที่ละเอียด เอาต์พุตโดยใช้ช่องว่างสำหรับไทล์ว่าง แต่สิ่งใดก็ตามยกเว้นkทำหน้าที่เป็นช่องว่างบนอินพุต นี่เป็นแนวทางที่แตกต่างอย่างสิ้นเชิงกับคำตอบก่อนหน้าของฉันดังนั้นฉันจึงคิดว่ามันสมควรได้รับคำตอบแยกต่างหาก มันขึ้นอยู่กับการสังเกตว่ากริดที่มี 16 รูสามารถแก้ปัญหาทั้งหมดได้ยกเว้นสิ่งที่มีสามก๊กใกล้มุม สิ่งหนึ่งที่ปัญหาเหล่านี้มีเหมือนกันคือทั้งสามอาณาจักรอยู่บนแถวและคอลัมน์ ในกรณีเช่นนี้เส้นตารางจะหักล้างในแนวทแยงมุมทำให้ได้ตารางที่มี 25 รู คำอธิบาย:
Ｆ⁹Ｆ⌕ＡＳk⊞υ⟦ικ⟧
อ่านในตารางและบันทึกพิกัดของอาณาจักร
Ｂ⁹ψ
เตรียมพื้นที่ว่างสำหรับกริด
Ｆ⁹Ｆ⁹
วนรอบแต่ละช่องบนเส้นตาราง
«Ｊκι
ข้ามไปที่ตำแหน่งนั้น
¿¬№﹪⟦ικ⟧²﹪ΠＥυΠ⊕λ² »
หากทั้งแถวและคอลัมน์มีความเท่าเทียมกันกับบิตหรือของพิกัดทั้งหมดให้วางช่องว่างที่ชัดเจนที่ตำแหน่งนั้นเพื่อป้องกันไม่ให้น้ำท่วม เนื่องจากฉันไม่มีวิธีที่ดีในการใช้บิตหรือรายการของรายการฉันจึงใช้กฎหมายของเดอมอร์แกนเพื่อตรวจสอบว่าทั้งแถวหรือคอลัมน์ไม่มีความเท่าเทียมกันของบิตและของส่วนเติมเต็มของรายการหรือไม่โดยสังเกตว่าเพื่อวัตถุประสงค์ ของความเท่าเทียมกันผลิตภัณฑ์เทียบเท่ากับบิตและ AND และส่วนเพิ่มจะเทียบเท่ากับส่วนเติมเต็ม
Ｆυ«Ｊ⊟ι⊟ιk»
วางอาณาจักรบนกริด
Ｆ³Ｆ³«Ｊ⁺³κ⁺³ι¤#
พยายามเติมน้ำให้ท่วมโดยเริ่มจากสี่เหลี่ยมตรงกลางทั้งเก้า สิ่งนี้รับประกันได้ว่าผลลัพธ์คือถนนที่เชื่อมต่อกันเพียงเส้นเดียว เป็นไปไม่ได้ที่จะมีเพียงสามอาณาจักรเท่านั้นที่จะตัดการเชื่อมต่อตรงกลางของกริดดังนั้นสิ่งนี้จึงปลอดภัยเสมอ
Perl 5 -00ap , 114 , 109 ไบต์
$_|=substr'iiiiiiiii
iaiaiaiai
'x5,10*!(grep/k/,@F[1,7]),90;1while s/(?<!i.{9})(?<!ii)i(?!iii|.{9}i.{9}i)/a/s
6 ไบต์บันทึกขอบคุณที่ @DomHastings แต่ 1 หายไปในการแก้ไขปัญหากรณี
ลองออนไลน์!
คำตอบ perl อื่นด้วยวิธีการที่แตกต่างฉันยังเพิ่มคะแนนให้กับคำตอบ perl อื่น ๆ
ฉันต้องแก้ไขหลายครั้งเนื่องจากบางกรณี (นอกเหนือจากคำถาม) ซึ่งไม่ได้ผล
วิธีการแก้
แนวคิดคือการเริ่มต้นจากเส้นตารางของถนนซึ่งเกือบจะใช้งานได้และแก้ไขได้สำหรับกรณีต่างๆ หากมีอาณาจักรอยู่ในพื้นที่สี่เหลี่ยมจัตุรัสของoแถว s: 1 หรือ 7 (หลังการตีกอล์ฟ) เส้นตารางจะอยู่ในแนวเดียวกับ (0,0) หรือใน (0,1)
......... ######### # # # # #
ooooooooo # # # # # #########
......... ######### # # # # #
......... # # # # # #########
......... ? ######### : # # # # #
......... # # # # # #########
......... ######### # # # # #
ooooooooo # # # # # #########
......... ######### # # # # #
จากนั้นสามารถแก้ไขถนนที่เหลือได้โดยการลบสี่เหลี่ยมเมื่อสี่เหลี่ยมทั้งหมดในสี่ทิศทางเชิงประจักษ์ (ยังไม่มีการพิสูจน์) ที่ระยะ 3 (ขวา) 2 (ซ้ายล่าง) หรือ 1 (ขึ้น) ไม่ใช่ถนน (หรืออยู่นอกแผนที่)
?
??#???
?
?
เหตุผล
กำลังมองหาตัวอย่างตอบโต้ เริ่มต้นจากเส้นตารางของถนนและสร้างอาณาจักรเพื่อให้ถนนสามารถตัดการเชื่อมต่อกับอาณาจักรได้
เนื่องจากความสมมาตรจะแสดงเฉพาะมุมแรกเท่านั้น สำหรับกริด 1 กรณีเดียวที่ทำให้เกิดปัญหา:
k.k###
. # #
k#####
# # #
และเนื่องจากไม่มีอาณาจักรใดในภูมิภาคที่อธิบายไว้ในโซลูชันจึงไม่สามารถเกิดขึ้นได้
สำหรับกริด 2 ตัวอย่างเดียว แต่มีการกำหนดค่าอื่น ๆ :
k # #
..k###
k # #
######
หนึ่งใน 2 อาณาจักรที่ตัดถนนต้องอยู่ในภูมิภาคที่อธิบายไว้ในวิธีแก้ปัญหาจึงไม่สามารถเกิดขึ้นได้