Rosetta Code

Railway circuit: Difference between revisions

Page Discussion

Railway circuit (view source)

Revision as of 15:03, 8 April 2016

1,747 bytes added ,  8 years ago
→‎{{header|Java}}: added support for straight tracks
m (→‎{{header|Java}}: they're permutations actually)
(→‎{{header|Java}}: added support for straight tracks)
Line 173:
 
public class RailwayCircuit {
final static int LEFT = 1, RIGHT = -1, STRAIGHT = 0;
 
static String normalize(int[] tracks) {
char[] a = new char[tracks.length];
for (int i = 0; i < a.length; i++)
a[i] = "abc".charAt(tracks[i] ==+ 1 ? 'a' : 'b');
 
/* Rotate the array and find the lexicographically lowest order
Line 196 ⟶ 197:
}
 
static boolean fullCirclefullCircleStraight(int[] tracks, int nStraight) {
if (nStraight == 0)
return true;
 
// do we have the requested number of straight tracks
if (stream(tracks).filter(i -> i == STRAIGHT).count() != nStraight)
return false;
 
// check symmetry of straight tracks: i and i + 6, i and i + 4
int[] straight = new int[12];
for (int i = 0, idx = 0; i < tracks.length && idx >= 0; i++) {
if (tracks[i] == STRAIGHT)
straight[idx % 12]++;
idx += tracks[i];
}
 
return !(range(0, 6).anyMatch(i -> straight[i] != straight[i + 6])
&& range(0, 8).anyMatch(i -> straight[i] != straight[i + 4]));
}
 
static boolean fullCircleLeft(int[] tracks) {
 
// all tracks need to add up to a multiple of 360
Line 205 ⟶ 226:
int[] rTurns = new int[12];
for (int i = 0, idx = 0; i < tracks.length && idx >= 0; i++) {
if (tracks[i] == 1LEFT)
rTurns[idx % 12]++;
idx += tracks[i];
Line 214 ⟶ 235:
}
 
static void circuits(int numTracksnCurved, int nStraight) {
Map<String, int[]> solutions = new HashMap<>();
 
PermutationsGen gen = new PermutationsGengetPermutationsGen(numTracksnCurved, nStraight);
while (gen.hasNext()) {
 
int[] tracks = gen.next();
 
if (!fullCirclefullCircleStraight(tracks, nStraight))
continue;
 
if (!fullCircleLeft(tracks))
continue;
 
solutions.put(normalize(tracks), tracks.clone());
}
report(solutions, numTracksnCurved, nStraight);
}
 
static PermutationsGen getPermutationsGen(int nCurved, int nStraight) {
assert (nCurved + nStraight - 12) % 4 == 0 : "input must be 12 + k * 4";
 
int[] trackTypes = new int[]{LEFT, RIGHT};
 
if (nStraight != 0) {
if (nCurved == 12)
trackTypes = new int[]{LEFT, STRAIGHT};
else
trackTypes = new int[]{LEFT, RIGHT, STRAIGHT};
}
 
return new PermutationsGen(nCurved + nStraight, trackTypes);
}
 
static void report(Map<String, int[]> solutionssol, int numTracksnumC, int numS) {
 
int size = solutionssol.size();
System.out.printf("%n%d solution(s) for C%d,%d %n", size, numTracksnumC, numS);
 
if (size < 10)
solutionssol.values().stream().forEach(tracks -> {
stream(tracks).forEach(i -> System.out.printf("%2d ", i));
System.out.println();
Line 243 ⟶ 282:
 
public static void main(String[] args) {
circuits(12, 0);
circuits(16, 0);
circuits(20, 0);
circuits(24, 0);
circuits(12, 4);
}
}
Line 253 ⟶ 293:
// not thread safe
private int[] indices;
private int[] permutationschoices;
private int[] sequence;
private int carry;
 
PermutationsGen(int numPositions, int[] choices) {
indices = new int[numPositions];
permutationssequence = new int[numPositions];
this.choices = choices;
}
 
Line 270 ⟶ 312:
carry = 0;
 
if (indices[i] == 2choices.length) {
carry = 1;
indices[i] = 0;
Line 277 ⟶ 319:
 
for (int i = 0; i < indices.length; i++)
permutationssequence[i] = choices[indices[i] == 0 ? 1 : -1];
 
return permutationssequence;
}
 
Line 286 ⟶ 328:
}
}</lang>
<pre>1 solution(s) for C12,0
1 1 1 1 1 1 1 1 1 1 1 1
 
1 solution(s) for C16,0
1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 -1
 
6 solution(s) for C20,0
1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 -1 1 1 -1
1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 -1 1 -1
1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 1 -1 -1
1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 -1 -1 ▼
1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1 1 1 1 -1
1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1
▲ 1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 -1 -1
 
40 solution(s) for C24,0
(35 solutions listed on talk page, plus 5)
1 1 1 -1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 -1 1 1 1
Line 307 ⟶ 349:
1 1 1 -1 -1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 -1 -1 1 1 1
1 1 -1 1 -1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 -1 1 -1 1 1 1
 
4 solution(s) for C12,4
1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0
1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0
1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0
1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0
</pre>
 
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/263315"