There is no Spoon - Episode 2 puzzle discussion

Puzzles
#61

Can you use linear solver with python ?
It’s true the problem really look like a flow problem from linear programming …

#62

I am not a professional developer (I am analithis, I interested in algorithms). I am solving puzzles on CodingGame for fun. I have wrote a Class on javascript for solving Linear Programming task. Rewrite it to Python… For what?
Linear Programming really has a problems. I just solved the Ticket to Ride puzzle as Linear Programming task and can not pass tests 18 and 19, due to some problems (algorithmic? technical?). The main problem is there is no one to discuss to, I am investigating the problem alone.

1 Like
#63

Hi,

I’m stuck on tests “Expert” and “CG” because the input() function never retrieves the last line.
It just hangs on, waiting.
Yet the code is fairly simple:

width = int(input()) # the number of cells on the X axis
height = int(input()) # the number of cells on the Y axis
grid = list()
for y in range(height):
…line = input()
…grid.append(line)

Anybody experiencing the same issue ?

#64

All tests pass in the dev mode but three fails in the submission mode, really frustrating!

#65

Just did this one, it was a bit challenging in Python.

First I just did a brutal backtracking, could just solve the easy testcases with it.

So I added a first step where I fill all edges that can be filled with logic.
With this additionnal step i could solve all testcases but the last validator failed.

So I tried different ways to sort the vertices before the backtracking step and checked the differences in time.
It appeared that not sorting at all was 3 times faster than my initial sort (sort by degree, ascending).

And it was enough to pass that last validator.

But it felt like the margin to pass this last validator was quite tight.

#66

If you are struggling with CG test/validator like I did try these 3 things:

  1. do not expand your search if you are looking at 1 1 or 2-2 part of graph (unconnected ones and 1 connection between twos) + check “back to basics” test as well since this is required connection if there are only 2 nodes
  2. sort your search space by distance between nodes you are about to connect - it is much more likely that closer nodes should be connected
1 Like
#67

If anyone is interested in actually playing this game as a puzzle, it’s included in Simon Tatham’s portable puzzle collection under the name “Bridges”. (Open source under an MIT-style license if you want to look at code.)
Start here: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

PS: Tatham is better known as the author of the widely-used Putty program.
PPS: Not spam…nobody’s making a peso off of this. :^)

2 Likes
#68

This collection is packaged for Debian, runs in Windows and has a package for Android.

#69

My program passes all the dev tests, but it fail in the 6th validator when i submit it.
i tried a lot but can’t figure it out. can any one provide me the data of the 6th validator please? admin perhapes?

#70

You have the replay, so you have the configuration, haven’t you?
https://www.codingame.com/replay/581118685

#71

Excact! didn’t see that in my small screen. thanks.

#72

I was happy when my C++ program finally passed 100% tests! The most complicated one (the CG) took 0.2 sec. on my machine and ~750 recursive iterations…

But then I tried this “moderately difficult” puzzle from Wikipedia: Hashiwokakero - Wikipedia

13
13
2.4.3.1.2..1.
.........3..1
....2.3.2....
2.3..2...3.1.
....2.5.3.4..
1.5..2.1...2.
......2.2.4.2
..4.4..3...3.
.............
2.2.3...3.2.3
.....2.4.4.3.
..1.2........
3....3.1.2..2

It’s still running for a few hours… Must be taking billions of recursions (it was millions when I’ve interrupted it after a few minutes).

Can anyone try to solve the test above? :slight_smile:

UPD: it passes on most others’ solutions. Which means something is wrong with mine… :frowning:

#73

Continuing the discussion from There is no Spoon - Episode 2 puzzle discussion:

Wow, currently the hardest I’ve solved here, 100% sure my solution is not best (I see ways even to optimize mine, but I’m lazy, it’s 100% score anyway).
Loved this!

#74

I really wanted to solve this one with a linear programming approach. It seemed like an interesting challenge. It took me about 8 hours, but I couldn’t figure out the proper constraints to avoid crossings and disconnected graphs, so when the solution is invalid I do a reiteration adding those errors as inequality constraints to avoid in the next. It’s not as robust as I wanted and required some workarounds to pass all validators, but it worked.

By the way, the scipy and numpy versions on the languages page are a little outdated. I spent a lot of those 8 hours trying to get scipy.optimize.linprog to work properly for an integer problem because the 1.6.3 version doesn’t have the integrality parameter, but it turned out the current scipy version here is 1.9.3, not 1.6.3 as documented on that page.

#75

Hello man, can u send me your solution?

#76

Please don’t ask for others’ completed solution codes on this forum.