Skip to content

Instantly share code, notes, and snippets.

@Xevion

Xevion/Doubled.java

Created April 29, 2021 19:04
Show Gist options
  • Save Xevion/d8ad0913ddfcd7a459541a8ef6d2423f to your computer and use it in GitHub Desktop.
Save Xevion/d8ad0913ddfcd7a459541a8ef6d2423f to your computer and use it in GitHub Desktop.
Download ZIP
Raw
Doubled.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;
class StackerPosition {
int x;
int y;
Character type;
StackerPosition(int x, int y) {
this(x, y, null);
}
StackerPosition(int x, int y, Character type) {
this.x = x;
this.y = y;
this.type = type;
}
public StackerPosition inverse() {
return new StackerPosition(-x, -y, type);
}
public StackerPosition add(StackerPosition other) {
return new StackerPosition(this.x + other.x, this.y + other.y);
}
public StackerPosition subtract(StackerPosition other) {
return new StackerPosition(this.x - other.x, this.y - other.y);
}
}
class Connectable {
char commonType;
List<StackerPosition> positions;
List<StackerPosition> filled;
List<StackerPosition> unfilled;
Connectable(List<StackerPosition> positions) {
}
}
class Stacker {
private final char[][] grid = new char[6][];
public static final char NONE = '.';
public static final char BLACK = 'B';
public static final char RED = 'R';
public static final StackerPosition[] directions = new StackerPosition[]{
new StackerPosition(1, 0),
new StackerPosition(0, 1),
new StackerPosition(1, 1),
new StackerPosition(1, -1)
};
public List<StackerPosition> getOpenSlots() {
List<StackerPosition> open = new ArrayList<>();
// Search from left to right
for (int c = 0; c < 7; c++) {
// Search from bottom to top
for (int r = 5; r >= 0; r--) {
// If open, it's open to air all the way up
if (grid[r][c] == NONE) {
open.add(new StackerPosition(c, r));
break;
}
}
}
return open;
}
public List<Connectable> findConnectables(char type) {
// Iterate along each checker position in the grid
for (int r = 0; r < 6; r++) {
for (int c = 0; c < 7; c++) {
// If the checker is of the type we want
if (grid[r][c] == type) {
StackerPosition position = new StackerPosition(c, r);
// Check each direction if it has three checkers in a row
for (StackerPosition direction : directions) {
List<StackerPosition> checkQueue = new LinkedList<>();
checkQueue.add(position.add(direction));
checkQueue.add(position.subtract(direction));
// Check if the base triple has been formed
boolean triple = validateAll(checkQueue, type);
if (!triple) continue;
// Check if right side node is free
StackerPosition frontEnd = position.add(direction).add(direction);
if (valid(frontEnd) && getType(frontEnd) == NONE) {
}
// Check if left side node is free
StackerPosition backEnd = position.subtract(direction).subtract(direction);
if (valid(backEnd) && getType(backEnd) == NONE) {
}
}
}
}
}
}
/**
* @param positions A list of StackerPosition objects
* @return True if all positions are valid and of the same type.
*/
private boolean validateAll(List<StackerPosition> positions)
{
StackerPosition first = positions.get(0);
if (valid(first))
return validateAll(positions, getType(first));
return false;
}
/**
* @param positions A list of StackerPosition objects
* @param type The type of checker that all StackerPosition objects must be
* @return True if all positions are valid and of the same type as requested.
*/
private boolean validateAll(List<StackerPosition> positions, char type)
{
for (StackerPosition next : positions) {
if (!valid(next) || getType(next) != type)
return false;
}
return true;
}
/**
* @return Returns true if the given position is valid within the grid.
*/
private boolean valid(StackerPosition forwards)
{
return forwards.x >= 0 && forwards.x < 7 && forwards.y >= 0 && forwards.y < 6;
}
/**
* @return Returns the checker type (char) at the given position in the grid
*/
private char getType(StackerPosition position)
{
return grid[position.y][position.x];
}
public void setRow(int r, char[] row)
{
grid[r] = row;
}
@Override
public String toString()
{
StringBuilder sb = new StringBuilder();
for (int r = 0; r < 6; r++) {
sb.append(String.valueOf(grid[r]));
sb.append("\n");
}
return sb.toString();
}
}
public class Doubled
{
public static void main(String[] args) throws FileNotFoundException
{
Scanner scanner = new Scanner(new File("doubled.dat"));
int inputs = scanner.nextInt();
scanner.nextLine();
for (int i = 0; i < inputs; i++) {
Stacker stacker = new Stacker();
char player = scanner.nextLine().charAt(0);
for (int r = 0; r < 6; r++) {
char[] row = scanner.nextLine().toCharArray();
stacker.setRow(r, row);
}
System.out.println(stacker);
System.out.println(stacker.findConnectables());
}
}
}
Raw
Memory.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;
/**
* Simple tuple class for storing pairs of Cards.
*/
class CardPair
{
Card a;
Card b;
boolean marked = false;
CardPair(Card a, Card b)
{
this.a = a;
this.b = b;
}
public boolean bothVisible()
{
return a.visible && b.visible;
}
}
class Card
{
public Card other; // Two-way reference to the other card.
int x; // Column
int y; // Row
int z; // Depth/Level
char value; // The actual a-Z letter of the card.
CardPair pair; // Reference to the CardPair containing both
boolean visible = false; // Whether or not the Card is considered visible
Card(char value, int x, int y, int z)
{
this.value = value;
this.x = x;
this.y = y;
this.z = z;
}
@Override
public String toString()
{
return String.format("Card{%s, x=%d, y=%d, z=%d, %s}", value, x, y, z, visible ? "Visible" : "Not Visible");
}
@Override
public boolean equals(Object o)
{
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Card card = (Card) o;
return x == card.x &&
y == card.y &&
z == card.z;
}
@Override
public int hashCode()
{
return Objects.hash(x, y, z);
}
}
class MemoryStructure
{
private final char[][][] charStructure;
private final Card[][][] cardStack;
public int width;
public int height;
public int depth;
private final HashMap<Character, CardPair> pairs;
public final Queue<Card> revealed; // A queue containing all newly
MemoryStructure(int width, int height, int depth)
{
this.width = width;
this.height = height;
this.depth = depth;
charStructure = new char[width][height][depth];
cardStack = new Card[width][height][depth];
pairs = new HashMap<>();
revealed = new LinkedList<>();
}
public CardPair getPair(char value)
{
return pairs.get(value);
}
public char getValue(int row, int column, int level)
{
return this.charStructure[column][row][level];
}
public Card getCard(int row, int column, int level)
{
return this.cardStack[column][row][level];
}
/**
* @param card The card you want to place into the structure.
*/
public void putCard(Card card)
{
if (card == null) return;
this.charStructure[card.x][card.y][card.z] = card.value;
this.cardStack[card.x][card.y][card.z] = card;
}
/**
* @param row The row (Y-coordinate)
* @param column The column (X-coordinate)
* @return The full vertical column of characters from top to bottom of the structure at a specific coordinate.
*/
public Card[] getVertical(int row, int column)
{
Card[] vertical = new Card[depth];
for (int z = 0; z < depth; z++)
vertical[z] = getCard(row, column, z);
return vertical;
}
/**
* @param row The row (Y-coordinate)
* @param column The column (X-coordinate)
* @param level The level/depth (Z-coordinate)
* @return A list of characters that are above the specific 3d coordinate
*/
public Card[] getAbove(int row, int column, int level)
{
Card[] above = new Card[level];
for (int z = 0; z < level; z++)
above[z] = getCard(row, column, z);
return above;
}
/**
* Prepare the Character/Pair map for use after values are set.
*/
public void prepareMap()
{
// Iterate through every position in structure
for (int x = 0; x < width; x++) {
for (int y = 0; y < height; y++) {
for (int z = 0; z < depth; z++) {
Card card = getCard(y, x, z);
if (pairs.containsKey(card.value)) {
// First part of pair has been found, add the other part
CardPair pair = pairs.get(card.value);
pair.b = card;
// Setup card references
pair.a.other = pair.b;
pair.b.other = pair.a;
pair.a.pair = pair;
pair.b.pair = pair;
} else {
// Never found before. Create new Pair instance and place first part in.
CardPair pair = new CardPair(card, null);
pairs.put(card.value, pair);
}
}
}
}
}
/**
* Adds all known visible cards by searching top down. Should only be ran once at the beginning (thus only
* searching to one depth, but could be used later on to go down to any depth necessary).
*/
public void setupVisible()
{
// Iterate only each XY coordinate in the grid
for (int x = 0; x < width; x++) {
for (int y = 0; y < height; y++) {
// Start moving down in depth until a non-marked card is found.
for (int z = 0; z < depth; z++) {
Card card = getCard(y, x, z);
CardPair cp = getPair(card);
// If on top of this column's stack
if (!cp.marked) {
card.visible = true;
revealed.add(card);
break;
}
}
}
}
}
private CardPair getPair(Card card)
{
return getPair(card.value);
}
@Override
public String toString()
{
return String.format("MemoryStructure{width=%d, height=%d, depth=%d}", width, height, depth);
}
/**
* Lifts a card off the stack by marking the one under a card as visible, and adding that one to the stack.
*
* @param card The card to 'lift' off the card stack, revealing the card beneath it.
*/
public void lift(Card card)
{
// Get the card beneath it
int newZ = card.z + 1;
// If there is going to be a card beneath
if (!(newZ > depth - 1)) {
Card under = getCard(card.y, card.x, newZ);
under.visible = true;
revealed.add(under);
}
}
public Set<Character> values()
{
return pairs.keySet();
}
}
public class Memory
{
public static void main(String[] args) throws FileNotFoundException
{
Scanner in = new Scanner(new File("memory.dat"));
int inputs = in.nextInt();
in.nextLine();
for (int i = 0; i < inputs; i++) {
MemoryStructure ms = new MemoryStructure(in.nextInt(), in.nextInt(), in.nextInt());
in.nextLine();
// Read in character inputs
for (int z = 0; z < ms.depth; z++) {
for (int y = 0; y < ms.height; y++) {
String line = in.nextLine();
for (int x = 0; x < ms.width; x++) {
Card card = new Card(line.charAt(x), y, x, z);
ms.putCard(card);
}
}
}
ms.prepareMap(); // Form all pairs in map
ms.setupVisible(); // Find initially visible cards
Set<Character> unseen = ms.values();
// Keep searching and unlocking card pairs
while (ms.revealed.size() > 0) {
Card next = ms.revealed.poll();
// Skip Cards that may have been marked by it's sibling while inside the queue
if (next.pair.marked)
continue;
// If both cards in the pair are visible
if (next.pair.bothVisible()) {
// Mark the pair
next.pair.marked = true;
// Remember that we've seen this character
unseen.remove(next.value);
// Mark cards beneath as visible and add them to the Queue
ms.lift(next);
ms.lift(next.other);
}
}
System.out.println(unseen.size() == 0 ? "solvable" : "impossible");
}
}
}
Raw
Othello.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
class Point
{
int x;
int y;
Point(int x, int y)
{
this.x = x;
this.y = y;
}
Point()
{
this(0, 0);
}
public Point add(Point other)
{
return new Point(this.x + other.x, this.y + other.y);
}
public Point subtract(Point other)
{
return new Point(this.x - other.x, this.y - other.y);
}
public Point multiply(int magnitude)
{
return new Point(this.x * magnitude, this.y * magnitude);
}
public Point multiply(Point other)
{
return new Point(this.x * other.x, this.y * other.y);
}
}
class OthelloBoard
{
private final int[][] tiles = new int[8][8];
public static final Point[] directions = new Point[]{
new Point(0, 1), // Down
new Point(1, 0), // Right
new Point(-1, 0), // Left
new Point(0, -1), // Up
new Point(1, 1), // Down + Right
new Point(-1, 1), // Down + Left
new Point(-1, -1), // Up + Left
new Point(1, -1), // Up + Right
};
public static final int BLACK = -1;
public static final int EMPTY = 0;
public static final int WHITE = 1;
OthelloBoard()
{
}
/**
* @param data Input row data
* @param row The row number to modify.
*/
public void read(char[] data, int row)
{
for (int x = 0; x < 8; x++) {
char next = data[x];
tiles[row][x] = next == 'B' ? BLACK : (next == 'W' ? WHITE : EMPTY);
}
}
/**
* Places a tile and evaluates the result.
*
* @param x Column of placement
* @param y Row of placement
* @param white Whether or not the tile being placed is white.
* @return Returns true if any tiles were flipped in the placement of the new tile.
*/
public boolean place(int x, int y, boolean white)
{
final int SELF = white ? WHITE : BLACK; // The tile type we are placing.
final int OTHER = white ? BLACK : WHITE; // The tile type we will be trying to flip.
final Point start = new Point(x, y); // The point we start at.
ArrayList<Point> flipped = new ArrayList<Point>(); // Tiles that will be flipped after move is completed.
// Start moving as far as possible in each direction
for (Point direction : directions) {
ArrayList<Point> between = new ArrayList<Point>(); // The tiles we found in between the end point (if any)
Point current = start.add(direction);
// Move forward in each direction as long as the tile is the opposite tile type
while (getTile(current) == OTHER) {
between.add(current); // Another tile between the two end points
current = current.add(direction); // Move forward another in that direction
// If the current position is no longer valid, break
if (!isValid(current))
break;
}
// If the end positio n is valid and it's the same as our placing tile, we've found a valid area
if (isValid(current) && getTile(current) == SELF) {
flipped.addAll(between);
}
}
// Set tile down
tiles[y][x] = white ? WHITE : BLACK;
// Flip all tiles found
for (Point unflippedPoint : flipped)
flip(unflippedPoint);
return flipped.size() > 0;
}
private void flip(Point tile)
{
flip(tile.x, tile.y);
}
private void flip(int x, int y)
{
int current = tiles[y][x];
if (current == WHITE)
tiles[y][x] = BLACK;
else if (current == BLACK)
tiles[y][x] = WHITE;
}
private boolean isValid(Point point)
{
return isValid(point.x, point.y);
}
private boolean isValid(int x, int y)
{
return x >= 0 && y >= 0 && y < tiles.length && x < tiles[0].length;
}
public int getTile(Point point)
{
return getTile(point.x, point.y);
}
public int getTile(int x, int y)
{
return tiles[y][x];
}
@Override
public String toString()
{
StringBuilder sb = new StringBuilder();
for (int y = 0; y < tiles.length; y++) {
for (int x = 0; x < tiles[y].length; x++) {
switch (tiles[y][x]) {
case 0:
sb.append(".");
break;
case -1:
sb.append("B");
break;
case 1:
sb.append("W");
break;
}
}
if (y < tiles.length - 1)
sb.append("\n");
}
return sb.toString();
}
}
public class Othello
{
public static void main(String[] args) throws FileNotFoundException
{
Scanner in = new Scanner(new File("othello.dat"));
int inputs = in.nextInt();
in.nextLine();
for (int i = 0; i < inputs; i++) {
OthelloBoard board = new OthelloBoard();
for (int y = 0; y < 8; y++) {
board.read(in.nextLine().toCharArray(), y);
}
int row = in.nextInt();
int column = in.nextInt();
char move = in.next("[BW]").charAt(0);
in.nextLine();
boolean change = board.place(column, row, move == 'W');
System.out.println(change ? board : "Invalid Move");
System.out.println();
}
}
}
Raw
Roads.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;
interface Intersection
{
void register(int intersection, Node node);
Intersection[] vertices();
int getVertexCount();
List<Integer> getEdges();
}
/**
* One of the two intersection variations where one of the edges faces upwards.
*/
class UpIntersection implements Intersection
{
Node edgeUp; // via Edge C
Node edgeLeft; // via Edge A
Node edgeRight; // via Edge E
Intersection vertexDown; // edgeLeft.b || edgeRight.d
Intersection vertexLeft; // edgeLeft.f || edgeUp.d
Intersection vertexRight; // edgeRight.f || edgeUp.b
public void registerA(Node node)
{
assert node != null;
this.edgeLeft = node;
if (vertexDown == null) vertexDown = edgeLeft.b;
if (vertexLeft == null) vertexLeft = edgeLeft.f;
node.a = this;
}
public void registerC(Node node)
{
assert node != null;
this.edgeUp = node;
if (vertexLeft == null) vertexLeft = edgeUp.d;
if (vertexRight == null) vertexRight = edgeUp.b;
node.c = this;
}
public void registerE(Node node)
{
assert node != null;
this.edgeRight = node;
if (vertexDown == null) vertexDown = edgeRight.d;
if (vertexRight == null) vertexRight = edgeRight.f;
node.e = this;
}
@Override
public void register(int intersectionIndex, Node node)
{
switch (intersectionIndex % 6) {
case 0: // Intersection A
registerA(node);
break;
case 2: // Intersection C
registerC(node);
break;
case 4: // Intersection E
registerE(node);
break;
default:
throw new IllegalArgumentException(
String.format(Locale.ENGLISH, "Intersection index (%d) must be a positive even number.", intersectionIndex)
);
}
}
public Intersection[] vertices()
{
return new Intersection[]{vertexDown, vertexLeft, vertexRight};
}
@Override
public int getVertexCount()
{
int i = 0;
if (vertexRight != null) i++;
if (vertexLeft != null) i++;
if (vertexDown != null) i++;
return i;
}
@Override
public List<Integer> getEdges()
{
LinkedList<Integer> edges = new LinkedList<>();
if (edgeLeft != null) edges.offer(edgeLeft.id);
if (edgeRight != null) edges.offer(edgeRight.id);
if (edgeUp != null) edges.offer(edgeUp.id);
Collections.sort(edges);
return edges;
}
@Override
public String toString()
{
return String.format("UpIntersection{%d, %d, %d}", edgeUp != null ? edgeUp.id : null,
edgeLeft != null ? edgeLeft.id : null,
edgeRight != null ? edgeRight.id : null);
}
@Override
public boolean equals(Object o)
{
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
UpIntersection that = (UpIntersection) o;
return Objects.equals(edgeUp, that.edgeUp) &&
Objects.equals(edgeLeft, that.edgeLeft) &&
Objects.equals(edgeRight, that.edgeRight);
}
@Override
public int hashCode()
{
return Objects.hash(edgeUp, edgeLeft, edgeRight);
}
}
/**
* One of the two intersection variations where one of the edges faces downwards.
*/
class DownIntersection implements Intersection
{
Node edgeDown; // via Edge F
Node edgeLeft; // via Edge B
Node edgeRight; // via Edge D
Intersection vertexUp; // edgeLeft.b || edgeRight.e
Intersection vertexLeft; // edgeLeft.c || edgeDown.e
Intersection vertexRight; // edgeRight.c || edgeDown.a
public void registerB(Node node)
{
assert node != null;
this.edgeLeft = node;
if (vertexUp == null) vertexUp = edgeLeft.a;
if (vertexLeft == null) vertexLeft = edgeLeft.c;
node.b = this;
}
public void registerD(Node node)
{
assert node != null;
this.edgeRight = node;
if (vertexUp == null) vertexUp = edgeRight.e;
if (vertexRight == null) vertexRight = edgeRight.c;
node.d = this;
}
public void registerF(Node node)
{
assert node != null;
this.edgeDown = node;
if (vertexLeft == null) vertexLeft = edgeDown.e;
if (vertexRight == null) vertexRight = edgeDown.a;
node.f = this;
}
@Override
public void register(int intersectionIndex, Node node)
{
switch (intersectionIndex % 6) {
case 1: // Intersection B
registerB(node);
break;
case 3: // Intersection D
registerD(node);
break;
case 5: // Intersection F
registerF(node);
break;
default:
throw new IllegalArgumentException(
String.format(Locale.ENGLISH, "Intersection index (%d) must be a positive odd number.", intersectionIndex)
);
}
}
public Intersection[] vertices()
{
return new Intersection[]{vertexUp, vertexLeft, vertexRight};
}
@Override
public int getVertexCount()
{
int i = 0;
if (vertexRight != null) i++;
if (vertexLeft != null) i++;
if (vertexUp != null) i++;
return i;
}
@Override
public List<Integer> getEdges()
{
LinkedList<Integer> edges = new LinkedList<>();
if (edgeLeft != null) edges.offer(edgeLeft.id);
if (edgeRight != null) edges.offer(edgeRight.id);
if (edgeDown != null) edges.offer(edgeDown.id);
Collections.sort(edges);
return edges;
}
@Override
public boolean equals(Object o)
{
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
DownIntersection that = (DownIntersection) o;
return Objects.equals(edgeDown, that.edgeDown) &&
Objects.equals(edgeLeft, that.edgeLeft) &&
Objects.equals(edgeRight, that.edgeRight);
}
@Override
public int hashCode()
{
return Objects.hash(edgeDown, edgeLeft, edgeRight);
}
@Override
public String toString()
{
return String.format("DownIntersection(%X, edges: [%d, %d, %d], vertices: [%X, %X, %X])",
this.hashCode(),
edgeDown != null ? edgeDown.id : null,
edgeLeft != null ? edgeLeft.id : null,
edgeRight != null ? edgeRight.id : null,
vertexLeft != null ? vertexLeft.hashCode() : null,
vertexRight != null ? vertexRight.hashCode() : null,
vertexUp != null ? vertexUp.hashCode() : null);
}
}
enum OffsetStyle
{
ODD_R,
EVEN_R,
ODD_Q,
EVEN_Q
}
class OffsetCoordinate
{
public int c;
public int r;
private final OffsetStyle style;
OffsetCoordinate()
{
this(0, 0);
}
OffsetCoordinate(int c, int r)
{
this(c, r, OffsetStyle.ODD_R);
}
OffsetCoordinate(int c, int r, OffsetStyle style)
{
this.c = c;
this.r = r;
this.style = style;
}
/**
* @return Cube coordinate conversion of these coordinates, accounting for offset style.
*/
public Cube toCube()
{
int x, y, z;
switch (style) {
case ODD_R:
x = c - (r - (r & 1)) / 2;
z = r;
break;
case EVEN_R:
x = c - (r + (r & 1)) / 2;
z = r;
break;
case ODD_Q:
x = c;
z = r - (c - (c & 1)) / 2;
break;
case EVEN_Q:
x = c;
z = r - (c + (c & 1)) / 2;
break;
default:
throw new IllegalStateException("Unexpected value: " + style);
}
y = -x - z;
return new Cube(x, y, z);
}
}
class Cube
{
public int x;
public int y;
public int z;
Cube()
{
this(0, 0, 0);
}
Cube(int x, int y, int z)
{
this.x = x;
this.y = y;
this.z = z;
}
public Cube add(Cube other)
{
return new Cube(x + other.x, y + other.y, z + other.z);
}
public Cube subtract(Cube other)
{
return new Cube(x - other.x, y - other.y, z - other.z);
}
public Cube multiply(Cube other)
{
return new Cube(x * other.x, y * other.y, z * other.z);
}
public Cube divide(Cube other)
{
return new Cube(x / other.x, y / other.y, z / other.z);
}
@Override
public String toString()
{
return String.format("Cube{x=%d, y=%d, z=%d}", x, y, z);
}
@Override
public boolean equals(Object o)
{
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Cube cube = (Cube) o;
return x == cube.x &&
y == cube.y &&
z == cube.z;
}
@Override
public int hashCode()
{
return Objects.hash(x, y, z);
}
}
class Node
{
private HexGraph parent;
public int id;
public int x;
public int y;
public int z;
public Cube cube;
private boolean sideReady = false;
private boolean intersectionReady = false;
// Sides along other Nodes
public Node[] sides;
public Node A;
public Node B;
public Node C;
public Node D;
public Node E;
public Node F;
// Intersections touching two other Nodes
public Intersection[] intersections;
public UpIntersection a;
public DownIntersection b;
public UpIntersection c;
public DownIntersection d;
public UpIntersection e;
public DownIntersection f;
private static final Cube[] offsets;
public final Cube[] neighbors;
static {
// A, B, C, D, E, F in that order
offsets = new Cube[]{
new Cube(+1, -1, 0), new Cube(+1, 0, -1), new Cube(0, +1, -1),
new Cube(-1, +1, 0), new Cube(-1, 0, +1), new Cube(0, -1, +1)
};
}
Node(int id, int c, int r)
{
this(id, new OffsetCoordinate(c, r));
}
Node(int id, OffsetCoordinate coordinates)
{
this(id, coordinates.toCube());
}
Node(int id, Cube cube)
{
this.id = id;
this.x = cube.x;
this.y = cube.y;
this.z = cube.z;
this.cube = cube;
// Generate all Node neighbor coordinates
int i = 0;
neighbors = new Cube[offsets.length];
for (Cube offset : offsets)
neighbors[i++] = cube.add(offset);
}
/**
* Initializes neighbor references.
*/
public void initSides(HexGraph parent)
{
// Remember the parent
this.parent = parent;
// Acquire all neighbors
A = parent.getNode(neighbors[0]);
B = parent.getNode(neighbors[1]);
C = parent.getNode(neighbors[2]);
D = parent.getNode(neighbors[3]);
E = parent.getNode(neighbors[4]);
F = parent.getNode(neighbors[5]);
sides = new Node[]{A, B, C, D, E, F};
sideReady = true;
// Recursively initialize all neighbors
for (Node neighbor : sides)
if (neighbor != null && !neighbor.sideReady)
neighbor.initSides(parent);
}
public void initIntersections()
{
if (sideReady) {
intersections = new Intersection[6];
boolean[] intersectionsReady = new boolean[6];
for (int i = 0; i < 6; i++) {
Node[] pertinentSides = new Node[]{getSide(i), getSide(i + 1)};
// For each of the other two nodes in the intersection
for (int j = 0; j < 2; j++) {
Node possible = pertinentSides[j];
// Check that the neighbor is available & it has already completed it's intersection math
if (possible != null && possible.intersectionReady) {
Intersection inter = possible.getIntersection(i + (2 * (j + 1)));
inter.register(i, this); // Register this node to the intersection
intersectionsReady[i] = true;
break;
}
}
// If neighbors had no Intersection, create our own
if (!intersectionsReady[i]) {
Intersection intersection;
// Alternate between Up and Down intersections on each edge
if (i % 2 == 0)
intersection = new UpIntersection();
else
intersection = new DownIntersection();
intersection.register(i, this); // Register ourselves
parent.intersections.add(intersection);
// Check the other two sides, register them to the intersection if valid sides
for (int j = 0; j < 2; j++) {
Node possible = pertinentSides[j];
if (possible != null && !possible.intersectionReady) {
int intersectionIndex = i + (2 * (j + 1));
intersection.register(intersectionIndex, possible);
}
}
}
intersections[i] = getIntersection(i);
}
intersectionReady = true;
for (Node neighbor : sides)
if (neighbor != null && !neighbor.intersectionReady)
neighbor.initIntersections();
} else {
throw new IllegalStateException("Must call initSide() before calling initIntersection().");
}
}
private Intersection getIntersection(int i)
{
switch (Math.abs(i) % 6) {
case 0:
return a;
case 1:
return b;
case 2:
return c;
case 3:
return d;
case 4:
return e;
case 5:
return f;
default:
return intersections[i % 6];
}
}
public Node getSide(int i)
{
return sides[i % neighbors.length];
}
@Override
public boolean equals(Object o)
{
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return id == node.id &&
x == node.x &&
y == node.y &&
z == node.z;
}
@Override
public int hashCode()
{
return Objects.hash(x, y, z);
}
@Override
public String toString()
{
ArrayList<Integer> edges = new ArrayList<>();
for (Node side : sides)
if (side != null)
edges.add(side.id);
return String.format("Node{id=%d, x=%d, y=%d, z=%d, neighbors=%s}", id, x, y, z, edges);
}
}
class HexGraph
{
public LinkedList<Intersection> intersections;
HashMap<Integer, Node> nodes; // HashCode -> Node
HashMap<Integer, Node> nodesByID; // Id -> Node
HexGraph(String data, int[] center)
{
String[] rows = data.split("\n");
nodes = new HashMap<>();
nodesByID = new HashMap<>();
int r = 0, c = 0;
for (String row : rows) {
String[] items = row.split(" ");
// Fill in the row with each item
for (String item : items) {
// Represent holes in this hexagon-shaped graph with null
if (!item.equals("-")) {
Node node = new Node(Integer.parseInt(item), c - center[0], r - center[1]);
putNode(node);
}
c++;
}
c = 0;
r++;
}
intersections = new LinkedList<>();
Node centerNode = getNode(0, 0, 0);
centerNode.initSides(this);
centerNode.initIntersections();
}
/**
* @param x Node X coordinate
* @param y Node Y coordinate
* @param z Node Z coordinate
* @return The Node with the coordinates placed into the HashMap
*/
public Node getNode(int x, int y, int z)
{
return nodes.get(Objects.hash(x, y, z));
}
/**
* @param node The node to put into the HashMap
*/
public void putNode(Node node)
{
nodes.put(node.hashCode(), node);
nodesByID.put(node.id, node);
}
@Override
public String toString()
{
return String.format(Locale.ENGLISH, "%d Nodes", nodes.size());
}
public Node getNode(Cube pos)
{
return getNode(pos.x, pos.y, pos.z);
}
public Intersection findIntersection(int a, int b, int c)
{
Set<Intersection> potentialA = new HashSet<>(Arrays.asList(nodesByID.get(a).intersections));
Set<Intersection> potentialB = new HashSet<>(Arrays.asList(nodesByID.get(b).intersections));
Set<Intersection> potentialC = new HashSet<>(Arrays.asList(nodesByID.get(c).intersections));
potentialA.retainAll(potentialB);
potentialA.retainAll(potentialC);
return (Intersection) potentialA.toArray()[0];
}
}
class Vertex implements Comparable<Vertex> {
int id; // Unique Hashcode ID
LinkedList<Vertex> adjacent; // All vertices this vertex touches
int distance = Integer.MAX_VALUE; // How far this node is from the source vertex (MAX_VALUE = Infinite)
boolean seen = false; // Whether or not the Node has been seen in the queue
List<Integer> parentIDs; // IDs of the corresponding Node edges
public Vertex touched; // The vertex this vertex was path'd by (LinkedList)
Vertex(Intersection truth) {
this.id = truth.hashCode();
this.parentIDs = truth.getEdges();
this.adjacent = new LinkedList<>();
}
@Override
public int compareTo(Vertex o)
{
return this.distance - o.distance;
}
public void addAdjacent(Vertex vertex)
{
adjacent.offer(vertex);
}
public Stack<Vertex> getTouchStack() {
Stack<Vertex> stack = new Stack<>();
Vertex current = this;
while (current.touched != null) {
stack.add(current);
current = current.touched;
}
return stack;
}
@Override
public String toString() {
return String.format("Vertex(%X, %b, distance: %d, vertices: %s, edges: %s, prev: %X)",
id ,
seen,
distance,
Arrays.toString(adjacent.stream().map(vertex -> String.format("%X", vertex.id)).toArray()),
parentIDs,
touched != null ? touched.id : null);
}
}
/**
* Manages a Dijkstra's Algorithm graph
*/
class Dijkstra
{
PriorityQueue<Vertex> queue;
HashMap<Intersection, Vertex> map;
Dijkstra(HexGraph hexGraph) {
queue = new PriorityQueue<>();
map = new HashMap<>();
// Create all Vertex objects
for (Intersection intersection : hexGraph.intersections)
map.put(intersection, new Vertex(intersection));
// Add all edges to Vertex objects
for (Map.Entry<Intersection, Vertex> pair : map.entrySet()) {
Vertex vertex = pair.getValue();
for (Intersection neighbor : pair.getKey().vertices())
if (neighbor != null) {
vertex.addAdjacent(map.get(neighbor));
}
}
}
public void generate(Intersection source) {
generate(source, null);
}
public void generate(Intersection source, Intersection destination) {
Vertex starter = map.get(source);
starter.distance = 0;
Vertex end = map.get(destination);
queue.offer(starter);
while (!queue.isEmpty()) {
Vertex extracted = queue.poll();
// Only start on unseen vertexes
if (!extracted.seen) {
extracted.seen = true;
if (end == extracted)
return;
// Iterate along all unseen adjacents
for (Vertex adjacent : extracted.adjacent) {
if (!adjacent.seen) {
int newKey = extracted.distance + 1;
if (newKey < adjacent.distance) {
adjacent.distance = newKey;
adjacent.touched = extracted;
queue.offer(adjacent);
}
}
}
}
}
}
}
public class Roads
{
// Simple input graph representing
public static final String data = "- 1 2 3 -\n4 5 6 7\n8 9 10 11 12\n13 14 15 16\n- 17 18 19 -";
public static final int[] center = new int[]{2, 2};
public static void main(String[] args) throws FileNotFoundException
{
HexGraph graph = new HexGraph(data, center);
Scanner scanner = new Scanner(new File("roads.dat"));
int inputs = scanner.nextInt();
for (int i = 0; i < inputs; i++) {
Dijkstra dijkstra = new Dijkstra(graph);
Intersection source = graph.findIntersection(scanner.nextInt(), scanner.nextInt(), scanner.nextInt());
Intersection destination = graph.findIntersection(scanner.nextInt(), scanner.nextInt(), scanner.nextInt());
dijkstra.generate(source, destination);
System.out.println(dijkstra.map.get(destination).distance);
}
}
public static void debugPrint(HexGraph graph) {
// Print every node, it's intersections, and those intersection's vertices.
for (Node node : graph.nodes.values()) {
System.out.printf("%s\n", node);
for (Intersection intersection : node.intersections)
if (intersection != null) {
System.out.println("\t" + intersection);
for (Intersection vertex : intersection.vertices())
System.out.println("\t\t" + vertex);
}
}
}
}
Raw
Rock.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Rock
{
public static final char ROCK = 'R';
public static final char PAPER = 'P';
public static final char SCISSORS = 'S';
public static void main(String[] args) throws FileNotFoundException
{
Scanner in = new Scanner(new File("rock.dat"));
int lines = in.nextInt();
in.nextLine();
for (int i = 0; i < lines; i++)
process(in.nextLine());
}
public static void process(String input)
{
int wins = 0, losses = 0, ties = 0;
char current = ROCK; // Always starts on Rock
for (char next : input.toCharArray()) {
// Get match result
int result = check(next, current);
// Increment win/loss/tie counnt
switch (result) {
case -1:
losses++;
break;
case 0:
ties++;
break;
case 1:
wins++;
current = chooseNext(next); // Opponent lost, strategy applied
break;
}
}
System.out.println(String.format("Wins: %d\nLosses: %d\nTies: %d\n", wins, losses, ties));
}
/**
* @param current The current RPS choice used
* @return The new RPS choice used by opponent
*/
public static char chooseNext(char current)
{
switch (current) {
case ROCK:
return PAPER;
case PAPER:
return SCISSORS;
case SCISSORS:
return ROCK;
}
return 0;
}
/**
* Calculate the result of a Rock, Paper, Scissors match.
*
* @param self The move used by yourself
* @param opponent The move used by your opponent
* @return A integer representing a loss (-1), tie (0), or win (1) for yourself.
*/
public static int check(char self, char opponent)
{
if (self == opponent)
return 0;
switch (self) {
// Rock beats Scissors, loses to Paper
case ROCK:
return opponent == SCISSORS ? 1 : -1;
// Paper beats Rock, loses to Scissors
case PAPER:
return opponent == ROCK ? 1 : -1;
// Scissors beats Paper, loses to Rock
case SCISSORS:
return opponent == PAPER ? 1 : -1;
}
return Integer.MAX_VALUE;
}
}
Raw
Tic.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
class TTCBoard
{
int[][] tiles = new int[3][3];
TTCBoard()
{
}
/**
* Places a move on the board.
*
* @param x The X position.
* @param y The Y position.
* @param player True for player X, False for player O
*/
public void move(int x, int y, boolean player)
{
tiles[y][x] = player ? 1 : 2;
}
/**
* @return Returns a integer representing the state of the board.
*/
public int check()
{
// Horizontals
for (int y = 0; y < 3; y++) {
int initial = tiles[y][0];
if (initial != 0 && initial == tiles[y][1] && initial == tiles[y][2])
return initial == 1 ? 1 : 2;
}
// Verticals
for (int x = 0; x < 3; x++) {
int initial = tiles[0][x];
if (initial != 0 && initial == tiles[1][x] && initial == tiles[2][x])
return initial == 1 ? 1 : 2;
}
int initialTLBR = tiles[0][0];
if (initialTLBR != 0 && initialTLBR == tiles[1][1] && initialTLBR == tiles[2][2])
return initialTLBR == 1 ? 1 : 2;
int initialTRBL = tiles[2][0];
if (initialTRBL != 0 && initialTRBL == tiles[1][1] && initialTRBL == tiles[1][2])
return initialTRBL == 1 ? 1 : 2;
// If any tiles are empty, game is incomplete
for (int y = 0; y < 3; y++) {
for (int x = 0; x < 3; x++) {
if (tiles[y][x] == 0)
return 4;
}
}
return 3;
}
@Override
public String toString()
{
StringBuilder sb = new StringBuilder();
for (int y = 0; y < 5; y++) {
if (y % 2 == 0) {
for (int x = 0; x < 5; x++) {
// Vertical line
if (x % 2 == 1) {
sb.append('|');
} else {
int place = tiles[y / 2][x / 2];
sb.append(getSymbol(place));
}
}
} else {
for (int i = 0; i < 5; i++)
// sb.append(i % 2 == 1 ? "+" : "-");
sb.append('-');
}
if (y < 4)
sb.append("\n");
}
return sb.toString();
}
public static String getSymbol(int place)
{
switch (place) {
case 1:
return "X";
case 2:
return "O";
default:
return " ";
}
}
public String translate(int check)
{
switch (check) {
case 1:
return "X wins!";
case 2:
return "Y wins!";
case 3:
return "Tie Game!";
case 4:
return "Incomplete";
default:
return "Invalid";
}
}
}
public class Tic
{
public static void main(String[] args) throws FileNotFoundException
{
Scanner in = new Scanner(new File("tic.dat"));
int sets = in.nextInt();
for (int i = 0; i < sets; i++) {
int moves = in.nextInt(); // Number of move inputs
TTCBoard board = new TTCBoard(); // Board which stores and manipulates state
boolean player = true; // Which player is going
// Scan in all moves and manipulate board state
for (int j = 0; j < moves; j++) {
// Get the position, make the move
int y = in.nextInt();
int x = in.nextInt();
board.move(x, y, player);
// Alternate current player
player = !player;
}
System.out.println(board);
System.out.println(board.translate(board.check()));
System.out.println();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment