|
![[logo]](http://repo.hu/projects/ch24retro/logo.svg){kind=logo}
|
Blog
Loopz (2011/pre-EC/S): generator
| loopz_gen by Tibor 'Igor2' Palinkas on 2020-02-13 | Tags: 2011, preec, 2011preec, generator |
Abstract: n/a
Datasheet
| Task | Loopz |
|---|---|
| When | 2011 preec S |
| Description | html |
| Input pack | zip |
Generator
Loopz was a 2011 pre-EC task S. It was a backtracking task.
This task was one of the rare cases where writing the input generator was the hardest part. The idea seemed simple:
- generate a closed loop of single-cell pipes filling up the n*m matrix
- split it up into longer sections
The first part is non-trivial. After some research Mate Nagy came up with the idea to invert the problem: generate the "walls between the pipes". The actual piping could be generated by tracing the inner side of the walls drawn with # on the above debug output. This is done by a small python script that emitted a matrix of single-cell pipes.
Next a C program called split loaded the matrix, started to walk the pipe and broke it up to longer segments randomly. The reference solver shared draw_text.[ch] and pipes.[ch] with this generator.
Since the input is the result of a split-up of a valid solution, each input has at least one solution. If segments are longer, it is likely to be the only valid solution, nevertheless with backtracking one should be able to find it.
The generator is Copyright (C) 2011 Mate Nagy and Tibor 'Igor2' Palinkas and is licensed under the GNU GPL version 2.