저번에 초등학교 5학년 문제가 올라온 것을 보았는데, 이 것도 재미있습니다 ㅋㅋ
저는 유치원생 해야겠습니다…
우선 문제를 읽는다는게 놀랍군요.
초1이면 받아쓰기 하는거 아니었나?
우리집 유치원생은 맨날 놀기만 하는데 두렵군요
MS 코파일럿(빙챗)힌테 물어봤는데 다음과 같다고 합니다.
인공지능 마저 제대로 못 푸는 문제인가요…
5?
앗 문제가 재밌어서 그러는데 , 친구들 보여줘도 되나요 ?
커뮤니티 성격의 개방적인 모임은 아니고… 동네친구톡 같은 곳이에요.
초등학교 1학년 문제 수준은 분명히 아니고 초등학교 4학년은 되어야 풀 수 있어 보이는데요, 요즘 문제 수준이 장난이 아니네요
이게 현재 교육의 문제 아닐까 합니다.
수학이나 산수는 몰라도 없이도 풀 수 있는 문제이긴 한 데요.
국어의 독해력과 숫자에 대한 이해는 필요한 문제라는 거죠.
국민학교일때는 국민학교에서 기본적인 읽고 쓰기를 가르쳤는데.
지금은 그 정도는 하고 오라는 건데요… 물론 요즘 엔간하면 유치원은 간다지만
못가는 집도 아주 소수이나마 있을건데. 그건 전혀 고려하지 않고 있는거죠.
흠…
2 9 4 7 1 6 3 5 8
일까요?
그래서 정답은 5??
2 8 1 4 7 9 6 3 5 이것도 되는것 같긴한데… 높은 수니까 5가 맞는 것 같기도…
이거 정답이 제일 큰 수 찾는 거라 2 9 4 7 1 6 3 5 8 배열로 5가 정답입니다
@BigSquare 님이 제일 먼저 맞추신 것 같아요
저도 퍼온 거라…
이 문제를 코드로 풀면 어떨까요? 도전 고고~~
조건식의 확장성에 주안점을 두고 만들어 봤습니다. (수열 생성은 ChatGPT의 도움을 빌렸어요)
인터페이스/추상 클래스
// 수열에 대한 조건을 나타내는 인터페이스
public interface ISequenceCondition<T>
{
bool IsSatisfied(T[] sequence);
}
public abstract class RangeCondition<T>(T left, T right) : ISequenceCondition<T>
where T : IComparable<T>
{
protected readonly T _left = left;
protected readonly T _right = right;
public virtual bool IsSatisfied(T[] sequence)
{
if (sequence.Length < 2)
{
return false;
}
int leftIndex = Array.IndexOf(sequence, _left);
int rightIndex = Array.IndexOf(sequence, _right);
if (leftIndex == -1 || rightIndex == -1)
{
return false;
}
return IsSatisfiedInternal(sequence, leftIndex, rightIndex);
}
protected abstract bool IsSatisfiedInternal(T[] sequence, int leftIndex, int rightIndex);
}
조건식들
public class NonAdjacentDifferenceCondition<T> : ISequenceCondition<T>
where T : INumber<T>
{
private readonly T _difference;
public NonAdjacentDifferenceCondition(T difference)
{
_difference = difference;
}
public bool IsSatisfied(T[] sequence)
{
if (sequence.Length < 2)
{
return false;
}
for (int i = 1; i < sequence.Length; i++)
{
if (sequence[i] - sequence[i - 1] == _difference
|| sequence[i - 1] - sequence[i] == _difference)
{
return false;
}
}
return true;
}
}
public class RangeCountCondition<T> : RangeCondition<T>
where T : IComparable<T>
{
private readonly int _count;
public RangeCountCondition(T left, T right, int count) : base(left, right)
{
_count = count;
}
protected override bool IsSatisfiedInternal(T[] sequence, int leftIndex, int rightIndex)
{
return Math.Abs(leftIndex - rightIndex) - 1 == _count;
}
}
public class RangeSumCondition<T> : RangeCondition<T>
where T : INumber<T>
{
private readonly T _sum;
public RangeSumCondition(T left, T right, T sum) : base(left, right)
{
_sum = sum;
}
protected override bool IsSatisfiedInternal(T[] sequence, int leftIndex, int rightIndex)
{
if (Math.Abs(leftIndex - rightIndex) < 2)
{
return false;
}
if (leftIndex > rightIndex)
{
(leftIndex, rightIndex) = (rightIndex, leftIndex);
}
T sum = T.Zero;
foreach (var value in sequence.AsSpan(leftIndex + 1, rightIndex - leftIndex - 1))
{
sum += value;
}
return sum.CompareTo(_sum) == 0;
}
}
public class PositionCondition<T> : RangeCondition<T>
where T : IComparable<T>
{
public PositionCondition(T left, T right) : base(left, right)
{
}
protected override bool IsSatisfiedInternal(T[] sequence, int leftIndex, int rightIndex)
{
if (leftIndex > rightIndex)
{
return false;
}
return true;
}
}
public class RangeContainsCondition<T> : RangeCondition<T>
where T : IComparable<T>
{
private readonly T _value;
public RangeContainsCondition(T left, T right, T value) : base(left, right)
{
_value = value;
}
protected override bool IsSatisfiedInternal(T[] sequence, int leftIndex, int rightIndex)
{
if (leftIndex > rightIndex)
{
(leftIndex, rightIndex) = (rightIndex, leftIndex);
}
int index = Array.IndexOf(sequence, _value);
return index > leftIndex && index < rightIndex;
}
}
시퀀스 생성
internal class SequenceHelper
{
public static void GeneratePermutations(List<int> numbers, int start, List<List<int>> results)
{
if (start >= numbers.Count)
{
results.Add(new List<int>(numbers));
return;
}
for (int i = start; i < numbers.Count; i++)
{
(numbers[start], numbers[i]) = (numbers[i], numbers[start]);
GeneratePermutations(numbers, start + 1, results);
(numbers[start], numbers[i]) = (numbers[i], numbers[start]);
}
}
}
var original = Enumerable.Range(1, 9).ToList();
var sequences = new List<List<int>>();
SequenceHelper.GeneratePermutations(original, 0, sequences);
var conditions = new List<ISequenceCondition<int>>()
{
new NonAdjacentDifferenceCondition<int>(1),
new NonAdjacentDifferenceCondition<int>(4),
new RangeCountCondition<int>(left: 5, right: 6, count: 1),
new RangeCountCondition<int>(left: 4, right: 5, count: 4),
new RangeSumCondition<int>(left: 2, right: 4, sum: 9),
new PositionCondition<int>(left: 6, right: 5),
new RangeContainsCondition<int>(left: 4, right: 6, value: 7),
};
var max = sequences.Select(sequence => sequence.ToArray())
.Where(sequence => conditions.All(condition => condition.IsSatisfied(sequence)))
.Max(sequence => sequence[^2]);
Console.WriteLine(max);
// output: 5
성능에 주안점을 둔 방법도 보고 싶네요!
오옷! 일과 시간에 이렇게 빠르게 구현을 하실 수 있다니 정말 대단합니다!
294716853
294716358
829471635
281479635
963572814
635728149
초1에 이걸 다 구해서 최대값 5를 찾는다~.
- 감기로 쉬고 있는 동안 머리좀 써볼까 해봤습니다.
- 제PC에서 3.5초 정도 걸립니다.
[225432.4020] [SolverLogic] COMPLETED: Δt= 3498ms
[225432.4037] [App] Main(): max=5, set=2 9 4 7 1 6 8 5 3
소스코드: App.cs
using System.Collections.Concurrent;
using System.Diagnostics;
using ILogger = System.IProgress<(string cat, object msg)>;//logger
using MSG = (string cat, object msg);//log message type
internal class App : ILogger
{
/// <summary>
/// the Main
/// </summary>
static void Main(string[] args)
{
var solver = new SolverLogic(new App());
while(true)
{
report("Press any key start...(ESC to quit)");
var key = Console.ReadKey(true);
if (key.Key == ConsoleKey.Escape) break;
var result = solver.Solve().Result;
report($"max={result.set[^2]}, set={string.Join(' ', result.set)}");
}
}
#region ---- LOG 메소드 ----
/// <summary>
/// <see cref="ILogger"/> 구현: <inheritdoc/>
/// </summary>
void ILogger.Report(MSG value) => _progress.Report(value);
static void report(string msg, [CN] string caller = "") => report((nameof(App), $"{caller}(): {msg}"));
static void report(LogItem msg) => Console.WriteLine($"[{msg.time:HHmmss.ffff}] [{msg.cat}] {msg.msg}");
static readonly IProgress<LogItem> _progress = new Progress<LogItem>(report);
record LogItem(DateTime time, string cat, object msg)
{
public static implicit operator LogItem(MSG msg) => new(DateTime.Now, msg.cat, msg.msg);
}
#endregion
}
#region ---- ISolverLogic & 구현 ----
/// <summary>
/// SolverLogic 기능 정의
/// </summary>
public interface ISolverLogic
{
/// <summary>
/// 문제를 풀어서 결과를 리턴한다.
/// </summary>
Task<(int max, int[] set)> Solve();
}
/// <summary>
/// SolverLogic 구현 클래스
/// </summary>
public class SolverLogic(ILogger _reporter) : ISolverLogic, IComparer<int>
{
static int[] _masks = Enumerable.Range(0, 9).Reverse().Select(x => (int)Math.Pow(10, x)).ToArray();
void report(object msg) => _reporter.Report(("SolverLogic", $"{msg}"));
/// <summary>
/// <inheritdoc/>
/// + 문제의 조건 <see cref="C1"/> ~ <see cref="C7"/>을 만족하는 조합을 모두 찾고
/// + 찾은 조합 중 10의 자리가 최대인 조합과 10의 자리수를 리턴한다.
/// </summary>
public async Task<(int max, int[] set)> Solve()
{
report("STARTING");
var sw = Stopwatch.StartNew();
var range = doCalcRange();//9자리 후보 정수의 범위 설정
var space = doGenerateSpace(range);//유효 정수(조합) 추출
var max = doFindMax(space);//최대값 선택
sw.Stop();
report($"COMPLETED: Δt= {sw.ElapsedMilliseconds}ms");
await File.AppendAllTextAsync("space.txt", $"[{DateTime.Now:O}] Δt= {sw.ElapsedMilliseconds}ms\n");
await File.AppendAllTextAsync("space.txt", string.Join("\n", space));
var set = _masks.Select(m => max / m % 10).ToArray();
return (max, set);
}
/// <summary>
/// 9자리 후보 정수의 범위 설정
/// </summary>
(int start, int end, int length) doCalcRange()
{
try
{
report("entering...");
var v1 = 123_456_789;
var v2 = 987_654_321;
return (v1, v2, v2 - v1 + 1);
}
finally { report("exiting..."); }
}
/// <summary>
/// 유효 정수(조합) 추출
/// </summary>
ConcurrentBag<int> doGenerateSpace((int start, int end, int length) range)
{
try
{
report("entering...");
IInspector[] inspectors = [ new C1(_reporter), new C2(_reporter), new C3(_reporter),
new C4(_reporter), new C5(_reporter), new C6(_reporter), new C7(_reporter) ];
var space = new ConcurrentBag<int>();
Parallel.ForEach(
Enumerable.Range(range.start, range.length),
new() { MaxDegreeOfParallelism = Environment.ProcessorCount },
isOk);
return space;
void isOk(int v)
{
for (int i = 0; i < inspectors.Length; i++) if (!inspectors[i].Inspect(v)) return;
space.Add(v);
}
}
finally { report("exiting..."); }
}
/// <summary>
/// 테스트: <paramref name="value"/>에 대해 7가지 조건 검증결과 리턴
/// </summary>
internal (string name, bool isPass)[] inspect(int value)
{
IInspector[] inspectors = [ new C1(_reporter), new C2(_reporter), new C3(_reporter),
new C4(_reporter), new C5(_reporter), new C6(_reporter), new C7(_reporter) ];
//for (int i = 0; i < inspectors.Length; i++) if (!inspectors[i].Inspect(value)) return false;
var result = inspectors.Select(x => (x.ToString(), x.Inspect(value))).ToArray();
return result;
}
/// <summary>
/// 조건에 따른 최대값을 갖는 정수 리턴
/// </summary>
int doFindMax(IEnumerable<int> space) => space.Max(this);
/// <summary>
/// <see cref="IComparer{T}"/> 구현 : 자연수의 10의자리만 비교
/// </summary>
public int Compare(int x, int y) => (x / 10 % 10) - (y / 10 % 10);
}//class SolverLoigc
#endregion
#region ---- IInspector & 구현 ----
/// <summary>
/// 조건을 검증하는 메소드를 제공한다.
/// </summary>
internal interface IInspector
{
/// <summary>
/// <paramref name="value"/>가 문제의 조건에 맞는지 판단한다.
/// </summary>
bool Inspect(int value);
}
internal abstract class InspectorBase(ILogger reporter, string name) : IInspector
{
readonly ILogger _reporter = reporter;
readonly string _name = name;
volatile int _count = 0;
static int[] _masks = Enumerable.Range(0, 9).Reverse().Select(x => (int)Math.Pow(10, x)).ToArray();
const int REPORT_INTERVAL = 10000;//진행정보 출력 주기
/// <summary>
/// <inheritdoc/>
/// + 공통조건 : 0을 포함하지 않는다.
/// + 같은 수가 중복출현하지 않는다.
/// + 상속 클래스의 조건 검증함수 <see cref="inspect(Span{int})"/>를 호출
/// </summary>
public bool Inspect(int value)
{
Span<int> set = stackalloc int[9];
for (int i = 0; i < 9; i++) set[i] = value / _masks[i] % 10;
if (set.Contains(0)) return false;
var flag = 0;
for (int i = 0; i < 9; i++)
{
var v = set[i];
if ((flag >> v & 0x01) != 0) return false;
flag |= 1 << v;
}
//적당할 주기로 상태 출력
if (_count % REPORT_INTERVAL == 0) _reporter.Report((_name, $"{value} [{_count / REPORT_INTERVAL:D2}]"));
_count++;
return inspect(set);
}
/// <summary>
/// 상속클래스에서 각자 조건을 판별한다.
/// </summary>
protected abstract bool inspect(Span<int> set);
public override string ToString() => _name;
}
/// <summary>
/// 조건 1,2에 대한 알고리즘 구현
/// </summary>
internal abstract class C12Base : InspectorBase
{
public C12Base(ILogger reporter, string name, int delta) : base(reporter, name) => _delta = delta;
readonly int _delta;
protected override bool inspect(Span<int> set)
{
for (int i = 0; i < set.Length - 2; i++)
{
var delta = set[i] - set[i + 1];
if (delta == _delta || delta == -_delta) return false;
}
return true;
}
}
/// <summary>
/// 조건 1에 대한 알고리즘 구현
/// </summary>
internal class C1 : C12Base
{
public C1(ILogger reporter) : base(reporter, nameof(C1), 1) { }
}
/// <summary>
/// 조건 2에 대한 알고리즘 구현
/// </summary>
internal class C2 : C12Base
{
public C2(ILogger reporter) : base(reporter, nameof(C2), 4) { }
}
/// <summary>
/// 조건 3,4에 대한 알고리즘 구현
/// </summary>
internal abstract class C34Base : InspectorBase
{
public C34Base(ILogger reporter, string name, int v1, int v2, int gap) : base(reporter, name)
{
_v1 = v1;
_v2 = v2;
_gap = gap;
}
readonly int _v1, _v2, _gap;
protected override bool inspect(Span<int> set)
{
//var i1 = Array.IndexOf(set, _v1);
//var i2 = Array.IndexOf(set, _v2);
var i1 = set.IndexOf(_v1);
var i2 = set.IndexOf(_v2);
var gap = i1 - i2;
return gap > 0 ? gap == _gap + 1 : gap == -_gap - 1;
}
}
/// <summary>
/// 조건 3에 대한 알고리즘 구현
/// </summary>
internal class C3 : C34Base
{
public C3(ILogger reporter) : base(reporter, nameof(C3), 5, 6, 1) { }
}
/// <summary>
/// 조건 4에 대한 알고리즘 구현
/// </summary>
internal class C4 : C34Base
{
public C4(ILogger reporter) : base(reporter, nameof(C4), 4, 5, 4) { }
}
/// <summary>
/// 조건 5에 대한 알고리즘 구현
/// </summary>
internal class C5 : InspectorBase
{
public C5(ILogger reporter) : base(reporter, nameof(C5)) { }
protected override bool inspect(Span<int> set)
{
//var i1 = Array.IndexOf(set, 2);
//var i2 = Array.IndexOf(set, 4);
var i1 = set.IndexOf(2);
var i2 = set.IndexOf(4);
var skip = 1 + (i1 < i2 ? i1 : i2);
var take = i1 < i2 ? i2 - i1 - 1 : i1 - i2 - 1;
//return 9 == set.Skip(skip).Take(take).Sum();
var a = set.Slice(skip, take).ToArray().Sum();
return 9 == a;
}
}
/// <summary>
/// 조건 6,7에 대한 알고리즘 구현
/// </summary>
internal abstract class C67Base : InspectorBase
{
public C67Base(ILogger reporter, string name, int v1, int v2, int v3 = 0) : base(reporter, name)
{
_v1 = v1;
_v2 = v2;
_v3 = v3;
}
readonly int _v1, _v2, _v3;
protected override bool inspect(Span<int> set)
{
//var i1 = Array.IndexOf(set, _v1);
//var i2 = Array.IndexOf(set, _v2);
var i1 = set.IndexOf(_v1);
var i2 = set.IndexOf(_v2);
if (_v3 == 0) return i1 < i2;
//var i3 = Array.IndexOf(set, _v3);
var i3 = set.IndexOf(_v3);
return (i1 < i2) && (i2 < i3) || (i3 < i2) && (i2 < i1);
}
}
/// <summary>
/// 조건 6에 대한 알고리즘 구현
/// </summary>
internal class C6 : C67Base
{
public C6(ILogger reporter) : base(reporter, nameof(C6), 6, 5) { }
}
/// <summary>
/// 조건 7에 대한 알고리즘 구현
/// </summary>
internal class C7 : C67Base
{
public C7(ILogger reporter) : base(reporter, nameof(C7), 4, 7, 6) { }
}
#endregion
ConsoleTester.csproj
<Project Sdk="Microsoft.NET.Sdk">
<PropertyGroup>
<OutputType>Exe</OutputType>
<TargetFramework>net8.0</TargetFramework>
<ImplicitUsings>enable</ImplicitUsings>
<Nullable>enable</Nullable>
<StartupObject>App</StartupObject>
</PropertyGroup>
<ItemGroup>
<Using Include="System.Runtime.CompilerServices.CallerMemberNameAttribute" Alias="CN" />
<Using Include="System.Runtime.CompilerServices.CallerArgumentExpressionAttribute" Alias="CA" />
</ItemGroup>
</Project>