[Community Puzzle] OneWay City

Puzzles
#1

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

#2

For ā€˜Megapolisā€™ testcase - it says expected ā€˜Nothingā€™ - any clues?

Failure
Found: 3375715115287449357506276695064ā€¦726014538258316337554755849302820688331524472512613578509997274
Expected: Nothing

My complete answer is ā€“
337571511528744935750627669506434248838060777255175561517910550780489905968124804562017354099174540336233599275767389009210547173333585270616695653031256733448728248255814658743274199733546547200929609258125133961382810722609225060931306661232015028185829053411607083130319808125013980911296374139939995694487720361335354009565632785551307253894009225188372943476261394613761332350053033862682544035976935437069175106904747221053997560780850398839559532570832402246987519140784907596916473540026727391887623344830748713701583693744640548995316198606772450647037362379871564404676147603823621817950447438749562574141967581742006067273505837938190967560305589910219367443065406884717487785297753203972355344791144609965850943893242914859682393583584237322257184059663888812648548161431523982244138189896876883838976859461836139273820266685132374047250047121319162282893506703805687463113881379834142982384933932956414272690604011859991068147260145382583163375547558493028206883315244725126135785099972748669810043228877657663817767007759059673835807071710260295225051495081120729539947185334438627246041122667578392885315441329242351579019799239611055127698776683811905726439448929400393492686072835975978331556420635681244311113778971903479219109204447752778760042970242690943088701054676733157964040374336380419946433197070597298525507419501582576927444773621069687613286374537763104395277366568727213888805305810728487448084490632468988788496928630068553319359005645356304547857608238105940006848219663045336405018805179712537119668639265938806139450551999054636425798500526622526220491394577665076161901065684538266031322751316909847595225741319522414421179486500114827894975354850999368425817062207498844223293227280868725129997893905372462734008320411481712411195021006219098977499531357504317571028655312072252551058508879741689810441385421373554638923818839923125315896225002615611698035617113627112683735816107892142388061674782251362407209266175573780371723893107276641826897592603034223054799026055306145489818335217023566454165323029695739174171336693785975950910220503129192740729334212461345005567846770853631274013283361138305068228856539134607180053427642992350255097543776456719057191335032877798382102920778332366953160032058488693593265163269693125758664320129420626574825205032528024316700339678813094963624707816987543732101089848875293249704648824902172175105762173717785901496508267931795529158519507925230840407485316788664260758361372335077899982705418252344896520000

OneWay City puzzle
#3

RTFMā€¦

ā€œActually, the numbers can get so big that your programā€™s output should only contain the first 1000 digits of the solution.ā€

So your answer is correct but you write just too much things, but i agree that this ā€œexpected: nothingā€ is annoying sometimes

#4

Thanks Frankich - my bad - let me try and find the manual now.
:+1:

#5

[Edited] it works fine with 1000 limit!

#6

I think there is an error in the description where it says (M) is the number of west-east roads and (N) is the number of north-south roads. Is it the number of roads? Or the number of buildings in that dimension of the grid? (M) west-east buildings is (M - 1) west-east roads.

The first test case is 4 x 4 with an expected result of 20 and, from what I can tell, 20 routes happens in a grid with 4 west-east buildings and 4 north-south buildings, not roads.

Either way, Iā€™m having trouble figuring out the formula for this one. Any hints would be appreciated.

#7

Update: I figured out the solution but I still think the description is incorrect.

#8

So the minimum would be 2 roads east-west and two roads north-south. I think of that visually as a square - and there are two routes - either east or south. The example of 4x4 is a grid that is 4 lines across and 4 lines down (so, I think thatā€™s like the 3x3 buildings concept you mention). I started by drawing it out and starting from the base case and building it up from there and thatā€™s how I found the pattern I needed.

#9

Oops - didnā€™t see you update when I replied :slight_smile:

#10

Ohhhh ok. I was thinking ā€œroadsā€ as in a grid dimension where a path between two buildings is one road. I see what they mean now.

I still think ā€œbuildingsā€ is more accurate. Look at the 2nd test case of 7 by 1. There are not 7 north-south roads, there are zero.

#11

I think it was 7 west-east roads and 1 north-south (doesnā€™t really matter though - itā€™s the same logic)

This quick attempt at a diagram might look like six different west to east roads - but itā€™s supposed to represent one long road. It could also be along the top instead of the bottom.

Thereā€™s only one route from the top left to the bottom right.

|||||||

I agree that the first paragraph of explanation isnā€™t as clear as it could be.

#12

Yeah youā€™re right it doesnā€™t matter which dimension is which, but letā€™s just say the 7x1 city is represented how the puzzle says, the diagram would be rotated vertically, with 7 roads going east-west, and one long road going north-south, which is essentially zero east-west roads, because what are the roads connecting? Nothing.

7 x 1 buildings on the other hand would be accurate. Iā€™m being way too particular here, I know, lol

#13

OK - I see what youā€™re saying.
Iā€™m reading it differently, so Iā€™ll change the scale to explain myself.
Imagine that thereā€™s more than one building per road and itā€™s a big city/town.
Iā€™ll represent each building with an X. And for the roads, Iā€™ll use a line of Rā€™s.
And Iā€™ll just do it for a 3x1 (so the diagram isnā€™t huge).

X X X X X X X X X X
X RRRRRRRRRRR X
X R X X X X X X X X
X R X
X R X X X X X X X X
X RRRRRRRRRRR X
X R X X X X X X X X
X R X
X R X X X X X X X X
X RRRRRRRRRRR X
X X X X X X X X X X

Now, to get from the building in the top left to the building in the bottom right - thereā€™s only one route.
Note, according to the rules, the roads are one-way, so on this example you can get from the ā€˜main roadā€™ to any of the buildings, but you canā€™t get from the dead end of the one-way roads back to the main road.

#14

Ok now you lost me. The first line of the puzzle is, ā€œYour city is a rectangular grid of buildings with streets joining them vertically and horizontally.ā€ That diagram is definitely not that.

1 Like
#15

Youā€™re totally right. Sorry if Iā€™ve confused you. I canā€™t seem to explain now how I made sense of it and came to the right solution so quickly. I guess I just abstracted it to a path problem and didnā€™t think about the buildings at all.

1 Like
#16

I am having a problem with OneWay City by Anst. I am able to get the first few test to pass but it fails on Conurbation and Megalopolis.

For Conurbation
I get
1400749509083708812240837853009143626989568
and it should be
1400749509083708812152608657850239525991600

Was anyone able to solve this problem correctly?

#17

Yes, I solved it.

#18

Itā€™s very strange. At first I thought about overflow but in this case problem should have been with high digits.
My solution correctly pass all tests but in Megalopolis test it exceeds time limit and I have no idea how to improve the performance.

#19

I did it! ))

1 Like
#20

Here is the beef of my code where I think I am having problems.
if (i > 0)
arr[i][j + 1] = arr[i][j] + arr[i - 1][j + 1];
// does the math for the next cell to the right by adding the current cell and the one on the top to the right of the current cell

I have two for loops that go through and create the outer rims so like for the 4x4 square the loop already has the ones when doing the if statement above.
1111
1
1
1