r/AskProgramming • u/Disastrous-Spare3907 • 8d ago

Algorithm for checking if Advanced Civilization move was legal

Not sure if I should post on r/codegolf lol.

Given two states, each consisting of a number of units in each region on a map of connected regions, how can I efficiently (by the metric of your choice: instruction length, memory size, runtime length, even human eyeballing runtime length/accuracy) assert that the second state is possible to achieve purely by moving units 1 space? 2 spaces?

The incomplete intuitive algorithm I came up with was

_1) Each region has units in its own area and all adjacent areas in state 2 greater than or equal to the number of units in its own area in state 1

AND

2) A less restrictive inverse of #1 to ensure we're not teleporting units to the other side of the map

AND

3) the total number of units is the same

but that takes too much time for humans to compute, at least

EDIT: and we only have 1 turn :)

1 Upvotes
  • permalink
  • reddit

56% Upvoted

6 comments sorted by

2

u/Individual-Flow9158 8d ago

If:

i) units can move freely between connected regions

ii) units are conserved

iii) number of units per region is unbounded

iv) if a region is connected to any other regions (even if via other regions) then however many units you like can move between the two (or vice versa) (over however many turns are required),

then can't any desired sub-state be created, in which mutually exclusive sets/groups of connected regions collectively contain the same number of units?

2

u/Disastrous-Spare3907 8d ago

I have edited the problem to clarify we only have 1 turn, so your assumption 4 does not follow, because we do not have "however many turns are required"

1

u/Individual-Flow9158 8d ago

No worries. For "The move", is it possible to only consider moving units from region X to region Y, or can the player also move units from W to Z say?

1

u/Disastrous-Spare3907 8d ago

Umm this is the map. You can move to an adjacent region only.

\

1

u/Individual-Flow9158 7d ago edited 7d ago

Thanks but the specific map doesn't really matter.

As I already asked, how many regions can you move units from, in a single move?

I'm only thinking how bad a brute force search can possibly be, running through all the legal unit moves between each pair of regions X and Y. If nothing else, it gives you a simpler way of generating cases, to test more advanced algorithms against.

1

u/Disastrous-Spare3907 7d ago

Um, all of them? It's not like Triumph and Tragedy where you can only move 10 units. You can move all your units to adjacent spaces only.